\html{
\head{
\title{CSCE 750 - Analysis of Algorithms - Fall 2025
}


\body{

\h2[align="center"]{
CSCE 750 - Analysis of Algorithms - Fall 2025
}

\p{
\h3{Disclaimer}
This is the best information available as of today, \b{\today} at \b{\now}.
Changes will appear in this web page as the course progresses.

\h2{\a[HREF="Syllabus.html"]{The Course Syllabus}}
Contains general course information and class policies.

\h3{Announcements}

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

(August 18, 2025) Hand-written notes from the 8/21/2024 class are
\a[HREF="lectures/2024-08-21.pdf"]{HERE}.

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

(September 8, 2022) Next week's quiz will be taken online by both
sections.  It will be at the usual time except for a small handful of
people who know who they are.  More details to follow.

(September 8, 2022) Recordings of all the lectures through next week's
are now available on Blackboard, but not all in the same place.  There
are three places to find them:
\ul{
\li For today's lecture, login to Blackboard, go to Courses, then your
section of CSCE 750, then click Blackboard Collaborate Ultra in the
left pane.  Then in the Sessions bar near the top, click on the menu
icon on the left (three horizontal bars), then select Recordings from
the pull-down menu.  (Any future recordings done virtually as we did
today will be there.)
\li For last Tuesday's lecture (on 9/6) as well as next week's
lectures, go to your section of the course on Blackboard, and click on
Collaborate Recording in the left pane (right below Blackboard
Collaborate Ultra).  It will be clear from that point on.
\li For recordings of all the normal in-person lectures, past and
future, go to your section of the course and click on Lectures in the
left pane.
}
Links to my hand-written notes for the virtual lectures are in the
table below, arranged by the date of the lecture.  Note that the 9/13
lecture is split in two.

(August 22, 2022) Homeworks\ 0 and 1 have been updated for Fall 2022
and reflect the 4th edition of the textbook.  Most of these are also
in the 3rd edition but numbered differently.  Homework\ 1 is due
August\ 30.

(August 9, 2022) THE TIME AND PLACE FOR LECTURES HAS CHANGED.  See the
syllabus (link above) for information.

(August 7, 2022)  I will be gone the week of September 12.  Lectures
for that week will most likely be pretaped.  That week's quiz may be
rescheduled.  I will be more definitive in a later announcement.

(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.
}

\h3{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.
\comment{
I will likely 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.
}
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.

\tabular[BORDER="1" CELLPADDING="1" CELLSPACING="3" WIDTH=1200]{
|| \b{Date}
| \b{What it is}
| \b{Description}
| \b{Fall 2023}
| \b{Fall 2024}
| \b{Fall 2025}
||
| Homework\ 0
| (not graded) \a[HREF="hw/hw0.pdf"]{\[hw0.pdf\]}
|| 2025-08-20
| Lecture 01
| Introduction to the course
\a[HREF="OKane-Fall-2020/notes-intro.pdf"]{\[notes-intro.pdf\]}
| \a[HREF="lectures/2023-08-24.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-08-21.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20250820.pdf"]{\[Hand-written notes\]}
\comment{|| | First day survey |}
|| 2025-08-25
| Lecture 02
| Models of computation; asymptotic notations
\a[HREF="OKane-Fall-2020/notes-asymptotics.pdf"]{\[notes-asymptotics.pdf\]}
| \a[HREF="lectures/2023-08-29.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-08-26.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20250825.pdf"]{\[Hand-written notes\]}
|| 2025-08-27
| Lecture 03
| Summations
\a[HREF="OKane-Fall-2020/notes-summations.pdf"]{\[notes-summations.pdf\]}
| \a[HREF="lectures/2023-08-31.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-08-28.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20250827.pdf"]{\[Hand-written notes\]}
|| 2025-09-03
| \i{Homework\ 1}\ due\ 
| \a[HREF="hw/hw1.pdf"]{\[hw1.pdf\]}
|| 2025-09-03
| Lecture 04
| Solving recurrences; substitution method; proving a stronger bound
\a[HREF="OKane-Fall-2020/notes-recurrences.pdf"]{\[notes-recurrences.pdf\]}
| \a[HREF="lectures/2023-09-05.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-09-04.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20250903.pdf"]{\[Hand-written notes\]}
|| 2025-09-08
| \b{Quiz 1}
| TBD
|| 2025-09-08
| Lecture 05
| More on recurrences; recursion tree method
| \a[HREF="lectures/2023-09-07.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-09-09.pdf"]{\[Hand-written notes\]}
| (class canceled)
|| 2025-09-10
| Lecture 06
| More on recurrences; recursion trees; Master theorem
\a[HREF="notes/2022-09-06.pdf"]{\[Hand-written notes (Fall 2022)\]}
| \a[HREF="lectures/2023-09-12.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-09-11.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20250910.pdf"]{\[Hand-written notes\]}
|| 2025-09-15
| Lecture 07
| Priority queues and heaps
\a[HREF="OKane-Fall-2020/notes-heaps.pdf"]{\[notes-heaps.pdf\]}
\a[HREF="notes/2022-09-08.pdf"]{\[Hand-written notes (Fall 2022)\]}
| \a[HREF="lectures/2023-09-14.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-09-16.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20250915.pdf"]{\[Hand-written notes\]}
|| 2025-09-17
| \i{Homework 2}\ due
| \a[HREF="hw/hw2.pdf"]{\[hw2.pdf\]}
|| 2025-09-17
| Lecture 08
| Randomized algorithms; Quicksort
\a[HREF="OKane-Fall-2020/notes-randomized.pdf"]{\[notes-randomized.pdf\]}
\a[HREF="notes/2022-09-13a.pdf"]{\[Hand-written notes (lect. 1, Fall 2022)\]}
\a[HREF="notes/2022-09-13b.pdf"]{\[Hand-written notes (lect. 2, Fall 2022)\]}
| \a[HREF="lectures/2023-09-19.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-09-18.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20250917.pdf"]{\[Hand-written notes\]}
|| 2025-09-22
| \b{Quiz 2}
| TBD
|| 2025-09-22
| Lecture 09
| More on randomized
algorithms \a[HREF="notes/2022-09-15.pdf"]{\[Hand-written notes
  (Fall 2022)\]}
| \a[HREF="lectures/2023-09-21.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-09-23.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20250922.pdf"]{\[Hand-written notes\]}
|| 2025-09-24
| Lecture 10
| Order statistics; randomized QuickSelect; deterministic selection in
linear time
\a[HREF="OKane-Fall-2020/notes-selection.pdf"]{\[notes-selection.pdf\]}
| \a[HREF="lectures/2023-09-26.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-09-25.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20250924.pdf"]{\[Hand-written notes\]}
|| 2025-09-29
| Lecture 11
| Lower bounds; hash tables
\a[HREF="OKane-Fall-2020/notes-lowerbounds.pdf"]{\[notes-lowerbounds.pdf\]}
\a[HREF="OKane-Fall-2020/notes-hash.pdf"]{\[notes-hash.pdf\]}
| \a[HREF="lectures/2023-09-28.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-09-30.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20250929.pdf"]{\[Hand-written notes\]}
|| 2025-10-01
| \i{Homework 3}\ due
| \a[HREF="hw/hw3.pdf"]{\[hw3.pdf\]}
|| 2025-10-01
| Lecture 12
| More on hash tables; binary search trees
\a[HREF="OKane-Fall-2020/notes-bst.pdf"]{\[notes-bst.pdf\]}
| \a[HREF="lectures/2023-10-03.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-10-02.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20251001.pdf"]{\[Hand-written notes\]}
|| 2025-10-06
| \b{Quiz 3}
| TBD
|| 2025-10-06
| Lecture 13
| More on binary search trees, including treaps
| \a[HREF="lectures/2023-10-05.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-10-07.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20251006.pdf"]{\[Hand-written notes\]}
|| 2025-10-08
| Lecture 14
| Treap analysis; augmenting data structures
\a[HREF="OKane-Fall-2020/notes-augmenting.pdf"]{\[notes-augmenting.pdf\]}
| \a[HREF="lectures/2023-10-10.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-10-09.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20251008.pdf"]{\[Hand-written notes\]}
|| 2025-10-13
| Lecture 15
| Dynamic programming
\a[HREF="OKane-Fall-2020/notes-dp.pdf"]{\[notes-dp.pdf\]}
| \a[HREF="lectures/2023-10-12.pdf"]{\[Hand-written notes\]}
| \[No hand-written notes for Fall 2024\]
| \a[HREF="lectures/20251013.pdf"]{\[Hand-written notes\]}
|| 2025-10-15
| \i{Homework 4}\ due
| \a[HREF="hw/hw4.pdf"]{\[hw4.pdf\]}
|| 2025-10-15
| Lecture 16
| Amortized analysis
\a[HREF="OKane-Fall-2020/notes-amortized.pdf"]{\[notes-amortized.pdf\]}
| \a[HREF="lectures/2023-10-17.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-10-16.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20251015.pdf"]{\[Hand-written notes\]}
|| 2025-10-20
| \b{Quiz 4}
| TBD
|| 2025-10-20
| Lecture 17
| Mergeable heaps, binomial heaps: introduction and basic structure
\a[HREF="notes/notes-mergeable-heaps.pdf"]{\[notes-mergeable-heaps.pdf\]}
| \a[HREF="lectures/2023-10-24.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-10-21.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20251020.pdf"]{\[Hand-written notes\]}
|| 2025-10-22
| Lecture 18
| Binomial heaps operations
| \a[HREF="lectures/2023-10-26.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-10-23.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20251022.pdf"]{\[Hand-written notes\]}
|| 2025-10-27
| Lecture 19
| Binomial heaps: merge operation; Fibonacci heaps: basic structure
and operations
\a[HREF="OKane-Fall-2020/notes-fibheap.pdf"]{\[notes-fibheap.pdf\]}
| \a[HREF="lectures/2023-10-31.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-10-28.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20251027.pdf"]{\[Hand-written notes\]}
|| 2025-10-29
| \i{Homework 5}\ due | \a[HREF="hw/hw5.pdf"]{\[hw5.pdf\]}
|| 2025-10-29
| Lecture 20
| Fibonacci heaps: analysis
| \a[HREF="lectures/2023-11-02.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-10-30.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20251029.pdf"]{\[Hand-written notes\]}
|| 2025-11-03
| \b{Quiz 5}
| TBD
|| 2025-11-03
| Lecture 21
| Disjoint sets
\a[HREF="OKane-Fall-2020/notes-disjoint-sets.pdf"]{\[notes-disjoint-sets.pdf\]}
| \a[HREF="lectures/2023-11-07.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-11-04.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20251103.pdf"]{\[Hand-written notes\]}
|| 2025-11-05
| Lecture 22
| More on disjoint sets; elementary graph algorithms
\a[HREF="OKane-Fall-2020/notes-graphs.pdf"]{\[notes-graphs.pdf\]}
| \a[HREF="lectures/2023-11-09.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-11-06.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20251105.pdf"]{\[Hand-written notes\]}
|| 2025-11-10
| \i{Homework 6}\ due
| \a[HREF="hw/hw6.pdf"]{\[hw6.pdf\]}
|| 2025-11-10
| Lecture 23
| Minimum spanning trees
\a[HREF="OKane-Fall-2020/notes-mst.pdf"]{\[notes-mst.pdf\]}
| \a[HREF="lectures/2023-11-14.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-11-11.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20251110.pdf"]{\[Hand-written notes\]}
|| 2025-11-12
| \b{Quiz 6}
| TBD
|| 2025-11-12
| Lecture 24
| Shortest paths on graphs
\a[HREF="OKane-Fall-2020/notes-dijkstra.pdf"]{\[notes-diskstra.pdf\]}
| \a[HREF="lectures/2023-11-16.pdf"]{\[Hand-written notes \]}
| \a[HREF="lectures/2024-11-13.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20251112.pdf"]{\[Hand-written notes\]}
|| 2025-11-17
| Lecture 25
| NP-completeness \a[HREF="OKane-Fall-2020/notes-npcomplete.pdf"]{\[notes-npcomplete.pdf\]}
| \a[HREF="lectures/2023-11-21.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-11-18.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20251117.pdf"]{\[Hand-written notes\]}
|| 2025-11-19
| \i{Homework 7}\ due
| \a[HREF="hw/hw7.pdf"]{\[hw7.pdf\]}
|| 2025-11-19
| Lecture 26
| More on NP-completeness
| \a[HREF="lectures/2023-11-28.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-11-20.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20251119.pdf"]{\[Hand-written notes\]}
|| 2025-12-01
| \b{Quiz 7}
| TBD
|| 2025-12-01
| Lecture 27
| More on NP-completeness, polynomial reductions
| \a[HREF="lectures/2023-11-30.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-12-02.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20251201.pdf"]{\[Hand-written notes\]}
|| 2025-12-03
| Lecture 28
| More on NP-completeness, polynomial
reductions; review
| \a[HREF="lectures/2023-12-05.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/2024-12-04.pdf"]{\[Hand-written notes\]}
| \a[HREF="lectures/20251203.pdf"]{\[Hand-written notes\]}
||
| Homework 8
| (not graded) \a[HREF="hw/hw8.pdf"]{\[hw8.pdf\]}
\comment{|| 2023-12-07 | Review |}
\a[HREF="OKane-Fall-2020/review.pdf"]{\[review.pdf\]}
| \a[HREF="lectures/2023-12-07.pdf"]{\[Hand-written notes\]}
|| 2025-12-12
| \b{Final Exam}
| 12:30pm - 3:00pm
}

\h3{Some Miscellaneous Resources}
\ul{
\li \a[HREF="course-notes.pdf"]{My old lecture notes}
\li \a[HREF="notes/index.html"]{Hand-written notes made while lecturing
a previous class}
\li \a[HREF="all-quizzes-fa09.pdf"]{Fall 2009 quizzes} with
solutions
\li \a[HREF="final-answers-fa05.pdf"]{Answer key} to the Fall 2005
final exam.
}

\h3{
\a[name="computerusage"]{} Proper Use of Computing Resources
}
Students are expected to be aware of the
\a[href="http://www.csd.sc.edu/Policies.shtml"]{university policy}
on use of computing resources, including the
\a[href="http://www.csd.sc.edu/Policies/Responsible.shtml"]{Student Guidelines for Responsible Computing},
as well as the
\a[href="http://www.engr.sc.edu/its/ComputerAbusePolicy.asp"]{college}
and
\a[href="http://www.cse.sc.edu/coeitAbusePolicy.html"]{departmental}
policies on proper use of computing resources.
Every instance of a suspected violation will be reported.
}

\hr

This page was last modified \today at \now.

}}}