COLLABORATIVE SOLUTIONS FOR PRACTICE PROBLEMS

CSE 12

God help us all

ALL MIGHTY CS LORDS GIVE US MERCY

• Use the google comment system to ask questions or leave comments on any answer

• How to use comments: https://support.Google.Com/docs/answer/65129?Hl=en

• When you write an answer, add the question along with the answer

• Add an explanation for your answer

• Always doubt everyone else’s answers until you confirm for yourself they’re correct

____________________________________________________________________________

Complexity Problems

1. Consider a small array a and large array b. Accessing the first element of a takes more/less/the same amount of time as accessing the first element of b.

A. The same amount of time

B. Less time  

C. More time

Should be the same because you don’t really need to iterate anywhere in an array, if you know what index you want to access you can just go there:

int[] array=new int[10];

//to get at the beginning index (0)

Int first=array[0];

The amount of elements n has no effect on accessing indices of arrays

2. True/False? Big-O is used as an upper bound

a) 2N/2 = O(2N)

True: N>(N/2), so O(2N) is an appropriate upper bound

b) N2 + N2 = O(N3)

True: Left side is 2N2 < N3 for large N, so O(N3) is an appropriate upper bound

c) 100 N3= Ω(N2)

True: Here we are looking for the lower bound

so N2<100N3 is an appropriate lower bound

d) N log N + N2 = Θ(N2)

True: if we let c be something large like 1,000,000, then 1,000,000*N^2>NlogN+N^2

We can also pick c=1, and N^2<NlogN+N^2

Also prove your answer for each question above.

3. What is the complexity of the mergeStep() method (merges two sorted arrays into

one)?

O(n)

4. Big-Theta complexity?

for (int j = 1 ; j < n ; j *= 2) // log n

for (int i = 1; i<n; i++) // (n+1)-1 = n

{some_statement;}

Θ(n log n)

Generics

Check out this link, it has a nice map of Collection: http://foratgweb.Blogspot.Com/2015/09/java-collection-diagram-with-short-notes.Html

1. Does this compile? If not, why not? And how do you fix it?

public static void myMethod( Collection arg ) { ... }

// in main

Collection<LinkedList> myL = new Collection<LinkedList>();

myMethod( myL );

Doesn’t compile, collection is an interface.

2. Which of the following compile?

• Collection<List> c = new LinkedList<List>();

Answer:

Yes, if LinkedList implements Collection.

• LinkedList<List> myL = new LinkedList<List>();

Answer: Yes, it does compile because <List> is a type in Java (thank you Pooja)

• LinkedList<List> myL = new LinkedList<ArrayList>();

          Answer: No, in order to compile, the type has to be the same.

• LinkedList<? Extends List> myL = new LinkedList<ArrayList>();

          Answer: Yes because <ArrayList> extends List

• LinkedList<? Super List> myL = new LinkedList<List>();

          Answer: Yes because <List> extends superinterface: Collection.

• LinkedList<? Super List> myL = new LinkedList<Collection>();

          Answer: Yes, List does extend Collection (Collection is supertype).

• LinkedList<Collection> myL = new LinkedList<Collection>();

          Answer: Yes, according to the discussion slides. Interfaces can be types?

So it will compile if:

interfaceA<E> c=new extendsInterfaceA<E>();

E can be List because it is a type

E must be of the same type:

If <? Extends List> --> <(Anything that extends List)>

If <? Super List> --> <(super interface or supertype)>

3. What are generic classes? Why do we use them? Clearly explain the advantage(s). Give an example generic class from the standard Java collection library.

The idea is to allow type (Integer, String, … etc) to be a parameter to methods, classes and interfaces. For example, classes like LinkedList, ArrayList, HashMap, etc use generics very well. We can use them for any type.

To solve the problem of downcasting at runtime, generics parameterise a class by type. So if you have:

class Arraylist<E> implements List<E>{..(Shtuff)..}

Somewhere else...

Arraylist<String> list=new Arraylist<String>();

Java can catch any errors like trying to add in integers or something  at compilation (otherwise those errors would crash the program at runtime).

C Questions

1. Consider:

int a[3];

