Name:

Student Number:

Instructions

The total number of points is 75. The total number of points you need to collect to get a 10 is 70. The total number of points you need to collect to pass is 40.

You have 180 minutes: Good Luck!

Exam questions

  1. (4 points) What is the divide and conquer (D&C) algorithmic technique? Describe an algorithm (no need to show its implementation) that uses D&C and present its evaluation strategy.
  1. (4 points) A typical problem with recursion is stack overflow errors. Write an (any!) function that will overflow and then re-write it so that it does not.
  1. (4 points) Rewrite the Fibonacci algorithm given below so that each individual recursion branch is only executed once.
def fib(x):
    if x == 0: return 0
    elif x == 1: return 1
    else: return fib(x - 2) + fib(x - 1)
  1. (20 points) Write a class that implements a singly linked list that stores integers, using the following prototype (each correct function implementation is worth 5 points):
class IntList(object):

    # Constructs an empty list
    def __init__(self):
      pass

    # Adds a element to the list
    def add(self, val):
      pass

    # Removes all elements equal to val
    def remove(self, val):
      pass

    # Prints the list like a Python array
    def __str__(self):
      pass

Here is an example usage scenario for it:

> a = IntList()
> print a
[ ]
> a.add(5)
> a.add(10)
> print a
[ 5, 10 ]
> a.add(15)
> a.add(5)
> print(a)
[ 5, 10, 15, 5 ]
> a.remove(5)
> print(a)
[ 10, 15 ]
  1. (2 points) Explain the differences in the working characteristics of data structures backed by arrays vs data structures backed by linked lists. When is each implementation preferable?
  1. (2 points) How does the Knuth-Morris-Pratt work and why is it faster than naive string search?
  1. (4 points) Calculate the jump table used by the Knuth-Morris-Pratt algorithm, for the search pattern \(P=12332112\). Describe the algorithm you used (in pseudocode or Python).
  1. (6 points) Write a recursive implementation of quicksort.
  1. (4 points) Describe 2 ways in which we can represent graphs in memory.
  1. (6 points) Given a set of web sites, we need to decide on how to split our advertising budget. One idea is to put most of our money on sites that have many incoming links, as the propability of users visiting them will be higher. In our servers, we keep a full copy of the home page of each web site. Describe a potential data structure/algorithm combination to use in order to calculate the budget distribution.
  1. (2 points) What is topological sorting for graphs? Describe a use case for it.
  1. (2 points) Why do we need optimization algorithms? Describe a problem that is best solved using any optimization technique.
  1. (15 points) What is the time complexity (\(O\)) of the following operations?