CS 3343/3341, Outline, Topics Covered, Spring 2012

CS 3343/3341
Analysis of Algorithms
Spring 2012

Online Course
Materials

Weird Topics.

Induction.

Loop Invariant.

Exclusive-Or (xor). Xor.

Exponentiation.

Circular Queues.

Recursion. Recitation 2: Recursion.

Linked Lists. Recitation 3: Linked Lists.

Binary search.

Binary search trees.

Quicksort. Quicksort Explained.

Random Numbers and Randomization.

Medians. Recitation 5: Medians.

Strassen Matrix Multiplication.

Heapsort, Priority Queues. All heaps are max-heaps.

Discussion and algorithms, including for heapsort and for a priority queue: Heaps.
Examples using diagrams of the heap at each stage:
- Building a heap from an array in random order: Building a heap.
- Running heapsort from an array in random order: Heapsort.
- Repeatedly extracting the maximum from a heap: Extract Maximum.
- Repeatedly inserting a new element into a heap: Inserting Into a Heap.
Heapsort implementation and test: Implementation and test of heapsort.
Priority Queue implementation and test: Implementation and test of a priority queue.
Examples in Recreation 5: Heap examples.
Examples in Recreation 6: Priority Queue examples.

Recursion Trees. For analysing an algorithm and for solving recurrences. The method applied to:

Master Method. Cookbook for solving recurrences.

Graph Representations. Internal representation of a graph. Java, C.

Graph Searches.

Dijkstra's Shortest Path in a Graph. Dijkstra's Algorithm

Hashing. Hashing

NP, NP-Complete.

Turing Machines.

Revision date: 2012-04-03. (Please use ISO 8601, the International Standard.)