Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Practice Final Exam, Semester 2, 2022

COMP20003 Algorithms and Data Structures

Question 1

A well-known artist is moving to Melbourne to live close to his family. He has a very big family, all of them living in the same street called Artists Avenue. He paid you to find the perfect house location number in the street that will minimize the total distance to all of his relatives.

You are given a variable (int nRel = N), indicating the number of relatives is N, and an array of integers containing the exact street number of each relative (int stNum[N]). Street numbers are positive integer values, and the distance between two street number is . Therefore the solution you are looking for is the street number x that minimizes the total distance .

For example if nRel = 3 and stNum = { 2, 4, 6 }, then your program should tell the artist to live in street number 4, as it will minimize the total distance to his relatives to 4. The distance to relative will be 2 (|4 - 2|), to relative is 0 (|4 - 4|), and to relative is 2 (|4 - 6|).

Before you write the code, take some time to think.

(a) (6 points) Write the function int total_dist(int x, int nRel, int* stNum) that given the selected street number x, the number of relatives, and street numbers array, returns the total distance to the selected street number x.

(b) (10 points) Write the main function in which you will: read the number of relatives using "scanf"; create an array of street numbers, allocating memory for this array and initializing it by assigning a street number randomly to each relative (assume int rand() gives you a random positive integer number, and no integer overflow occurs in your program). Call the "total dist" function accordingly to find the best street number, and print the final answer with the street number and the total distance. Last but not least, free your memory. You do not need to write the include statements.

(c) (2 points) We will take into account best practice use of C (1 mark), and readability (1 mark).

You should write the code below. Include brief comments in the code to explain your reasoning and help with readability.

Question 2

p 0 words Prove that is in . Provide values for and . </>

Question 3

Suppose you must write an algorithm to reverse the order of items in a linked list.

So for example, the linked list:

would become:

(a) (1.5 points) Describe a method to reverse the linked list that would minimize the time required.

(b) (1.5 points) Describe a method to reverse the linked list that would minimize the space required (this can be the same method as in (a)).

In each case, assume the linked list contains n items and n is very large. You should discuss both the big-O performance and the approximate actual time/space required to justify your design choices. You may use code or pseudo code to explain your method but this is not required; a clear description is sufficient.

Question 4

An online retailer has set up a database to store information about the products for sale on their website. The database is implemented as a hash table that uses chaining to resolve collisions. The key used to hash items into the table is the product ID number. The hash table array size is n and m products have been inserted into the database.

Some product IDs appear in the database more than once. The retailer asks you to write an efficient algorithm that will take a product ID and count how many times that product ID occurs in their database.

(a) (1.5 points) What is the expected average-case time complexity of this algorithm?

(b) (1.5 points) What is the worst-case time complexity of this algorithm?

Give the closest upper bound in big-O notation, and briefly explain how the algorithm would work in order to justify your choice of big-O in each case. You may use code or pseudo code to explain your method but this is not required; a clear description is sufficient.

Question 5

Given the following heap:

[72, 40, 59, 31, 11, 26, 3, 14, 29, 8]

Show the array representation of the heap after deleting the maximum element and fixing the heap (deletemax). You may use any representations you like to work out the problem, but make sure your answer shows the array in its final state. Feel free to upload an image if you prefer to work on paper.

Question 6

Dijkstra’s algorithm for single source shortest paths on a directed, weighted graph uses a priority queue to get the next edge with the minimum weight. For each of the following implementations of a priority queue, give the least upper bound big-O complexity of Dijkstra’s algorithm, in terms of V, the number of vertices in the graph, and E, the number of edges in the graph. Explain your answers briefly.

(a) (2 points) A heap is used for the priority queue.

(b) (2 points) A linked list sorted by weight is used for the priority queue.

(c) (2 points) An Balanced Binary Search Tree is used for the priority queue.

(d) (2 points) What is the big-O difference between a heap and BST priority queue? Is there any reason you should prefer one over the other?

Question 7

Build a 2,3,4-tree by inserting the following keys:

[6, 3, 7, 5, 1, 2, 4]

What is the final tree that results from inserting these keys in the order given above? Show the intermediate trees that are produced as the keys are inserted and indicate any steps in which a key is promoted.

Please scan/photograph your diagram(s) and include the image(s) in the space below.

Question 8

Suppose you need to sort a binary array (meaning, each element of the array is either 0 or 1) of length n.

(a) (2 points) What is the most efficient method to sort the array and what is this method's worst-case time complexity? You can assume there are no limitations on memory space.

(b) (2 points) Suppose that memory space is limited, so you are required to sort this array using an in-place sort. What is the most efficient method and what is its worst-case time complexity?

Give the closest upper bound in big-O notation, and briefly explain how your algorithm would work in order to justify your choice of big-O in each case. You may use code or pseudo code to explain your method but this is not required; a clear description is sufficient.

Question 9

Consider the algorithm described by the following recurrence relation and answer the questions below.

You may wish to refer to the Master Theorem:

The three cases of the Master Theorem:

if

, then

if

, then

if

, then

(a) (1 point) What is the depth of the recursion tree (the number of time the function recurses)?

(b) (1 point) What is the time complexity of the algorithm ?

Question 10

Prim’s algorithm constructs a Minimum Spanning Tree (MST) of a connected, weighted graph G(V, E). In this question you are asked to sketch a small enhancement to the traditional Prim’s algorithm that would enable it to construct an MST for each connected component of an unconnected, weighted graph G before terminating.

For your convenience, a brief description of Prim’s algorithm is given below, as described in lectures and in your textbook.

In Prim’s algorithm, the MST grows by adding a new vertex v from the “fringe”, that is vertex v is not yet in the tree and also has an edge (u, v) to a vertex u that is already in the tree. Vertices in the fringe are stored in a priority queue, according to their least weight edge w(u, v) to a vertex in the MST. The vertex with the minimum edge weight w(u, v) is picked and removed from the priority queue. Once a vertex v is put into the MST, each vertex reachable from vertex v and not yet in the MST is added to the priority queue, or if already in the priority queue has its weight (priority) and predecessor updated if appropriate.

Prim’s algorithm can start with any vertex in G, and terminates when the priority queue is empty (or, depending on implementation when all vertices in the priority queue have weight ∞). Auxiliary arrays are used to keep track of predecessors, edge weights, and whether or not a vertex is in the MST.

Only a connected graph can have a minimum spanning tree, and Prim’s algorithm works only on connected graphs. Vertices that cannot be reached from the growing MST are not inserted into the priority queue (or, depending on implementation, remain in the priority queue weight ∞ and are never updated or deleted).

Sketch briefly, in words or pseudocode, a small enhancement you could make to Prim’s algorithm that would enable it to construct an MST for each connected component of an unconnected, weighted graph G before terminating

Question 11

Consider a connected weighted directed graph G = (V, E, w). Define the fatness of a path P to be the maximum weight of any edge in P. Give an efficient algorithm that, given such a graph and two vertices u, v ∈ V, finds the minimum possible fatness of a path from u to v in G.

Question 12

A workshop building cars gives you a graph with a set of tasks and the relationships indicating which tasks have to be completed before other ones. You need to figure out in which order you should schedule the tasks in order to build the car. Explain how would you model this problem as a graph, and which algorithm with worst-case complexity O(E) would you use to find a solution.