MAN

Distance/Internal

MASSEY UNIVERSITY

MANAWATU CAMPUS

EXAMINATION FOR

159.271 Computational Thinking For Problem Solving

Time Allowed: THREE (3)hours

All students are required to answerSIX (6)out of EIGHT (8)

Questions.

Calculators are not permitted

The Examination Question Paper is not to be removed from the exam

room.

Write your answers in the Blue Script Book supplied.

This exam paper will be available at the library after the exam period.

Total marks for this exam[60 marks]

Each question is worth 10 Marks.

MAN

Distance/Internal

Question 1

Dynamic Programming [10 marks]

Catherine has promised candy to the student producing the fasted solution to the first tutorial.
However, the three fastest solutions ended up being too close to call, so we now have three winners
instead of one. That means that the candy (which Catherine already bought) has to be split as evenly
as possible between the three winners. There areN (N ≈50) individual candies in Catherine’s bag,
and each candy is worth between 1 and M cents (M≈50, all values are in whole cents). The goal is
to minimize the difference in total candy value between the student receiving the most candy, and the
student receiving the least. E.g. if the students were to receive $4.90, $5.00 and $5.01 worth of candy,
the difference would be 11 cents.
Note: All candy must be distributed - Catherine can’t keep any for herself!

(a) A brute force approach for finding an optimal candy distribution would be to iterate over all possible
distributions, compute the difference for each and pick the best.
What is the complexityof this approach, as a function ofN? Justify your answer. [2 marks]
Answer: There are 3Ndistributions, computing the difference of each requiresO(N) steps, so the
overall complexity isO(N· 3 N).

(b) A greedy approach is to iterate over the list of candies in the order they are given in, and assign each candy to the student with the lowest current total. Give a small exampleto show that this approach may not produce an optimal solution. [2 marks] Bonus: Give such an example with candies sorted by decreasing value. [+1 mark]

Answer: For candies worth 1,1,1 and 2 the greedy approach will produce the totals 3=(1+2), 1 and
1, for a difference of 2. Optimal would be 2=(1+1), 2 and 1, for a difference of 1.
Bonus: For candies of worth 5,4,4,3,3,2,2 the greedy approach will produce the totals

9 = (5 + 2 + 2) 7 = (4 + 3) 7 = (4 + 3)

whereas the optimal solution has totals of

8 = (5 + 3) 8 = (4 + 2 + 2) 7 = (4 + 3)

(c) Using pseudocode,describe an algorithmthat finds the minimal difference achievable for a given
list of candies. Your algorithm must be exact and have a running time polynomial inNandM.
[6 marks]
Answer: Compute possiple total-triples using dynamic programming.
1:totals← {(0, 0 ,0)}
2:forcandyincandiesdo
3: newTotals← {} // empty set
4: fortotalintotalsdo
5: inserttotal + (candy,0,0)intonewTotals
6: inserttotal + (0,candy,0)intonewTotals
7: inserttotal + (0,0,candy)intonewTotals
8: totals←newTotals
9:returnmin{distance(total)|total∈totals}
Some notes on complexity (not required for full marks):

• Basic Analysis: The highest total any student can receive is bounded byN·M. Thus the number of distinct total triples is bounded byN^3 ·M^3 , which in turn bounds the number of iterations in the

MAN

Distance/Internal

inner loop (note that the algorithm is using a set, so duplicates are eliminated). The overall
number of iterations is thus bounded byN^4 ·M^3. As the work performed in each iteration is
constant (assuming a hash-set is used for newTotals), this gives us an overall complexity bound
ofO(N^4 ·M^3 ). The work to find the minimal distance of possible totals is negligible.

• Improvement: Since all total triples add up to the same value (=total value of candies distributed so far), the third value is always determined by the first two. This reduces the bound on the number of total triples toN^2 ·M^2 , for an overall complexity ofO(N^3 ·M^2 ).

MAN

Distance/Internal

Question 2

Complexity [10 marks]

In the following let the input consist of graphsG= (V, E) withV vertices andEedges. All input
graphs are connected and do not contain duplicate edges.
Note:V andEmay refer either to the vertex and edge sets, or to the cardinalities of these sets. Which
interpretation is correct will be clear from the context.

(a)Indicate all pairwise containment relationshipsbetween the following complexity classes:

O(V^3 ) O(V·E) O(V·E+V^2 ) O(V·E·logV) O(V·log^3 V+E)

