CMSC 37000: Algorithms -- Winter 2008

What's new?

QUIZ #3 HAS BEEN GRADED. You can pick it up from Raghav at the Monday office hour (March 17, 4pm).

Quiz-3 posted (click "Tests" on the banner).

The TAs hold an office hour every Monday 4 to 5pm. Meet at Ry 162 ("Theory lounge"). Take advantage of this opportunity; bring your own questions.

Go to top

Old news

Midterm statistics posted (click "Stat" on the banner)

"Repeated squares" handout posted (click "Handouts" on the banner)

"Tests" updated (Quizzes 1, 2 and the Midterm posted)

Statistics of Quiz-2 posted (click "Stat" on the banner)

Grading scheme and test dates posted (click the "Grading, test dates" tab on the banner)

Statistics of First Quiz posted. (Click on "Stat" on the banner.)

First Quiz posted. Please solve the problems, including the bonus problems, without the time pressure.

Tutorials are held each Wednesday, 3:30 pm - 4:20 pm, in Ry-277.
Tutorials are mandatory unless waived by the instructor. Attendance will count toward the "class participation" component of the grade. The first tutorial will be on Wednesday, Jan 16.

A request to all who attend this class. (By "all," in mean ALL, no exceptions.) Please send email to the instructor with the following information:

your name
your status at the university or other institution (for instance, "3rd year undergrad math major" or "2nd year grad student at TTI-C")
if grad student, your field of specialization (e.g. "computational linguistics"), name of advisor
have you taken CMSC 37110 (Discrete Math)?
your goal with this course (letter grade, P/F, just sitting in for fun)? (You may change your mind about this later; if so, let me know at that time.)
are you satisfying a degree requirement with this course?
do you expect to graduate at the end of this term?

This web page is up. Please report any errors, especially bad links.

Past tests from this class, along with some tests from previous years, are available.

First quiz Thursday, Jan 24. No books, no notes, no scratch paper.

Go to top

Course information

Class: TuTh 9:00 - 10:20 Ry 251

Tutorial: We 3:30 - 4:20 Ry 277 (mandatory unless waived by instructor)

Instructor: László Babai Ryerson 164 e-mail: laci(at)cs(dot)uchicago(dot)edu.

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

Teaching assistants:

Raghav Kulkarni Eckhart 2-A e-mail: raghav(at)cs(dot)uchicago(dot)edu.

Ozgur Sumer Ryerson 165A e-mail: ozgursumer(at)gmail(dot)com.

Office hour: Monday 4:00 - 5:00 pm, Ry 162 ("Theory lounge")

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 handouts and web postings. Please always check this website.

Printed text:

Jon Kleinberg - Éva Tardos: "Algorithm Design"

Pearson/Addison-Wesley, Publ. 2005

ISBN 0-321-29535-8

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

A large part of the prerequisites is covered in the instructor's
Discrete Mathematics Lecture Notes.
For other handouts, click the "Handouts" tab on the banner.

Go to top

Grading

Grades are based on class participation (4%), homework (24%), 3 quizzes (6% each), a midterm (18%), and the final exam (36%). The tests are "closed book" (no books or notes). 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.

Test dates

First Quiz: Thursday, Jan 24

Second Quiz: Thursday, Feb 7

Midterm: Thursday, Feb 21

Third Quiz: Tuesday, Mar 11

Last class: Thursday, Mar 13

Final exam: Tuesday, March 18, 8:00 - 10:00 am

Go to top

Rules on HOMEWORK

Unless otherwise stated, homework is always due the next class (before class). Please always check the website for updates. The problems will be posted shortly after class. However, errors may occur, so please check the website, especially if you suspect an error. If you find an error or something that looks suspicious in an assignment, please notify the instructor (by email). If you are the first to point out a serious error, you may receive bonus points. "DO" problems are meant to check your understanding of the concepts. Do them but do not hand them in. If you encounter any difficulties, please check with a TA during office hours. Challenge problems don't have a specific deadline except they cease to be assigned once they have been discussed in class. If you are working on a challenge problem, please send email to the instructor so as to avoid the problem being discussed before you handed in the solution. Solutions to Challenge problems don't earn you credit toward your grade but they do earn you the instructor's respect, in addition to giving you valuable experience.

Policy on collaboration

Studying in groups is strongly encouraged. Collaboration on current homework is discouraged but not prohibited. If you do collaborate, state it at the beginning of your solution (give name of collaborator). DO NOT COPY someone else's solution: after the discussion, throw away any written records. Understand the ideas discussed and give your own rendering. The same applies to other sources such as the Web: give the source (URL), but DO NOT COPY. Understand; then write your own version without looking at the source or your notes.