Lectures

Lecture 02: The Analysis of Algorithm Efficiency

• Correctness of an algorithm

• Loop/Recursion invariants

• Running time

• Worst-case, average case, best case

• Asymptotic notations

• Case studies of  InsertionSort and MergeSort

Lecture 03: Randomized Algorithms

• Nondeterministic Algorithms

• Monte Carlo Algorithms

• Las Vegas Algorithms

• Case studies of Primality Testing and QuickSort

Supplementary bibliography:

• An introduction to randomized algorithms

Lecture 04: Probabilistic Analysis

• Probabilistic Analysis of Deterministic Algorithms

• First Occurrence in a list

• Nuts and Bolts

• Problem Reductions

Supplementary bibliography:

• Matching nuts and bolts optimally

Lectures 5, 6: NP-complete problems

• Decision Problems and Optimisation Problems

• Reductions, Karp Reductions

• PTIME, NPTIME

• NP-complete problems

• English-language lecture notes: https://jeffe.cs.illinois.edu/teaching/algorithms/book/12-nphard.pdf

Weeks 9, 10: String Matching

Lecture 11: Backtracking and Branch & Bound

• Algorithmic Paradigms

• Backtracking

• Optimization Problems

• Branch & Bound

Lecture 12: Dynamic Programming

• General Description

• One-dimensional problems

  • Fibonacci

  • Longest Increasing Subsequence

  • Rod Cutting

• General Approaches

• Two-dimensional problem

  • Discrete Knapsack

Lecture 13: Advanced Dynamic Programming

• Other Classic DP Problems

  • Longest Common Subsequence

  • Edit Distance

• DP on trees

  • Maximum Independent Set

• Partial Sums

Lecture 14: Greedy

• Optimization Problems

• Greedy Ingredients

• Problem Properties

• Problems

  • Continous Knapsack

  • Interval Scheduling

  • Minimum Spanning Tree

  • Median Maximization