2020 Semester One Deferred & Supplementary (August 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
SPECIFICALLY PERMITTED ITEMS if yes, items permitted are:
YES NO YES NO YES NO
nstructions
Page 1 of 20
lease attempt as many questions as possible. Each page is composed of questions from the same topic.
est wishes and all the best!
Page 2 of 20
Instruction
Information
Please attempt as many questions as possible. Each page is composed of questions from the same topic.
Best wishes and all the best!
Page 3 of 20
Complexity
Question 1
Consider the function mystery(N, M) shown below:
What is the recurrence relation for the time complexity of mystery(N, M) function?
Select one: A.
Page 4 of 20
Question 3
Consider a Graph G with vertices V and edges E.
The pseudocode below attempts to store thedegree for each vertex v in V.
What is the time and space complexity of the pseudocode above? Explain your solution.
Question 4
Consider a prefix Trie T built from N words with the longest word having M characters. None of the words are stored in the Trie (even at the leaves). Each node only stores a single character (except the root, which does not store any characters).
For a given query word Q, what is the time complexity to print out all the words intrie T with the query word Q as the prefix? Reason out your time complexity.
Question 2
Consider the function mystery(N, M) shown below:
What is the auxiliary space complexity of mystery(N, M) function? Explain your answer.
Page 5 of 20
Non-Comparison Sorts
Question 5
Given two strings of length N and M. What is the best and worst case time complexity to compare these strings in a comparison-based sorting algorithm?
Question 6
Consider radix sort for a list of N strings, where the strings are sorted by running a count sort on each column, right to left. Discuss using examples why there is a need for the count sorts to bestable
in ensuring correctness, and whether ensuring stability incurs any costs.
Page 6 of 20
Quick Sort and Quick Select
Question 7
Consider a standard Quick Sort implementation with the following approaches: Approach 1: Perform 2-way partitioning for < pivot and >= pivot
Approach 2: Perform 3-way partitioning for < pivot, == pivot and > pivot
State the best and worst-case time complexity for each of the approaches. Briefly explain when they
Question 8
Consider a list of N positive integers.
Describe a linear time algorithm (using high level plain language) to find the item in a list whose value
is closest to the average of the i-th and j-th largest elements in a list.
You may assume that you have a Quick Select function that operates in linear time complexity.
Page 7 of 20
Dynamic Programming
Question 9
Consider the standard knapsack problem. You are given a set of items, each with a weight and a value, and each item can only be used once. You have a knapsack of some capacity, and you wish to determine which combination of items has:
The highest total value
Has a total weight less than or equal to your knapsack’s capacity
This problem can be solved using Dynamic Programming. Write the definition for the set of overlapping sub problems which need to be solved in order to solve the knapsack problem.
Question 10
Give an example of a problem which can be solved using dynamic programming, where the space complexity of the DP algorithm which solves it is lower than the time complexity.
Briefly explain how this is achieved.
Page 8 of 20
Question 11
What is the best case and worst case time complexityto insert an item into a Hashtable containing N items. The Hashtable is implemented using Separate Chaining with AVL Trees. Explain your complexity.
Question 12
Consider a Hashtable implemented using Cuckoo Hashing with the following criteria: There are 3 tables, A B and C.
H1, H2, H3 are the hash functions for tables A, B and C respectively.
Describe in plain words how you would implement an algorithm toinsert a
Page 9 of 20
Question 13
What is the state of the following AVL tree after the deletion of 48?
Select one: A.
Page 10 of 20
Page 11 of 20
Trie and Suffix Tree
Question 14
Consider the suffix trie of the string aabaabba (shown below). How many nodes (including the root) will the corresponding suffix tree have?
Select one:
Question 15
Consider a Suffix Trie T generated from a String S.
Describe how and why the suffix trie T can be used to determine ifquery Q is a substring of string S with a time complexity of O(Q).
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 4 characters; with the corresponding rank array shown below:
We are now sorting on the first 8 characters.
Describe how will you compare the following two suffixes on their first8 characters in O(1):
Suffixes with ID 2 and ID 3 Suffixes with ID 3 and ID 9
Page 13 of 20
Burrows- (BWT)
Question 17
Suppose you are performing the naive algorithm to invert of BWT. The given BWT string is b$baaa
You have computed the following 2-mers.
Write down the 3-mers (in lexicographical order) which would be obtained after one more iteration of the algorithm. Write each 3-mer on a separate line, with no spaces between the characters
Question 18
Consider the problem of searching for all occurences of the substring “ab” in the string “aaabaabbaaba”. We want to solve this using the transform substring search algorithm. The diagram below shows the sorted characters of the string in the third column and the BWT of the string in the fourth column. The second column shows the indices, and the first column shows the suffix array.
The general idea of the algorithm is:
1. You have a start and end character in the BWT, which define arange (initially 1 and the last position)
2. You contract that range appropriately
3. Use the LF mapping to obtain a newrange
4. If you have processed the pattern, stop and return the appropriate suffix array indices.
5. Proceed by one character in the substring we are searching for, and go back to step 1
What are the start and end indices of the ranges during the search for “ab” after each step 3
Page 14 of 20
Select one:
(2,9), (10,12)
(10,13), (7,9)
(2,11), (5,10)
(1,13), (2,11)
(10,13), (2,4)
Page 15 of 20
Graph and Shortest Distance
Question 19
Consider the following 2 approaches to dealing with the priority queue when implementing Dijkstra’s algorithm. In the following descriptions, “key” refers to the distance value of each vertex which is used to order the priority queue.
Approach 1 – Initialise the priority queue with all the vertices of the graph. Set their keys to infinity, and set the key of the source to 0. Whenever relaxation occurs, update the corresponding key in the priority queue.
Approach 2 – Initiliase the priority queue with the source vertex, with a key of 0. Whenever relaxation occurs for a vertex v, add a new element to the priority queue with key = the new distance forv and value = v. When removing an element from the priority queue, if that vertex has already been finalised (i.e. already been processed by the algorithm), just discard it.
State, for each approach, the total complexity (i.e. the total cost over the lifetime of the algorithm) of performing
1. The extract_min operations
2. The relaxation operations (and the associated priority queue updates)
Justify your answers
Question 20
The Bellman-Ford algorithm for computing single-source shortest paths in a graph with negative weights can be optimised so that it has the ability to terminate early.
Explain how this can be done and state the best case time complexity of the resulting algorithm.
Page 16 of 20
Question 21
The Floyd Warshall all pairs shortest path algorithm works as follows:
– Iterates over all the vertices in the graph. Call the current vertex “k”.
– For each k, look at every pair of vertices i,j . Try to find a path from i to j passing through k, which is
shorter than the current shortest path from i to j. Let us call k the “detour” vertex.
Suppose that you have the following distance matrix just before using vertex D as the detour vertex. What is the state of the matrix after the iteration in which D is used as the detour vertex?
Please format your answer like this:
x,x,x,x;x,x,x,x;x,x,x,x;x,x,x,x
Where the “x” are replaced by the values in the distance matrix. “,” indicates a new element, and “;” indicates the end of a row.
The values should be left to right, top to bottom. Represent infinity as “inf”.
For example, the state shown in the diagram above would be: 0,-7,1,-5;inf,0,8,2;inf,inf,0,inf;4,inf,5,0
Page 17 of 20
Graph and Minimum-Spanning Tree
Question 22
Consider the following Union-Find data structure (Linked Trees with Size) for a Kruskal’s algorithm at some step k in finding a Minimum Spanning Tree (MST):
Then in plain words, answer the following:
What is the size of the largest tree? What are the vertices in the largest tree?
Describe the steps which would occur when performing theunion(2,9) operation. Question 23
Describe an algorithm to determine if a graph G with V vertices and E edges have a unique Minimum Spanning Tree (MST) in a time complexity of O(E log V).
If a unique MST exist, return the edges that form the MST. Else, return False.
Page 18 of 20
Directed Acyclic Graph
Question 24
You are overseeing the development of an app. There are many features to implement, and some features rely on other features. Consider a Directed Acyclic Graph G with vertices V and edges E , where each vertex corresponds to a feature. There is an edge from feature A to feature B if feature A must be implemented before work can start onfeature B.
Your superior has decided the project will be broken up into “phases”. Each phase consists of implementing four features, but it does not matter which four, the phases are purely for marketing hype.
So the first four features will comprise phase 1, and the next four will comprise phase 2, etc. Note that if feature B requires feature A, they can both be implemented in the same phase, provided A is implemented first.
Describe an algorithm that returns the first phase in which you have a choice about which features to implement.
As an example, consider the following DAG:
F cannot be started until C and D are complete. E cannot be started until F and C are complete, so A,B,C,D must be completed before F or E can be started. Although they can be completed in different orders, phase 1 will always comprise A, B, C and D, so there is no choice.
In Phase 2, we must complete F, then E, and then we have 3 features we could implement next, but we only need 2 more features to finish phase 2. Therefore, we have a choice in what features we implement in phase 2, so the solution would be 2.
Page 19 of 20
Network Flow
Question 25
You are running a conference. The plan is to have the attendees eat at various local restaurants.
Each attendee has indicated several places they would be happy to eat dinner.
Each dining place has informed you of the most conference attendees that can eat there.
You are concerned that it will not be possible to allow everyone to eat where they would prefer, but you want to let as many people as possible eat at one of their preferred places.
What is the largest number of attendees who can eat at a restaurant for which they have a preference?
1. Describe how to model this problem as a maximum flow problem.
2. State how you would solve the problem, once it was modeled as a maximum flow problem.
Question 26
Consider the following flow network with source s and sink t. Currently there is a flow of 4 units in this network. Determine the maximum flow which can be sent through this network. Write your answer as a number, using digits (not words).