



Announcements
Final Exam, Friday, August 17, 2007
 Exam policies
 Closed book, closed notes. No
cheating.
 The exam begins promptly at 9:40 and
ends at 10:40.
 Premidterm topics covered
 Stacks and Queues, array and list
implementations.
 Recursion. Designing algorithms
recursively.
 Asymptotic analysis, BigO. Worst
case, upper bound, lower bound, analyzing loops, recurrences, amortized
complexity.
 Trees – definitions
 Binary Heaps, Dheaps  Findmin,
Deletemin, Insert. Additional operations of
increase, decrease, buildheap.
 Binomial Queues  Findmin,
Deletemin, Insert. Additional operations of merge, increase, decrease.
 Binary search trees – Inorder,
preorder, postorder traversals, insert, delete, find.
 AVL trees  Single and double
rotations, insert, find.
 Splay trees  Splaying, insert,
find.
 B trees  Motivation, choice of M
and L.
 Disjoint Union/Find  Uptrees.
Weighted union (union by size) and path compression.
 Postmidterm topics covered
 Hashing. Properties of good hash
functions. Selecting hash table size. Separate chaining and open
addressing. Linear Probing, Quadratic Probing, & Double Hashing to
resolve collisions. Rehashing.
 Sorting. Insertion sort, Selection
sort, Heap sort, Merge sort, quicksort.
 Bucket sort, Radix sort. Lower bound
on comparison sorting. Inplace sorting. Stable sorting.
 Graphs. Directed and undirected.
Adjacency list and adjacency matrix representations.
 Topological sorting.
 Graph searching. Depthfirst,
breadthfirst search
 Shortest paths. Dijkstra's algorithm
for SSSP. (Greedy Algorithms) FloydWarshall for APSP (Dynamic
programming)
 Minimum spanning tree: Prim’s and
Kruskal’s algorithms
 Network flows. FordFulkerson
method, augmenting flows, uses of network flow
 NPcompleteness. Definition of P,
NP, NPhard, NPcomplete. Euler and Hamiltonian circuits; clique and
vertexcover. Reduction proofs
 Binary search trees – Inorder,
preorder, postorder traversals, insert, delete, find.
 In
general: Algorithmic analysis (best case, worst case, average case,
amortized). Order notation (Big Oh, big Omega). Recursion.
 Study guides:
 Do concrete problems from the book
and rework problems from lecture, section, and homeworks. Suggestions
of more problems from the book: Chapter 2:
2.6, 2.10. Chapter 3: 3.21, 3.22, 3.23 (a). Chapter 4: 4.1, 4.8, 4.22,
4.27, 4.28. Chapter 6: 6.2, 6.3, 6.30.
 Selected
solutions to practice problems. Please note that some
of the figures end up on the last page.
 More problems: Chapter 5: 5.1, 5.8, 5.9, 5.10, 5.11. Chapter 7:
7.1, 7.15, 7.19, 7.39. Chapter 9: 9.20, 9.34, 9.53. Ruth Anderson's homework
3.
 Practice all the sorting and hashing
algorithms. Practice topological sort, graph search, and shortest path.
Practice analysis of algorithms.
 All material from lecture up through
NP Completeness is fair game. This material
corresponds to: Chapters: 1, 2, 3, 4, 5, 6 (not including 6.6 and 6.7),
7, 8 (not including 8.6), and 9 (not including 9.4).
Midterm
The midterm will be held during lecture on Monday, July 16. A list of topics has been posted.
Class EMail Lists
 All students must sign up for the cse326announce
mailing list. You are responsible for any information posted to this
list. Only the instructor and TAs are allowed to post to this list,
so it should be fairly lowvolume.
Office Hours
Lectures
Section

Instructor

When

Where

A

Ben Lerner

MWF 09:4010:40

EEB 026

Sections
Section

When

Where

AA

Th 09:4010:40

EEB 025

Textbook:
Data Structures and Algorithm Analysis in Java 2nd Ed.,
Mark Allen Weiss,
Addison Wesley: 2007, ISBN: 0321370139
Errata is here
