CSCE 750 - Analysis of Algorithms - Fall 2023

Disclaimer

This is the best information available as of today, Wednesday December 13, 2023 at 11:26:25 EST. Changes will appear in this web page as the course progresses.

The Course Syllabus

Contains general course information and class policies.

Announcements

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

(August 30, 2023) Hand-written notes from Lecture~1

Schedule of Lectures, Homework, and Quizzes

These are subject to change as the course progresses. The typeset notes are from Prof. O'Kane's CSCE 750 class in Fall 2020. All hand-written notes are from Fall 2022 and 2023. I intend to include ALL hand-written notes for this semester here, albeit with some unavoidable delay.

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

Some Miscellaneous Resources

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.

This page was last modified Wednesday December 13, 2023 at 11:26:25 EST.