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
    7Divide 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
    15Matchings, Image segmentationSection 7.5
    16Circulations, etc.Section 7.7
    17Lower bounds: Sorting by comparisons, Halting Problem.
    18Probabilistic Algorithms. Sections 13.1 (beginning), 13.3, 13.5
    19ReductionsSection 8.1
    20Satisfiability, NP-hard problemsSection 8.2,8.3,8.4
    21Proving NP-completeness: Hamitonian Circuits (Section 8.5)
    Other topics to be covered: Strategies to cope with NP-hardness: approximation algorithms (sections from Chapter11) 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.
  • Assignment 6 Due Wednesday February 22nd in class.
  • Assignment 7 Due Wednesday February 29th in class.
  • Bonus Assignment Due Wednesday March 7 in my office (1PM).
    •

    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!