int *p = a;

The value stored at the memory address found in p is:

A: the name a

B: the address of the first slot of the array

C: the value of the first element of the array

D: undefined, since the operation is illegal

2. The array access a[3] can be rewritten as:

A. *(a) + 3

B. *(a) + 2

C. *(a + 3)

D. *(a + 2)

3. Consider:

int a[] = { 10, 100, 100 };

int *p = a;

The expression p + 1:

A: points to the second slot of a

B: evaluates to 101

C: points to the first slot of a

D: evaluates to 11

4. The string "dog" is stored as:

A: three non-contiguous memory locations

B: 4 contiguous locations in memory

C: a single location in memory

D: 3 contiguous locations in memory

this is because there is an “invisible” null terminator to let c know where the string ends: “d”,”o”,”g”,”STOP” (the actual chars are ‘d’ ‘o’ ‘g’ ‘\0’, \0 terminates the char)

Heaps

1. Binary Min Heaps. Recall that a binary min heap with n elements can be stored in an array A, where A[1] contains the root of the tree. Given that values are stored in A[1] to A[size], BubbleUp and TrickleDown are defined below:

// Move the value A[i] up as needed. Void BubbleUp (int[] A, int size, int i);

// Move the value A[i] down as needed. Void TrickleDown (int[] A, int size, int i);

a) Implement the deleteMin method (as described in class) below. You may call BubbleUp and TrickleDown as needed:

// Given that values are stored in A[1] to A[size],

// remove and return the smallest value in the heap.

int deleteMin(int[] A, int size)

int deleteMin(int[] A, int size) {

if (size == 0)

return null;

int currRoot = A[1];

A[1] = A[size];

size—-;

TrickleDown (A, size, 1);

return currRoot;

}

{ b) Implement the BubbleUp method below:

// Given that values are stored in A[1] to A[size], // move the value A[i] up as needed. Void BubbleUp(int[] A, int size, int i) {

