Advanced Data Structures and Algorithms (ADSA) Notes

Welcome to the comprehensive repository of notes for the Advanced Data Structures and Algorithms course.

📚 Lecture Notes & Summaries

The following table provides links to highly detailed Markdown summaries for each lecture. Each summary includes mathematical derivations, technical proofs, and historical contexts.

Lecture	Title	Overview	Summary
Lec 1	Principles of Algorithm Design	Fundamental philosophy of algorithms, history of computing (von Neumann), and abstraction.	Summary
Lec 2	Asymptotic Analysis	Formal definitions of Big O, Theta, and Omega. Growth rates and complexity classes.	Summary
Lec 3	Incremental vs Decremental	Design paradigms. Features the optimal $O(n)$ solution to the Celebrity Problem.	Summary
Lec 4	Heap Fundamentals	Introduction to Binary Heaps, structural/order properties, and the log-time Delete Max.	Summary
Lec 5	Implicit Heaps & Build-Heap	Array representation of heaps and the comparison between $O(n \log n)$ and $O(n)$ build.	Summary
Lec 6	Binary Search & Rank	Formalization of Binary Search and introduction to Order Statistics (Rank).	Summary
Lec 7	Linear-Time Selection	The "Median of Medians" algorithm for $O(n)$ Kth-element selection.	Summary
Lec 8	Number Theory: GCD & EEA	Euclidean Algorithm complexity and introduction to Bezout's Identity.	Summary
Lec 9	Extended Euclidean (EEA)	Algorithmic derivation of EEA, modular inverses, and Merge Sort analysis.	Summary
Lec 10	Karatsuba Multiplication	Recursive multiplication algorithm reducing complexity from $O(n^2)$ to $O(n^{1.59})$.	Summary
Lec 11	Master Theorem	Rigorous derivation of the Master Theorem cases using recursion trees.	Summary
Lec 12	More for Less (MSS)	Deriving a linear-time $O(n)$ algorithm for the Maximum Subarray Sum problem.	Summary
Lec 13	Dictionary ADT & BSTs	Performance of Binary Search Trees and the necessity of self-balancing Red-Black Trees.	Summary

⚠️ Note: These summaries are based on automated processing and may contain minor errors.