i = n; while(i > 0) { if(binarySearch(list, i)) System.out.println("Found"); i--; }In the above code fragment, list is a sorted int array of size n and binarySearch is a boolean function that performs binary search for i on the array list and returns true if i is found; false otherwise.
What is the running time of the code fragment shown above, as a function of n. Express your answer in Big Oh notation. Carefully show the steps you went through in deriving your answer.
Solution: The worst case running time is O(n log n). This is because the while-loop executes n times and in each execution takes O(log n) time, in the worst case. O(log n) work in the worst case, repeated n times is O(n log n) work in the worst case.
Common errors: Most of you correctly noted that each call to binarySearch in the above code takes O(log n) time. However, some of you stopped at this. Some of you attempted to go further, but got O(n) or O(n^2) instead.
public Link deleteLast()If the linked list is empty, then the function just returns null.
Solution: Here is the code.
public Link deleteLast() { // if list is empty if(first == null) return null; else{ Link current = first; Link previous = null; while(current.next != null) { previous = current; current = current.next; } // if list has one element, first needs to be // updated if(previous == null) first = null; else previous.next = null; return current; } }
Common errors: Many of you forgot to update first when the list has one item. Some of you assumed that the linked list is doubly linked and that there was a reference called last to the last item in the linked list. Some of you reached the last Link correctly, but had trouble deleting it. For example, in some answer books, I saw previous = null as an incorrect attempt at deletion.
Solution:
public boolean haveCommonNeighbor(String vertex1, String vertex2) { int id1 = getIndex(vertex1); int id2 = getIndex(vertex2); for(int i = 0; i < numVertices; i++) { // Check if i is a neighbor of both // id1 and id2 boolean check1 = false; boolean check2 = false; if(i <= id1) check1 = Edges[id1][i]; else check1 = Edges[i][id1]; if(i <= id2) check2 = Edges[id2][i]; else check2 = Edges[i][id2]; return (check1 && check2); } return false; }Common Errors: Many of you ignored the triangular structure of the 2-dimensional boolean array Edges and checked Edges[id1][i], Edges[id2][i], etc. without paying attention to the relative values of i, id1, and id2. Some of you wrote correct but extremely inefficient solutions if which you got the list of neighbors of vertex1, list of neighbors of vertex2, and then checked if the two neighbor lists had a common element. Such solutions also typically ignored the fact that you had to just supply the missing code and not write the function from scratch.
Write a brief description (5-6 lines) of how you would implement the STRANGE_QUEUE ADT so that the insert and delete functions, both run in O(1) time. Your description would have two parts: (1) describing the data structures you will use for your implementation and (2) how the two operations are implemented, using these data structures.
Solution: We should keep two separate regular queues, one exclusively for items with priority 0 and another for items with priority 1. So the data members could just be:
private Queue q0; private Queue q1;Any implementation of the Queue class that performs insert, delete, and isEmpty in O(1) time will suffice for our purposes.
The insert operation inserts the given item into q0 if it has priority 0 and into q1 if it has priority 1. The delete operation checks if q0 is empty first. If it is non-empty, then it deletes an item from q0 and returns it. If q0 is empty, it deletes an item from q1 and returns it, assuming that q1 is non-empty.
Common errors: Many of you wrote solutions that performed the operations correctly, but not in O(1) time per operation. Some of you had more exotic and incorrect solutions such as using hash tables, etc.