CS5800, Algorithms. Spring 2017, Sections 1 and 2.

Description

Presents the mathematical techniques used for the design and analysis of computer algorithms. Focuses on algorithmic design paradigms and techniques for analyzing the correctness, time, and space complexity of algorithms. Topics may include asymptotic notation, recurrences, sorting and searching, divide and conquer, data structures, hashing, greedy algorithms, dynamic programming, graph algorithms, and NP-hardness.

Instructor

Emanuele Viola

When and where

Section 1: 11:45 am - 1:25 pm MR Behrakis Health Sciences Cntr 325
Section 2: 2:50 pm - 4:30 pm MW Behrakis Health Sciences Cntr 315

Staff, office hours, and communication

Piazza discussion board.

Staff and office hours (on Piazza)

Email: viola-class1@ccs.neu.edu

Grading

Homework (15%), in-class quizzes (total 15%), 2 midterms (20% each), and final (30%). All in-class quizzes and exams are cumulative.

Policies

No late homework will be accepted.
Collaborating with other students in the class on homework problems is fine and encouraged, though we urge you to attempt working out all of the problems by yourself first. In any case, you must write up your solutions, in your own words. Furthermore, if you did collaborate on any problem, you must clearly list all of the collaborators in your submission.
Finding solutions to homework problems on the web, or by asking students not enrolled in the class (or the class staff) is strictly prohibited.

Tentative class schedule and topics

We will be following the instructor's slides. However, we list next a few books that cover overlapping material:

[CLRS] Introduction to Algorithms, third edition, by T. Cormen, C. Leiserson, R. Rivest, and C. Stein
[DPV] Algorithms, by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani
[KT] Algorithm Design, by Jon Kleinberg, Éva Tardos

Some of the material we cover will be written down here:

[V] Algorithms and complexity, by E. Viola

Note: this text is in a preliminary stage, but it may be useful as an extra reference.

Class	Topics	Due
1-09 Mon	Administration and introduction. [CLRS, 1] Asymptotic notation. [CLRS, 3]	PS1 OUT
1-11/12 Wed/Thu	Bubblesort [CLRS, Problem 2-2] Countingsort [CLRS, 8.2] Radixsort [CLRS, 8.3]
1-16 Mon	Holiday, no classes	PS1 DUE/ PS2 OUT
1-18/19 Wed/Thu	Mergesort [CLRS, 2.3] Quicksort [CLRS, 7]
1-23 Mon	Oblivious mergesort [V, 2.1]	PS 2 DUE
1-25/26 Wed/Thu	Median [CLRS, 9.3] Closest pair [CLRS, 33.4]
1-30 Mon	Karatsuba's integer multiplication [KT, 5.5] Strassen's matrix multiplication [CLRS, 4.2]	QUIZ/ PS3 OUT
2-01/02 Wed/Thu	Polynomials and fast Fourier transform [CLRS, 30], [KT, 5.6]
2-06 Mon	Introduction to dynamic programming	PS3 DUE
2-08/09 Wed/Thu	Practice midterm. Thursday class canceled due to weather.
2-13 Mon	Midterm I NOTE: Different rooms 11:45am - 1:25pm in HT (Hurtig) 129 2:50pm - 4:30pm in BK (Behrakis) 310
2-15/16 Wed/Thu	Dynamic programming Subset sum with small numbers Coin-change problem
2-20 Mon	Holiday, no classes	PA1 OUT
2-22/23 Wed/Thu	Dynamic programming in economics [V, 3.1] Longest common subsequence [CLRS, 15.4]	PS4 OUT
2-27 Mon	Binary search trees [CLRS 12.1, 12.2] [V 4] Rotations [CLRS 13.2] [V 4]
3-01/02 Wed/Thu	AA Trees [V 4]	PS 4 DUE by Wed 2 PM
3-06 Mon	Spring break, no classes	PA1 DUE
3-08/09 Wed/Thu	Spring break, no classes
3-13 Mon	Hash functions [CLRS 11]	QUIZ
3-15/16 Wed/Thu	Review
3-20 Mon	Midterm II NOTE: Different rooms 11:45am - 1:25pm in HT (Hurtig) 129 2:50pm - 4:30pm in BK (Behrakis) 310	PS 5 OUT/ PA2 OUT
3-22/23 Wed/Thu	Heaps [CLRS 6] Graph representations [CLRS 22.1] Breadth-first search [CLRS 22.2]
3-27 Mon	Bellman-Ford [CLRS 24.1] Dijkstra [CLRS 24.3]	PS 5 DUE
3-29/30 Wed/Thu	All-pairs shortest-path via matrix multiplication [CLRS 25.1] Floyd Warshall [CLRS 25.2] Johnson's algorithm [CLRS 25.3]
4-03 Mon	3SAT reduces to CLIQUE [CLRS 34.5.1]	QUIZ / PS 6 OUT/ PA2 DUE
4-05/06 Wed/Thu	CLIQUE to VERTEX-COVER [CLRS 34.5.2] 3SAT reduces to SUBSET-SUM [CLRS 34.5.5] 3SAT reduces to 3COLOR
4-10 Mon	Flow networks [CLRS 26.1] (our notation is closer to edition 2 CLRS) Ford-Fulkerson [CLRS 26.2] Edmonds-Karp [CLRS 26.3] Maximum bipartite matching [CLRS 26.4]	PS 6 DUE/ PS 7 OUT
4-12/13 Wed/Thu	The linear programming problem [CLRS 29.1, 29.2] The simplex algorithm [CLRS 29.3] 2-approximation for VERTEX-COVER [CLRS 35.1] 2-approximation for weighted VERTEX-COVER [KT 11.6]
4-17 Mon	Holiday, no classes	PS 7 DUE
4-19/20 Wed/Thu	Review
4-26 Wed	Final exam 10:30 am - 12:30 pm Science Engineering Complex 102

