CMSC 27200 Theory of Algorithms

  • Course Mechanics
  • Course Overview
  • What we covered so far
  • Assignments and Handouts

    • Course Mechanics

    Instructor

    Janos Simon
    165 Ryerson
    email: simon (at) cs.uchicago.edu

    Office Hours: Fridays 2-3 and by appointment

    TAs

    TAs: Denis Pankratov, Pooya Hatami

    Office hours:

    Pooya Hatami: Mondays 4-5
    Dennis Pankratov: Tuesdays 5-6

    Lecture:

    MWF 11:30-12:20 in Ryerson 276
    Textbook: "Algorithm Design" by Kleinberg and Tardos

    Other useful sources:
    - "Introduction to Algorithms" by Cormen, Leiserson, Rivest and Stein
    - "Algorithms" by Dasgupta, Papadimitriou and Vazirani

    Grading will be based on weekly homework assignments, a midterm (on 2/8) and a final.

    Course Overview

    We will study algorithms: roughly the first half will be deterministic exact algorithms, the second half will examine hardness results, approximation algorithms and probabilistic algorithms.

    Approximate Syllabus

    LectureTopicsReading
    1Stable matchingsChapter 1
    2Running time analysisChapter 2
    3Interval SchedulingSection 4.1,4.2
    4Minimum Spanning TreesSection 4.5
    5Union-FindSection 4.6
    6Dijkstra's shortest-pathsSection 4.4
    7Divid and conquer: mergesort. Recurrence equations and recursive programs.Section 5.1,5.2
    8Lower bound on sorting. Dynamic programming
    9Shortest pathsSection 6.8
    10Sequence alignmentSection 6.6
    11Matrix chain multiplication
    13Max-flow part 1Section 7.1
    14Max-flow part 2Section 7.2
    15Max-flow part 3Section 7.3
    Other topics to be covered: Max flow, min cut and matchings (Chapter 7), NP-completeness, and reductions (first 4 sections of Chapter 8).
    Strategies to cope with NP-hardness: approximation algorithms (sections from Chapter11), randomized algorithms (Quicksort, Section 13.5); randomized approximations (Sections 13.2, 13.4) Time permitting: local search and ideas about quantum algorithms.

    Material covered so far

    See here

    Homework

  • Assignment 1 Due Wednesday January 11 in class.
  • Assignment 2 Due Wednesday January 18 in class.
  • Assignment 3 Due Wednesday January 25 in class.
  • Assignment 4 Due Wednesday February 1st in class.
  • Assignment 5 Due Wednesday February 15th in class.
    •

    Important Homework Instructions

    Students are encouraged to work together, but each student must independently write up their solutions.
    Write-ups must include the names of any collaborators and any sources used to help solve a problem, other than the textbook.
    Do NOT search the web for solutions!