Datastrukturer (DAT037), lp2 2014

The exam aims at covering all the material from the lectures and is structured in the following manner:

  1. Complexity Analysis

    Examples:


  2. Linked Lists. Stacks. Queues. Dynamic Arrays

    Examples:


  3. Trees. Binary Search Trees. AVL Trees. Red-Black Trees

    Examples:


  4. Graphs. Algorithms on Graphs. Minimum Spanning Trees

    Examples:


  5. Hash tables. Heaps

    Examples:


  6. Build new data structure. Understand new program. New algorithm for a problem.

    Examples:

Additional Assignments + Solutions

    1. What is the time complexity of the following program ? 
               for(int i=1; i<=n; i++)
           for(int j=1; j<=n; j++)
              a.add(i);
         v=a.toArray();
         insertSort(v);
      where
      • a is a dynamic array
      • toArray is linear in the number of elements
      • v is a normal array of integers
      • insertSort is insertion sort
    2. What is the time complexity of the following program ? 
            for(int i=n; i>=1; i=i/2)
        a.add(i);
      v=a.toArray();
      insertSort(v);
      where
      • a is a dynamic array
      • toArray is linear in the number of elements
      • v is a normal array of integers
      • insertSort is insertion sort
    3. What is the time complexity of the following program ? 
            for(int i=1; i<=n; i=i*2)
        t.add(i);
      where
      • t is a binary search tree (unbalanced)

    1. Give an algorithm that recreates a binary tree from its postorder and inorder traversals, assuming that the tree contains distinct values or prove that it's not possible, by providing two distinct binary trees that have the same traversals in postorder and inorder.
    2. Give an algorithm that recreates a binary search tree from its preorder traversal or prove that it's not possible by providing two distinct binary search trees that have the same traversals in preorder.
    3. Give an algorithm that recreates a binary search tree from its inorder traversal or prove that it's not possible by providing two distinct binary search trees that have the same traversals in inorder.
    4. Write an algorithm that converts the sorted array of length N into a balanced binary search tree.
    5. Print all nodes from level k of a binary tree.
    6. Show each step of the AVL tree obtained by inserting the elements 1, 2, 3, 4, 5, 6 in this order

    1. Implement a stack using two queues. What is the complexity of enqueue and dequeue ?
    2. Implement large number addition using a singly linked list to represent the numbers (right to left).

      Example: 159+841= 1000, where 159 is represented as: Cons 9 (Cons 5 (Cons 1 Nil)).

    3. Write a function that checks if a singly-linked list contains a cycle.
    4. Write a function that finds the kth element before the last in a singly-linked list.

    1. The square of the unweighted graph G=(V,E) is G'=(V,E'), where E' contains the edge (v1,v2) if v2 can be reached from v1 in 2 steps on less in G. Given the graph G, compute G', its square. You can choose adjacency lists or an adjacency matrix to represent edges.
    2. If all edges are integers 1...|V|, can you optimize Kruskal's algorithm even further ?
    3. Traverse the graph in DFS and BFS.
    4. Find the shortest path between node and the rest of the nodes with Dijkstra's algorithm.
    5. Apply Prim's algorithm to find an MST of the graph.
    6. Apply Kruskal's algorithm to find an MST of the graph

    1. Show what happens when we insert the keys 50; 28; 19; 15; 20; 33; 12; 17; 91 into a hash table with collisions resolved by chaining. Let the table have 9 slots, and let the hash function be h(k)= k mod 9.
    2. Show each step of what happens when we insert the elements: 4, 9, 2, 5, 1, 10, 6 in an initially empty binary heap.
    3. Show each step of what happens when we insert the elements: 4, 9, 2, 5, 1, 10, 6 in an initially empty binary leftist heap.

    1. Assuming that we have an initially sorted array of length N which contains distinct elements and has been rotated to the right a number of times, write an O(log N) algorithm to find the minimum element in the array.

      Example: 7 8 9 1 2 3

    2. Assuming that we have an initially sorted array of integers of length N which contains distinct elements and has been rotated to the right a number of times, write an O(log N) algorithm to see if an integer value is found in the array.