CS381 Introduction to the Analysis of Algorithms

Spring 2019

Tu/Th 10:30 am - 11:45 am MATH 175

Course staff

Instructors:


Graduate TAs:

  • Ryan Davis,(head)
    davis791@purdue.edu,
  • Young-San Lin, (head)
    lin532@purdue.edu,
  • Yu Shi,
    shi442@purdue.edu ,
  • Minshen Zhu,
    minshen.zh@gmail.com

Undergraduate TAs:

  • Yuting Guo
  • Ian Renfro (head)
  • Shubhang Kulkarni
  • Matthew Muhaberac
  • Abhishek Sharma
Announcements

Welcome to CS 381!

Texts
  • Algorithm design

    J. Kleinberg, E. Tardos. Pearson Education.

  • Intro to algorithms

    T. Cormen, C.Leiserson, R. Rivest, C. Stein. 3rd edition. MIT

Class websites

Blackboard for assigned homework and grades.

Piazza for class discussions.

Course description
The course gives a broad introduction to the design and analysis of algorithms. A tentative list of topics includes: sorting and order statistics; common algorithm design techniques, including divide-and-conquer, dynamic programming, and greedy; design and use of data structures; flows and cuts; lower bound techniques; graph algorithms; NP-completeness; randomized algorithms; approximation algorithms.

Prerequisites: CS 251, CS 182.

Grading
  • 5% clicker (bring your own)
  • 20% homework
  • 20% each midterm
  • 35% final.
Schedule (subject to change)
(two lectures will be cancelled to make-up for the evening exams)

  • Jan. 8 Lecture 1. Course intro. Review induction.
  • Jan. 10Lecture 2. Asymptotic notation.
  • Jan. 15 Lecture 3. Divide and conquer. Merge sort. Recurrences.
  • Jan 17 Lecture 4. Counting inversions slides, demo. Max subsequence Book 4.1.
  • Jan. 22 Lecture 5. Max subarray problem. Master theorem. Book 4.1, 4.5, 4.6
  • Jan. 24 Lecture 6. Median and order statistics.
  • Jan 29 Lecture 7. Order statistics
  • Jan 31 Lecture 8. Closest pair of points
  • Feb. 5 Lecture 9 at Skyline and exam review and EVENING MIDTERM 8:00p - 9:30p PHYS 114 and 201(overflow)
  • Feb 7 Lecture 10. Dynamic Programming
  • Feb. 12 Lecture 11. DP
  • Feb 14 Lecture 12.DP
  • Feb 19 Lecture 13 DP
  • Feb. 21 Lecture 14. DP
  • Feb. 26 Lecture 15. DP
  • Feb. 28 Lecture 16. DP
  • Mar. 5 Lecture 17 Graph algorithms
  • Mar. 7 Lecture 18. Shortest path
  • Mar. 12 Lecture 19. Spring Break
  • Mar. 14 Lecture 20. Spring Break.
  • Mar. 19 Lecture 21. Belman Ford and evening MIDTERM 8:00p - 9:30p WALC 1055
  • Mar 21 Lecture 22 CANCELLED
  • Mar 26 Lecture 23 Topological sorting
  • Mar. 28 Lecture 24 Flow networks
  • Apr. 2 Lecture 25 Flow networks
  • Apr 4 Lecture 26 Ford-Fulkerson
  • Apr. 9 Lecture 27 Max Flow Min Cut Theorem
  • Apr 11 Lecture 28 Reductions
  • Apr. 16 Lecture 29 P, NP
  • Apr 18 Lecture 30 NP-completeness
  • Apr 23 Lecture 31 NP-completness
  • Apr 25 Lecture 32 CANCELLED
  • May 1 1-3pm Room CL50 224 FINAL EXAM