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
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.
[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
2017-10-17
Lecture 16
2017-10-24
Lecture 17
2017-10-26
Lecture 18
2017-10-31
Lecture 19
2017-11-02
Quiz 6
2017-11-02
Lecture 20
2017-11-07
Lecture 21
2017-11-09
Lecture 22
2017-11-14
Lecture 23
2017-11-16
Quiz 7
2017-11-16
Lecture 24
2017-11-21
Lecture 25
2017-11-23
Thanksgiving
(no class)
2017-11-28
Lecture 26
2017-11-30
Quiz 8
2017-11-30
Lecture 27
2017-12-05
Lecture 28
2017-12-07
Lecture 29
2017-12-14
Final Exam
12:30pm–3:00pm