void BubbleUp(int[] A, int size, int i) {

if(size == 0)

return;

if(i == 0)

return;

int parentIndex = i/2;

if(A[i]<A[parentIndex] {

int temp = A[i];

A[i]=A[parentIndex];

A[parentIndex]=temp;

BubbleUp(A, size,parentIndex);

     }

}

2. Give one reason why inserting a value into a d-heap containing N items might be faster than inserting a value into a binary heap of the same size.

There are fewer potential steps to climb/step/percolate

Inserting a value into a heap only depends on the number of levels of the heap, since bubbleUp does not require comparison between same‐level elements. Thus the time it takes to insert is O(logd(n)). With bigger ‘d’ resjjults in faster insertion.

If a parent can hold more children, your tree will get shorter since you don’t have to keep making new levels after 2 children; you can keep adding up to d elements on that same level for each parent (d parents at each level). A shorter tree means less parents to check on bubble up, and less checks=fast

Draw the binary min-heap that results from inserting 12, 1, 3, 7, 4, 5, 15, 0, 6 in that order into an initially empty binary heap.

the array looks like: 0|1|3|4|7|5|15|12|6

Could anybody check again the result? It might be 0|1|3|7|4|5|15|12|6

I think the first one is correct

//agreed with 0|1|3|4|7|5|15|12|6

//How can 4 be before 7? We have to put 7 before 4 right?

//4 swaps place with 7 and pushes 7 down during one step

// why and how we swap 2 childrens of the same parent? I don’t get it. Only swap parent and child when bubble up or trickle down

If you look at the implementation of bubble up above, it it a recursive method and will go until it reaches the root if it does not satisfy the condition that the child is greater than the parent in value

The key to heaps is O(1) insert and O(1) delete using arrays. Since the only convenient spot for that complexity in arrays is at the end of the array, inserting always happens at the end.

In an empty subtree, step 1 is easy:

12

         /      \

     null     null

Then, whenever you add, add to the leftmost spot, as that would be the corresponding “ending” to the array. The amount of children should be specified. In the case of binary heap=2 children.

12

          /    \

       1      null

The array would look like:   |12|1|null|

Remember to bubble up when inserting to keep the heap property. Always compare the leaf that was just inserted with the parent. If it was a max heap, the current state is fine, but since it’s a min heap, we have to bubble it up because 1 is not greater than 12.

1

          /    \

       12    null

4. Draw the result of doing 2 deletemins on the heap you created in problem 3.

The process for removing is similar. You swap the “last” element in the array with the root (first element in the array). Then you check ALL children to make sure the heap property is kept:

• If all children are larger (min heap) then you’re done

• If only one is smaller, swap with that one (min heap)

• If more than one is smaller, swap with the smallest child (min heap)

Also update the “nelems” variable with something like “nelems--;” so it’s “gone” from the array

So the first delete would look like this:

Swap the end with the node to deletetrickle down for heap property

nelems=9;nelems--;  nelems=8;

5. Give the worst possible case estimate for finding the maximum of a binary min-heap. Explain

O(n), The maximum value could be anywhere, so we have to check through all data of the heap.

I’m thinking like a stack  where upon insertion you compare with the “bottom” of the stack (thinking of a linked list with a tail to implement the stack, the head = bottom). If your value is smaller than what’s at the bottom, push it into the bottom (add at the head). Otherwise, add it into the tail. You can push and pop and peek from the tail with the tail pointer, and the comparison at insert doesn’t take too much time since it only compares one element

BST

1. Draw the BST that results from inserting 12, 1, 3, 7, 4, 5, 15, 0, 6 in that order into an initially empty tree.

Inserting is a bit different in this case, since we’d like to start from the root to compare, then move left if it’s smaller, or right if it’s larger. You’d have to specify what to do with duplicate keys, but like if you decide they always go to the right, you have to keep that rule (be consistent). You can also chain duplicates in a single node, that’s valid too.

2. Remove the root from the tree you just created.

     15(case 3, go right)     7 (case 3, go left)

           1          1       15

                0           3        0     3

7       4

      4          5

          5  6

    6

The above is correct, it’s lucky that 15 had no children. To delete you want to consider the following cases:

Case 1: the node has no children

• You just sever it from the tree, and done

Case 2: the node has one child

• You connect the child to the parent of the deleted node

Case 3: the node has two children

• Find either the LARGEST element in the LEFT subtree for that node or the SMALLEST element in the RIGHT subtree for that node (not the entire tree, though this example has us search the entire tree because we are removing from the node)

  • In the case above, we went right and then kept moving as far left as we could to get the smallest element in the right subtree, which happened to be 15.

  • 7 is a valid answer as well, as it is the largest element in the left subtree.

• Once you found it, swap it with the node you want to remove, then apply either case 1 or case 2 to remove the node you want to remove

OR use lazy deletion to simplify your life by using a boolean in the node like isDeleted=true; (bad for memory though)

3. What is the postorder, preorder and inorder traversals for the tree from problem 2?

Post Order- 0 6 5 4 7 3 1 15 (think of depth first search)

Pre Order- 15 1 0 3 7 4 5 6  (think of breadth first search)

InOrder -  0 1 3 4 5 6 7 15 (this should always be in order for a true BST)

4. Given the following orders of traversals of a binary tree, recreate the tree:

Postorder: G, D, B, H, I, E, F, C, A           

Inorder: D, G, B, A, H, E, I, C, F

For reconstructing a binary tree you need at least two traversal orders. The previous answer was wrong, because the traversal doesn’t generate a unique tree if you only have one to work from.

A

BC

 D     E          F

      G            H      I

^ that is correct xD

*claps*

Nice!

Hash Tables

1. Consider a set of objects with hash codes 40, 5, 18, 29, 35, 7 and a hash table of size 11.

a) Hash the above objects using separate chaining.

40 mod 11 =  7

5 mod 11 =  5

618 mod 11 = 7

29 mod 11 = 7

35 mod 11 = 2

7 mod 11 = 7

b) Linear Probing

40 → 7

5 → 5

18 → 7 *collision, so next → 8

29 → 7 *collision,8** collision → 9

35 → 2

7 → 7 * collision, collision, collision so  10

c) Quadratic Probing

So, if you’re hashed to index i, then for every collision c:

