2021 Semester One (June 2021)
Network | 作业network | Algorithm作业 | mining代做 | oop代写 – 本题是一个利用network进行练习的代做, 对network的流程进行训练解析, 涵盖了Network/network/Algorithm/mining/oop等方面
Examination Period
Faculty of Information Technology
TITLE OF PAPER: Algorithms and data structures
EXAM DURATION: 2 hours 10 mins
Rules
During an exam, you must not have in your possession any item/material that has not been authorised for your exam. This includes books, notes, paper, electronic device/s, mobile phone, smart watch/device, calculator, pencil case, or writing on any part of your body. Any authorised items are listed above. Items/materials on your desk, chair, in your clothing or otherwise on your person will be deemed to be in your possession.
You must not retain, copy, memorise or note down any exam content for personal use or to share with any other person by any means following your exam.
You must comply with any instructions given to you by an exam supervisor.
As a student, and under Monash Universitys Student Academic Integrity procedure, you must undertake your in-semester tasks, and end-of-semester tasks, including exams, with honesty and integrity. In exams, you must not allow anyone else to do work for you and you must not do any work for others. You must not contact, or attempt to contact, another person in an attempt to gain unfair advantage during your exam session. Assessors may take reasonable steps to check that your work displays the expected standards of academic integrity.
Failure to comply with the above instructions, or attempting to cheat or cheating in an exam may constitute a breach of instructions under regulation 23 of the Monash University (Academic Board) Regulations or may constitute an act of academic misconduct under Part 7 of the Monash University (Council) Regulations.
Authorised Materials
OPEN BOOK YES NO
CALCULATORS YES NO Calculator
DICTIONARIES YES NO
NOTES YES NO Notes – Double Sided A4 x 5 Max
SPECIFICALLY PERMITTED ITEMS YES NO
if yes, items permitted are: FIT2004 Unit Notes
Instructions
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 pseudocode questions, you are allowed to use either:
1. Structured indented text structure.
2. Numbered list.
Best wishes and all the best!
You are permitted to download the Notes from the link below for this exam.
Unit notes
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 pseudocode questions, you are allowed to use either:
1. Structured indented text structure.
2. Numbered list.
Best wishes and all the best!
You are permitted to download the Notes from the link below for this exam.
Unit Notes
Correctness
Question 1
Consider the following Algorithm to determine the parity of the sum of a list.
Note that not 0 = 1, not 1 = 0.
def parity(L[1..n])
p = 0
i = 1
###here###
while i <= n
if L[i] % 2 == 1
p = not p
i += 1
return p
Write down a useful invariant for the algorithm above. Your invariant must be true at the line marked
with the comment "###here###", i.e. just before the check of the while condition.
####### 1
Mark
Question 2
Show that the invariant you identified in Question 1 holds at the line marked #Here, before the l oop is
entered for the first time. 0.
Mark
Question 3
Show that your invariant is true at the line marked ###here### each time the loop runs (excluding i=1,
since you will have proved that in Question 2.
Make sure your argument is logically sound.
####### 3
Marks
Question 4
Since you have now shown that the invariant you chose in Question 1 holds for all iterations of the
loop, now argue that the algorithm is correct. 0.
Mark
Complexity and Recurrence Relation
Question 5
f(n) is (g(n)) means that f grows asymptotically as fast g, as opposed to O(g(n)) which only gives an upper bound.
For a constant c, consider the recurrence relation given by:
T(n) = c ; if n=
T(n) = 2*T(n/2) + c*n ; if n>1.
Which of the following statements is true?
Select one:
####### 3
Marks
2
a.
T(n) = (n^2 )
b.
T(n) = (n^2 * log n)
c.
T(n) = (n^2 * log n * log n)
d.
T(n) = (n^3 )
e.
T(n) = (n^3 * log n)
Question 6
Given an algorithm which runs in O(NlogN) time, which of the following are possible auxiliary space
complexities for this algorithm?
Mark all that are possible.
Select one or more:
a.
O(1)
b.
O(N)
c.
O(NlogN)
d.
O(N^2)
####### 1
Mark
Question 7
What is the auxiliary space complexity of the following algorithm (expressed in big-O)?
The input n is always a positive integer.
f(n):
lst = [None]*n
for i in range(n):
lst = [i] * n
Select one:
####### 1
Mark
a.
O(1)
b.
O(log(N))
c.
O(N)
d.
O(N^2)
Quick Sort and Quick Select
Question 8
Consider a list of lap times for a stage in the game of Fall Guys for Twitch Rivals, represented as a list
of N unsorted positive floats with values from 0.0 seconds to 100.00 seconds.
To pass this stage, participants would need to clock in a lap time no more than 20.0 seconds.
As the game master however, you would want at least 30% of the players to move on to the next stage;
with the following rules:
If you are within the top-30% fastest time and within the 20.0 seconds requirement, you would move
onto the next stage without any issues.
If you are within the top-30% fastest time but is above the 20.0 seconds requirement, then you
would be penalized for the next round. The penalty is how much slower are you compared to the
median of the top-30% ; if the time is below the median then there is no penalty.
Describe an efficient algorithm using quick select to determine the sum of all penalties ; in O(N) time
complexity with the assumption that you have access to a quickselect algorithm which runs in O(N)
time.
####### 3
Marks
Dynamic Programming
Question 9
For this question you must answer in the following format:
Write the indices of the houses that you have chosen, in ascending order, separated only by a single
comma with no spaces. For example if the answer were houses 7, 8 and 9, you would write 7,8,
Recall the following problem from the Dynamic Programming studio :
You are trying to sell to a row of houses. You know the profits which you will earn from selling to each
house 1..n. If you sell to house i, you cannot sell to houses i+1 or i-1. What is the maximum profit you
can obtain?
Suppose that you have following DP array, where cell i of the DP array contains the maximum profit you
can obtain by selling to a subset of houses 1..i.
Determine which houses you should sell to in order to maximise your profit (i.e determine the optimal
solution to the problem which this DP array is solving).
i 1 2 3 4 5 6 7
DP[i] 20 20 30 50 60 100 100
####### 2
Marks
Hash Tables and Dictionary
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 Binary Search Trees (BST)?
M is the size of the table (i.e. the number of BST)
N is the number of items currently in the table
What is the best case complexity?
- O(N + M) O(M) O(N) O(1) O(log N)
- O(log M)
What is the worst case complexity?
- O(N + M) O(M) O(N) O(1) O(log N)
- O(log M)
####### 2
Marks
Self-Balancing Trees
Question 11
Which of the following would be the result of deleting 48 from the following AVL tree?
Select one:
####### 1
Mark
a.
b.
c.
d.
Trie, Suffix Tree and Suffix Arrays
Question 12
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.
a) Provide an example of two suffix IDs whose relative order has not been determined at this point. Justify
your example.
b) Describe how this situation is resolved in the current iteration of prefix doubling.
c) State the resulting order between the suffixes in your example, after this resolution.
####### 2
Marks
Burrows-Wheeler Transform (BWT)
Question 13
Consider the following information ( indices in this question start from 1 )
BWT:bccb$bbaaaaaa
occ: 0011023012345
The rank array for the BWT above:
$ a b c
1 2 8 12
Note:
occ[i] is the number of times the character at BWT[i] occurs in the BWT before position-i
rank[c] is the position that character c would first appear in the sorted characters of the BWT
These definitions are the same as in the lectures.
What is the index in the BWT of the character preceding the character at
index 1? (recall that we are using 1-indexing in this question)
####### 7 3 2 10 13 1 6 5 12 8 11 4
####### 9
What is the index in the BWT of the character preceding the character at
index 10? (recall that we are using 1-indexing in this question)
####### 7 3 2 10 13 1 6 5 12 8 11 4
####### 9
####### 2
Marks
Question 14
Consider the following statement:
The result of applying run-length encoding on the Burrows-Wheeler transform of a string is never bigger than the
result of applying run-length encoding on the original string.
Select one:
####### 1
Mark
True
False
Question 15
Consider the following information (indices in this question start from 1)
BWT:b c c b$bbaaaaaa
occ[$] 0 00 00111111111
occ[a] 0 00 00000123456
occ[b] 0 11 12234444444
occ[c] 0 01 22222222222
rank array for the BWT above:
$ a b c
1 2 8 12
Note:
occ[c][i] is the number of times the character c occurs in the BWT before position-i
rank[c] is the position that character c would first appear in the sorted characters of the BWT
These definitions are the same as in the lectures.
Suppose we are performing substring search for the query string "aba". At
the start of the first iteration, in which we are looking for the last "a" in the
query, the start and end indices are 1 and 13. At the end of this iteration, the
start index will be 2. What will the end index be?
####### 7 9 8 13 5 1 6 10 12 4 2 11
####### 3
Suppose we are performing substring search for the query string "aba". At
the start of the third iteration, in which we are looking for the first "a" in the
query, the start and end indices are 9 and 11. At the end of this iteration, the
end index will be 5. What will the start index be?
####### 7 9 8 13 5 1 6 10 12 4 2 11
####### 3
####### 2
Marks
Graph Representation
Question 16
For each of the following operations, determine its time complexity.
In this question,
V refers to the number of vertices in the graph
E refers to the number of edges in the graph
N(x) refers to the number of neighbors of vertex-x.
Assume that in the adjacency list representation, the interior lists are unsorted.
Deter mining if an edge from u to v exists in an adjacency matrix O(V+E)^ O(N(u))^ O(V^2)^ O(1)^ O(V)
Determining if an edge from u to v exists in an adjacency list O(V+E)^ O(N(u))^ O(V^2)^ O(1)^ O(V)
Finding all neighbors of u in an adjacency matrix O(V+E)^ O(N(u))^ O(V^2)^ O(1)^ O(V)
Finding all neighbors of u in an adjacency list O(V+E)^ O(N(u))^ O(V^2)^ O(1)^ O(V)
Performing a complete BFS traversal in an adjacency matrix O(V+E)^ O(N(u))^ O(V^2)^ O(1)^ O(V)
Performing a complete BFS traversal in an adjacency list O(V+E)^ O(N(u))^ O(V^2)^ O(1)^ O(V)
####### 3
Marks
Graph and Shortest Distance
Question 17
Consider the following version of the Bellman-Ford algorithm :
and the following directed graph
Let S be the source node for the execution of the Bellman-Ford algorithm.
If the edges are relaxed in the following order (S,B), (A,C), (B,C), (S,A), (B,A), (C,E), (D,E), (A,D), (B,D).
What is the value of dist[C] after the first iteration of the outer loop is done?
Select one:
####### 1
Mark
a.
dist[C]=
b.
dist[C]=-
c.
dist[C]=-
Question 18
What is the value of dist[D] after the first iteration of outer loop of Bellman-Ford in the scenario above?
Select one:
####### 1
Mark
a.
dist[D]=
b.
dist[D]=-
c.
dist[D]=-
Question 19
What is the value of dist[E] after the first iteration of outer loop of Bellman-Ford in the scenario above?
Select one:
####### 1
Mark
a.
dist[E]=
b.
dist[E]=-
c.
dist[E]=-
Question 20
Consider the Floyd-Warshall algorithm
and the following directed graph
After the outer loop of the algorithm finished two iterations , what is the sum of all values in the array
dist that are not equal to infinity? Just type the numerical answer without punctuation or spaces.
####### 2
Marks
Directed Acyclic Graph
Question 21
How many distinct topological orderings does the following directed acyclic graph have?
Just type the numerical answer without punctuation or spaces.
####### 3
Marks
network Flow
Question 22
Which edges comprise the minimum cut in this network?
Select one or more:
####### 1.
s->a
####### 2.
s->b
####### 3.
b->a
####### 4.
a->c
####### 5.
b->d
####### 6.
c->d
####### 7.
c->t
####### 8.
d->t
####### 1.
Marks
Question 23
What is the maximum possible flow from s to t in this network?
Write your answer with digits , not as a word.
####### 1.
Marks
Applications of Algorithms and Data Structures
Question 24
Consider a directed graph with V vertices and E edges.
Assuming that E is greater than or equal to V-1, describe a method with time complexity O(EV) for
detecting if the graph has a negative cycle or not.
####### 3
Marks
Question 25
There are:
n objects v, v, …, v
Their pairwise distances dist(v, v)
It is assumed that dist(v, v)=0 for any object v, and that for any distinct objects vand vit holds that
dist(v, v)=dist(v, v)>0.
For a value 1<k<n, we want to partition the objects in k non-empty sets C, C, ..., C the so called clusters, in such
way that the minimum distance between any pair of objects assigned to distinct clusters is as big as possible.
Give a high-level description of a method with time complexity O(n log n) for finding an optimal solution for the
partitioning.
Hint: an optimal solution to this application can be found using a trivial adaption of an algorithm extensively
covered in this unit
####### 5
1 2 n Marks
i j
i i i i j
i j j i
1 2 k,
2
Question 26
You are scheduling FIT2004 exams for the students.
There are 3 possible venues available for the exam.
Each venue could only accommodate up to 200 students.
The university has allowed each student to state their venue preference:
There are 400 students in total.
Each student could select 2 venues as their preferred venues.
You come to the realization that you are not able to fit all of the students to their preferred venues.
However, you would like to satisfy as many of the students' preferred venues as possible.
Describe how you would model this problem as a flow network ; which is then solved using the Ford-Fulkerson
method.
####### 3
Marks