In this class, we focus on designing and analyzing data structures and algorithms. We will build on the material from 142 by describing balanced binary trees and looking at some more sophisticated graph algorithms. Then we will examine a variety of problems to illustrate important techniques like greed, amortized analysis, divide and conquer, dynamic programming, network flow, and randomization. We also consider the limitations of computing by examining lower bounds, NP-completeness, and undecidability.
We meet Monday, Wednesday, Thursday, and Friday during 4th period (noon-1:20). All classes will meet in SMC A219. There will be no class on 10/6 or 10/27 to give you time to work on exams for this course.
Our textbook is "Algorithm Design" by Jon Kleinberg and Eva Tardos. We will be following this text reasonably closely, but with some added material.
In addition, the following may be useful references:
The text and both of these references are on reserve in SMC library.
If you find yourself struggling in this course, get help right away. The term will move quickly and concepts in this course build on one another so you can't afford to get too far behind. Don't hesitate to come by my office or email me a question.
Week 1: (aka "Day 1") Array ADT
Week 2: Assymptotic notation. Review of data structures. Balanced trees.
Week 3: Greedy algorithms.
Week 4: Amortized analysis.
Week 5: Divide and conquer algorithms. Exam one.
Week 6: Dynamic programming.
Week 7: Network flow.
Week 8: Lower bounds. Reductions. Exam two.
Week 9: NP-hardness. Undecidability.
Week 10 plus the last day: Approximation algorithms. Randomized algorithms.
Assignments for this class will mostly be written descriptions of algorithms and proofs rather than code. Some programming assignments may also be given. There will be regular homeworks, two midterm exams, and the final. The exams and midterm will probably all be takehomes.
You should plan on submitting all work by the due date, but I know this is not always possible. Therefore, you will get two "late days" that may be used on homework assignments during the term. Each allows you to submit one homework 24 hours late without penalty. They can be used for the same or different assignments. To use them, write a note on the top of your submission. Late assignments without such a note will lose 10% of their points for each 24 hours they are late. Late submissions will not be accepted once solutions have been posted so let me know if you intend to work on something past its normal deadline. Individual extensions beyond these two days will require extraordinary circumstances.
I assign extra credit problems infrequently. I will however give extra credit for attending colloquium talks sponsored by the CS department (possibly other departments, depending on the content of the talk) and submitting a short writeup about the talk. Give a quick summary and any impressions you had in a couple of paragraphs (~1 page). This offer applies to any qualifying talk you are not otherwise getting credit to attend.
Regular attendance is expected, but there will not be a specific penalty for missing lecture. You are responsible for your own education. This means that you need to find someone to turn in homework if you are absent on the due date and you must find a way to learn the material covered during absences. In addition, please send me an email if you will be missing class so I know what is going on.
Exams in this class must be completed individually. You are allowed to talk with your classmates about homework. When you do this, however, you must do two things:
The same policies apply to getting help from inanimate sources. If you use the web or a textbook other than the one we're using, you must cite this source. As in collaborations with another person, you are expected to write you own solution; do not copy text or code from any source. In addition, you may look at other sources for examples or conceptual help, but not actual solutions. Some problems assigned for this class may have been previously assigned to other classes, but you are expected not to deliberately seek solutions. (If you come across one accidently, let me know and I will give you a modified assignment.)
Please feel free to contact me if you have any questions about this policy.
At the end of the term, all of your work will combined into an overall course percentage based on the following weights:
| Homework | 30% |
| Midterms | 40% (20% each) |
| Final | 30% |
The range of scores mapping to each grade will be determined at the end of the term. In general, spend your time learning the material rather than worrying about your grade, but feel free to talk with me if you are concerned about it.