COMP 103   Data Structures and Algorithms

Test 1

1 Sept 2021:
5pm - 6pm  NZ time.

%=============================================================================
% WITH ANSWERS
%=============================================================================
 
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   
     (ii)  Set          	     false
     (iii) Queue        	TRUE 
     (iv)  PriorityQueue	     false

(b) [2 marks] Items in the collection are only removed from one end:
     (i)   Set          	     false 
     (ii)  Stack        	TRUE
     (iii) List         	     false
     (iv)  Queue        	TRUE

(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      	     false   %, because there is no position k
     (ii)  TreeSet      	     false   %  because there is no position k
     (iii) ArrayList    	TRUE 
     (iv)  ArrayDeque   	     false   %  because you can only remove the ones at the ends

(d) [2 marks] The collection may contain duplicate items:
     (i)   Set          	     false
     (ii)  List         	TRUE
     (iii) Stack        	TRUE   
     (iv)  Queue        	TRUE   


(e) [2 marks] Which of the following statements about Maps is true? 
     (i)   Values must be added to a Map with a key                	TRUE
     (ii)  A Map can contain duplicate keys.                       	     false
     (iii) A Map can contain duplicate values.                     	TRUE   
     (iv)  A TreeMap contains key-value pairs sorted by the values.	     false
     (v)   A HashMap contains key-value pairs sorted by the keys.  	     false


(f) [2 marks] Explain why it is more efficient to use an ArrayDeque than an
ArrayList to store a queue of items.

ANSWER: 
% Using an ArrayList for a queue of items means either adding or removing
% items from the 0th position in the ArrayList.  This is inefficient because
% all the items in the list need to be moved up (or down) each time.




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

  NOTE: WE INTENDED TO ASK A MUCH SIMPLER QUESTION.
        WE GAVE PARTIAL MARKS FOR THE SECOND ANSWER BELOW
	 AND BONUS MARKS FOR A CORRECT ANSWER TO THE ORIGINAL QUESTION
    /**
     * 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<String> findUnique(List<String> words){
    //ANSWER:
%        Set<Item> occurOnce = new HashSet<String>();
%        Set<Item> occurMoreThanOnce = new HashSet<String>();
%        if (words!=null) {
%            for(String word : words){
%                if (occurOnce.contains(word)){
%                    occurMoreThanOnce.add(word);
%                }
%                else {
%                    occurOnce.add(word);
%                }
%            }
%        }
%        occurOnce.removeAll(occurMoreThanOnce);
%  [OR   for (String word : occureMoreThanOnce){ occurOnce.remove(word); }  ]
%        return occurOnce;
     }

    /**  INTENDED VERSION
     * findUnique() is given a List of words which may contain many duplicates.
     * It should return a Set of all the distinct words that occur in the list
     * It should return an empty set if the list is null or empty.
     */
    public Set<String> findUnique(List<String> words){
%       Set<String> ans = new HashSet<String>();
%       if (words!=null) { 
%          for (String word : words){
%              ans.add(word);
%          }
%       }
%       return ans; 
    }



-----------------------------------------
(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<Item> findAll(Map<String,Item> map, Set<String> queries){
    //ANSWER:
%        Set<Item> ans = new HashSet<Item>();
%        if (queries!=null && map!=null) {
%            for(String str : queries){
%                Item item = map.get(str);
%                if (item != null){
%                    ans.add(item);
%                }
%            }
%        }
%        return ans;
    }

-----------------------------------------
(c) [3 marks] Give two reasons why the size of the Set returned by findAll(...) might
be smaller than the size of queries.

ANSWER: 
% Some of the Strings in queries might not be keys in the map  
% Some of the Strings in queries might map to the same Item.
% 2 marks for one answer, 3 marks for a second 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<String> answer = new ArrayList<String>(); 
2     for (String value : myItems){
3        answer.add(value);          //cost = O(   1     )   times=O(  n   )
4     }

      Total cost = O(   n     )

----------------------------------
(b) [4 marks]
1    List<String> answer = new ArrayList<String>();
2    for (String value : myItems){
3       if (! answer.contains(value) ){    //cost = O(   n     )   times = O(  n   ) 
4          answer.add(value);              //cost = O(   1     )   times = O(  n   )
5         }
6      }
7    Collections.sort(answer);             //cost = O( nlog(n) )   times = O(  1   ) 

     Total cost = O(   n^2   )               

----------------------------------
(c) [4 marks] (Hint: note the TreeSet)

1   Set<String> answer = new TreeSet<String>();
2   for (String value1 : myItems){
3       for (String value2 : myItems){
4           if (value1.equals(value2) ){   //cost = O(   1    )   times= O(  n^2   )
5              answer.add(value1);         //cost = O( log(n) )   times= O(  n^2   )
6            }
7       }
8   }
 
    Total cost = O( n^2 log(n) )


=======================================================
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<Request> allocate(List<Request> requests, double amountRaised){
   //ANSWER:
%       requests.sort( (Request r1, Request r2) -> {
%           if (r1.getBenefit()/r1.getCost() > r2.getBenefit()/r2.getCost()) { return -1; }
%           if (r1.getBenefit()/r1.getCost() < r2.getBenefit()/r2.getCost()) { return 1; }
%           return 0;});
%         OR   Collections.sort(requests, .....);
%       Set<Request> allocation = new HashSet<Request>();
%       double remainder = amountRaised;      
%       for (Request req : requests){
%          if (req.cost <= remainder) {
%             allocation.add(req);
%             remainder = remainder - req.cost;
%          }
%       }
%       return allocation;
   }

------------

(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:          {[c:12, b:120], [c:9, b:72], [c:11, b:66]}
  * amountRaised:             20
  * the optimal allocation:   {[c:9, b:72], [c:11, b:66]}
  * answer from allocate(...):{[c:12, b:120]}