Meetings

Click on the theme item for the meeting plan for that theme.
Click on the meeting item for references, exercises, and additional reading related to it.

Theme 1 : The Algorithmists Hat - 12 meetings

Meeting 01 : Mon, Jul 28, 11:00 am-11:50 am

To be compensated.

Meeting 02 : Tue, Jul 29, 10:00 am-10:50 am

Review of asymptotic analysis.

Meeting 03 : Wed, Jul 30, 09:00 am-09:50 am

Review of asymptotic analysis.

Meeting 04 : Thu, Jul 31, 12:00 pm-12:50 pm

To be compensated.

Meeting 05 : Tue, Aug 05, 10:00 am-10:50 am

Introduction and Administrative announcements about the course. Important algorithms around. Designers thoughts. What is expected from an algorithm designer. Need of mathematical rigor and proofs.

Meeting 06 : Wed, Aug 06, 09:00 am-09:50 am

Algorithm designers hat. Four stage thought process after any algorithm design. Termination, Correctness, Analysis, Optimality. Optimality of analysis vs optimality of the algorithm itself. Idea of lower bounds for a problem.

Meeting 07 : Thu, Aug 07, 12:00 pm-12:50 pm

Techniques for proof of correncess for iterative algorithms. Loop invariants. Analysis of running time by direct counting. Example of insertion sort.

Meeting 08 : Mon, Aug 11, 11:00 am-11:50 am

Multiplying two n-bit numbers. Trivial Methods. A O(2^n) algorithm. Improvement to O(n^2) algorithm. ecursive methods. Termination argument by base case. Correctness argument by induction. Runtime analysis by recurrences. Question of lower bounds. Lower bound of O(n). Karastuba's multiplication surprise. The Karstuba recurrence.

Meeting 09 : Tue, Aug 12, 10:00 am-10:50 am

Solving recurrences by substitution method. Proofs by induction. Recursion tree method. Developing into masters theorem.

Meeting 10 : Wed, Aug 13, 09:00 am-09:50 am

Example applications for masters theorem. Proof of master theorem.

Meeting 11 : Wed, Aug 13, 06:00 pm-06:50 pm

Completing the proof of masters theorem. Introdcution to adversary arguments. Finding the largest element in an array of n elements require n-1 comparisons.

Meeting 12 : Thu, Aug 14, 12:00 pm-12:50 pm

Tutorial - I

Theme 2 : Divide & Conquer Technique - 7 meetings

Meeting 13 : Mon, Aug 18, 11:00 am-11:50 am

Merge Sort Algorithm. Correctness. Analysis. Optimality. Adversary Arguments for sorting algorithms.

Meeting 14 : Tue, Aug 19, 10:00 am-10:50 am

Quicksort Algorithm. Correctness, and analysis. Role of the pivot. Worst case pivot. Best case pivot. Average case analysis.

Meeting 15 : Wed, Aug 20, 09:00 am-09:50 am

Randomized Quicksort. Quick recap of probability distributions, random variables and expectation. How to model our problem using this. Decomposing into "simpler" random variables.

Meeting 16 : Mon, Aug 25, 11:00 am-11:50 am

Indicator random variables and their expectation. Linearity of expectation. Computing the analysis of the randomized quicksort. Overview and features of the method.

Meeting 17 : Tue, Aug 26, 10:00 am-10:50 am

The task of finding the median. Finding the k-th smallest element. Quick-sort-like method. Median of medians to get an "approximate median" to get a balanced split. The analysis and recurrence relation. Linear time algorithm for k-th smallest element.

Meeting 18 : Thu, Aug 28, 12:00 pm-12:50 pm

Counting the number of inversions. The divide and conquer by strengthening the induction/recursion.

(Upcoming) Meeting 19 : Mon, Sep 01, 11:00 am-11:50 am

To Be Announced

