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).
Instructor
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.
·
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