Probe i+c2, where c=0 at the start, increment c for every collision

Also, if you reach the end of the array, like in linear probing, you just circle around to the beginning and continue with the count.

Is quadratic the same as double hashing?

No, double hashing will use two hash functions to rehash so you always map to an empty bucket. In quadratic, if you collide, you don’t rehash anymore, you just look for an empty bucket down the list like probing, only you quadratically search  so they don’t bunch up

2. What is the best definition of a collision in a hash table?

A. Two entries are identical except for their keys.

B. Two entries with different data have the exact same key.

C. Two entries with different keys have the same exact hash value.

D. Two entries with the exact same key have different hash values.

3. Convert word “coffee” into an integer (hash table index) using Horner’s

method. (Use base = 32).

Horner’s method is given by the equation:

Number = A[0] + A[1]*base1 + A[2]*base2 + A[3]*base3 + …

So, the integer representation for “coffee” = (99 + 111*(32) + 102*(32^2) + 102*(32^3) + 101*(32^4) + 101*(32^5) + 0*(32^6)) % table size

Coding questions

1. Write a method to implement a merge sort (including the method for merge step).

Recursion (if you need more practice go here: http://codingbat.Com/java/ Recursion-1 http://codingbat.Com/java/Recursion-2

Found this link: http://www.Codenlearn.Com/2011/10/simple-merge-sort.Html

/*
    * The mergeSort algorithm implementation

    * this part of the code splits up the arrays, then puts the back together
    */
   private void mergeSort(int[] array, int left, int right) {
 //left=the start of the array

 //right=the end of the array

       if (left < right) {

           //split the array into 2
           int center = (left + right) / 2;

           //sort the left and right array
           mergeSort(array, left, center);
           mergeSort(array, center + 1, right);

           //merge the result
           merge(array, left, center + 1, right);
       }//else that array is of size 1, which is technically sorted
   }

   /*
    * The mergestep method used by the mergeSort algorithm implementation.
    */
   private void merge(int[] array, int leftArrayBegin,
           int rightArrayBegin, int rightArrayEnd) {

       int leftArrayEnd = rightArrayBegin - 1;

       int numElements = rightArrayEnd - leftArrayBegin + 1;
       int[] resultArray = new int[numElements];
       int resultArrayBegin = 0;

       // Find the smallest element in both these array and add it to the result
       // array i.E you may have a array of the form [1,5] [2,4]
       // We need to sort the above as [1,2,4,5]
       while (leftArrayBegin <= leftArrayEnd && rightArrayBegin <= rightArrayEnd) {
           if (array[leftArrayBegin] <= array[rightArrayBegin]) {
               resultArray[resultArrayBegin++] = array[leftArrayBegin++];
           } else {
               resultArray[resultArrayBegin++] = array[rightArrayBegin++];
           }
       }

       // After the main loop completed we may have few more elements in
       // left array copy them.
       while (leftArrayBegin <= leftArrayEnd) {
           resultArray[resultArrayBegin++] = array[leftArrayBegin++];
       }

       // After the main loop completed we may have few more elements in

   // right array copy.
       while (rightArrayBegin <= rightArrayEnd) {
           resultArray[resultArrayBegin++] = array[rightArrayBegin++];
       }

       // Copy resultArray back to the main array
       for (int i = numElements - 1; i >= 0; i--, rightArrayEnd--) {
           array[rightArrayEnd] = resultArray[i];
       }
   }

3. Write a recursive Java method int sameStack(StackLi s1, StackLi s2) to test whether two integer stacks contain the same elements (in the same order).

The method will return 1 if the stacks contain the same elements and 0 otherwise. You can use the methods below in your method, and don't worry about how the data type is implemented. Once you are done, try to solve the same problem but do not destroy the stacks.

• int pop()

• void push(int x)

• boolean isEmpty()

//the following will destroy the stacks and is non-recursive

public int sameStack(StackLi s1, StackLi s2){

while(!S1.IsEmpty()){

if(s2.IsEmpty())

return 0;

else{

if(s1.Pop() != s2.Pop())

return 0;

}

}

if(!S2.IsEmpty())

return 0;

else

return 1;

}

//this method is recursive, but does destroy the stacks

public int sameStack(StackLi s1, StackLi s2){

if(s1.IsEmpty() && s2.IsEmpty())

return 1;//base case, both are empty at the same time with same

  //popped elements

else{

//from the first if statement, we know both aren’t empty

//so then if one of the stacks is empty, there is unbalance

//also if you pop from both and they aren’t the same element,

//then stacks aren’t the same

if(s1.IsEmpty() || s2.IsEmpty() || s1.Pop() =! S2.Pop())

return 0;

else

//recursion if the same elements have been popped

return sameStack(s1,s2);

}

}

//you can rebuild the stacks if at each pop you push those elements into two

//holding stacks, then pop off at the end into s1 and s2 accordingly

Sorting

1. What needs to be true about the choice of pivot value to ensure that quicksort has an expected time of O(n log n)?

The pivot value is at or near the median of the set of values

2. A newspaper route has recently been computerized. Information about each of the 100 customers is stored in individual records containing first name, last name, and payment due. In writing a computer program to process the customer records, the programmer is uncertain whether to add a procedure to sort the records.  

a) If the records are not sorted, what is the maximum possible number of comparisons that must be made to obtain a particular customer's record using a sequential search?  