Theme 3 : Greedy Technique
- 11 meetings
(Upcoming) Meeting 20 : Tue, Sep 02, 10:00 am-10:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 21 : Wed, Sep 03, 09:00 am-09:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 22 : Thu, Sep 04, 12:00 pm-12:50 pm
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 23 : Mon, Sep 08, 11:00 am-11:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 24 : Tue, Sep 09, 10:00 am-10:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 25 : Wed, Sep 10, 09:00 am-09:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 26 : Thu, Sep 11, 12:00 pm-12:50 pm
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 27 : Mon, Sep 15, 11:00 am-11:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 28 : Tue, Sep 16, 10:00 am-10:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 29 : Wed, Sep 17, 09:00 am-09:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 30 : Thu, Sep 18, 12:00 pm-12:50 pm
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
Theme 4 : Dynamic Programming Techniques
- 8 meetings
(Upcoming) Meeting 31 : Mon, Sep 22, 11:00 am-11:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 32 : Tue, Sep 23, 10:00 am-10:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 33 : Wed, Sep 24, 09:00 am-09:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 34 : Mon, Sep 29, 11:00 am-11:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 35 : Tue, Sep 30, 10:00 am-10:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 36 : Wed, Oct 01, 09:00 am-09:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 37 : Mon, Oct 06, 11:00 am-11:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 38 : Tue, Oct 07, 10:00 am-10:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
Theme 5 : Iterative Improvement Technique - 15 meetings
(Upcoming) Meeting 39 : Wed, Oct 08, 09:00 am-09:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 40 : Thu, Oct 09, 12:00 pm-12:50 pm
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 41 : Mon, Oct 13, 11:00 am-11:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 42 : Tue, Oct 14, 10:00 am-10:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 43 : Wed, Oct 15, 09:00 am-09:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 44 : Thu, Oct 16, 12:00 pm-12:50 pm
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 45 : Tue, Oct 21, 10:00 am-10:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 46 : Wed, Oct 22, 09:00 am-09:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 47 : Thu, Oct 23, 12:00 pm-12:50 pm
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 48 : Mon, Oct 27, 11:00 am-11:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 49 : Tue, Oct 28, 10:00 am-10:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 50 : Wed, Oct 29, 09:00 am-09:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 51 : Thu, Oct 30, 12:00 pm-12:50 pm
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 52 : Mon, Nov 03, 11:00 am-11:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 53 : Tue, Nov 04, 10:00 am-10:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
Theme 6 : Evaluation Meetings - 4 meetings
Meeting 54 : Thu, Aug 21, 12:00 pm-12:50 pm
Short Exam 1
References
Exercises
Reading
Short Exam 1
References: None
(Upcoming) Meeting 55 : Thu, Sep 25, 12:00 pm-12:50 pm
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 56 : Thu, Oct 02, 12:00 pm-12:50 pm
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 57 : Mon, Oct 20, 11:00 am-11:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
Theme 7 : Intractability - 6 meetings
(Upcoming) Meeting 58 : Wed, Nov 05, 09:00 am-09:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 59 : Thu, Nov 06, 12:00 pm-12:50 pm
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 60 : Mon, Nov 10, 11:00 am-11:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 61 : Tue, Nov 11, 10:00 am-10:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 62 : Wed, Nov 12, 09:00 am-09:50 am
To Be Announced
References
Exercises
Reading
To Be Announced
References: None
(Upcoming) Meeting 63 : Thu, Nov 13, 12:00 pm-12:50 pm
To Be Announced
References
Exercises
Reading
To Be Announced
References: None

CS5800 - Advanced Data Structures and Algorithms

Today : Sat, Aug 30, 2025

Announcements

Meetings

References	<a href="https://www.cs.cmu.edu/~15451-f21/lectures/lec22.pdf">Karastuba Multiplcation</a>
Exercises
Reading

References	<a href="https://goldman.cse.wustl.edu/crc2007/handouts/adv-lb.pdf">Reference for Optimality using adversary arguments for sorting</a>.
Exercises
Reading

References	Setion 5.2 and Setion 7.4 of [CLRS]
Exercises
Reading

References	Section 1.8 in <a href="https://jeffe.cs.illinois.edu/teaching/algorithms/book/01-recursion.pdf">Jeff Erikson's Book</a>.
Exercises
Reading