Naveed Anwar Bhatti Assistant Professor

Algorithms (CS-310)

Lecture slides and downloadable notes. Topics below are corrected to match the linked PDFs.

Lecture Collection

Each lecture highlights a core theme with a direct download to the accompanying PDF.

Lecture Topic Download
Lecture 1 — Algorithmic Thinking & Course Foundations
  • Course logistics and problem-solving mindset.
  • Models of computation; RAM cost measures.
  • Warm-up analysis of simple iterative algorithms.
 Download PDF
Lecture 2 — Stable Matching I (Gale–Shapley)
  • Stable marriage problem; preferences and stability.
  • Gale–Shapley algorithm and termination.
  • Optimality and absence of blocking pairs.
 Download PDF
Lecture 3 — Stable Matching II (Proofs & Properties)
  • Correctness proofs and invariants.
  • Rural hospitals theorem; strategic issues.
  • Extensions and variations.
 Download PDF
Lecture 4 — Asymptotic Analysis
  • Big-O, Big-Ω, Big-Θ definitions and usage.
  • Growth rates: poly vs. exp vs. log.
  • Limits/dominant terms for runtime classification.
 Download PDF
Lecture 5 — Graphs I: Representations & Basics
  • Adjacency lists vs. matrices; directed/undirected.
  • Degrees, paths, cycles, trees.
  • Cost models for graph algorithms.
 Download PDF
Lecture 6 — Graphs II: BFS & Intro to DFS
  • BFS trees, distances, and layers.
  • DFS basics, recursion/timestamps.
  • Running-time analysis on list/matrix reps.
 Download PDF
Lecture 7 — Graphs III: BFS Applications & Bipartiteness
  • Testing bipartiteness with BFS.
  • Shortest paths in unweighted graphs.
  • Connected components and structure.
 Download PDF
Lecture 8 — Graphs IV: Depth-First Search (DFS) & Applications
  • Parenthesis theorem; edge classification.
  • DFS trees/forests; recursion insights.
  • Typical DFS applications and analyses.
 Download PDF
Lecture 9 — Graphs V: Strongly Connected Components
  • Kosaraju/Tarjan approaches and intuition.
  • Reverse graph, finishing times, condensation DAG.
  • Linear-time implementations.
 Download PDF
Lecture 10 — Graphs VI: Topological Ordering & DAG Algorithms
  • Topological sort via DFS finishing times.
  • Linear-time DAG processing patterns.
  • Applications to scheduling and DP on DAGs.
 Download PDF
Lecture 11 — Divide & Conquer: Counting Inversions
  • Merge-sort-based inversion counting.
  • Correctness and O(n log n) analysis.
  • Related divide-and-conquer patterns.
 Download PDF
Lecture 12 — Recurrences & Lower Bounds (Master Theorem I)
  • Substitution and recursion-tree methods.
  • Master Theorem cases and examples.
  • Decision-tree lower bound for sorting.
 Download PDF
Lecture 13 — Master Theorem II (Proof & Applications)
  • Proof ideas and boundary cases.
  • Applying MT to common recurrences.
  • Pitfalls and non-MT recurrences.
 Download PDF
Lecture 14 — Greedy Algorithms (Interval Scheduling, etc.)
  • Greedy-choice property & exchange arguments.
  • Interval scheduling and variants.
  • Proof patterns and counter-examples.
 Download PDF
Lecture 15 — Single-Source Shortest Paths (Dijkstra)
  • Relaxation framework and invariants.
  • Priority-queue implementation details.
  • Limits: non-negative weights only.
 Download PDF
Lecture 16 — Minimum Spanning Trees (Kruskal, Union–Find, Prim)
  • Cut property; safe edges.
  • Kruskal with union-by-rank & path compression.
  • Prim’s algorithm overview.
 Download PDF
Lecture 17 — Dynamic Programming I (Fundamentals)
  • Optimal substructure; overlapping subproblems.
  • Memoization vs. tabulation; Fibonacci examples.
  • State design and transitions.
 Download PDF
Lecture 18 — Dynamic Programming II (Weighted Interval Scheduling)
  • Recurrence design and correctness.
  • Binary-search precomputation (p(j)).
  • O(n log n) implementation details.
 Download PDF
Lecture 19 — TBD — confirm slide deck topic
  • This entry reflects the current PDF, whose topic wasn’t clear from the opening slide.
  • Replace with the precise topic once verified.
 Download PDF
Lecture 20 — TBD — confirm slide deck topic
  • This entry reflects the current PDF, whose topic wasn’t clear from the opening slide.
  • Replace with the precise topic once verified.
 Download PDF
Lecture 21 — Network Flows (Max-Flow / Min-Cut)
  • Flow conservation and residual networks.
  • Ford–Fulkerson / Edmonds–Karp.
  • Max-flow min-cut theorem; basic applications.
 Download PDF
Lecture 22 — NP-Completeness (Reductions & Classics)
  • P, NP, verifiers; reductions technique.
  • From SAT to CLIQUE/IS/VC, etc.
  • Implications for practice and heuristics.
 Download PDF
Lecture 23 — Approximation Algorithms (Ratios & Techniques)
  • Approximation ratios and guarantees.
  • Greedy/rounding examples (e.g., vertex cover).
  • When to approximate and why.
 Download PDF
Lecture 24 — Parameterized & Exact Exponential Algorithms
  • Fixed-parameter tractability, kernels, branching.
  • Measure-and-conquer refinements.
  • Case studies: FPT for vertex cover, etc.
 Download PDF
Lecture 25 — Course Synthesis & Exam Preparation
  • Design paradigms recap and common pitfalls.
  • Proof strategies and problem-solving checklists.
  • Practice exam pointers and further study.
 Download PDF