CMSC 28100 Introduction to Complexity Theory

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

    Course Mechanics

    Please read about rules, homework, and grading here

    Instructor

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

    Office Hours: TBA

    Lecture: MWF 9:30- 10:20 in Ry 251

    TA

    David Kim
    162B Ryerson
    email: hongk (at) cs.uchicago.edu

    Office hours: TBA

    Textbook: "Introduction to the Theory of Computation 3E" by Michael Sipser

    Other useful sources:
    -

    Grading will be based on weekly homework assignments, two midterms 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

    This is an overall plan for the course. I will surely not follow it in every detail. Look here for what we actually covered.
    LectureTopicsReading
    1Stable matchingsChapter 1
    2Running time analysisChapter 2
    3Interval SchedulingSection 4.1,4.2
    4Minimum Spanning TreesSection 4.5
    5Heaps, and other data structures; Shortest pathsSection 4.6
    6Implementing Dijkstra, Divide (into "equal" parts) and ConquerSection 4.4
    7Sequence AlignmentSection 6.7
    8More sequence Alignment: using little spaceSection 6.6
    9More Dynamic Programming: optimal matrix multiplication sequence
    10Even more Dynamic Programming: Top Down vs Bottom UpSection 6.2
    11Max Flow Problem
    13Max-flow: Ford-Fulkerson algorithmSection 7.1
    14Max-flow residual graphsSection 7.2
    15Max-flow Min Cut Theorem (using Ford-Fulkerson)Section 7.3
    15Network Flows: scaling algorithms Chapter 7
    16Applications of Max Flow: matchings, Hall's Theorem, Section 7.5, 7.7
    17Extensions: multiple sources and sinks. Circulations.
    18Applications of Max FlowChapter 7
    19Randomized Algorithms. Contention in Distributed ComputationChapter 13 (beginning)
    20Randomized Access to Resource. Karger's Global Min Cut AlgorithmSection 13.2
    21Randomized median. Quicksort. Randomized Max 3-SATSection13.4, 13.5
    19Polytime Reductions. The class NPSection 8.1
    20NP hardness, NP-completeness. Vertex Cover, Independent SetChapter 8
    21More NP-completeness Proofs: 3-SAT, Hamiltonian Cycle, Hamiltonian Path, TSPChapter 8
    Other topics as time permits: approximation algorithms, intractability, quantum computation?

    Material covered so far

    See here

    Homework

    Please read about general guidelines here
  • Assignment 1 Due Wednesday January 15 in class.
  • Assignment 2 Due Wednesday January 22 in class.
  • Assignment 3 Due Wednesday January 29 in class.
  • Assignment 4 Due Friday, February 7 in class.
  • Assignment 5 Due Wednesday February 12 in class.
  • Assignment 6 Due Wednesday February 19 in class.
  • Assignment 7 Due Friday February 28 in class.
  • Assignment 8 Due Friday March 7 in class.
  • Assignment 9 Due Wednesday March 12 in class.
    •