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.
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; email@example.com
Office Hours: Monday, 12-1:15pm or by appointment
Graduate Teaching Assistants
· Tatiana Kuznetsova, firstname.lastname@example.org, Office hours: Tuesday, 3-4:20pm
· Anudeep Dwaram, email@example.com, Office hours: Thursday, 4:30-6pm
· Raine Yeh, firstname.lastname@example.org, Office hours: Tuesday, 1:30-3pm
Undergraduate Teaching Assistants
· Ryan Davis, email@example.com, Office hours: Wednesday, 11:45-1:20pm
· Akshat Goyal, firstname.lastname@example.org, Office hours: Monday, 2:30-4pm
· Shubhang Kulkarni, email@example.com, Office hours: Friday, 11-12:30pm
· Ian Renfro, firstname.lastname@example.org, Office hours: Wednesday, 4:30-6pm
· Kevin Xia, email@example.com , 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)
· 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.
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.
· 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