CSPP 55001: Algorithms
Spring 2013

Announcements

Quiz 3 is Wednesday May 29

Homework 8 is posted

Negar's office hours on Monday May 27 will be on-line, starting at 5:00 pm

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:

• ( 5%) Homework assignments
• (20%) Quizzes: April 24, May 1, May 29, June 5
• (25%) Midterm examination: May 8
• (50%) Final examination: June 12

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

April 3

Lecture 1: Analysis of algorithms: insertion sort and merge sort
Divide-and-conquer technique

5:30–8:30 pm in Eckhardt 202

Reading assignment: CLRS chapters 1 and 2; chapter 4, sections 4.1–4.3

Supplementary reading: CLRS chapter 3 (asymptotic notation, common functions)

April 10

Lecture 2: Quicksort; median and order statistics

5:30–8:30 pm in Ryerson 276

Reading assignment: CLRS chapters 7 and 9

April 17

Lecture 3: Dynamic programming

5:30–8:30 pm in Ryerson 276

Reading assignment: CLRS chapter 15, sections 15.1–15.4

April 24

Quiz 1

Lecture 4: Dynamic programming

5:30–8:30 pm in Eckhardt Ryerson 276

Reading assignment: CLRS chapter 15, sections 15.1–15.4

May 1

Quiz 2

Lecture 5: Graph traversal: breadth-first search

5:30–8:30 pm in Ryerson 276

Reading assignment: CLRS chapter 22, sections 22.1–22.2

May 8

Midterm exam

5:30–7:00 pm in Ryerson 276

Lecture 6: Graph traversal: depth-first search

7:15–8:30 pm in Ryerson 276

Reading assignment: CLRS chapter 22, section 22.3

May 15

Lecture 7: DFS: topological sort, strongly connected components; Shortest paths: Dijkstra's algorithm

5:30–8:30 pm in Ryerson 276

Reading assignment: CLRS chapter 22, sections 22.4–22.5; chapter 24, section 24.3

May 22

Lecture 8: Shortest paths: Bellman-Ford algorithm; Minimum spanning trees

5:30–8:30 pm in Ryerson 276

Reading assignment: CLRS chapter 23; chapter 24, section 24.1

May 29

Quiz 3

Lecture 9: MST; NP-complete problems

5:30–8:30 pm in Ryerson 276

Reading assignment: CLRS chapter 23, section 23.2; chapter 34, section 34.1

June 5

Quiz 4

Lecture 10: Hashing and other topics

5:30–8:30 pm in Ryerson 276

Reading assignment: CLRS chapter 11

June 12

Final exam

5:30–8:30 pm in Ryerson 276

---

Organization

Staff

• Instructor
  

  Gerry Brady
  Office hours: Tuesday 7:00–9:00 pm
  Office: Ryerson 165A
  Email: brady at cs dot uchicago dot edu

• Teaching Assistants:
  

  Negar Mirsattari
  Email: mirsattari at uchicago dot edu
  Office hours: Monday 5:00–7:00 pm Gleacher Center
  

  Young Ko
  Email: youngkun at uchicago dot edu
  Office hours: Tuesday 8:30–9:30 pm in Ryerson 162
  

Lectures

• Wednesday 5:30–8:30 pm in Ryerson 276

Problem session

• Saturday 10:00 am –12:00 noon in Ryerson 276

---

brady at cs dot uchicago dot edu