Note: Containment meansO(.. .)⊆O(.. .). [4 marks]
Answer: As graphs are connected we haveE≥V−1, and the absence of duplicate edges ensures
E≤V^2. This leads to the following containment relationships:

O(V·log^3 V+E)⊆O(V·E) =O(V·E+V^2 )⊆O(V^3 ), O(V·E·logV)

(b) The algorithm given below finds a maximal independent set.

1:functionMaxIndSet(G)
2: ifGis emptythen
3: return∅
4: x←random vertex inG
5: picked = MaxIndSet(G−{x}−N(x))∪ {x} //N(x) denotes the neighbours ofxinG
6: notPicked = MaxIndSet(G−{x})
7: returnbigger(picked, notPicked)

Establish a reasonably tight complexity boundfor the algorithm’s running time. [2 marks]
Bonus: Establish a complexity bound that’s as tight as possible. [+2 marks]

Answer: For each recursive call made, the number of vertices is reduced by at least one. This limits
the height of the binary recursion tree toV, resulting in (at most) 2V recursive calls. The work
performed during each recursive call (for copying the graph and result set) isO(V+E) =O(E), for
a total complexity ofO(E· 2 V).
Improvement (for +2 bonus marks): We can break down the work further by recursion depth. For
depth levelnwe perform 2nrecursive calls, on graphs of size at mostV−n. This limits the total
work performed for depth levelnto 2n·(V−n)^2. Adding up all depth levels now gives us an overall
complexity bound of

O

(

(V−0)^2 · 20 + (V−1)^2 · 21 +.. .+ (V−(V−1))^2 · 2 V−^1

)

=O

(

2 V·

(

V^2 ·^12

V
+ (V−1)^2 ·^12
V− 1
+.. .+ 1·^12

1 ))

⊆O

(

2 V·

(

2
3

V
+^23
V− 1
+.. .+^23

1 ))

=O

(

2 V· 2

)

=O

(

2 V

)

MAN

Distance/Internal

(c) The algorithm given below finds an upper bound (not necessarily minimal) on the number of colours
needed to colour a given graph such that adjacent vertices have different colours.

1:functionMinColours(G)
2: colours← 0
3: whileGis not emptydo
4: G←G−MaxIndSet(G)
5: colours←colours + 1
6: returncolours

Establish a reasonably tight complexity boundfor the algorithm’s running time. [2 marks]
Hint 1: The work performed by MaxIndSet depends on the size of theremaininggraph.
Hint 2:^12 +^14 +^18 +.. .≤ 1.
Answer: In each iteration the size ofGis reduced by at least 1, so the number of iterations is
bounded byV. As established previously, the running time of MaxIndSet is bounded byE· 2 n(or
2 n), wheren=V, V− 1 ,... ,1 is the number of vertices in the remaining graph. This gives us a
complexity of
O

(

E· 2 V +E· 2 V−^1 +.. .+E· 21

)

=O

(

E· 2 V+1·

( 1

2 +

1
4 +

1
8 +...

))

=O

(

E· 2 V+

)

=O

(

E· 2 V

)

When using the improved bound for MaxIndSet, we getO(2V) instead.

(d) Give examplesthat show that the complexity bounds established for algorithms MaxIndSet and MinColours are tight up to a polynomial factor. [2 marks] Note: Recall that the initial input graph must be connected (→examples must be connected). Hint: Consider what happens whenGcontains vertices but no edges. Answer: WhenGcontains vertices but no edges, then each recursive call in algorithm MaxIndSet reduces the size ofGby exactly one. Thus the number of recursive calls becomes 2V, providing a lower bound of Ω(2V) for the worst-case complexity of both algorithms. To satisfy the condition that input graphs are connected, we can extend such graphs by adding a single vertexwthat is connected to all others (i.e. we get astar graph). Then, after one recursion (on the notPicked branch ifx=w, or on the picked branch otherwise) the remaining graph contains vertices (at most 2 fewer) but no edges, providing the same lower bound for connected graphs. Note that this means the improved bound is tight without any polynomial factor.

MAN

Distance/Internal

Question 3

Shortest Paths [10 marks]

For the following questions, consider the edge-weighted graph given below:

A

B

D C

E

-

3

5

-

1

-

2

(a) The Floyd-Warshall algorithm computes the all-pair shortest paths for graphs with arbitrary edge
weights.

