csce750 Analysis of Algorithms

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

Past Present Future Undated Exams
2016-08-18
Homework 00
This is a quick reminder of material that you should know from your undergraduate algorithms course. [hw00.pdf] [hw00-sol.pdf]
2016-08-18
Introduction to the course. What is an algorithm? Models of computation.
2016-08-23
Asymptotic notations. Summations.
2016-08-23
Homework 01
2016-08-25
More on summations. Recurrences: Substitution method.
2016-08-25
Homework 02
2016-08-30
Recurrences: More on the substitution method. Tree method.
2016-08-30
Homework 03
2016-09-01
More on the Tree method. Master theorem. Heaps.
2016-09-01
Homework 04
2016-09-06
More on heaps. Randomized quicksort. Worst-case expected analysis.
2016-09-06
Homework 05
2016-09-08
Analysis of randomized quicksort. Lower bounds for sorting.
2016-09-08
Homework 06
2016-09-13
Order statistics. Quickselect. Deterministic linear time selection.
2016-09-08
Homework 07
2016-09-15
Preview Test 1. Hash tables.
2016-09-15
Test 1 Sample Questions
These are sample questions similar to what you might expect for Test 1, but in the single-question quiz format used in previous semesters. Some of these contain standard formulas for references; because you'll be allowed notes on the exam, these formulas will not be provided for you. [quiz01-sol.pdf] [quiz02-sol.pdf] [quiz03-sol.pdf] [quiz04-sol.pdf] [quiz05-sol.pdf] [quiz06-sol.pdf]
2016-09-15
Test 1 Review Sheet
2016-09-20
Test 1
Covers Lectures 1-8 (Chapters 1-9 and Appendix A.) Average score 112 (Q1:17, Q2:22, Q3:22, Q4:23, Q5:17, Q6:13). [test1-sol.pdf]
2016-09-22
More on hash tables. Balanced binary search trees.
2016-09-22
Homework 08
2016-09-27
Treaps.
2016-09-27
Homework 09
2016-09-27
Office hours are cancelled for today.
2016-09-29
Augmenting data structures.
2016-10-04
Dynamic programming.
2016-10-04
Homework 10
2016-10-06
Lecture 15
Canceled due to weather.
2016-10-11
Lecture 16
Use this time to catch up on the Homeworks 8-10. No lecture, due to instructor's travel.
2016-10-13
Fall break
2016-10-18
Dynamic programming. Amortized analysis.
2016-10-20
Potential method for amortized analysis.
2016-10-20
Homework 11
2016-10-21
Test 2 Sample Questions
These are sample questions similar to what you might expect for Test 2. but in the single-question quiz format used in previous semesters. [quiz07-sol.pdf] [quiz08-sol.pdf] [quiz09-sol.pdf] [quiz10-sol.pdf]
2016-10-21
Test 2 Review Sheet
2016-10-25
Test 2 preview. Fibonacci heaps: Basic structure, insert.
2016-10-27
Test 2
Covers Lectures 9-19. Average score: 114 (Q1:21, Q2:21, Q3:22, Q4:14, Q5:17, Q6:20) [test2-sol.pdf]
2016-11-01
Fibonacci heaps: ExtractMin including Consolidate, DecreaseKey including cascading cuts.
2016-11-03
Fibonacci heaps: Delete, analysis for maximum degree. Disjoint sets.
2016-11-08
Election day
(no class)
2016-11-08
Homework 12
2016-11-10
Disjoint set forests. Elementary graph algorithms.
2016-11-10
Homework 13
(no votes recorded) [hw13.pdf]
2016-11-15
Minimum spanning trees.
2016-11-17
Shortest paths on graphs.
2016-11-18
Homework 14
2016-11-22
NP-Completeness: Decision problems. Deciding a language. Verifying a language. P and NP.
2016-11-24
Thanksgiving recess
2016-11-28
Homework 15
2016-11-29
NP-Completeness: Definitions of NP-hard and NP-complete. Reductions.
2016-11-29
Homework 16
2016-12-01
Wrap up. Preview final exam. Course evaluations.
2016-12-01
Final Exam Review Sheet
2016-12-01
Final Exam Sample Questions
These are sample questions similar to what you might expect in the final exam but in the single-question quiz format used in previous semesters. The sample questions from the first two exams are also relevant. [quiz11-sol.pdf] [quiz12-sol.pdf] [quiz12.5-sol.pdf] [quiz13-sol.pdf]
2016-12-05
Office Hour for Final Exam Questions
9am until 11am
2016-12-06
Final exam
12:30pm. Covers Lectures 1-28, with emphasis on Lectures 21-28. Average score: 178/240 (Q1:21, Q2:18, Q3:22, Q4:14, Q5:17, Q6:20 Q7:14 Q8:19 Q9:16 Q10:14)