Name:
Student Number:
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!
Answer: D&C works by recursively breaking down the problem space, until the individual problems become simple enough to be solved independently. A typical D&C algorithm is mergesort; mergesort will split an unsorted list into \(n\) sublists, until it gets to 1 element lists. Then, it will merge and sort the indvidual sublists.
Answer:foo will overflow for \(n > 100\)
def foo(n):
if n == 0:
return 0
return 1 + foo(n - 1)foo_it works for arbitrarily large \(n\)s
def foo_it(n):
i = 0
for j in range(0, n):
i = i + 1
return iAnswer:
def fib(x):
if x == 0: return 0
elif x == 1: return 1
else: return fib(x - 2) + fib(x - 1)A recursive solution can use memoization to prune recursion branches.
mem = {}
mem[0] = 0
mem[1] = 1
def fib_mem(x):
if x in mem.keys():
return mem[x]
mem[x] = fib_mem(x - 2) + fib_mem(x - 1)
return mem[x]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):
passHere 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 ]Answer: The trick is to implement a class Node that stores the value and has a pointer to the next list item. The remove method is particularly tricky as we need to keep 2 pointers to the head and to the previously processed item.
class IntList(object):
class Node(object):
def __init__(self, val, next = None):
self.val = val
self.next = next
def __init__(self):
self.head = None
self.cur = None
def add(self, val):
node = IntList.Node(val)
if self.head is None:
self.head = node
self.cur = node
else:
self.cur.next = node
self.cur = node
# Remove all elements equal to val
def remove(self, val):
prev = self.head
p = self.head
while p:
if p.val != val:
prev = p
p = p.next
continue
if p == self.head:
self.head = p.next
else:
prev.next = p.next
p = p.next
#Prints our list formated as a Python array
def __str__(self):
res = "["
cur = self.head
while cur:
res = "%s %d," % (res, cur.val)
cur = cur.next
if res[-1] is ',':
res = res[:-1]
res = res + " ]"
return res
__repr__ = __str__Answer: Data structures backed by arrays usually have constant access, insert and delete time, and can be sorted and searched in logartithmic time. However, we cannot use them to store arbitrarily large datasets, as the arrays are statically initialized to a fixed size.
Data structures backed by linked lists can store as many items as the computer memory allows; the drawback is increased memory use and mostly linear time access operations.
Answer: KMP pre-calculates a jump table on the pattern that is used to skip some checks when a match fails. The table contains the lengths of prefixes in the search pattern that are also suffixes.
Answer:
P: 1 2 3 3 2 1 1 2
J: 0 0 0 0 0 0 1 1 2def jump_table(pattern):
result = [None]
for i in range(0, len(pattern)):
j = i
while True:
if j == 0:
result.append(0)
break
if pattern[result[j]] == pattern[i]:
result.append(result[j] + 1)
break
j = result[j]
return resultquicksort.Answer: A beautiful (but inefficient!) implementation
def quicksort(xs):
if xs:
pivot = xs[0]
below = [i for i in xs[1:] if i < pivot]
above = [i for i in xs[1:] if i >= pivot]
return quicksort(below) + [pivot] + quicksort(above)
else:
return xsAnswer: For graphs with \(m\) nodes, we can use:
Answer: The data structure to use is obviously a graph; we could use a tree if we were certain that there are no loops, i.e. web page \(A\) links to \(B\), which links to \(C\) which links to \(A\).
Then, we need an estimate of how important a web page is in this graph. For that, we can calculate each node’s Pagerank, or probability that a random surfer will hit a web page by simply following links. Since the total PageRank of a graph is always 1, we can simply multiply each node’s Pagerank with the total amount of money we have to calculate the total investment per page.
Answer: Topological sorting allows us to get a linear ordering of the vertices of a directed graph, in a way that if there exists an edge between \(m\) and \(n\), then \(m\) will come before \(n\). The canonical application of topological sorting is in scheduling a sequence of jobs or tasks based on their dependencies. For example, if we want to calculate a schedule for courses that depend upon each others, we can topologically sort them.
Answer: We need optimization because some problems have a solution space that far exceeds the computational power available. A typical problem solved by optimization is the traveling salesman problem for graphs.