csce750: Analysis of Algorithms

Fall 2019 - University of South Carolina - Jason O'Kane

Past Present Future Undated
2019-08-22
Lecture 01
Introduction to the course. What is an algorithm? (Note: No video is available for this lecture. Instead, the material was reviewed in Lecture 2.)
[notes-intro.pdf]
2019-08-22
Homework 0
2019-08-27
Lecture 02
Models of computation. Example algorithms. Asymptotic notations.
[notes-asymptotics.pdf]
2019-08-29
Lecture 03
2019-09-03
Lecture 04
Solving recurrences. Substitution method.
[notes-recurrences1.pdf]
2019-09-04
Homework 1
2019-09-05
Quiz 1
Average score: 31.34/40
[quiz01-sol.pdf]
2019-09-05
Lecture 05
Recursion trees.
[notes-recurrences2.pdf]
2019-09-10
Lecture 06
Master theorem. Heaps.
[notes-recurrences3.pdf]
2019-09-12
Lecture 07
More on heaps. Randomized algorithms.
[notes-heaps.pdf]
2019-09-17
Homework 2
2019-09-17
Lecture 08
More on randomized algorithms.
[notes-randomized.pdf]
2019-09-19
Quiz 2
Average score: 35.34/40
[quiz02-sol.pdf]
2019-09-19
Lecture 09
2019-09-24
Lecture 10
Hash tables.
[notes-hash.pdf]
2019-09-26
Lecture 11
No class meeting in Innova 1400. Instead, please use the lecture time for this recorded lecture on lower bounds.
[lect-lowerbounds.mp4]
[notes-lowerbounds.pdf]
2019-10-01
Homework 3
2019-10-01
Lecture 12
Binary search trees. Treaps.
[notes-bst.pdf]
2019-10-03
Quiz 3
2019-10-03
Lecture 13
More on treaps.
2019-10-08
Lecture 14
Augmenting data structures.
[notes-augmenting.pdf]
2019-10-10
Fall break
2019-10-15
Lecture 15
Dynamic programming.
[notes-dp.pdf]
2019-10-17
Homework 4
2019-10-17
Lecture 16
Amortized analysis.
[notes-amortized.pdf]
2019-10-22
Quiz 4
2019-10-22
Lecture 17
More on amortized analysis.
2019-10-24
Lecture 18
Fibonacci heaps.
[notes-fibheap.pdf]
2019-10-29
Lecture 19
More on Fibonacci heaps.
2019-10-31
Homework 5
2019-10-31
Lecture 20
2019-11-05
Quiz 5
2019-11-05
Lecture 21
(No additional lecture after Quiz 5.)
2019-11-07
Lecture 22
Guest lecture on geometric data structures.
2019-11-12
Lecture 23
Graph algorithms. Spanning trees. Kruskal's algorithm.
[notes-graphs.pdf]
[notes-mst.pdf]
2019-11-14
Homework 6
2019-11-14
Lecture 24
More on spanning trees. Prim's algorithm. Shortest paths. Dijkstra's algorithm.
[notes-dijkstra.pdf]
2019-11-19
Quiz 6
2019-11-19
Lecture 25
More on shortest paths. Negative weights. Bellman-Ford. Start on NP-completeness. Problems as languages.
[notes-npcomplete.pdf]
2019-11-21
Lecture 26
All-pairs shortest paths.
[notes-apsp.pdf]
2019-11-26
Lecture 27
More on NP-completeness. P, NP, NP-hard, NP-complete. Cook-Levin Theorem.
2019-11-28
Thanksgiving break
2019-11-28
Homework 7
2019-12-03
Quiz 7
2019-12-03
Lecture 28
Reductions to prove NP-completeness.
2019-12-05
Lecture 29
Finish NP-completeness. Approximation algorithms. Wrap up. Course evaluations.
[notes-approx.pdf]
2019-12-09
Homework 8