INTRODUCTION TO ANALYSIS OF ALGORITHMS

Class:		TTh 4:00-5:45, Stevenson Acad. 175
Office hours:   Mo,We 10-11, 331 Baskin Engineering
Prerequisite:   CMPS 101 and CE 16

Final: 		Th June 12, 8-11 am
		Final w. answers


TA:		Dima Kuzmin
Office hours:	We 1-3, 352 Baskin Engineering

Sections:	Monday  3:30 	- 4:40 Natural Sciences Annex 102
		Thur   12:00 	- 1:45 Oakes 106
		Friday 11:00 	- 12:10 Baskin Engineering 372


Readers:	Eric W. Poon
		Mark Pauley


Texts

Syllabus and Updated Policies

Holyhedron

LECTURES

1:	Introduction using multiplication as an example
	- Standart alg.
	- Multiplication a la russe
	- Divide and Conquer alg. with improved time bound
    	- Correctness of a la russe multiplication
	Read Chapter 1
	- Try to prove (1.9) and (1.12) on page 22
	Hw1

2	What is a good algorithm?
	How to evaluate efficiency?
	Unit cost and log cost model
	Average and worst-case complexity
	Motivation of O notation

3	O notations 
        Proving O bounds using l'Hospital
	Average and worst-case analysis of Binary search
	Read Chapter 2 
	Hw1 solutions
	Hw2

4	Abstract Data Types
	Recursion
	Proofs of correctness
	Read Chapter 3

5	Recurrence relations
        Read Chapter 4
	Hw2 solutions
	Hw3

6	Insertion sort 
	- correctness 
	- average case and worst case lower bounds for algs 
	  that eliminate at most one inversion per comparison
	Quicksort
	- worst-case and average case lower bounds
	- relationship to building binary search trees
	- various optimizations

7	Merge Sort
	Improved Heap Sort
	Radix Sort
	Lower bound for comparison sorts
	Read Chapter 5
	Hw3 solutions
	Hw4

8	Finish sorting
	Adversary lower bounds

	Typical midterm questions

	Sample midterm
	Solutions for sample midterm
	Ignore Problem 2 b) - needs techniques not covered in class
	Some questions assume existence of linear alg. for finding median

9 	More adversary lower bounds 
	Linear algorithm for finding the median

	Questions about midterm
	Hw4 solutions

10	Midterm on Chapters 1-5
	Midterm solutions

11	Return midterm
	Amortized analysis (example: doubling arrays)
	Red Black Trees
	Read Chapter 6

	Hw5

12	Hashing
	Union-Find amortized anaysis

13	Graph traversals 
	Algs for directed and undirected graphs
	Hw5 solutions
	Hw6

14	Finding strongly connected components
	and biconnected components
	Greedy algorithms
	Read Chapter 8

15	Finish greedy algs
	Transitive closure and all pairs shortest path algorithm
	Read Chapter 9
	Hw6 solutions
	Hw7

16      Modifications of all pairs shortest path algorithm
	Dynamic Programming
	Read Chapter 10

17   	Dynamic programming

18	Various homework problems
	Strassen's Matrix Multiplication
	(Chapter 12)

	Hw8
	Hw7 solutions

19 	String matching
        Sols to Hw8

	Read Chapter 11

20	Review for final
        Hw8 solutions
	Sols to two problems of last class