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

**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