COMP 103 Data Structures and Algorithms Test 1 1 Sept 2021: 5pm - 6pm NZ time. -------------------------------------- TYPE YOUR NAME AND ID HERE: name: id: -------------------------------------- Time allowed: 60 minutes Instructions: * Type your answers in this file. Use notepad (on Windows) or textedit (on Macintosh) to edit this file. * Submit the file with your answers at the end of the test time. * There are 50 marks in total * You must NOT use BlueJ or any other Java editor. * Brief Java documentation is provided with the test, on the same web page as this file: * You may not access any web pages except - https://ecs.wgtn.ac.nz/Courses/COMP103_2021T2/TermTest - The two documentation files linked on the Test page - The ecs submission system at https://apps.ecs.vuw.ac.nz/submit/COMP103/Test_1 * If you think some question is unclear or has an error, ask for clarification by emailing comp103-help@ecs.vuw.ac.nz. We will attempt to answer immediately. * You may not communicate with anyone (except via comp103-help@ecs.vuw.ac.nz) while working on the test. ======================================================= Questions 1: [12 marks] Properties of Collections 2: [14 marks] Programming with Lists, Sets, Maps, and Queues 3: [11 marks] Complexity analysis (Big-O) 4: [13 marks] Programming with Lists, Sets, and sorting ======================================================= Question 1: Properties of Collections [12 marks] For each property in (a) to (d), state which of the listed Collection types or classes have that property. Delete TRUE or false, leaving the correct answer (a) [2 marks] Items in the collection are stored in the order they were added: (i) Stack TRUE false (ii) Set TRUE false (iii) Queue TRUE false (iv) PriorityQueue TRUE false (b) [2 marks] Items in the collection are only removed from one end: (i) Set TRUE false (ii) Stack TRUE false (iii) List TRUE false (iv) Queue TRUE false (c) [2 marks] The item at position k in the collection can be removed (assuming there are at least k items in the collection). (i) HashSet TRUE false (ii) TreeSet TRUE false (iii) ArrayList TRUE false (iv) ArrayDeque TRUE false (d) [2 marks] The collection may contain duplicate items: (i) Set TRUE false (ii) List TRUE false (iii) Stack TRUE false (iv) Queue TRUE false (e) [2 marks] Which of the following statements about Maps is true? (i) Values must be added to a Map with a key TRUE false (ii) A Map can contain duplicate keys. TRUE false (iii) A Map can contain duplicate values. TRUE false (iv) A TreeMap contains key-value pairs sorted by the values. TRUE false (v) A HashMap contains key-value pairs sorted by the keys. TRUE false (f) [2 marks] Explain why it is more efficient to use an ArrayDeque than an ArrayList to store a queue of items. ANSWER: ======================================================= Question 2: Programming with Lists, Sets, Maps, and Queues [14 marks] ----------------------------------------- (a) [5 marks] Complete the following findUnique(...) method. Your answer should be as efficient as possible. /** * findUnique() is given a List of words which may contain many duplicates. * It should return a Set of all the words that occur only once in the list * It should return an empty set if the list is null or empty. */ public Set findUnique(List words){ //ANSWER: } ----------------------------------------- (b) [6 marks] Complete the following findAll(...) method. /** * findAll is given a Map (from Strings to Items) and a Set of Strings. * It returns a new Set containing every Item in map that * is associated with a String in queries. * It returns an empty set if map or queries are null */ public Set findAll(Map map, Set queries){ //ANSWER: } ----------------------------------------- (c) [3 marks] Give two reasons why the size of the Set returned by findAll(...) might be smaller than the size of queries. ANSWER: ================================================================ Question 3: Big-O Complexity [11 marks] For each of the code fragments below, work out the worst-case big-O cost of the code, assuming that myItems is an unordered collection of n Strings. For each of the specified lines (<===), fill in * The cost of doing the line: * The maximum times the line will be run: Then fill in the total cost of the code. Possible answers are: O(1), O(log(n)), O(n), O(n log(n)), O(n^2), O(n^2 log(n)), O(n^3), O(n^3 log(n)) Note: n^2 means "n squared", and n^3 means "n cubed" --------------------------------- (a) [3 marks] 1 List answer = new ArrayList(); 2 for (String value : myItems){ 3 answer.add(value); //<===== 4 } ANSWER: Line 3: cost = O( ) times=O( ) Total cost = O( ) ---------------------------------- (b) [4 marks] 1 List answer = new ArrayList(); 2 for (String value : myItems){ 3 if (! answer.contains(value) ){ //<===== 4 answer.add(value); //<===== 5 } 6 } 7 Collections.sort(answer); //<===== ANSWER: Line 3: cost = O( ) times = O( ) Line 4: cost = O( ) times = O( ) Line 7: cost = O( ) times = O( ) Total cost = O( ) ---------------------------------- (c) [4 marks] (Hint: note the TreeSet) 1 Set answer = new TreeSet(); 2 for (String value1 : myItems){ 3 for (String value2 : myItems){ 4 if (value1.equals(value2) ){ //<===== 5 answer.add(value1); //<===== 6 } 7 } 8 } ANSWER: Line 4: cost = O( ) times= O( ) Line 5: cost = O( ) times= O( ) Total cost = O( ) ======================================================= Question 4: Programming with Lists and sorting [13 marks] Each month, a charity funding agency has to allocate the money it has raised to charitable projects. It has a large set of requests for funding but it can't fund all the requests, and must choose the best projects to fund. You are to write a method to do the allocation. ------------------------- /** Class to represent information about funding Requests */ public class Request { private String name; // The name of the project private double cost; // How much money the project needs. (Always more than 0) private double benefit; // How much social value the project will achieve. // It may be larger or smaller than the cost. public Request(String n, double b, double c){ name = n; benefit = b; cost = c; } public String getName() { return name; } public double getBenefit(){ return benefit; } public double getCost() { return cost; } } ------------------------- (a) [9 marks] Complete the allocate(...) method below to return a Set of good Requests, keeping the total cost within the amountRaised. Generally, requests with a high ratio of benefit to cost are good choices. Your method should - Sort the Requests by their (benefit divided by cost); Requests with a higher value of (benefit/cost) should be earlier in the ordering. - Iterate through the Requests, adding each Request to the answer as long as it doesn't take the total cost over the amountRaised. - return the answer (Note, Request is not Comparable) /** * Given an unordered list of requests and the amount of money to allocate, * Return a Set of the best (high benefit/cost) requests whose total * cost is at most amountRaised */ public Set allocate(List requests, double amountRaised){ //ANSWER: } ------------ (b) [4 marks] The optimal allocation would be the set of requests with the maximum total benefit without letting the total cost go over amountRaised. The allocate(...) method above may not give the optimal allocation. (It is too "greedy"!) Give an example of a list of 3 to 5 requests and an amountRaised, where the allocate(...) method would NOT give the optimal allocation. (Show each request by its cost and benefit). ANSWER: * set of requests: { } * amountRaised: $ * the optimal allocation: { } * answer from allocate(...):{ }