• September 15, 2020: webpage draft created.


This is an introductory graduate-level course on algorithm design and analysis, covering fundamental techniques in designing algorithms and proving bounds on their time and space complexity.

As the course focuses on the analysis (therefore mathematical aspect) of algorithms, students are expected to have a solid undergraduate mathematical background (e.g., elementary combinatorics, discrete probability, linear algebra and calculus). Students are also expected to have learned elementary algorithms, including basic data structures, basic sorting and searching, elementary graph terminology, and asymptotic analysis of time and space complexity for algorithms (i.e. big-O/Omega/Theta notation). There will be no programming requirement in this course. However, it will be very helpful to have past experience with implementation of basic algorithms and data structures.


Qin Zhang
Office hour: Wednesday 11am-12pm, Via this Link (Zoom).

Associate Instructors
  • Harshad Badiyani
    Office hour: Friday 4-5pm via this Link (Zoom).
  • Yan Song (helper, office hour only)
    Office hour: Tuesday 2-3pm via this Link (Zoom).

  • Time and place

    9:25am-10:40am, Monday/Wednesday. (Synchronized) lectures via Zoom (see the Canvas page for the link).


    Required Textbook: [KT] Algorithm Design, J. Kleinberg, E. Tardos. Pearson Education.
    Lecture notes will be posted on Canvas.

    Course contents

  • Introduction [slides]
  • Greedy algorithms: interval scheduling, minimum spanning tree, shortest path
  • Divide and conquer: merge sort, counting inversions, closest pairs, fast fourier transform
  • Dynamic Programming: weighted interval scheduling, knapsack, sequence alignment, all-pair shortest path
  • NP-completeness
  • Selected topics: approximation and randomized algorithms

  • Grading

    • Class participation 10%

    • Assignments 40%

      Five written assignments. Assignments are posted in Canvas. The answers should be typeset in LaTeX and submitted via Canvas; here is a template to start with. No extensions or late homeworks will be granted.

    • Exams 50%

      (1) Midterm 20%
      (2) Final 30%
      There will be NO make-up exams. If students have to miss the midterm exam due to family/medical emergencies (and/or other reasons which will be granted on a case by case basis, but conference travels etc. cannot be the reason), they need to contact the instructor before the exams for permission, and their other exam grades will be re-weighted. Internship and job application interviews and paper deadlines are NOT proper reasons to miss an exam.

    Course policies

    For assignments, students may discuss answers with anyone, including problem approaches and proofs. But all students must write their own proofs, and write-ups. The names of all people that you have talked to should be listed at the beginning of the first page. If a solution comes from existing papers/web/books, they must be properly cited, and you must write the solution in a way that demonstrates your understanding (simply copying the solution will be considered as plagiarism, and will result an "F" for the entire course). All deadlines are firm. No late assignments will be accepted unless there are legitimate circumstances.
    For more details, see Indiana University Code of Student Rights, Responsibilities, and Conduct.


      CSCI-C241 "Discrete Structures for Computer Science", CSCI-C343 "Data Structures", and MATH-M 216 "Analytic Geometry and Calculus II" (or MATH-M 212 CALCULUS II). The prerequisites are enforced.