Homework 1 (due Wed Sep 6)
 Email me (adanner at cs or adanner1 at swat) a brief CS biography.
Let me know if you have a preferred name other than your name listed by the
registrar.
List any prior CS or Math courses you have had here and any other
courses you think may be relevant. Please describe your exposure and
ability in the following areas; mathematical induction, recursion,
permutations and combinations, probability, tree and graph algorithms,
and programming languages.
 Read chapters 1 and 2 in CLRS.
 Work on problems 1.22, 1.23, and 11 and be prepared to present
you solutions in class on Wednesday. You do not have to hand in your
work to these problems
Homework 2 (Due Fri Sep 8)
 Read chapter 3 and Appendix A
 Read over and think about both interesting problems.
 Designate a leader, a recorder, and a presenter in your
group. These roles will change throughout the project, so don't debate
the roles too much.
 Think about an initial strategy for solving and coding a solution
to your interesting problem
 Be prepared to give a brief 510 minute presentation on Wednesday on
how your groups plan to attack your problem. You will also need to
submit a written summary of 12 typed pages of your groups meeting
notes and plan.
CS41 home
Homework 3 (Due Mon Sep 11)

Be able to prove equations (A.3) and (A.4) in class on Monday
PDF available if you don't have the book
yet.
Homework 4 (Due Wed Sep 13)
 Written solutions to A.11, A.21, A.22, and A1b are due at the
beginning of class.
PDF available if you don't have the book
yet.
Homework 5 (Due Fri Sep 15)
 Read chapters 3 and 4. Know what the master method is and how
to use it for solving recurrences. You may skim the proof of the
master method, but please read the rest of chapter 4 thoroughly.
Homework 6 (Due Mon Sep 18)
 Work on problems 4.11 and 4.21 and be prepared to
present/discuss them in class.
 Read chapter 6 and appendix B.
 Keep working on group projects
CS41 home
Homework 7 (Due Fri Sep 22)

Written solutions to 4.12, 4.23, 4.31abc and 4.33 are due at the
beginning of class.

Progress reports and presentations on group projects are also due.
Prepare to give a 510 presentation as before. You should have some
working code and a thorough analysis of runtime and spaceusage of
your algorithm. The written summary should be 12 typed pages as
before. You can email your report to me if you like.
CS41 home
Homework 8 (Due Wed Sep 27)
 Read Chapters 7, 8, 9, and 10

Show that T(n)=T(n/10)+T(9n/10)+n has solution T(n)=n lg n
and be prepared to present your solution in class
Homework 9 (Due Fri Sep 29)
 Read Chapters 12 and 13
 Bring any questions you have about Chapter 12 to class.
The review of this material will be quite brief.
CS41 home
Homework 10 (Due Mon Oct 2)
 Final reports and presentations on group projects due. Final
reports should include; a high level description of the algorithm,
an analysis of runtime and space usage, test cases or sample runs,
an electronic copy of relevant source code written, and
general thoughts of what you thought about the project, what
you would change, what you would have liked to keep working on.
Homework 11 (Due Wed Oct 4)
 Written solutions to 6.56 (FIFO Queues and Stacks using heaps),
6.58 (merging k sorted lists), 73 (Stooge Sort), and 84 (Water
jugs) are due at the beginning of class. For 73, you may assume that
n=3^k which eliminates any need for floor/ceilings, though the problem
isn't much harder without the assumption. Start early and ask
questions early! While less mathy, many of these problems require more
thinking to find the best solution.
Homework 12 (Due Fri Oct 6)

Look at problems 13.14 and 13.17 and be prepared to discuss results
in class.
CS41 home
Homework 13 (Due Mon Oct 9)

Read chapters 18, 15, and 16.
Homework 14 (Due Wed Oct 11)

Written solutions to problems 8.24, 82, 9.39, 91, and 10.16 are
due at the beginning of class.
Homework 15 (Due Wed Oct 25)

Read Chapter 17 on Amortized Analysis
CS41 home
Homework 16 (Due Mon Oct 30 )
Homework 17 (Due Wed Nov 1)

Written solutions to Problems
156, 161, 16.24, 17.13, 17.21, and 17.37
are due at the beginning of class
CS41 home
Homework 18 (Due Fri Nov 3 )
Homework 19 (Due Wed Nov 8 )

Written solutions to Problems
22.28, 22.311, 22.42, 22.45
are due at the beginning of class
Homework 20 (Due Wed Nov 15 )

Written solutions to Problems
22.55, 23.18, 23.24
are due at the beginning of class
Homework 21 (Due Wed Nov 22 )

Written solutions to Problems
24.24, 24.34 and chain graph problem PDF
are due at the beginning of class. No late homeworks accepted.
Homework 22 (Due Wed Dec 6 )

Written solutions to Problems
33.14, 33.23, 34.14, and 34.16 are due at the beginning of class.
For problem 33.14, it may help to look at 33.13 but you do not have
to write a solution to 33.13 and you can use the result of 33.13 if
you like. However, if you need to modify the algorithm, describe the
modifications you need to make. 34.14 refers to 16.22. You can just
use the result of 16.22 without showing the dynamic programming
algorithm. In 34.16, you do not need to prove the result for Kleene
star. Closed under concatenation means if L1 and L2 are two languages
in P then the string xy (x concatenated by y) is in P for x in L1 and
y in L2. Note this is different than union.