Description
1. Work on (a) Exercise 2.1-1 and (b) Exercise 2.3-1 based on the string (array of 14 characters):
“BESTALGORITHMS”. Please mark the two T’s as T1 and T2, and the two S’s as S1 and S2
according to their order in the input, and show their positions during the processing.
2. Exercise 2.2-2. Make sure your loop invariant fulfills the three necessary properties.
3. Exercise 2.3-7.
4. Problem 2-4 (a), (b), and (d).
5. Exercise 3.1-1.
6. Problem 3-3. For (a), please work on the 15 functions in the 2nd, 4th, and 6th columns. (Hint:
Stirling’s approximation of 𝑛!)
7. Exercise 4.2-1.
8. Exercise 4.3.7.
9. Exercise 4.4-9.
10. Exercise 4.5-4.
11. Problem 4-1 (a), (c), and (e).
12. Problem 4-3 (a), (c), and (e).
13. There’s a class of folk songs and holiday songs in which each verse consists of the previous
verse, with one extra line added on. “The Twelve Days of Christmas” has this property; for
example, when you get to the fifth verse, you sing about the five golden rings and then,
reprising the lines from the fourth verse, also cover the four calling birds, the three French hens,
the two turtle doves, and of course the partridge in the pear tree [see page 3].
These songs tend to last a long time, despite having relatively short scripts. In particular, you
can convey the words plus instructions for one of these songs by specifying just the new line
that is added in each verse without having to write out all the previous lines each time. (So the
phrase “five golden rings” only has to be written once, even though it will appear in verses five
and onward.)
Department of Electrical Engineering September 10, 2019
National Taiwan University Iris Hui-Ru Jiang
Algorithms, Fall 2019
2/3
There’s something asymptotic that can be analyzed here. Suppose, for concreteness, that each
line has a length that is bounded by a constant 𝑐, and suppose that the song, when sung out loud,
runs for 𝑛 words total. Show how to encode such a song using a script that has length 𝑓(𝑛),
for a function 𝑓(𝑛) that grows as slowly as possible.
14. (DIY Problem) For this problem, you are asked to design a problem set related to Chapter(s) 1,
2, 3, and/or 4 and give a sample solution to your problem set. Grading on this problem will be
based upon the quality of the designed problem as well as the correctness of your sample
solution.
Study and, in general, the pursuit of truth and beauty is a sphere of activity in which we are
permitted to remain children all our lives.
— A. Einstein
Department of Electrical Engineering September 10, 2019
National Taiwan University Iris Hui-Ru Jiang
Algorithms, Fall 2019
3/3
The Twelve Days of Christmas
On the first day of Christmas
my true love sent to me:
A Partridge in a Pear Tree
On the second day of Christmas
my true love sent to me:
2 Turtle Doves
and a Partridge in a Pear Tree
On the third day of Christmas
my true love sent to me:
3 French Hens
2 Turtle Doves
and a Partridge in a Pear Tree
On the fourth day of Christmas
my true love sent to me:
4 Calling Birds
3 French Hens
2 Turtle Doves
and a Partridge in a Pear Tree
On the fifth day of Christmas
my true love sent to me:
5 Golden Rings
4 Calling Birds
3 French Hens
2 Turtle Doves
and a Partridge in a Pear Tree
On the sixth day of Christmas
my true love sent to me:
6 Geese a Laying
5 Golden Rings
4 Calling Birds
3 French Hens
2 Turtle Doves
and a Partridge in a Pear Tree
On the seventh day of Christmas
my true love sent to me:
7 Swans a Swimming
6 Geese a Laying
5 Golden Rings
4 Calling Birds
3 French Hens
2 Turtle Doves
and a Partridge in a Pear Tree
On the eighth day of Christmas
my true love sent to me:
8 Maids a Milking
7 Swans a Swimming
6 Geese a Laying
5 Golden Rings
4 Calling Birds
3 French Hens
2 Turtle Doves
and a Partridge in a Pear Tree
On the ninth day of Christmas
my true love sent to me:
9 Ladies Dancing
8 Maids a Milking
7 Swans a Swimming
6 Geese a Laying
5 Golden Rings
4 Calling Birds
3 French Hens
2 Turtle Doves
and a Partridge in a Pear Tree
On the tenth day of Christmas
my true love sent to me:
10 Lords a Leaping
9 Ladies Dancing
8 Maids a Milking
7 Swans a Swimming
6 Geese a Laying
5 Golden Rings
4 Calling Birds
3 French Hens
2 Turtle Doves
and a Partridge in a Pear Tree
On the eleventh day of Christmas
my true love sent to me:
11 Pipers Piping
10 Lords a Leaping
9 Ladies Dancing
8 Maids a Milking
7 Swans a Swimming
6 Geese a Laying
5 Golden Rings
4 Calling Birds
3 French Hens
2 Turtle Doves
and a Partridge in a Pear Tree
On the twelfth day of Christmas
my true love sent to me:
12 Drummers Drumming
11 Pipers Piping
10 Lords a Leaping
9 Ladies Dancing
8 Maids a Milking
7 Swans a Swimming
6 Geese a Laying
5 Golden Rings
4 Calling Birds
3 French Hens
2 Turtle Doves
and a Partridge in a Pear Tree
