Lectures

Lecture 01: Computational Problems

• Defining computational problems

• Classifying computational problems

• Internal representation of data

• From problem to algorithm to implementation

Lecture 02: Algorithm efficiency analysis

• Correctness of an algorithm

• Algorithm analysis. Worst case, best case, average

• Asymptotic notations

• Turing problem reductions

Lecture 03: Nondeterministic and Probabilistic Algorithms

• Nondeterminnistic algorithms

• Choice, success, failure

• Probabilistic algorithms

• Las Vegas algorithms

• Monte Carlo algorithms

• Appendix: Mathematical background, terminology and notations

Lecture 04: Probabilistic Analysis

• Expected time for deterministic algorithms

• Case studies:false

  • Hiring problem

  • Streaks

  • First occurrence in a list

  • Nuts and Bolts

• Supplementary readings:

  • Phillip G Bradford. Matching nuts and bolts optimally.

  • UIUC CS 473:Algorithms (Spring 2017). Sorting nuts and bolts