Algorithms and Data Structures

G52ADS Coursework for Autumn 2008

Formal Coursework

General Introduction

The Assignment

Please read the official brief here. In essence, the goal is to implement interfaces SimpleMap and AdvancedMap as declared here. This is: 

/**
 * A simple Map-like interface. A subset of java.util.Map.
 */
public interface SimpleMap<V> {
    
    /**
     * Associates the specified value with the specified key in this map.        
     * 
     * @param key Key to insert
     * @param v   Value to associate with key  
     * @return    If the map has an entry with k already, the associated 
     *            value is returned. Otherwise, null.     
     */
    public V put(int key, V value);    

    
    /**
     * Retrieves the value with associated with the specified key in this map.
     * 
     * @param key Key we are retrieving  
     * @return    If the map has an entry with key already, the associated 
     *            value is returned. Otherwise, null.     
     */
    public V get(int key);
    
    
    /**
     * A destructive element query. Deletes the key-value pair, returning value.
     * 
     * @param key Key we are retrieving    
     * @return    If the map has an entry with key already, the associated 
     *            value is returned. Otherwise, null.     
     */
    public V remove(int key);

    
    /**
     * Returns the number of elements in the SimpleMap.
     * @return The number of elements in the SimpleMap.
     */
    public int size();    


    /**
     * Returns true, if there are no elements in the SimpleMap.
     * @return true, if there are no elements in the SimpleMap.
     */
    public boolean isEmpty(); 

    
    /**
     * Produces a human-readable representation of the map. Notice that to conform
     * to the contract of Collection, you should print out all elements.
     *      
     * @return A String with human-readable representation 
     * of the elements inside the SimpleMap.
     */
    @Override
    public String toString();    
}

/**
 * An advanced Map-like interface for implementations based on semi-balanced trees. 
 * A superset of SimpleMap. Akin to java.util.Map. 
 */
public interface AdvancedMap<V> extends SimpleMap<V> {
    
    /**
     * Sets the maximum imbalance of the tree. 
     *     
     * @param k  Upper bound on the imbalance. Read -1 as no limit on imbalance.
     */
    public void setMaxImbalance(int k);    


    /**
     * Automatically sets the maximum imbalance of the tree to suit the input.
     * Calls setMaxImbalance internally. 
     */
    public void setAutoImbalance(); 

    
    /**
     * Produces a human-readable representation of the map in Newick Format:
     * http://en.wikipedia.org/wiki/Newick_format
     * with leaf nodes named, and nothing but leaf nodes names. Use keys to
     * label nodes. Notice that this largely conforms to the contract of 
     * Collection, saying you should print out all elements.
     *      
     * @return A String with human-readable representation 
     * of the elements inside the AdvancedMap in Newick Format.
     */
    // @Override
    public String toString();    
}

This should be done first using linked lists (SimpleMapImpl1), and then properly, using (semi)balanced search trees (SimpleMapImpl2, AdvancedMapImpl).

Submission

You are given two interfaces (SimpleMap, AdvancedMap), three stubs (SimpleMapImpl1, SimpleMapImpl2, AvancedMapImpl), and a stub of a test suite (SimpleTests) in a zip file, and you are expected to submit a zip file with an implementation extending the stubs, which passes the suitably extended test suite SimpleTests, including all source code, via cw. Please work on your own.

See more of Jakub's homepage or the list of exercises, if you please.