Week 1. Foundations of Algorithms
Projects and Exercises
2.2 Projects and Exercises
2.2.1 Compulsory Projects
These projects should be solved as part of the weekly assignment. When you phrase your answers, you should always write with fellow students in mind. Write so that they would understand, and be convinced by your argument. If you are unsure what is a comprehensible argument, discuss it with fellow students. Always use drawings and sketches when they are more comprehensible than prose.
Problem 2.1 (Sorting Cards)
Consider the problem of sorting a hand of cards. How would you do it naturally?
If you have a deck of cards, shuffle and draw at least ten cards at random. If you do not, you can write down ten (or more) numbers at random.
Look at the cards/numbers. How would you intuitively start to sort them?
Answer the following,
- 1.
- Is your approach systematic or not?
- 2.
- Can you write down pseudo-code describing how you do it?
- 3.
- If you cannot, why is that? Can you make changes so that it is possible?
- 4.
- Is your approach similar to insertion sort? What are the main differences?
(You should do this exercise together with other students, and discuss and compare approaches. Do not spend more than about 30 minutes on the problem. There is no ideal answer.)
Problem 2.2 (Letter Frequencies) Simple substitution ciphers work by replacing each letter in the alphabet with another. To encrypt a text, the same substitution is applied throughout the text. Such ciphers are easily broken by using frequency analysis.
Consider a program which takes a text as input and outputs frequency tables for each letter in the text. I.e. for each letter in the alphabet, output the number of occurrences of this letter in the text. (See also P-2.22 in the textbook.)
You are going to describe (not implement) such a program. Think throught the following questions first:
- How do you model the text (input)?
- How do you model the frequency tables (output)?
- How do you parse the text?
Describe your program in the form of an algorithm, with pseudo-code and precise definitions of input and output.
- How do you know that the algorithm produces the correct answer?
- How many operations does the algorithm require when the text is characters long and there are letters in the alphabet?
2.2.2 Exercises
Problem 2.3 (Change Making) Design and describe a program (algorithm) which takes two amounts (numbers) as input. One is the amount charged and the other the amount given. The program should return the number of each kind of bill and coin to give back as change for the difference between the amount given and the amount charged. The values assigned to the bills and coins avalaible can be based on the monetary system of any current or former government. Try to design your program so that it returns the fewest number of bills and coins as possible.
You can for instance use the denominations available for Norwegian kroner:
Does your algorithm always produce the fewest number of bills and coints? Would it always give the fewest coins and bills if you change the denominations?
Consider the similar problem of selecting stamps to make up a given amount of postage. Suppose the stamps have values 1, 24, 33, and 44 pence. Test the algorithm to find the required stamps for 67p postage.
(Cf. Goodrich, Tamassia, & Goldwasser P-2.26)
Problem 2.4 (Selection Sort) Selection Sort is a sorting algorithm, sinilar to insertion sort. It can be described as follows:
Input: Array A[] of size n.
Output: The same array A[] in sorted order.
- 1.
- Rewrite the pseudo-code in Java. Note in the indices in particular. Is the first element A[0] or A[1].
- 2.
- How many swap operations must be made in the worst case? What about the best case?
- 3.
- Can you prove that the algorithm is correct, i.e. produces a sorted array? Compare it to the proof for insertion sort.