### 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
```