CMSC 37000: Algorithms -- Winter 2010

What's new?

(Last updated: March 11, 2010)

Homework statistics and statistics of the cumulative scores (homework plus tests) posted (3-11-2010, 1:20am). Click "Statistics" on the banner.

Statistics of third quiz and cumulative test scores posted (3-10-2010). Click "Statistics" on the banner.

Homework set #5 posted. Due Wed, Mar 10, before the tutorial. Click "Homework" on the banner.

Third quiz posted. Click "Grading, tests" on the banner. Solve all problems, including the bonus problems.

Homework set #4 posted. Due Tue, Mar 9. Click "Homework" on the banner.

Statistics of second quiz and midterm posted (3-5-2010). Click "Statistics" on the banner.

Handouts posted. Click "Handouts" on the banner.

Please report any errors on this website by email to the instructor. Those who are first to report significant errors receive homework bonus points.

Questionnaire

Please send email to the instructor with answers to these questions, even if you are only sitting in on the class, did not register, answered the same questionnaire in an earlier class by the instructor, or have an unusual status. Your answers to these questions will help me better to plan the course. Please write "CMSC 37000 data" in the subject.

• Your name
• Your field, area of specialization, and status at the university (e.g., "3rd year math major with minor in economics," or "2nd year TTI-C grad student specializing in pattern recognition," or "student at large specializing in oceanography")
• If you are a graduate student in computer science, who is your advisor?
• Do you expect to graduate this quarter?
• Did you register for this class? (It is ok if you did not, I still want to hear from you.)
• If you did, what type of grade do you seek (letter grade [A-F], P/F, audit)? (You can change your mind about this later.)
• Are you fulfilling a requirement with this class? If yes, please elaborate.
• Please tell me about your math background. Have you had proof-based courses before? Have you been exposed to creative problem solving? If so, tell me in what course(s) or program(s). Tell me about the four most advanced math courses you have taken (name of instructor, title of course, course number if at Chicago, name/location of institution).

Go to top

Old news

This site is up.

Homework set #3 posted. Due Wed, Feb 10, before tutorial (or later, as posted). Click "Homework" on the banner.

Second quiz posted. Click "Grading, tests" on the banner and then click "second quiz."

Mistake in class (Feb 2). The original author of "Prim's algorithm" (1957) presented in class today is Jarník (1930), not Boruvka, as I mistakenly said in class. Boruvka's was the first greedy algorithm for min-cost spanning tree (1928) and is somewhat more complcated than. Both Boruvka's and Jarník's algorithm are described in the Discrete Mathematics text,

Homework set #2 posted. Due Tue, Jan 26. Click "Homework" on the banner.

Statistics of first quiz posted (1-18-2010). Click "Statistics" on the banner.

First quiz posted. Click "Grading, tests" on the banner and then click "first quiz."

Homework set #1 posted. Due Tue, Jan 12. Click "Homework" on the banner.

Go to top

Course description

The subject is the design and analysis of efficient algorithms and the data structures supporting them. The algorithms will be stated in terms of mathematical models of computation and will be described in (often strikingly elegant) pseudocode. The analysis will consist of rigorous mathematical arguments; this is a proof-based class. The results of the analysis are mathematical theorems that estimate the running time or other resources used by the algorithm as a function of the length n of the input. The typical result is asymptotic as n → ∞. We shall also discuss the subject of computational intractability, rigorously formalized in the concept of NP-compleness.

The class will focus on a small number of algorithmic topics central to both the theory and the practice of computing (sorting in a variety of models, shortest paths, optimal spanning trees, fast multiplication and exponentiation, cliques and chromatic number, etc.). Emphasis will be on the conceptual development; the mathematical beauty of the subject will be highlighted. Elegance of the arguments and of the pseudocode descriptions will be prized. Those who enjoy solving mathematical puzzles will have a great time. There will be no programming assignments in this class.

Prerequisites:

The Discrete Mathematics 2009 course (CMSC37110) is a prerequisite to this class unless waived by the instructor. (Send email to the instructor asap, describing your background in proof-based mathematics, if you want a waiver.) Concepts and methods discussed in the Discrete Mathematics class will be bread and butter to this course; DM topics ubiquitous in the algorithms course include asymptotic notation, discrete probability, the elements of number theory, graph theory, counting, recurrences, the Fibonacci numbers, matrices.

The principal prerequisite is a degree of mathematical maturity. No programming background is required for this class, although a basic understanding of the cycle structure of programs is helpful in the design of simple and elegant pseudocode, one of the skills to be developed during this class.

Go to top

Course information

Office hours: by appointment (please send e-mail)

Teaching assistant:

Raghav Kulkarni    raghav(at)cs(dot)uchicago(dot)edu.

The TA holds office hours Monday 4:30-5:30pm in Ry-162 (the "Theory Lounge").

Classes: TuTh 9:00 - 10:20 Ry 277

Tutorial: Wed 3:30 - 4:20 pm, Ry-276. Attendance mandatory unless waived by instructor. The main theme is solving problems, especially homework and test problems.

LAST CLASS: Thursday, March 11. Attendance mandatory.

Go to top

Text

Your primary text will be your course notes, so please make sure you don't miss classes. If you do, you should copy somebody's class notes and discuss the class with them.

There will also be frequent web-based handouts. Please always check this website.

Printed texts:

Main text: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Cliff Stein: "Introduction to Algorithms"

MIT Press and McGraw-Hill
ISBN-10 0-262-03384-4
ISBN-13 978-0-262-03384-8

The current printing is the third edition, but the previous editions also cover virtually all required material.

The text is available at the Seminary Co-op Bookstore (5757 S University Avenue)

Recommended additional reading:

Jon Kleinberg - Éva Tardos: "Algorithm Design"

Pearson/Addison-Wesley, Publ. 2005

ISBN 0-321-29535-8

(You can probably get copies from last years' students enrolled in this class.)

The Discrete Mathematics 2009 course (CMSC37110) is a prerequisite to this class. Please check the homework sets and tests for this class (all posted on the class website). A considerable part of that class, but not the entire class, is covered in the instructor's Discrete Mathematics Lecture Notes.

Recommended reference (undergraduate text):

Kenneth H. Rosen: Discrete Mathematics and its Applications (n-th edition, n=2,3,4,5,...)

Go to top

Grading

Grades are based on homework (24%), a midterm (18%), three quizzes (6% each), class participation (4%) and the final exam (36%).

The tests are closed-book; no notes permitted. Calculators may be used for basic arithmetic, logarithms and exponentials but not for more complex calculations such as g.c.d's or modular exponentiation. Calculators will seldom be of any use; the problems tend to involve very little numerical calculation.

Test dates

Thursday, Jan 14: first quiz (6%)

Thursday, Feb 4: second quiz (6%)

Thursday, Feb 18: midterm (18%)

Tuesday, March 9: third quiz (6%)

Thursday, Mar 11: last class (attendance mandatory)

Thursday, March 18, 8:00 - 10:00 am: Final exam (36%)

Go to top

Rules on HOMEWORK

Go to top

Policy on collaboration

View the instructor's class material from previous years

Return to the Department of Computer Science home page

Go to top