Welcome to CS 513:
    Design and Analysis of Data Structures and Algorithms.

Instructor: S. Muthu Muthukrishnan. x2379, Core 319. muthu@cs.rutgers.edu.
Meeting time: Thursday 6.10 - 9 PM .  Place: ARC 107.
Office Hours:    Mondays 3 - 4 PM.
TA: Jamie Friedman . Office: Core 246 . Office hours: Tues 4.30 --6.30 PM.

FINALS: grade distribution is as follows.

Grade
 No of Students
A
 9
B+
 13
B
 7
C+
 2
C
 2
I
 3

 Final Message:
                        Thank you for being open
                                to my idiocyncratic way,
                        Hope you picked up a trick of my trade,
                                a thought or any pattern beneath.
                                
                        Stop by, mail me
                                if I can help you some way.
                       Good luck, Happy holidays!



Some relevant reading materials:

  1. Detecting false matches in string matching algorithms. S. Muthukrishnan, Algorithmica 18(4): 512-520 (1997).
  2. Some Applications of Rabin's fingerprinting method. A. Broder. SEQUENCES. 1993. Citeseer . Local Cache.
Announcement : Check out the "job title" of Udi  Manber at Amazon.com.

You studied perfect hashing for integers in Lecture 7, and hashing for strings in Lecture 8.
Here is a paper on Perfect Hashing for Strings: formalization and Algorithms , by
M. Farach and S. Muthukrishnan, CPM, 1996.
Ignore all the PRAM part when you read this paper, and just focus on the sequential algorithm.
There is one theorem there which can be obtained much more simply than we did, but the
O(log log n) query time result is new and interesting. This material is not within the scope
of  this course.

 Some reading material.

  1. Optimal logarithmic time randomized suffix tree construction . M. Farach and S. Muthukrishnan. Read only Section 2.
  2. Farach-Colton made this algorithm deterministic and extended it to large alphabet in a very nice paper, and later, with Paolo Ferragina, we extended these algorithms to work with large strings in disk-bound data. There is a wonderful presentation of this result by Roman Manevich here .
  3. We discussed LCA and RMQ. A nice LCA presentation with examples and animation by Erez Sayer can be found here.