(i)Draw the initial distance matrixcorresponding to the graph above. [2 marks]
Answer: With values of∞omitted, in row→column format:

A B C D E

A 0 -1 3
B 0 5
C -4 0 1
D 0 -
E 2 0

(ii)Draw the state of the distance matrixafter a single iteration of the Floyd-Warshall algo-
rithm with nodeAas intermediate node. [2 marks]
Answer: Updated values in bold:

A B C D E

A 0 -1 3
B 0 5
C -4 -5 0 -
D 0 -
E 2 1 5 0

(b) Johnson’s algorithm reduces the all-pair shortest paths problem for graphs with arbitrary edge weights to graphs with non-negative edge weights.

(i) Demonstrate this reduction byreducing the graph above. Show your workings. [4 marks]
Answer: To start, we calculate the q-distance to all nodes:

q-distance:

A B C D E

-4 -5 0 -1 -

MAN

Distance/Internal

Afterwards we modify the weight of each edgev→wby adding q-dist(v)−q-dist(w):

A

B

D C

E

0

0

0

0

2

0

3

(ii) Using the reduced graph,compute the lengthof the shortest path from C to E in the original
graph. Show your workings. [1 mark]
Note: You don’t need to explain how you compute shortest paths in the reduced graph.
Answer: We first compute the length of the shortest path from C to E in the reduced graph,
which turns out to be 0. Afterwards we reverse the edge-weight adjustments by subtracting
q-dist(C)−q-dist(E). This gives us 0−(0−-3) = -3.

(c) Which of the two algorithms would you recommend?Justify your answer. [1 mark]

Answer: Depends on the density of the graph. Floyd-Warshall is simpler to implement and slightly
faster for very dense graphs. On the other hand, Johnson’s algorithm is much faster for sparse graphs.

MAN

Distance/Internal

Question 4

Network Flow [10 marks]

The following questions refer to the graph given below, with C being the source and E the sink:

A B

C D E

F G

4

2

6 6

3

3

4 1

5

5

2

(a) The Edmonds-Karp algorithm computes a maximal flow for a given edge-weighted graph. For the
graph given above,draw the residual graphafter one iteration of the algorithm. [3 marks]
Answer: In each iteration, Edmonds-Karp finds the shortest path from source to sink, and sends the
maximal available flow through it. The residual graph is constructed by subtracting this flow from
each edge along this path and adding it to inverse edges. For the given graph the shortest path is
C→F→G→E, resulting in

A B

C D E

F G

4

2

6 6

1

3

4 1

2

3

5

2

2

(b) Find and drawa maximal flow for the graph given above. [3 marks]

Answer: The solution identified by Edmonds-Karp is:

A B

C D E

F G

4 4 5

3

3

1

3

2

2

(c) Identify a minimal cutfor the given graph, andgive an argumentto show that it is minimal.
[2 marks]
Answer: The bi-partition into A,C and B,D,E,F,G is a cut of size 7. Since there exists a flow of size
7, as identified above, the cut must be minimal by the max-flow min-cut theorem.

MAN

Distance/Internal

(d) A business offering personal guided tours employs a group of multilingual guides. Travellers can request tours, but when there are many requests for the same time slot, the business cannot service them all. In this case, the business would like to maximize the number of acceptable pairings between travellers and guides. A pairing is acceptable if the guide shares a language with the traveller assigned to them. Explain howsuch an optimal pairing could be found efficiently. [2 marks] Answer: The problem can be modelled as a bipartite graph, with guides and travellers as vertices, and an edge for each acceptable pairing. The goal is then to find a maximal matching, which can be reduced to the maximal flow problem by adding a new source and sink node (each connected to all guides and travellers, respectively). Afterwards any algorithm for solving maximal flow can be employed, e.g. Edmonds-Karp.

MAN

Distance/Internal

Question 5

Loop invariants [10 marks]

Consider the following Python function that merges two sorted lists.
Here is a loop invariant for loop 1:
“the contents ofnewlistare in sorted order,newlistcontainsaelements oflistAandbelements of
listB”

def mergeSortedLists(listA, listB):
newlist = [ ]
a = 0
b = 0

# loop 1
while a < len(listA) and b < len(listB):
if listA[a] < listB[b]:
newlist.append(listA[a])
a +=
else:
newlist.append(listB[b])
b +=

if a < len(listA):
newlist.extend(listA[a:])

