INTRODUCTION TO ANALYSIS OF ALGORITHMS

Class:		TTh 12:00-1:45, Kresgue 327
Office hours:   Mo 2-3, We 10-11: E2-357 
Prerequisite:   CMPS 101 and CE 16

Final: 		Mo Dec 5, 4-7pm
		The final is "closed book" !
		We will provide all technical theorems if needed
		Solutions of final


Additional office hours by Manfred 

for answering questiong re. the final: F 12-2pm



TA:		Lindsay Brown
Thanksgiving Week: OH Monday 4-6 Jack's Lounge. No section this week. 
Office Hours:	Tuesday 5:00 - 7:00  BE 314B  
Section:	Wed     5:00 - 6:00 Social Sciences 1, Rm 145
		Friday 11:00 - 12:00 Thimann Lab 101






Texts

Syllabus and Updated Policies


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 I1-3
	Hw1

2	Insertionsort (correctness and time analysis)
        Loop invariants
	Merge sort (correctness and recurrence)
        All 4 O notations

3	Recurrences (Substitution and Recursion-tree methods)
	Master Theorem and how to apply it
	Hw1 solutions
	Hw2

4	Heapsort and Quicksort
        Analysis of both including average case 
	of Quicksort and Insertionsort


5	Information theoretic lower bound for sorting
	- worst case and average case
	Counting sort, Radix sort, Bucket sort
	Hw2 solutions
	Hw3

6	Finding the minimum, minimum and maxim, largest and 2nd largest
        Simple adversary lower bound
        Randomized alg for finding ith largest
        Average and worst-case analysis

7       Linear alg for finding ith largest that is
  	linear in worst case
	Simple data structures, linked lists
        Linear alg for Game of Life
	Hw3 solutions
	Hw4

8	Hash tables - Collission resolution by chaining
 	Good hash functions
        Universal Hashing
	Hw4 solutions

9	Hash tables - Open addressing
        Review for midterm
	Sample Midterm 98 with sols
	Sample Midterm 03 with sols
	Will post solutions Sunday afternoon	
	Sample Midterm Questions

10	Midterm

11 	Midterm sols
	Midterm solutions
        Binary Search Trees
	Hw5

12	Red Black trees
 	Augmenting data structures

13    	Dynamic Programming
	-Fibonacci #'s, making change, Knap sack, height in dag
	Hw5 solutions
	Hw6
        
14    	Dynamic Programming
	-longest increasing subsequence (inluding O(nlogn) alg) 
        -Cocke-Younger-Kasami alg., all pair shortes path

15    	Dynamic Programming
	-longest common subsequence, optimal binary search trees
        Huffman Coding
	Hw6 solutions
	Hw7

16	Greedy algorithms
   	Amortized analysis
     	-aggregate analysis

17	B-trees - Delete
        Binomial heaps
	Hw7 solutions
	Hw8

18      Divide and conquer
        -muliplying numbers and Strassen's matrix multiplication

19      Fast Fourier Transform
	Sample final
	Hw8 solutions
	Hw8 solution to problem 4

20	Review
	Sample Final Questions
	Solutions for Sample final