CSS 343 practice problem sample solutions

1.  You're at a small company that currently has 10 departments.
    It is growing, but new departments are added rarely.
    The departments have names and can have an assigned code.
    Explain how you would store the information for a fast look-up.  

Use a hash table (array).  With only 10 items, you can make the table large
and allow for many more departments with little sacrifice.  You can hash
on the names, codes, or a combination.

2.  You're trying to map out directions to get from one room in a
    building to another room in either the same building or a
    different one.  How would you store the information?  Why?

You would store the information in a directed graph (digraph).  The rooms
and key points (like a door) are the graph nodes.  The path from room to
room, room to door, door to door, etc are the edges.  (Directed because
while most paths will go either way, there might be a one way path,
something like a one-way street for a car. Maybe you can exit through a door,
but can't enter through it.)

3.  You have a huge amount of information, too much to
    fit into main memory.  You rarely do inserts once
    you have the initial data.  How do you store the
    information for a fast lookup?

Use a B-tree which we briefly studied.  Recall the 'B' stands for balanced
as the distance from the root to each leaf is the same.

Make the size of the node (size of the array) as large as can fit into
one block of memory (amount that can fit into main memory).  This way you
do the smallest number of swaps out to disk (which is time consuming).

4.  You have a small collection of rare books. How would you
    store the information so that it can be quickly found, but
    also can be listed alphabetically by author. Why?

Use both some ordered collection such as a balanced tree so the items can be
displayed in sorted order. Also use a hash table for fast look up.  Nodes in
both collections point to the same object so you don't duplicate information.
Because it is a small amount, you could just use a balanced tree. For small n,
log n complexity is good.