CS 381: Introduction to the Analysis of Algorithms
Fall 2017


The course gives a broad introduction to the design and analysis of algorithms.  The course strives to strengthen a student’s ability to solve problems computationally by effectively utilizing an understanding of algorithm design techniques, algorithms analysis, and data structures. Topics to be covered include: growth of functions; asymptotic analysis;  recurrences; sorting and order statistics; common algorithm design techniques including divide-and-conquer, dynamic programming, and greedy; streaming and on-line algorithms; design of advanced data structures; graph algorithms; parallel algorithms; lower bound techniques and problem reductions; NP-completeness, approximation algorithms.

Detailed Syllabus.  Learning Outcomes.

Class Times: Monday, Wednesday, Friday, 1:30-2:20pm, ARMST 1010 


Optional Problem Solving Sessions

·         Wednesday, 3:30-4:20, WALC 2127 (seats 45)

·         Friday 2:30-3:20, LWSN 1106 (seats 44)


Midterm 1: Wednesday, September 27, 8:00-9:00 pm

Midterm 2: Wednesday, November 1, 8:00-9:00 pm

Final Exam: set by university during final exam week


Note: Do not schedule an interview trip at exam times; do not schedule to leave town before the exam date is posted (it could be on Saturday).




Professor S.E. Hambrusch

LWSN 1179; seh@cs.purdue.edu
Office Hours: Monday, 12-1:15pm or by appointment


Graduate Teaching Assistants

·         Tatiana Kuznetsova, tkuznets@purdue.edu, Office hours:  Tuesday, 3-4:20pm

·         Anudeep Dwaram, adwaram@purdue.edu, Office hours: Thursday, 4:30-6pm

·         Raine Yeh, yeh10@purdue.edu, Office hours: Tuesday, 1:30-3pm


Undergraduate Teaching Assistants

·         Ryan Davis, davis791@purdue.edu, Office hours: Wednesday, 11:45-1:20pm

·         Akshat Goyal, goyal26@purdue.edu, Office hours: Monday, 2:30-4pm

·         Shubhang Kulkarni, kulkar17@purdue.edu, Office hours: Friday, 11-12:30pm

·         Ian Renfro,  renfroi@purdue.edu, Office hours: Wednesday, 4:30-6pm

·         Kevin Xia, xia51@purdue.edu , Office hours: Thursday, 10:30-noon


All TA office hours are held in HAAS G50 (if HAAS G50 is full, TAs may use HAAS 143)


Course work, standards, and policies. Academic honesty policy.

·         Make sure to read and understand all expectations and policies on course work, assignments, and academic honesty described on those pages.


iClickers. Clickers will be used during class for short answer questions and feedback. If you do not have a clicker, obtain one before the first class.


The discussion forum for the class is on Piazza. Assignments and lecture slides are posted on Piazza.

Course Textbook
. Introduction to Algorithms, T. Cormen, C. Leiserson, R. Rivest, C. Stein, McGraw-Hill, 2009 (3rd edition). Digital version in Purdue Library.

Related Material

·         Theoretical Computer Science Cheat Sheet. Ten pages of mathematical formulas and other useful information for computer scientists (compiled by Steve Seiden).

·         MIT OpenCourseWare. Site contains links to an algorithm course; provides supplementary material, practice material and selected lectures. 

·         Video lectures and other material by Tim Roughgarden

·         Related algorithm text book

o    Algorithm Design, J. Kleinberg, E. Tardos, Pearson AddisonWesley, 2006

o    Kleinberg-Tardos slides as revised by Kevin Wayne