Lectures

Lecture 1: Introduction

• What is an algorithm

• Alk Language

• Computation of an Algorithm

• Problem Solved by an Algorithm 

Examples 

Alk Primer

Supplementary  notes: 

• A note on why a formal definition for the notion of algorithm is needed

• A note on solvability (decidability) versus  correctness, with two examples of correct algorithms

• A note with an example where the analysis of the problem domain is important 

• A note with an almost complete description of the Alk language as a computation model

The site where the Alk interpreter can be downloaded is https://github.com/alk-language/java-semantics.

Alk reference manual: https://github.com/alk-language/java-semantics/wiki/Reference-Manual

Lecture 2: Complexity of Algorithms, Algorithmic Complexity of Computational Problems

• Algorithm efficiency: cost functions

• Worst-case analysis

• The complexity of the computational problems

• The complexity of sorting

• Polynomial reduction of problems

Examples: .zip

Supplementary bibliography: 

• A note on design and understanding sorting algorithms 

• A note on computing the worst-case complexity

• Sections 1.2, 1.3 in [LC2008]

 Lecture 3:  Nondeterministic algorithms, probabilistic algorithms 

• nondeterministic algorithms

• problem solved by a nondeterministic algorithm

• nondeterministic algorithms for decision problems

• probabilistic algorithms

• Monte Carlo algorithms

• Las Vegas algorithms

Examples: .zip

Supplementary bibliography

More examples of non-deterministic algorithms

Jacobi Symbol

1. Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan. 1972. Linear time bounds for median computations. pdf

2. Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ronald L. Rivest, and Robert E. Tarjan.Time Bounds for Selection. pdf

3. CMU 15-451 (Algorithms), Fall 2011. Lecture 4. Selection (deterministic & randomized): finding the median in linear time. pdf

4. Sections 2.6.5 and 2.6.6 from the Alk Reference Manual.

Lecture 4: Probabilistic analysis of the deterministic algorithms (expected time)

• expected time for deterministic algorithms

• case studies:

  •   the first occurrence in a list 

  •   Quicksort

  •   Nuts and Bolts

  •   Treaps

Examples: .zip

Supplementary bibliography

UIUC CS 473: Fundamental Algorithms, Spring 2011 March 10, 2011. Chapter 14- Introduction to Randomized Algorithms: Quick Sort and QuickSelection

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

Raimund Seidel and Cecilia R. Aragon. Randomized search trees. Algorithmica, 16(4/5):464-497, 1996. Available at https://faculty.washington.edu/aragon/pubs/rst96.pdf

Jeff Erickson. Algorithms, Treaps and Skip Lists section.