U Chicago CS Dept Logo

CSPP 55001: Algorithms
Autumn 2013


announcements | general information | organization | homework


Announcements

Homework 9 is posted

Problem session: Sunday at 2:00 pm in Ryerson 276

Office hours: Monday 4:00–5:00 pm & 8:30–9:30 pm in Ryerson 162

Textbook: Introduction to Algorithms (Third Edition) by T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein (ISBN 978-0-262-03384-8) = CLRS

The course grade will be determined using the following weights:

Homework Collaboration Policy: You are allowed and encouraged to discuss course material and homework assignments with each other, but you must work out and write up the solutions to the homework assignments on your own. Exchanging solutions to homework problems or sharing solutions is strictly prohibited. Solutions to homework problems must reflect YOUR understanding of the ideas and must be YOUR own work. DO NOT COPY a solution from a written source, from the internet, or from another person. Copied solutions obtained from a written source, from the internet, or from another person will receive zero credit.

Schedule of lectures

October 1
Lecture 1: Analysis of algorithms: insertion sort and merge sort
Divide-and-conquer technique
5:30–8:30 pm in Ryerson 251
Reading assignment: CLRS chapters 1 and 2; chapter 4, sections 4.1–4.2
Review: CLRS chapter 3 (asymptotic notation, common functions); chapter 4, sections 4.3–4.5 (methods of solving recurrences).
October 8
Lecture 2: Quicksort; median and order statistics
Randomized algorithms
5:30–8:30 pm in Ryerson 251
Reading assignment: CLRS chapters 5, 7, and 9
October 15
Lecture 3: Dynamic programming
5:30–8:30 pm in Ryerson 251
Reading assignment: CLRS chapter 15, sections 15.1–15.4
October 22
Quiz 1
Lecture 4: Dynamic programming
5:30–8:30 pm in Ryerson 251
Reading assignment: CLRS chapter 15, sections 15.1–15.4
October 29
Quiz 2
Lecture 5: Graph traversal: breadth-first search
5:30–8:30 pm in Ryerson 251
Reading assignment: CLRS chapter 22, sections 22.1–22.2
November 5
Midterm exam
5:30–7:00 pm in Ryerson 251
Lecture 6: Graph traversal: depth-first search
7:15–8:30 pm in Ryerson 251
Reading assignment: CLRS chapter 22, sections 22.3–22.4.
November 12
Lecture 7: Strongly connected components
Shortest paths: Dijkstra's algorithm
5:30–8:30 pm in Ryerson 251
Reading assignment: CLRS CLRS chapter 22, section 22.5; chapter 24, section 24.3.
November 19
Lecture 8: Shortest paths: Bellman-Ford algorithm; shortest-paths in DAGs
Minimum spanning trees
5:30–8:30 pm in Ryerson 251
Reading assignment: CLRS chapter 23; chapter 24, section 24.1–24.2.
November 26
Quiz 3
Lecture 9: NP-complete problems
5:30–8:30 pm in Ryerson 251
Reading assignment: CLRS chapter 34
December 3
Quiz 4
Lecture 10: Hashing and other topics
5:30–8:30 pm in Ryerson 251
Reading assignment: CLRS chapter 11
December 10
Final exam
5:30–8:30 pm in Ryerson 251


Organization

Staff

Lectures

Problem session


brady at cs dot uchicago dot edu