CMSC 341 -- Fall 2003 -- Project 4

Copy this file into your directory and edit it to add your answers to the
following questions about project 4.

These questions count for 10% of your project grade.


1. (5 points) Given two lists of length N and M respectively, a naive
   implementation of a method to compute the intersection of the lists
   will take O(NM) time.  How can you use hash tables to compute the
   intersection in O(N + M) time?

2. (5 points) Suppose Google came to you and said that they wanted to
   use your project to service queries sent to their search engine.
   What problems do you foresee in scaling up your project to deal
   with hundreds of thousands of distinct words and hundreds of
   millions of web pages?  How would you address these problems?