## 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.)

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

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