CSCE 750 - Analysis of Algorithms - Fall 2024

Disclaimer

This is the best information available as of today, Tuesday November 5, 2024 at 13:55:21 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.

(September 6, 2024) The TA's contact information and office hours for Fall 2024:

This information is also listed on the syllabus.

(August 26, 2024) Hand-written notes from the 8/21 class are HERE.

(August 26, 2024) Today's and all future lectures will be in Swearingen 2A05.

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, 2023 and 2024. I intend to include ALL hand-written notes for this semester here, albeit with some unavoidable delay.

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

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 Tuesday November 5, 2024 at 13:55:21 EST.