Where, When, and Who
The class will meet daily (MTuWThF) from 9:30am - 10:50am in CSIC 1122.
The instructor is Tom DuBois (tdubois at cs.umd.edu). Unless requested, I will not hold regularly scheduled office hours, however I will be in my office in AVW 3204 (right across from the 32xx printer room) and available much of the time, and will happily make appointments. Just send me an email first or see me after class.
Why
This course teaches fundamental techniques for designing efficient computer algorithms, proving their correctness, and analyzing their running times.
What
We will cover the following material (A more detailed schedule is available):
- Review of the related mathematics and some basic algorithms
- Graph algorithms
- Greedy algorithms
- Dynamic programming
- Network flow
- NP and NP completeness
- Approximation algorithms
- Randomized algorithms
Textbooks
The official textbook for the course is Algorithm Design by Jon Kleinberg and Éva Tardos, 2005, Addison-Wesley, ISBN: 0321295358. If you plan to purchase this from the campus bookstore, you must do so by Tuesday July 15 (the second day of classes). After that point the bookstore may begin shipping back summer books in preparation for the fall semester.
Another excellent algorithms reference is Introduction to Algorithms (2nd Edition), T. Cormen, C. Leiserson, R. Rivest, and C. Stein, McGraw Hill, 2002. This book is not required.
Prerequisites
The prerequisite for the course is CMSC 351. As such, students should have be proficient in
- Programming: there will not be programming assignments, though students will be expected to be able to read and write pseudo code.
- Data structures: we will use lists, queues, trees, graphs, etc without much explanation of the underlying structure
- Some basic algorithms: such as different sorting routines as well as BFS/DFS
- Mathematical concepts: induction, combinatorics, summations, solving recurrences, probability, logarithms, calculus
Let me know in advance if any of this sounds unfamiliar.
Grading
The grading for the course will be split 25% homework, 30% midterm, and 45% final. The final exam will be cumulative, but will focus on the material since the midterm.
There will be one homework every week. They will be given our early in the week, perhaps even before the material necessary is covered. In this case it is very useful to read the homework carefully first, so when the material is covered you know what to look for. Homeworks will be due by the start of class on the due date. If for some reason you cannot make it to class, you must email me a copy of the homework by the start of class and then get me a hard copy asap, or make arrangements with me in advance. We will drop the lowest of the 6 homework grades.
Homeworks must be neat: clearly written or typeset (preferably typeset, I will be happy to help anyone learn latex), stapled if multiple pages. For full credit they must also be complete. For example solutions that have a correct idea but are missing some important details, or a proof that skips some important steps (like an induction proof without a clear base case) will not receive full credit.
Academic Dishonesty
You may discuss homework problems and strategies with classmates, but your solutions must be your own. If you make use of other sources in coming up with your answers you must cite these sources clearly. (This includes papers or books in the literature, friends or classmates, and information downloaded from the web.) In general you do not need to cite the course notes of the official textbook. Academic dishonesty will be dealt with according to university policy.