

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 9780262033848) = CLRS




The course grade will be determined using the following weights:
 ( 5%) Homework assignments
 (20%) Quizzes
 (25%) Midterm examination
 (50%) Final examination
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
Divideandconquer 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: breadthfirst 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: depthfirst 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: BellmanFord algorithm; shortestpaths 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: NPcomplete 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
Staff
 Instructor
Gerry Brady
Office hours: Monday 7:00 pm to 9:00 pm and by appointment
Office: Ryerson 165A
Email:
brady at cs dot uchicago dot edu
 Teaching Assistants:
Pooya Hatami
Email:
pooya at cs dot uchicago dot edu
Office hours: Monday 8:30 to 9:30 pm in Ryerson 162
Negar Mirsattari
Email:
mirsattari at uchicago dot edu
Office hours: Monday 4:00 to 5:00 pm in Ryerson 162
Online office hours: Sunday at 8:00 pm
Lectures
 Tuesday 5:30–8:30 pm in Ryerson 251
Problem session
 Sunday 2:00–4:00 pm in Ryerson 276
brady at cs dot uchicago dot edu