CS5800, Algorithms. Spring 2019, Sections 1 and 2.
Video lectures below
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
Grading
- Class participation 10%.
- Homework 30%.
- Midterm 30%. Out on Wednesday, February 27, 2019, 15:00 EST. Due on Thursday, February 28, 2019, 15:00 EST.
- Final 30%. Out on Monday, April 22, 15:00 EST. Due on Tuesday, April 23, 15:00 EST.
The homework, midterm, and final are take-home. You should upload your solutions on blackboard as PDF. Note for the midterm and final exams you are given 24 hours. The final exam is cumulative.
Policies
- No late homework or exam 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.
- No collaboration is allowed on the midterm and final exams. You must work on the midterm and final exams on your own.
- For your solutions you can use what we saw in class and what you were supposed to know before taking this class. Anything else must be proved from scratch. In particular, finding solutions to problems on the web, or by asking students not enrolled in the class (or the class staff) is strictly prohibited.
No late homework or exam will be accepted.
- You should type your solutions to the homework and exams using LaTeX. LaTeX is a scientific document preparation system; most CS technical publications are prepared using this tool. There are many good, cross-platform, free editors. They include LyX (which I use regularly), TeXstudio, and overleaf (which I also use regularly). To use LyX you don't really have to know anything about LaTeX. If you want to know more about LaTeX The not so short introduction to LateX is a good reference to get you started.
Tentative class schedule and topics
We will be following the video lectures below. The video lectures are in turn based on the instructor's slides. However, we list next a few books that cover overlapping material:
- [E] Algorithms, by J. Erickson
- [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:
Note: this text is in a preliminary stage, but it may be useful as an extra reference.
Video 1
Youtube, Local
Introduction to algorithms. Defines algorithm.
Extra pointers: [E, 0] [CLRS, 1]
Video 2
Youtube, Local
Measuring the performance of algorithms. Asymptotic notation Big-Oh, Omega, and Theta. Length: 27:05 (note: this is longer than usual. A good breaking point is right before we introduce Big-Omega)
Extra pointers: [CLRS, 3]
Video 3
Youtube, Local
Bubble sort.
Extra pointers: [CLRS, Problem 2-2]
Video 4
Youtube, Local
Counting sort.
Extra pointers: [CLRS, 8.2]
Video 5
Youtube, Local
Radix sort.
Extra pointers: [CLRS, 8.3]
Video 6
Youtube, Local
Divide and conquer paradigm, mergesort.
Extra pointers: Mergesort [E, 1.4], [CLRS, 2.3]
Video 7
Youtube, Local
Quicksort.
Extra pointers: Quicksort [E, 1.5], [CLRS, 7]
Video 8
Youtube, Local
Oblivious mergesort
Extra pointers: [V, 2.1]
Video 9
Youtube, Local
Review of sorting. Computing the median [E, 1.7], [CLRS, 9.3]
Video 10
Youtube, Local
Closest pair [CLRS, 33.4]
Video 11
Youtube, Local
Karatsuba's integer multiplication [E, 1.8], [KT 5.5]
Video 12
Youtube, Local
Strassen's matrix multiplication [CLRS, 4.2], Fast Walsh-Hadamard transform [V, 2.2]
Video 13
Youtube, Local
Dynamic programming, coin change
Video 14
Youtube, Local
Longest common subsequence [CLRS, 15.4]
Video 15
Youtube, Local
Dynamic programming in economics [V, 3.1]
Video 16
Youtube, Local
Subset sum [E, 3.8]
Video 17
Youtube, Local
Greedy algorithms, activity selection problem [E, 4.2], [CLRS, 16.1]
Video 18
Youtube, Local
Data structures, binary search trees [CLRS 12.1, 12.2] [V 4]
Video 19
Youtube, Local
Rotations, AA trees [CLRS 13.2] [V 4]
Video 20
Youtube, Local
Insertion and deletion in AA trees [V 4]
Video 21
Youtube, Local
Hash functions [CLRS 11]
Video 22
Youtube, Local
Queues and heaps [CLRS 6]
Video 23
Youtube, Local
Graphs, breadth-first-search [E 5.4], [CLRS 22.1], [E 8.4], [CLRS 22.2]
Video 24
Youtube, Local
Bellman-Ford weighted minimum distance [E 8.7] [CLRS 24.1]
Video 25
Youtube, Local
Dijkstra shortest path [E 8.6], [CLRS 24.3]
Video 26
Youtube, Local
All pairs shortest path. All-pairs shortest-path via matrix multiplication [E 9.7], [CLRS 25.1]. Floyd Warshall [E 9.8], [CLRS 25.2]. Johnson's algorithm [E 9.4], [CLRS 25.3]
Video 27
Youtube, Local
Flow networks [E 10.1 - 10.3] [CLRS 26.1] (our notation is closer to edition 2 CLRS). Ford-Fulkerson [E 10.4] [CLRS 26.2]
Video 28
Youtube, Local
Edmonds-Karp [E 10.6] [CLRS 26.3]. Maximum matching [E 11.3], [CLRS 26.4].
Video 29
Youtube, Local
3SAT reduces to CLIQUE [CLRS 34.5.1]
Video 30
Youtube, Local
CLIQUE to VERTEX-COVER [CLRS 34.5.2]
Video 31
Youtube, Local
3SAT reduces to SUBSET-SUM [CLRS 34.5.5]
Video 32
Youtube, Local
3SAT reduces to 3COLOR [E 12.10]
Tentative list of topics to be covered.
Asymptotic notation. [CLRS, 3]
Bubblesort [CLRS, Problem 2-2]
Countingsort [CLRS, 8.2]
Radixsort [CLRS, 8.3]
Divide and conquer:
Mergesort [E, 1.4], [CLRS, 2.3]
Quicksort [E, 1.5], [CLRS, 7]
Oblivious mergesort [V, 2.1]
Median [E, 1.8], [CLRS, 9.3]
Closest pair [CLRS, 33.4]
Karatsuba's integer multiplication [E, 1.9], [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:
Coin-change problem
Longest common subsequence [CLRS, 15.4]
Subset sum [E, 3.8]
Dynamic programming in economics [V, 3.1]
Greedy:
Activity selection [E, 4.2], [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 [E 5.4], [CLRS 22.1]
Breadth-first search [E 8.4], [CLRS 22.2]
Bellman-Ford [E 8.7] [CLRS 24.1]
Dijkstra [E 8.6], [CLRS 24.3]
All-pairs shortest-path via matrix multiplication [E 9.7], [CLRS 25.1]
Floyd Warshall [E 9.8], [CLRS 25.2]
Johnson's algorithm [E 9.4], [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 [E 12.10]
Maximum flow:
Flow networks [E 10.1 - 10.3] [CLRS 26.1] (our notation is closer to edition 2 CLRS)
Ford-Fulkerson [E 10.4] [CLRS 26.2]
Edmonds-Karp [E 10.6] [CLRS 26.3]
Maximum bipartite matching [E 11.3], [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