CSci2110 - Assignment 3

Due: Tuesday Feb. 27  by 11:55pm

Revisions History:
- Created Feb. 15th, 2007

Assignment Goals:

  1. Practice designing a new data structure to solve a given problem.
  2. Practice with expected case analysis.
  3. Practice experimentally evaluating data structure performance.

Introduction

Caching is a very powerful idea in computer science, one that plays an important role in the design of systems from processors to databases. The idea is that if some piece of data is expensive to compute (or request from another system) then maybe it is worth keeping a copy in case it is required again. A cache is a high speed storage repository for temporary data.

For example, web browsers typically maintain a cache of recently visited pages and images so that if they are requested again they can be accessed locally rather than being re-transferred over the network . There also may be network-based web caches as illustrated below.


From http://www.cisco.com/univercd/illus/1/93/111393.jpg.

It might be nice to have an infinite size cache, but that is not practical so caches are typically designed to have some given fixed size and use some kind of cache replacement policy to determine what to do when the cache is full. One popular replacement policy, LRU, replaces the Least Recently Used entry if the cache is full. The replacement policy must also decide where in the cache a copy of a particular entry will go. If the replacement policy is free to choose any entry in the cache to hold the copy, the cache is called fully associative.

Your Task

  1. Design a data structure and a set of operations for a fully associative data cache. Your data structure should support a constructor which specifies MAXSIZE, the maximum number of values to be stored in the cache. This constructor should run in O(MAXSIZE) time and allocate up to O(MAXSIZE) space. Your data structure should support the following operations:
     
    1. retrieve(key) - returns the associated value if it exists or null otherwise.
       
    2. evict() - implements a least recently used replacement policy OR an approximation of one. Hint: consider using a move-to-front heuristic.
       
    3. insert(key,value) - insert the key-value pair into the cache, where key is a unique integer and value is an object.

    All of these operations should run in expected O(1) time. Submit your write up for this question as a MSWord or .pdf file. This is a design exercise in which you will be marked on the clarity, simplicity, and efficiency of your solution. Draw pictures! You may design a composite data structure that uses other data structures as helpers. In your analysis you should focus on expected case performance but also discuss worst-case performance.
     

  2. Implement your data structure from Question 1. Your may use any source code you like from the Weiss Data Structures Library but you may NOT use any of the Java collections classes. Be sure to define an appropriate interface.
     
  3. Test your data structure. If you have any tuning parameters be sure to illustrate their effect on performance and recommend settings.

Be sure follow all of the code craft requirements carefully! Be sure to do sufficient testing! You are to use only code that you have developed yourself for this assignment.

Note: No late assignments will be accepted.