This is an introductory course in algorithms. We will cover standard topics such as definitions of algorithmic complexity (worst case, average case); basic tools such as sorting, searching and dynamic programming; advanced analysis techniques, such as amortized analysis; graph algorithms and searching techniques such as minimum spanning trees, depth-first search, shortest paths; and more advanced topics.
Emphasis will be given to arguing the correctness of algorithms and performing an analysis of their running time.
Undergraduates must have successfully completed 600.226 (Data Structures). Please talk to me if you are unsure about your preparation.
The book for this class is Introduction to Algorithms (3rd Edition) by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Cliff Stein.
600.363 Introduction to Algorithms
600.463 Algorithms I
For a list of known bugs and selected solutions to problems in the text, go to http://mitpress.mit.edu/algorithms/.
If you do not have a copy of the textbook, copies are available for
purchase at the Johns Hopkins University Bookstore.
The textbook has been placed on reserve at the MSE Library (Building 19).
If you have already purchased a 2nd edition and are concerned about moving to the 3rd
edition, please send email to the instructor.
Susan Hohenberger's office hours are Mondays 11-12 (right before class) in Wyman Park room 419 or by appointment.
Ming Chuang's office hours are Thursdays 3-4 in NEB 218 or by appointment.
The mailing list is cs363[ignore this spam break]@cs.jhu.edu.
There will be (approximately) bi-weekly problem sets and three
in-class quizzes. The final grade will be
computed using the following weights:
Some of the homework exercises will be routine, but others will be more challenging. I do not expect you to solve all of the homework problems, but I hope that you will benefit from working on the more difficult ones. A few hints on homework:
- Problem Sets: 35%
- Quizzes: 60%
- Participation in class: 5%
There will be three quizzes held during regular class time. The quizzes are closed book, closed note. Calculators, laptops and other electronic devices are prohibited. There is no final exam for this course.
- Start Early. Most problems will not be hard, but some will be. Difficult problems are not typically solved in one sitting. Start early and let the ideas come to you over the course of a few days.
- Be rigorous and concise. We expect real proofs and real analyses, at the level of rigor in the textbook. Express your ideas at the proper level of detail. Most solutions require a few paragraphs at the most. Take some time to think over the clearest way to express your thoughts before you start writing.
- Acknowledge known errors. More credit will be given for solutions with errors or gaps in proofs when these problems are explicitly pointed out by the student. This tells us that you understood there was a problem, even if you did not know how to fix it. When errors are not acknowledged, we will assume they were not recognized.
- Typing? We recommend that all problem set solutions be typed up using LaTeX. However, we will accept neatly hand-written solutions and hand-drawn diagrams. If we can't read it, no credit will be given.
- Collaboration? You are encouraged to solve all the homework questions on your own, but are permitted to brainstorm difficult problems in small groups, as long as each of you writes the solutions individually and honestly acknowledges the cooperation. Needless to say, if you work with others but never come up with the solution on your own, you may do okay in the homework component of your grade, but you will suffer on exams, so be careful.
- Cheating? More or less, you are only allowed to use the textbook, your lecture notes and discussions with classmates to help you solve the problem sets. In particular, the use of the internet, course bibles, outsiders, and other clearly "cheating" resources is strictly prohibited. Please talk to me if you are having problems keeping up with the material.
Last modified: Monday, August 24, 2009