|
|
|
|
|
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.
- Pre-midterm topics covered
- Stacks and Queues, array and list
implementations.
- Recursion. Designing algorithms
recursively.
- Asymptotic analysis, Big-O. Worst
case, upper bound, lower bound, analyzing loops, recurrences, amortized
complexity.
- Trees – definitions
- Binary Heaps, D-heaps - 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 - Up-trees.
Weighted union (union by size) and path compression.
- Post-midterm 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. In-place sorting. Stable sorting.
- Graphs. Directed and undirected.
Adjacency list and adjacency matrix representations.
- Topological sorting.
- Graph searching. Depth-first,
breadth-first search
- Shortest paths. Dijkstra's algorithm
for SSSP. (Greedy Algorithms) Floyd-Warshall for APSP (Dynamic
programming)
- Minimum spanning tree: Prim’s and
Kruskal’s algorithms
- Network flows. Ford-Fulkerson
method, augmenting flows, uses of network flow
- NP-completeness. Definition of P,
NP, NP-hard, NP-complete. Euler and Hamiltonian circuits; clique and
vertex-cover. 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 re-work 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 E-Mail Lists
- All students must sign up for the cse326-announce
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 low-volume.
Office Hours
Lectures
|
Section
|
Instructor
|
When
|
Where
|
A
|
Ben Lerner
|
MWF 09:40-10:40
|
EEB 026
|
Sections
|
Section
|
When
|
Where
|
|
AA
|
Th 09:40-10:40
|
EEB 025
|
Textbook:
Data Structures and Algorithm Analysis in Java 2nd Ed.,
Mark Allen Weiss,
Addison Wesley: 2007, ISBN: 0-321-37013-9
Errata is here
|
CSE Home 
