Computer Science 385
Analysis of Algorithms
Spring 2011, Siena College
Lecture 20: Hashing Wrapup
Date: Thursday, March 31, 2011 (Opening Day!)
Agenda
- Announcements
- Friday office hours will start late, but I plan to be
available for an extra hour from 3:30 until about 4:30, weather
permitting.
- The short Problem Set 5 is due at the start of class
Tuesday, and since we will go over it in class on Tuesday, no
late submissions will be accepted.
- Exam 2 information
- Focus on topics since exam 1:
- divide and conquer: merge sort, quicksort, binary
search, Strassen's algorithm, closest pairs
- decrease and conquer: exponentiation examples, insertion
sort, graph traversals, topological sort
- binary search trees: tree sort, balanced trees, AVL
trees
- array representation of trees, priority queues, heaps,
heapsort
- counting sorts
- hashing
- Note: string matching will not be a topic on this exam
- Still be aware of previous topics: you may need to analyze
algorithms or compare sort procedures.
- Exam out at the end of class Tuesday, April 5, due back at
the start of class Thursday, April 7. The intent is that it
will take 2-3 hours to complete.
- Ground rules: permitted sources are your own notes, problem
sets, and other assignments, my online lecture pages and topic
notes, our textbook. All other sources are not allowed.
Obviously, you will work alone and may not discuss the exam with
your classmates (or anyone else except me) until everyone has
submitted the exam.
- Typeset and/or handwritten responses OK.
- As much time as you wish at the start of class on Tuesday
will be dedicated to exam Q&A.
- Lecture assignment recap
- Hashing
- some hashCode examples from Java
- handling collisions with open addressing and external chaining
- analysis
(Exam topic cutoff here)
Lecture Assignment 20
Due at the start of class, Tuesday, April 5.
No real lecture assignment, just prepare your questions for exam review on Tuesday.
Examples