if b < len(listB):
newlist.extend(listB[b:])

return newlist

(a) Write down (in regular English) a pre-condition for the function. What important property needs to
be true about the input in order for this function to work correctly? [1 marks]

(b) Write down (in regular English) a post-condition for the function. What do we want this function to return? [1 marks]

(c) Give an argument to show that the loop invariant is true before loop 1 is entered for the first time.
[2 marks]

(d) Give an argument to show that, if the loop invariant is true upon entry to an arbitrary iteration of loop 1, it remains true after that iteration of the loop. [2 marks]

(e) Write down (in regular English) a post-condition for loop 1. What is established by the loop invariant
and the loop exit condition upon exit from loop 1? [2 marks]

(f) Give an argument to show that your post-condition for loop 1, along with action of the code following
the loop, infers your post-condition for the function. [2 marks]

MAN

Distance/Internal

Question 6

Recursion [10 marks]

Consider the following Python class for constructing binary ordered trees:

class TNode:
def __init__(self, data):
# initialize the node fields
self.left = None
self.right = None
self.data = data

class BinOrdTree:
def __init__(self):
# initialize the root node
self.root = None

def addNode(self, data):
# insert new data value into tree
self.root = self.__insert(self.root, data)

def __insert(self, root, data):
# insert new data value into subtree and return new subtree root
if root == None:
return TNode(data)
else:
if data <= root.data:
root.left = self.__insert(root.left, data)
else:
root.right = self.__insert(root.right, data)
return root

(a) Design arecursivemethodlookUpfor this class, that searches for a given value in a tree. If the
value is present in the treelookUpreturns True, otherwiselookUpreturns False. [5 marks]

(b) Design arecursivemethodmaxPathfor this class, that returns the maximum number of edges on any path in a tree from the root to a leaf. If the tree consists of only one node, thenmaxPathshould return zero. If the tree is empty, thenmaxPathis not defined, in other words, it doesn’t make sense to callmaxPathon an empty tree. Consider carefully how this will affect the design of your recursive solution. [5 marks]

Write the code for your algorithms using normal Python syntax. Minor syntax errors will not be
penalised.

MAN

Distance/Internal

Question 7

Greedy algorithms [10 marks]

Theactivity selection problemis defined as follows: Givennactivities and their start and finish
times, find a subset ofknon-conflicting activities, withkas large as possible. Two activities conflict if
there is a point in time when both are active.

(a) Suppose I develop a greedy algorithm to solve the activity selection problem using the following
greedy rule: “At each step, choose the activity requiring shortest time that doesn’t conflict with any
previously chosen activity.”
Present a counter-example, by drawing a diagram of a set of activities on a timeline, to show that a
greedy algorithm using this rule will not always return the largest possible subset of non-conflicting
activities. [4 marks]

(b) Givetwomore different greedy rules (not necessarily optimal, but sensible) that could be used to develop a greedy algorithm to solve the activity selection problem. [2 marks]

(c) For each of your greedy rules from part (b), give theO(f(n)) running time for a greedy algorithm that
attempts to solve theactivity selection problemby applying this rule on a set ofnactivities.
[4 marks]

MAN

Distance/Internal

Question 8

Recursive backtracking [10 marks]

Suppose I want to burn some songs onto a 650MB CD (some people still do!) and I have a list of song
tracks of various sizes. I want to fill up as much of my CD as I can. I can use a recursive backtracking
strategy to find a subset of the song tracks that optimally fills my CD (that is, with the least space left
unfilled). You should recognise this problem as a version of theKnapsack problem.
Here is the basic recursive backtracking strategy:

if there are no more songs to consider:
return solution
else:
for the next song in the list:
try not adding it to the CD, use recursion to evaluate the best solution without it
try adding it to the CD, use recursion to evaluate best solution with it
return the best of these two results as the best solution from here

(a) What should an input instance for this problem consist of? [2 marks]

(b) Given an input instance, what should be returned as a valid solution for the problem? [2 marks]

(c) Given a valid solution, what is the measure to be used to determine if it is better than some other
solution? [1 marks]

(d) What basic strategy can be used to prune the recursion tree? [1 marks]

(e) Using your answers to the previous parts of this question as a basis, write down arecursive back-
tracking algorithmthat solves theCD-fill problem. You can write the code for your algorithm
using normal Python syntax, or you can use pseudocode. [4 marks]

++++++++