Tentative list of topics

Asymptotic notation. [CLRS, 3]
Bubblesort [CLRS, Problem 2-2]
Countingsort [CLRS, 8.2]
Divide and conquer:
Radixsort [CLRS, 8.3]
Mergesort [CLRS, 2.3]
Quicksort [CLRS, 7]
Oblivious mergesort [V, 2.1]
Median [CLRS, 9.3]
Closest pair [CLRS, 33.4]
Karatsuba's integer multiplication [KT, 5.5]
Strassen's matrix multiplication [CLRS, 4.2]
Fast Walsh-Hadamard transform [V, 2.2]
Polynomials and fast Fourier transform [CLRS, 30], [KT, 5.6]
Dynamic programming:
Subset sum with small numbers
Coin-change problem
Dynamic programming in economics [V, 3.1]
Longest common subsequence [CLRS, 15.4]
Activity selection [CLRS, 16.1]
Data structures:
Binary search trees [CLRS 12.1, 12.2] [V 4]
Rotations [CLRS 13.2] [V 4]
AA Trees [V 4]
Hash functions [CLRS 11]
Heaps [CLRS 6]
Graph algorithms:
Graph representations [CLRS 22.1]
Breadth-first search [CLRS 22.2]
Bellman-Ford [CLRS 24.1]
Dijkstra [CLRS 24.3]
All-pairs shortest-path via matrix multiplication [CLRS 25.1]
Floyd Warshall [CLRS 25.2]
Johnson's algorithm [CLRS 25.3]
NP completeness:
3SAT reduces to CLIQUE [CLRS 34.5.1]
CLIQUE to VERTEX-COVER [CLRS 34.5.2]
3SAT reduces to SUBSET-SUM [CLRS 34.5.5]
3SAT reduces to 3COLOR
Maximum flow:
Flow networks [CLRS 26.1] (our notation is closer to edition 2 CLRS)
Ford-Fulkerson [CLRS 26.2]
Edmonds-Karp [CLRS 26.3]
Maximum bipartite matching [CLRS 26.4]
Linear programming:
The linear programming problem [CLRS 29.1, 29.2]
The simplex algorithm [CLRS 29.3]
Duality [CLRS 29.4]
Approximation algorithms:
2-approximation for VERTEX-COVER [CLRS 35.1]
2-approximation for weighted VERTEX-COVER [KT 11.6]
Vector programs, randomized rounding, and max-cut