6.042J/18.062J Staff Notes
Week of Tues., Feb. 15 through Monday, Feb. 21.

----------------------------------------------------------------------

Reading: M&R Chapter 1; CLR Chapters 1, 11 (handout)

----------------------------------------------------------------------

Lecture 5 -- Tuesday, Feb. 15 -- Algorithms

15    Specifying algorithms
	Ex: Insertion sort
	Algorithmic language
	Arrays
	Loops

20    Correctness
	Termination
	Weak correctness
	Loop invariants
	Induction

20    Running time
	Worst-case/average-case analysis
	Asymptotic notation (Theta)
	Growth of functions
	Insertion sort analysis

20    Merge sort
	Merging two sorted lists
	Recursive algorithm for merge sort
	Recurrences
	Recursion tree analysis of merge sort
	Comparison of running times of merge sort and insertion sort

----------------------------------------------------------------------

Lecture 6 -- Thursday, Feb. 17 -- Elementary Data Structures

15    Stacks and FIFO queues (see CLR, Chapter 11)

10    Linked lists
	Singly and doubly linked lists
	List-Search
	List-Insert
	List-Delete
	Sentinels

15    Implementing pointers and objects
	Multiple-array representation
	Single-array representation
	Allocating and freeing objects

10    Representing rooted trees
	Binary trees
	Unbounded branching: left-child, right sibling

10    Representing graphs
	Adjacency matrix: size $\Theta(V^2)$
	Adjacency lists: size $\Theta(V+E)$

20    Tree walks
	Preorder, Inorder, Postorder
	Analysis: $\Theta(n)$ time	
	Binary search trees
	  Binary search tree property
	  Search
	  Insertion
	Analysis: $\Theta(n)$ worst case, but also $\Theta(h)$ worst case.
	
----------------------------------------------------------------------

Recitation 3 -- Friday, Feb. 18

Show linear/binary search
Set up recurrences
Solve by intuitive or ad hoc means.

Review binary search trees
Sort with binary search trees = insert + tree walk
Analysis: worst-case = $\Theta(n^2)$, but really $\Theta(nh)$

Dynamic set operations (CLR, Chap. 13)
Minimum, Maximum (get them to give algorithm)
Successor: either min in right subtree, or go up until hit right branch.
Deletion: tricky, but fun.  Omit if not enough time.

All operations: w-c $\Theta(h)$.  




----------------------------------------------------------------------