2020 Semester Two (November-December 2020) Examination Period
EXAM CODES: TITLE OF PAPER: EXAM DURATION:
Faculty of Information Technology
Algorithms and data structures 2 hours 10 mins
uring an exam, you must not have in your possession any item/material that has not been authorised for your exam. This includes books, otes, paper, electronic device/s, mobile phone, smart watch/device, calculator, pencil case, or writing on any part of your body. Any uthorised items are listed below. Items/materials on your desk, chair, in your clothing or otherwise on your person will be deemed to be in our possession.
ou must not retain, copy, memorise or note down any exam content for personal use or to share with any other person by any means ollowing your exam.
ou must comply with any instructions given to you by an exam supervisor.
s a student, and under Monash University’s Student Academic Integrity procedure, you must undertake your in-semester tasks, and end- f-semester tasks, including exams, with honesty and integrity. In exams, you must not allow anyone else to do work for you and you must ot do any work for others. You must not contact, or attempt to contact, another person in an attempt to gain unfair advantage during your xam session. Assessors may take reasonable steps to check that your work displays the expected standards of academic integrity.
ailure to comply with the above instructions, or attempting to cheat or cheating in an exam may constitute a breach of instructions under egulation 23 of the Monash University (Academic Board) Regulations or may constitute an act of academic misconduct under Part 7 of the
onash University (Council) Regulations.
Authorised Materials
CALCULATORS
DICTIONARIES
SPECIFICALLY PERMITTED ITEMS
if yes, items permitted are:
YES NO YES NO YES NO YES NO YES NO
Notes – Double Sided A4 x 5 IT2004 unit notes, FIT2004 lectures slides, Student’s personal notes
Page 1 of 23
nstructions
lease attempt as many questions as possible; each page is composed of questions from the same topic.
ead each question carefully. The marks associated with a question is not an indicator of the question difficulty or solution length. or algorithms and psuedocode questions, you are allowed to use either:
1. Structured indented text structure. 2. Numbered list.
est wishes and all the best!
Page 2 of 23
Instructions
Information
Please attempt as many questions as possible; each page is composed of questions from the same topic.
Read each question carefully. The marks associated with a question is not an indicator of the question difficulty or solution length.
For algorithms and psuedocode questions, you are allowed to use either:
1. Structured indented text structure. 2. Numbered list.
Best wishes and all the best!
Page 3 of 23
Correctness
Question 1
State a useful invariant for odd_prod. Use that invariant to prove that odd_prod calculates the product of all odd numbers in L.
Note that the empty product (i.e. multiplying no numbers together) is 1.
def odd_prod(L[1…n]): prod = 1
while i < len(L)
if L[i] % 2 == 1:
prod *= L[i]
return prod
Page 4 of 23
Complexity and Recurrence Relation
Question 2
Consider the algorithm for division by subtraction given below (assume that both inputs are always positive integers).
What is the big-O time complexity of this algorithm? Note that we do not want the best or worst case complexity, but rather an expression for the exact complexity.
Select one:
b. O(number)
c. O(divisor)
Question 3
Consider the following pseudocode for three-way merge sort. Which of the recurrences is an expression for the time complexity of this algorithm?
Note that merge() is a function which takes as input three sorted lists, and returns a single sorted containing all the elements from each of the inputs, and runs in linear time.
Def DivBySub(number, divisor) q=0
r = number
while r >= divisor
r -= divisor
return q, r
Def merge_sort(L[1..n]): if len(L) <= 1:
n = len(L)
A, B, C = L[1..(n//3)], L[(n//3)+1..(2n//3)], L[(2n//3)+1..n] A, C, C = merge_sort(A), merge_sort(B), merge_sort(C)
return merge(A, B, C)
Select one:
T(N) = 3T(N/3) + bN T(1) = c, T(0) = c
T(N) = 2T(N/2) + bN T(1) = c, T(0) = c
T(N) = 3T(N/3) + bN^2 T(1) = c, T(0) = c
T(N) = 3T(N/3) + b T(1) = c, T(0) = c
Page 5 of 23
Non-Comparison Sorts
Question 4
Given a list of N strings, where:
The longest string is M characters long.
Total number of unique character is C (i.e. the alphabet is of size C)
In each of the following two scenarios, determine which of stable insertion sort and stable radix sort
would be more time efficient. Briefly (1 sentence or so) justify your answer to each. 1. N is significantly larger than both M and C.
2. C is significantly larger than both M and N. Question 5
Given a list of N integers in a range of between 1 to K (assume integers take O(1) space).
Discuss the optimal auxiliary space complexity to sort this list in ascending orderusing Count Sort if:
1. The sorted list does not need to be stable and the original list does not need to be maintained. 2. The sorted list needs to be stable and the original list does not need to be maintained.
Note: Only providing the auxiliary space complexity without an explanation would result in no marks given.
Page 6 of 23
Quick Sort and Quick Select
Question 6
Consider a Quick Sort variant which uses 2 pivots to perform 4-way partitioning:
Partition 1 for items that are of lesser value than pivot 1.
Partition 2 for items that are of equal value with pivot 1.
Partition 3 for items with values between pivot 1 and pivot 2. Partition 4 for items that are of greater or equal value than pivot 2
Quick sort is then called recursively on Partition 1, 3 and 4.
State the best and worst-case time complexity for this Quick Sort variant, if thepartitioning can be
performed in O(N) time. Briefly explain when they occur. Question 7
Consider a list of exam results, represented as a list ofN unsorted positive integers with values from 0 to 100.
You realized that more than half of the class failed the exam. Thus, you are looking to moderate the results. You would want to moderate the results according to the following:
To pass the exam, a student requires at least 50 marks.
Exactly 60% of the class needs to pass the exam (don't worry about rounding the number of students up or down).
In order to increase the passing percentage to 60%, we will give some failed students bonus marks equivalent to difference between their current marks and 50.
Priority is given to the students that are the closest to the passing point. For example a student scoring 48 would be prioritised over a student scoring 45 for the bonus marks.
Describe an efficient algorithm using quick select to determine the total bonus marks to be given out; in O(N) time complexity with the assumption that you can partition a list in O(1) time.
Page 7 of 23
Dynamic Progrmamming
Question 8
Consider the following Dynamic Programming problem:
Given a rod of some length N, what is the optimal way to cut this rod up to obtain maximum profit?
You are given a list of pricesP[1..n] for each length from 1 to n, which is the amount of profit you will get for selling a rod section of that length.
Write down a definition of the overlapping subproblems (NOT the optimal substructure) for this problem.
Page 8 of 23
Hashtable and Dictionary
Question 9
The objective of a good hash function is to distribute keys more or less randomly in the table. Why then is it a bad idea to hash items to random positions in the table?
Question 10
What is the best and worst case time complexity for looking up an item into a separate chaining hash table, where the chains are implemented using AVL trees?
M is the size of the table (i.e. the number of AVL trees) N is the number of items currently in the table
What is the best case complexity? What is the worst case complexity?
Question 11
Consider the cuckoo hashing scheme which uses two arrays to store the values in the hashtable.State the worst case time complexitiesin big-O notation for the following operations, andbriefly justify each of your answers.
Deleting an item from a cuckoo hash table. Inserting an item into a cuckoo hash table.
• O(N) • O(1) • O(M) • O(log(N)) • O(log(M)) • O(N) • O(1) • O(M) • O(log(N)) • O(log(M))
Page 9 of 23
Self Balancing Tree
Question 12
What is the state of this AVL tree when 16 is deleted (after rebalancing)?
Select one: a.
Page 11 of 23
Page 12 of 23
Trie and Suffix Tree
Question 13
Consider a suffix trie generated from a string of size N.
Instead of an array, each node of the trie stores the children of that node with asorted linked list.
Briefly discuss:
1. A use of the trie/an operation performed on the trie in which such implementation is less time
efficient than the array implementation.
2. A use of the trie/an operation performed on the trie in which such implementation is more time
efficient than the array implementation.
Question 14
ConsiderastringS oflengthN.
You then perform the following step:
1. Generate all of the suffixes for the string, and store them in alist.
2. Insert all of the suffixes generated in step 1 into a suffix trie.
3. Compress the suffix trie generated in step 2 by compressing non-branching paths into a single
edge with [start, end] indices
What is the space complexity for the data structure in each step?
Select one:
2. O(N^2) 3. O(N)
2. O(N) 3. O(N)
2. O(N^2) 3. O(N^2)
2. O(N^2) 3. O(N)
2. O(N) 3. O(N)
Question 15
Briefly discuss how a suffix array can be constructed using a suffix trie for any given stringS.
Suffix Array
Question 16
Assume that we are constructing the suffix array for a string S using the prefix doubling approach. We have already sorted the suffixes for string S according to their first 2 characters; with the corresponding rank array shown below:
We are now sorting on the first 4 characters.
For the following pairs of suffixes, describe how will you compare them on their first 4 characters in
O(1), and what the resulting order would be.
1. Suffixes with ID 1 and ID 5 2. Suffixes with ID 3 and ID 5
Page 14 of 23
Burrows- (BWT)
Question 17
Consider a string S consisting of the following 5 characters (the characters are presented in no particular order): "$", "a", "a", "b", "c".
S contains the following 2-mers:
What is the 4th character (using 1-indexing) of the Burrows of S?
Select one: c
Question 18
The Burrows has TWO important properties that make it useful for compression. State these properties, and briefly explain why each of them are important for BWT to be useful for compression.
Page 15 of 23
Graph and Shortest Distance
Question 19
Consider the following pseudocode for Breadth First Search.
def BFS(G, s) visited[1...n] = False visited[s] = True
q = Queue()
while not q.isEmpty()
current = q.pop()
for each vertex v adjacent to u
if not visited[v]
visited[v] = True
What is the time complexity of this code in big-O notation if the graph is implemented as an adjacency matrix?
What is the time complexity of this code in big-O notation if the graph is implemented as an adjacency list?
Question 20
Consider the following graph.
• O(V+E) • O(ElogV) • O(E^2) • O(V^2) • O(V+E) • O(ElogV) • O(E^2) • O(V^2)
After some number of iterations of Bellman-Ford, the distance values to each vertex are as shown in the table below.
What would the distance values be after one more iteration of ? Please choose the appropriate value for each vertex from the drop-down options.
Assume that the edges are being processed in the following order: a->b, a->c, b->d, c->b, d->c, s->a, s- >b
What is the distance to s after iteration 2? What is the distance to a after iteration 2? What is the distance to b after iteration 2? What is the distance to c after iteration 2? What is the distance to d after iteration 2?
• -3 • -2 • 1 • 2 • 3 • -1 • 0 • -3 • -2 • 1 • 2 • 3 • -1 • 0 • -3 • -2 • 1 • 2 • 3 • -1 • 0 • -3 • -2 • 1 • 2 • 3 • -1 • 0 • -3 • -2 • 1 • 2 • 3 • -1 • 0
Page 16 of 23
Question 22
Consider the following pseudocode for Dijkstra’s algorithm. The priority queue contains the values in V (i.e. the vertices in graph G) and is ordered based on the values in dist.
def dijkstra(G(V,E), s) dist[1..n] = inf pred[1..n] = None dist[s] = 0
q = priority_queue(V[1..n], dist[1..n]) while not q.is_empty()
u = q.pop_min()
for each edge (u,v,w)
if dist[u] + w < dist[v]
dist[v] = dist[u] + w
update priority queue based on new distance for v
return dist, pred
In this pseudocode, the pred array is not being updated.
1. Write down the line of pseudocode which needs to be added to the algorithm above in order to update pred correctly, and state between which two lines it should be inserted.
2. Write an algorithm, path(u, v, pred) which determines the shortest path from vertex u to vertex v. The algorithm path takes as input two vertices u and v, and the array pred which Dijkstra's algorithm produces as output.
The output of path should be a list where thefirst element is u, the final element is v, and the elements in between are the vertices on the shortest path from u to v, in order.
Question 21
Consider a weighted, directed graph G with V vertices and E edges. The edge weights may be negative. Describe how the standard Floyd-Warshall algorithm can determine if graph G contains a negative
Discuss a modification which could be made to the standard Floyd-Warshall algorithm to achieve the fastest possible best case time complexity for this.
Page 17 of 23
Graph and Minimum-Spanning Tree
Question 23
Consider a weighted, connected graph G with V vertices and E edges. All of the edges E for the graph are weighted with negative values.
The Kruskal minimum spanning tree algorithm can be used to obtain the minimum spanning tree for graph G by sorting the edges in increasing order.
Briefly discuss and justify how the graph G can be preprocessed to work withKruskal algorithm as described above to obtain the maximum spanning tree for G.
Page 18 of 23
Direct Acyclic Graph
Question 24
In a graph G, it is possible that all topological orderings of the vertices of G share some common prefix (i.e. there is no choice for these vertices, they must appear in the same order in all topological orderings of the graph). We will refer to these vertices as a common prefix of all topological orderings of G.
Consider a directed acyclic graph (DAG) G of V vertices and E edges; represented using an adjacency matrix. You want to obtain a topological sort of the vertices using the Kahn's algorithm.
Describe briefly how you would implement Kahn's algorithm in order to:
1. Determine when a vertex can be added to the queue in O(1) time complexity. 2. Determine if a vertex belongs to the common prefix of G.
Page 19 of 23
Network Flow
Question 25
Consider the following pair of vertices in a flow network.
There is an edge with capacity 5 from vertex a to vertex b, with a flow of 4.
There is an edge with capacity 7 from vertex b to vertex a, with a flow of 2.
Which of the following scenarios corresponds to this pair of vertices in the residual graph?
Select one: a.
Page 20 of 23
Page 21 of 23
Question 26
What is the maximum possible flow in the flow network below?
Page 22 of 23
Question 28
You are scheduling FIT2004 exams for the students.
There are 5 possible timeslots available for the exam. Each timeslot has a randomized set of questions from a database of 1000 exam questions.
Each student could only attend a single timeslot; but the student can select 3 of the timeslots as their preferred timeslots.
Each timeslot could only fit up to 50 students.
You come to the realization that you are not able to fit all of the students to their preferred timeslots.
The exam questions will still be randomized irrespective of the timeslots.
However, you would like to satisfy as many of the students' preferred timeslots as possible.
1. Describe how to model this problem as a maximum flow problem.
2. State how you would solve the problem algorithmically, once it was modeled as a maximum flow
Question 27
A minimum cut is a partition of the vertices of a network into two sets, S and T, such that: The source is in S, the sink is in T.
The capacity of the edges which are directed from S to T is minimum. Which edges are in the minimum cut in the network shown below?
Select one or more: s->a
d->t s->b b->d a->c c->t
Page 23 of 23