1a) (A version of a classic problem to get started with.) If you choose 72 people at random, what is the probability that at least two of them share the same birthday (the same day and month)?
b) How many different people do you need to choose at random before you've found at least one person with a birthday on each of the 365 days of the year?
2. A duck being chased by a fox swims to the centre of a perfectly circular deep pond. The fox cannot swim to catch the duck but the duck cannot fly away as it is unable to take off from the surface of the water. The fox can move four times faster than the duck. Is it possible for the duck to swim to the edge of the pond to reach dry land and fly away before being caught by the fox?
3. A String is a sequence of characters, and a String variable in Java can be declared like this:
String message = "Hello World";
The individual characters can be accessed with the method charAt(), for example:
char c = message.charAt(0); // c is initialised to 'H', as counting starts at 0 char d = message.charAt(5); // d is initialised to the space character
The number of characters in a String can be determined using the length() method:
int n = message.length(); // n is initialised to 11
An algorithm to find the position of a character in a String can be expressed as follows:
String text = "Some text";
char c = 'x';
int position = -1;
for (int n = 0 ; n < text.length() ; n++)
{
if (text.charAt(n) == c) // See if the character at position n has the same value as c
{
position = n;
}
} // After the loop position should have the value 7, counting from 0.
Note that the algorithm is expressed in Java code but the intention is to capture the detail of the algorithm not to worry about precise Java syntax. You should be able to follow the algorithm in your head or by making notes to determine what it does.
The following questions don't require a computer to answer them but you might want to turn your answers into working programs after the problem class to confirm they work correctly. Your answers will require additional variables, loops and if statements. You may want to break your algorithms into a collection of methods (functions), each solving a sub-part of the problem.
a) Modify the example algorithm above so that it finds the position of the first occurrence of a character in a String. For example, initialising c to 't' will leave position with the value 5. If the character is not in the String position is left with the value -1.
b) Modify the example algorithm again so that it finds the position of the nth occurrence of a character. For example:
String text = "Some text"; char c = 't'; int occurrence = 2;
Will leave position with the value 9, the position of the 2nd occurrence of 't'.
c) Write an algorithm to find the position of a Substring within a String. For example, starting with:
String text = "Some text"; String substring = "me"; int startposition = -1; int endposition = -1;
Will leave startposition with the value 2, which is the position where the substring "me" begins in "Some text", and endposition with the value 3, which is the position where "me" ends. If the substring is not present both startposition and endposition should be left with the value -1.
4. A wildcard matches one or more characters in a String. The wildcard '?' will match a single character, while '*' will match multiple characters.
Searching for the substring pattern "a?b" will find any substring that starts with the character 'a', followed by any character, followed by 'b'. For example:
String text = "Some text"; String substring = "o?e"; int startposition = -1; int endposition = -1;
Will leave startposition with the value 1, and enposition with the value 3, as the substring "ome" will match.
Searching for the substring pattern "a*b" will find any substring that starts with the character 'a', followed by a sequence of characters of any length (including zero), followed by 'b'. For example:
String text = "Some text"; String substring = "m*x"; int startposition = -1; int endposition = -1
Will leave startposition with the value 2, and endposition with the value 7 as the substring "me tex" will match. A search for the substring pattern "S*o" will leave startposition with the value 0, and endposition with the value 1, as the substring "So" will match.
a) Develop an algorithm to search for substrings using the '?' wildcard character.
b) Extend your algorithm to work with the '*' wildcard character as well. Note - it may be easier to solve simpler versions of the problem first and work your way up to the full version step-by-step.
Substring patterns can use multiple wildcards, for example: "ab?c*d". Make sure your answer to b can deal with any pattern.
5. The wildcard [ ] is introduced. This allows a selection from a set of characters. For example "[ac]" would match either 'a' or 'c', and "[a-d] specifies the range from 'a' to 'd' inclusive and would match 'a' or 'b' or 'c' or 'd'.
a) Develop an algorithm to search for substrings using the [ ] wildcard only.
b) Now combine your answer from a) with your algorithm from 4b). Make sure your algorithm will work with combinations of wildcards, for example: "th?[mn]" would match "than", "then", "them", "thin". "file*[0-9]" would match "fileName0", "fileName1" …, "fileName9".
Note that the system of wildcards explored in these questions is a standard used by operating systems such as Unix and also within programming languages. *, ? and [ ] are a subset of something called "Regular Expressions".
The Unix command line is a good example of where wildcards are used, typically to match file and directory names. For example, the command ls file*[0-9] would list any files in the current directory whose names match the pattern. Experiment with the ls command to get used to using wildcards.