# FIT2004 代写代考 Algorithms And Data Structures 算法数据结构 –

FIT2004 Exam ~ Semester 2, 2020

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.

Question 2 Consider the algorithm for division by subtraction given below (assume that both inputs are always positive integers).

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.

Question 4

Given a list of N strings, where: • ThelongeststringisMcharacterslong. • 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 order using 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. Answer: • O(K) for unstable as we just need to count the frequency and the original list value can be replaced. • O(K+N) for stable as we need to store the relative ordering of the items in the list. Note: We are using integer here, we can assume each integer takes O(1) space to store in the list.

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 the partitioning can be performed in O(N) time. Briefly explain when they occur. Answer: • Best case is O(N) when all items are equal to pivot 1, leaving partition 1, 3 and 4 empty without needing to recurse again. • Worst case is O(N^2) when all items end up in partition 1, 3 or 4 with the other partitions having only 1 item.

Question 7

Consider a list of exam results, represented as a list of N 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. Answer: Algorithm must mention: • Quick select to get the top 60% of the original list • Loop through this partition and sum up the difference from the passing mark of 50

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 prices P[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. Answer: Memo[i] = {The maximum profit that can be obtained by optimally cutting a rod of length i}

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? Answer: Since hash tables need to be able to look values up, hash functions need to be deterministic so that when an item is hashed to some position, we know where to find it later. Note: Just saying a random hash is bad/unusable is not enough, since that information is given in the question.

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 Answers: What is the best case complexity? → O(1) What is the worst case complexity? → O(log(N))

Question 11

Consider the cuckoo hashing scheme which uses two arrays to store the values in the hashtable. State the worst case time complexities in big-O notation for the following operations, and briefly justify each of your answers. • Deleting an item from a cuckoo hash table. • Inserting an item into a cuckoo hash table. Answer: Deletion: O(1) This is because there are only two locations the item can be, and when we find it we can delete it without any additional work. Insertion: There are a few possible answers here: • Best answer: O(maxloop) where maxloop is some predefined cutoff. The insertion terminates after a fixed number of iterations in order to prevent an infinite loop. • Alternative answer: infinite/unbounded. It is possible for cuckoo hashing to keep kicking items out in a cycle which never ends.

Question 12

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?
• What is the distance to s after iteration 2? → 0,
• What is the distance to a after iteration 2? → 1,
• What is the distance to b after iteration 2? → -3,
• What is the distance to c after iteration 2? → -1,
• What is the distance to d after iteration 2? → 0
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 cycle.
Discuss a modification which could be made to the standard Floyd-Warshall algorithm to achieve the fastest possible best case time complexity for this.
• The diagonal for the matrix is initialized to 0. If there is a negative value on the diagonal at any point we have detected a negative cycle

• Best case when the first intermediate vertex form a negative cycle in O(1) for a vertex back to itself. We can terminate immediately in this case.

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.

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 problem.