## CSCE 750 - Analysis of Algorithms - Fall 2021

### Disclaimer

This is the best information available as of today, Thursday December 2, 2021 at 06:40:15 EST. Changes will appear in this web page as the course progresses.

### The Course Syllabus

Contains general course information and class policies.

### Schedule of Lectures, Homework, and Quizzes

These are subject to change as the course progresses. The links to the notes are from Prof. O'Kane's CSCE 750 class last Fall. I will be making adjustments to these as the course moves forward. The easiest way to tell if I've updated a document is when it no longer says "Fall 2020" but "Fall 2021" instead.

 Homework 0 (not graded) [hw00.pdf] 2021-08-19 Lecture 01 Introduction to the course [notes-intro.pdf] First day survey 2021-08-24 Lecture 02 Models of computation; asymptotic notations [notes-asymptotics.pdf] 2021-08-26 Lecture 03 Summations [notes-summations.pdf] 2021-08-31 Homework 1 [hw1.pdf] [hw1-ans.pdf] 2021-08-31 Lecture 04 Solving recurrences; substitution method [notes-recurrences.pdf] 2021-09-02 Quiz 1 TBD 2021-09-02 Lecture 05 More on recurrences; substitution method: proving a stronger bound 2021-09-07 Lecture 06 More on recurrences; recursion trees; Master theorem 2021-09-09 Lecture 07 Priority queues and heaps [notes-heaps.pdf] 2021-09-14 Homework 2 [hw2.pdf] 2021-09-14 Lecture 08 Randomized algorithms; Quicksort [notes-randomized.pdf] 2021-09-16 Quiz 2 TBD 2021-09-16 Lecture 09 More on randomized algorithms 2021-09-21 Lecture 10 Order statistics; randomized Quickselect; deterministic selection in linear time [notes-selection.pdf] 2021-09-23 Lecture 11 Lower bounds; hash tables [notes-lowerbounds.pdf] [notes-hash.pdf] 2021-09-28 Homework 3 [hw3.pdf] 2021-09-28 Lecture 12 More on hash tables; binary search trees [notes-bst.pdf] 2021-09-30 Quiz 3 TBD 2021-09-30 Lecture 13 More on binary search trees, including treaps 2021-10-05 Lecture 14 Treap analysis; augmenting data structures [notes-augmenting.pdf] 2021-10-12 Lecture 15 Dynamic programming [notes-dp.pdf] 2021-10-14 Homework 4 [hw4.pdf] 2021-10-14 Lecture 16 Amortized analysis [notes-amortized.pdf] 2021-10-19 Quiz 4 TBD 2021-10-19 Lecture 17 Fibonacci heaps: basic structure [notes-fibheap.pdf] 2021-10-21 Lecture 18 Fibonacci heaps: operations 2021-10-26 Lecture 19 Fibonacci heaps: analysis 2021-10-28 Homework 5 [hw5.pdf] 2021-10-28 Lecture 20 TBD 2021-11-02 Quiz 5 TBD 2021-11-02 Lecture 21 Disjoint sets [notes-disjoint-sets.pdf] 2021-11-04 Lecture 22 More on disjoint sets; elementary graph algorithms [notes-graphs.pdf] 2021-11-09 Homework 6 [hw6.pdf] 2021-11-09 Lecture 23 Minimum spanning trees [notes-mst.pdf] 2021-11-11 Quiz 6 TBD 2021-11-11 Lecture 24 Shortest paths on graphs [notes-diskstra.pdf] 2021-11-16 Lecture 25 NP-completeness [notes-npcomplete.pdf] 2021-11-18 Homework 7 [hw7.pdf] 2021-11-18 Lecture 26 More on NP-completeness 2021-11-23 Quiz 7 TBD 2021-11-23 Lecture 27 TBD, possibly pretaped 2021-11-30 Lecture 28 TBD, possibly pretaped Homework 8 (not graded) [hw8.pdf] 2021-12-02 Review [review.pdf] 2021-12-09 Final Exam 12:30pm - 3:00pm

### Announcements

Announcements (with dates) will be posted here in reverse chronological order.

(November 30, 2021) To find the recordings of make-up lectures, go to the course in Blackboard, then click Blackboard Collaborate Ultra in the left menu, then in the Sessions bar at the top, click on the menu icon (horizontal lines) on the left.

(August 17, 2021) The University requires wearing masks in all UofSC buildings and on campus transportation.

### Proper Use of Computing Resources

Students are expected to be aware of the university policy on use of computing resources, including the Student Guidelines for Responsible Computing, as well as the college and departmental policies on proper use of computing resources. Every instance of a suspected violation will be reported.