• 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.2-2, 1.2-3, and 1-1 and be prepared to present you solutions in class on Wednesday. You do not have to hand in your work to these problems

• 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 5-10 minute presentation on Wednesday on how your groups plan to attack your problem. You will also need to submit a written summary of 1-2 typed pages of your groups meeting notes and plan.

CS41 home

• Be able to prove equations (A.3) and (A.4) in class on Monday
  PDF available if you don't have the book yet.

• Written solutions to A.1-1, A.2-1, A.2-2, and A-1b are due at the beginning of class.
  PDF available if you don't have the book yet.

• 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.

• Work on problems 4.1-1 and 4.2-1 and be prepared to present/discuss them in class.
• Read chapter 6 and appendix B.
• Keep working on group projects

CS41 home

• Written solutions to 4.1-2, 4.2-3, 4.3-1abc and 4.3-3 are due at the beginning of class.
• Progress reports and presentations on group projects are also due. Prepare to give a 5-10 presentation as before. You should have some working code and a thorough analysis of run-time and space-usage of your algorithm. The written summary should be 1-2 typed pages as before. You can email your report to me if you like.

CS41 home

• 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

• 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

• Final reports and presentations on group projects due. Final reports should include; a high level description of the algorithm, an analysis of run-time 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.

• Written solutions to 6.5-6 (FIFO Queues and Stacks using heaps), 6.5-8 (merging k sorted lists), 7-3 (Stooge Sort), and 8-4 (Water jugs) are due at the beginning of class. For 7-3, 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.

• Look at problems 13.1-4 and 13.1-7 and be prepared to discuss results in class.

CS41 home

• Read chapters 18, 15, and 16.

• Written solutions to problems 8.2-4, 8-2, 9.3-9, 9-1, and 10.1-6 are due at the beginning of class.

• Read Chapter 17 on Amortized Analysis

CS41 home

• Read Chapters 22 and 23

• Written solutions to Problems 15-6, 16-1, 16.2-4, 17.1-3, 17.2-1, and 17.3-7 are due at the beginning of class

CS41 home

• Read Chapters 24 and 25

• Written solutions to Problems 22.2-8, 22.3-11, 22.4-2, 22.4-5 are due at the beginning of class

• Written solutions to Problems 22.5-5, 23.1-8, 23.2-4 are due at the beginning of class

• Written solutions to Problems 24.2-4, 24.3-4 and chain graph problem PDF are due at the beginning of class. No late homeworks accepted.

• Written solutions to Problems 33.1-4, 33.2-3, 34.1-4, and 34.1-6 are due at the beginning of class. For problem 33.1-4, it may help to look at 33.1-3 but you do not have to write a solution to 33.1-3 and you can use the result of 33.1-3 if you like. However, if you need to modify the algorithm, describe the modifications you need to make. 34.1-4 refers to 16.2-2. You can just use the result of 16.2-2 without showing the dynamic programming algorithm. In 34.1-6, 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.

Home Page

Last updated: Tuesday, September 22, 2020 at 01:07:43 PM