A. 100, B. 50, C. 7, D. 5 E. 3  

b). If the records are first sorted, what will be the maximum number of comparisons needed with a binary search to find a particular customer's record?

A. 100 , B. 50, C. 7, D. 5, E. 3

3. In a selection sort of n elements, how many times is the swap function called in the complete execution of the algorithm?

A. 1

B. N - 1

C. N log n

D. N2

4. Selection sort and quicksort both fall into the same category of sorting algorithms. What is this category?

A. O(n log n) sorts

B. Divide-and-conquer sorts (recursive)

C. Comparison sorts

D. Average time is quadratic.

5. Suppose we are sorting an array of ten integers using a some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here: 1234506789

Which statement is correct? (Note: Our selection sort picks largest items first.)

A. The algorithm might be either selection sort or insertion sort.

B. The algorithm might be selection sort, but could not be insertion sort.

C. The algorithm might be insertion sort, but could not be selection sort.

D. The algorithm is neither selectionsort nor insertionsort.

6. What is the worst-case time for quicksort to sort an array of n elements?

A. O(log n)

B. O(n)

C. O(n log n)

D. O(n2)

7. Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this:

2 5 1 7 9 12 11 10

Which statement is correct?

A. The pivot could be either the 7 or the 9.

B. The pivot could be the 7, but it is not the 9.

C. The pivot is not the 7, but it could be the 9.

D. Neither the 7 nor the 9 is the pivot.

8. Which of the following sorting algorithms perform in O( n ) time in the best case?

a. Insertion Sort

b. Bubble Sort

c. Selection Sort

d. All of the above

e. None of the above // so e? Since a and b are both correct

Miscellaneous

1) Of the following data structures, which would be best suited for an application where search time must be minimized and where data can be easily added?

A. Sorted array //great for search, bad for insertion (shifting)

B. Hash table//assuming you have the key of what you’re searching this, is it

C. Sequential file

D. Circularly linked list with two header nodes //still bad for search

E. Singly linked list //bad for search

2) What does the acronym “ADT” stands for? What is an ADT? What is the connection, if any, between an ADT and a data structure? Use an example to illustrate the answer to your last question.

x Data Type. An ADT is a language-neutral description of a data structure.

3) Why does a queue implementation using a linked list require a tail pointer but a stack implementation does not?

Stacks access and adds and removes from one end whereas queue at one end and removed from the opposite end. Stack only needs the one pointer to the end it’s adding and removing from (the head), while the queue needs two pointers for each end (one for the head, and one for the tail)

4) What is the best data structure to solve the following problem? A list needs to be built dynamically. Data must be easy to find, preferably in O(1). The user does not care about any order statistics such as finding max or min or median. First assume that the index is given. Then assume that it is not given.

i. Use an Array (if index if given)

ii. Use a Singly LL

iii. Use a Stack

iv. Use a Queue

v. None of the above (hash table if index is not given)