csce750: Analysis of Algorithms

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

Past Present Future Undated Key Dates
Syllabus
Homework 0
2018-08-23
Lecture 01
Introduction to the course. What is an algorithm? Models of computation.
[notes-intro.pdf]
2018-08-28
Lecture 02
Example problems and example algorithms. Insertion sort. Mergesort. Asymptotic notations.
[notes-asymptotics.pdf]
[notes-summations.pdf]
2018-08-29
Add/Drop deadline
2018-08-30
Lecture 03
Summations. Recurrences. Substitution method.
[notes-recurrences1.pdf]
2018-09-04
Homework 1
Note: Access to the solutions document is password protected. The username is the three-digit number for this course. The password is the same as the username.
[hw1.pdf]
[hw1-sol.pdf]
2018-09-04
Lecture 04
More on the substitution method. Change of variables. Recursion trees.
[notes-recurrences2.pdf]
2018-09-06
Quiz 1
2018-09-06
Lecture 05
More on recursion trees. The Master Theorem.
[notes-recurrences3.pdf]
2018-09-11
Lecture 06
(no class due to hurricane)
2018-09-13
Lecture 07
(no class due to hurricane)
2018-09-19
Homework 2
2018-09-18
Lecture 08
2018-09-20
Quiz 2
2018-09-20
Lecture 09
Randomized Algorithms
[notes-randomized.pdf]
2018-09-25
Lecture 10
More on randomized algorithms. Selection problems QuickSelect. Deterministic linear time selection.
[notes-selection.pdf]
2018-09-27
Homework 3
2018-09-27
Lecture 11
More on linear time selection. Hash tables.
[notes-hash.pdf]
2018-10-02
Quiz 3
2018-10-02
Lecture 12
No additional class meeting in Innova 1400 after Quiz 3. Instead, please use the lecture time for this recorded lecture on lower bounds.
[lect-lowerbounds.mp4]
[notes-lowerbounds.pdf]
2018-10-04
Lecture 13
Guest lecture: Hazhar Rahmani.
2018-10-09
Lecture 14
Balanced binary search trees.
[notes-bst.pdf]
2018-10-11
Lecture 15
(no class due to hurricane)
2018-10-14
Homework 4
No change to due date, in spite of class cancellation on Oct 11.
[hw4.pdf]
[hw4-sol.pdf]
2018-10-16
Quiz 4
No change to date for Quiz 4, in spite of class cancellation on Oct 11.
[quiz4-sol.pdf]
2018-10-16
Lecture 16
More on treaps. Augmenting data structures. Order statistic trees.
[notes-augmenting.pdf]
2018-10-18
Last day to drop without WF
(extended)
2018-10-18
Fall Break
(no class)
2018-10-23
Lecture 17
Dynamic programming
[notes-dp.pdf]
2018-10-25
Homework 5
2018-10-25
Lecture 18
Amortized Analysis
[notes-amortized.pdf]
2018-10-30
Quiz 5
2018-10-30
Lecture 19
Fibonacci heaps
[notes-fibheap.pdf]
2018-11-01
Lecture 20
More on Fibonacci heaps
2018-11-06
Election Day (no class)
(no class)
2018-11-08
Lecture 21
Disjoint sets. Linked list method. Disjoint set forests. Basic graph algorithms.
[notes-disjoint-sets.pdf]
[notes-graphs.pdf]
2018-11-13
Homework 6
2018-11-13
Lecture 22
Minimum spanning trees
[notes-mst.pdf]
2018-11-15
Quiz 6
2018-11-15
Lecture 23
Single source shortest paths: Dijkstra
[notes-dijkstra.pdf]
2018-11-20
Lecture 24
More on single-source shortest paths. Bellman-Ford. All-pairs shortest paths. Floyd-Warshall.
[notes-apsp.pdf]
2018-11-22
Thanksgiving Break
(no class)
2018-11-27
Lecture 25
2018-11-29
Homework 7
2018-11-29
Lecture 26
NP-hard and NP-complete. Reductions.
2018-12-04
Quiz 7
2018-12-04
Lecture 27
Approximation algorithms
[notes-approx.pdf]
2018-12-06
Lecture 28
More on approximation algorithms. Final exam preview. Wrap up.
2018-12-11
Final exam
12:30-3:00
[review.pdf]