Data Structures and Algorithms

CS35 Final Exam Study Guide

The final exam for this course is comprehensive: it will contain material from throughout the semester, albeit with a slight emphasis on more recent material. This study guide contains only material from after Test 3. To prepare for the final exam, please consult the following problems as well as the older study guides.

Hash Tables

  1. What is a hash? What is a hash collision?

    A hash is a function which transforms data (e.g. a dictionary key) into uniform data like an integer. A collision occurs when two different inputs map to the same hash value.

  2. We discussed two techniques for resolving hash collisions in class: linear probing and chaining. The technique used by a HashTable affects its structure.

    1. Briefly explain the difference between these hash collision resolution techniques.

      In linear probing, each hash value is assigned a bucket which holds at most one value and collisions are resolved by moving on to the next bucket. In chaining, each bucket may hold many values.

    2. Give a C++ data type which could be used as the contents of each type of hash table. (You may use pair and other data types we discussed in class. You may also use a pair within a pair or assume the existence of a type triple for three elements.)

      A linear probing hash table might store all of its buckets as an array pair<pair<K,V>,bool>*, where the boolean indicates whether a bucket is in use or not. A chaining hash table might store its buckets as an array LinearDictionary<K,V>* where each bucket is a vector containing all keys of the same hash.

  3. What is load factor? How is it used in a hash table?

    The load factor of a hash table is its size divided by its capacity. Load factor is used to determine when more buckets are allocated in order to keep mappings spread out between buckets.

  4. What is the worst case time for inserting an element into a hash table? How does this worst case time relate to the hashing function?

    In the worst case, an element insertion takes \(O(n)\) time; this occurs if all of the mappings have the same hash. The likelihood of this occurring is based on the quality of the hash function used with the table.

  5. Suppose you have an empty chaining hash table with three buckets and a maximum load factor of 0.75. Assume that keys and values are integers and that the hash function is hash(x, capacity) is x % capacity. We will insert the mappings \(4 \mapsto 8\), \(1 \mapsto 5\), \(0 \mapsto 6\), and \(6 \mapsto 2\). Draw the hash table after each addition. Assume that ensure_capacity doubles the number of buckets before rehashing.

    Empty hash table:

    latex 6dc2b1ab2db9209a90d09a6e9f5bcb5c

    After \(4 \mapsto 8\):

    latex 0b6bef8ae12b31892b618f8806c71b1e

    After \(1 \mapsto 5\):

    latex 60402fe427f67fe79297f9a9857ce7cb

    After \(0 \mapsto 6\), which expands the hash table:

    latex 03abf0e07b19cc721ef5c85fb92945f5

    After \(6 \mapsto 2\):

    latex 3eff7d5e71cf57635917e44e0e9cdfcd

Graphs

  1. What is a graph?

    A graph is a pair of sets. The first set, \(V\), is a set of vertices of any type. The second set, \(E\), is a set of edges. An edge is a grouping between a source vertex, a target vertex, a weight, and a label.

  2. Define the following terms in relation to graphs:

    1. Weighted

      A graph is weighted if its edges have weights / have meaningful weights / have non-uniform weights. A social network, for instance, is unlikely to be weighted, while a geographical map probably is (where weight is distance, difficulty of traveling, etc.).

    2. Directed

      A graph is undirected if, for each edge heading in one direction, there is an identical edge heading in the opposite direction. A graph is directed if it is not undirected.

    3. Connected

      A graph is connected if, for each vertex in the graph, there is a path to every other vertex in the graph. A graph is weakly connected if its undirected equivalent is connected.

  3. Consider the following graph:

    latex 7b59868474ff06ccf42afb1e5656add7

    1. Which path would a breadth first search find from vertex A to vertex G?

      A breadth-first search would find the path [A, D, G].

    2. Which path would Dijkstra’s algorithm find from vertex A to vertex G? Why is this path different from the BFS path above?

      Dijkstra’s algorithm would find the path [A, C, D, E, G]. This is different from breadth-first search because the sum of the weights of this path is less than the sum of the weights of the path with the fewest edges.

    3. Ignoring the weights on this graph, perform a topological sort of it. Give the resulting topological sort as a list of vertices.

      There are many valid sequences that may result from the topological sort. Here are a two possible outcomes:

      • [A, B, F, C, D, E, G]

      • [A, C, B, F, D, E, G]

  4. The graph data structure you used in class uses a dictionary to store the edges of the graph. Edges may be stored in a variety of different ways, so let us consider the adjacency matrix representation. Instead of a dictionary, we will store a two-dimensional array of weight values of size \(|V|^2\): that is, there is a row and a column for each vertex. If an edge exists from vertex A to vertex B, then the cell in row A and column B will contain its weight; otherwise, that cell contains a zero (for simplicity). Answer the following questions, using \(|V|\) for the number of vertices in the graph and \(|E|\) for the number of edges.

    1. What is the worst-case time complexity of adding an edge to this graph?

      The worst-case time complexity for adding an edge to the graph is \(O(1)\); the only action necessary is indexing into an array.

    2. What is the worst-case time complexity of producing a list of edges in this graph?

      The worst-case time complexity to find all edges in the graph is \(O(|V|^2)\), since we have to look at every cell in the matrix to find all of the edges.

    3. What is the worst-case time complexity of determining the out-degree of a vertex?

      The worst-case time complexity of determining a vertex’s out degree is \(O(|V|)\), since we must examine each vertex individually to determine if an edge exists to it.

    4. Suppose that we copy our edge data into a new matrix of size \((|V|+1)^2\) each time a new vertex is added. What is the time complexity of addVertex in this implementation?

      The complexity of this copy is \(O(|V|^2)\), proportional to the number of elements copied from the old matrix.