## csce750 Analysis of Algorithms

### Fall 2017 - University of South Carolina - Jason O'Kane

Past Present Future Undated Quizzes and Exam
2017-08-24
2017-08-24
Lecture 01
Course format and policies. What is an algorithm? Models of computation.
[notes-intro.pdf]
2017-08-29
Lecture 02
Example problem (sorting) and example algorithms (insertion sort, merge sort). Asymptotic notations. Summations.
[notes-asymptotics.pdf]
[notes-summations.pdf]
2017-08-31
Homework 1
[hw01.pdf]
[hw01-sol.pdf]
2017-08-31
Lecture 03
Summations. Bounding by individual terms. Bounding by adding or removing terms. Telescoping sums. Bounding by integrals.
2017-09-05
Quiz 1
Covering material from HW1. CLRS chapters 1, 2, 3, and Appendix A.

Average score: 31.6/40.0

Quiz papers may be collected from the instructor during office hours.
[quiz01-sol.pdf]

2017-09-05
Lecture 04
Recurrences. Substitution method.
[notes-recurrences1.pdf]
2017-09-07
Lecture 05
More on the substitution method. Recursion trees.
[notes-recurrences2.pdf]
2017-09-12
Homework 2
2017-09-12
Lecture 06
Unbalanced recursion trees. The master theorem.
[notes-recurrences3.pdf]
2017-09-14
Quiz 2
Covering material from HW2. CLRS Sections 4.3 and 4.4.

Average score: 34.5/40.0
[quiz02-sol.pdf]

2017-09-14
Lecture 07
More on the master theorem.
2017-09-19
Lecture 08
Heaps and heapsort.
[notes-heaps.pdf]
2017-09-21
Homework 3
2017-09-21
Lecture 09
Quicksort: Deterministic and randomized versions.
[notes-quicksort.pdf]
2017-09-26
Quiz 3
Covering material from HW3. CLRS Section 4.5 and Chapter 6.

Average score: 37.3/40.0
[quiz03-sol.pdf]

2017-09-26
Lecture 10
September 26 will have Quiz 3 only. No additional lecture after the quiz.
2017-09-28
Lecture 11
No class meeting in WMBB 409. Instead, please use the lecture time to watch this recorded lecture on lower bounds, in preparation for HW4 and Quiz 4.
[lect-lowerbounds.mp4]
[notes-lowerbounds.pdf]
2017-10-03
Homework 4
2017-10-03
Lecture 12
Medians and order statistics. Quickselect. Linear time deterministic selection.
[notes-selection.pdf]
2017-10-05
Quiz 4
Covering material from HW4.

Average score: 26.3/40.0
[quiz04-sol.pdf]

2017-10-05
Lecture 13
More on linear time deterministic selection.
2017-10-10
Lecture 14
Hash tables.
[notes-hash.pdf]
2017-10-12
Lecture 15
More on hash tables. Binary search trees.
[notes-bst.pdf]
2017-10-13
Homework 5
2017-10-16
Midpoint
Last day to drop without WF
2017-10-17
Quiz 5
Covering material from HW5.

Average score: 34.8/40.0
[quiz05-sol.pdf]

2017-10-17
Lecture 16
Treaps.
2017-10-19
Fall break
(no class)
2017-10-24
Lecture 17
More on treaps. Augmenting data structures.
[notes-augmenting.pdf]
2017-10-26
Lecture 18
More on augmenting data structures. Dynamic programming.
[notes-dp.pdf]
2017-10-31
Homework 6
2017-10-31
Lecture 19
More on dynamic programming. Amortized analysis.
[notes-amortized.pdf]
2017-11-02
Quiz 6
Covering material from HW6.

Average score: 31.6/40.0
[quiz06-sol.pdf]

2017-11-02
Lecture 20
Potential method for amortized analysis.
2017-11-07
Lecture 21
Fibonacci heaps: Structure.
[notes-fibheap.pdf]
2017-11-09
Lecture 22
Fibonacci heaps: Operations and analysis.
2017-11-14
Homework 7
2017-11-14
Lecture 23
Fibonacci heaps: Degree bound. Disjoint sets via linked lists. Disjoint set forests.
[notes-disjoint-sets.pdf]
2017-11-16
Quiz 7
Covering material from HW7.

Average score: 30.9/40.0
[quiz07-sol.pdf]

2017-11-16
Lecture 24
Disjoint sets: Path compression and union-by-rank.
2017-11-21
Lecture 25
Basic graph algorithms. Minimum spanning trees: Definitions, basics, Kruskal's algorithm.
[notes-disjoint-sets.pdf]
[notes-mst.pdf]
2017-11-23
Thanksgiving
(no class)
2017-11-28
Homework 8
2017-11-28
Lecture 26
Minimum spanning trees: Prim's algorithm. Shortest paths.
2017-11-30
Quiz 8
Covering material from HW8.

Average score: 34.4/40.0
[quiz08-sol.pdf]

2017-11-30
Lecture 27
More on shortest paths. Negative weights.
2017-12-05
Lecture 28
NP-complete problems.
[notes-npcomplete.pdf]
2017-12-07
Lecture 29
NP-complete problems. End of course evaluations.
2017-12-10
Reference Sheet
The final exam will include a crowd-sourced one-page reference sheet filled with information that you, as a class, recommended. To add information to the reference sheet, use this link to edit the current draft, by 11:59pm on December 10. Though I reserve the right to revise the final version, the intent is to include any information you suggest that (a) fits reasonably within the one-page format without resorting to tiny fonts, (b) is factually correct, and (c) is of general reference value, rather than a recapitulation of solutions to specific types of problems. The finalized sheet will be made available before the exam, so you will know what to expect.

When the deadline for edits to the reference sheet passed, the document extended well beyond the one-page limit and contained some LaTeX compile errors. I've cleaned up the parts that I could (page 1) and let the rest (page 2) stand pretty much as is. The version linked here (both pages) is the one that will be available for the final exam.
[reference-sheet.pdf]

2017-12-12
Homework 9
2017-12-14
Final Exam
Average score: 275/320

In the dropbox, exam grades are split into four columns, because that software cannot store grades higher than 100. Add the four numbers to obtain your total exam score.
[review.pdf]