Csc220 Final Exam Review

Front 1

How many cycles are in a GHz (giga Hertz)?

Back 1

a billion (10^9)

Front 2

What is the nearest power of 2 to one million?

Back 2

20

Front 3

What is the minimum time to the nearest second that a computer with 16 GB RAM and a quad (4) core 2 GHz processor can locate all bytes in its RAM which are set to 'V'?

Back 3

2 seconds because 4 cores checking 2 billion bytes per second = 8 billion bytes per second

Front 4

Give at least two reasons why it is a harder task for Google to find the best ten pages with Victor Milenkovic on them (compared to #2).

Back 4

1.)Web site is more than one byte: more like 100 to 1000

2.) a trillion web sites, not 16 billion

3.) has to rank them (by number of "back links")

Front 5

If one weighing can determine that a pile of coins contains one real coin, how many weighings does it take to locate one real coin in a pile of 1000?

Back 5

10 because we can split the number of coins by 2 every time and measure which side has a larger imbalance, thus log n (log base 2 of n) would give us 10.

Front 6

True or False: You can access the private variables of a parent class

Back 6

False

Front 7

True or False: You can place a child instance into a parent variable

Back 7

True

Front 8

What kind of error occurs if you try and call a child exclusive method from a parent variable holding a child instance?

Back 8

A compiler error occurs

Front 9

If a child instance is placed into a parent variable , and a method independently defined in both classes is called from that parent variable, which method gets called -- the child's method or the parent's method?

Back 9

The child's method/method of the instance

Front 10

True or False: You can upscale a parent instance into a child variable

Back 10

True

Front 11

If a parent instance is upscaled into a child variable, and a child exclusive variable is called, what kind of error occurs?

Back 11

A run time error

Front 12

How many numbers can YOUR computer (the one you use to do your homework) add up in one millisecond? If you don't remember the exact speed of your computer, take a guess.

Back 12

My computer is quad core 2.6 GHz so...4*2.6 billion / 1000 = 100,000,000

Front 13

Using ui.getInfo(prompt) and ui.sendMessage(message), write code that gets a name from the user and sends a message "Blank is not allowed" if the user gives you a blank name. Cancel should not cause your code to crash.

Back 13

If it's not null(user didn't press cancel) and the length is 0, then send the user the message that "Blank is not allowed"

Front 14

If a class implements an interface, does it need to have a public method with the same name and parameters for EVERY method in the interface? Can the class have methods OTHER than those in the interface it implements? (Hint: ArrayBasedPD.)

Back 14

YES YES

Front 15

Set name1="Victor and name2="Vincent". Why is name1.compareTo(name2) == -11?

Back 15

The difference between the values of the first differing letters, 'c' in name1 and 'n' in name2, is -11. If we had :name1.compareTo(name2), it would actually equal positive 11.

Front 16

Variable 'strings' is of type String[] with length 10. Variables index1 and index2 are of type int in the range from 0 to 9 inclusive with index1 > index2. Write code to print out the contents of strings from index index1 to index index2. Yes, you are going backwards through the array.

Back 16

Make a loop starting from index1 and going down to and equaling index 2, like so:

for (int i = index1; i >= index2; i--) System.out.println(strings[i]);

Front 17

In ArrayBasedPD, how would we remove "Bob" from this list:

Jay

1

Bob

8

Ian

2

Ann

3

Eve

6

Back 17

You would swap him with the last person in the list and reduce the size by 1.

Front 18

In SortedPD, how would we remove "Bob" from this list:

Jay

1

Bob

8

Ian

2

Ann

3

Eve

6

Back 18

Move everyone after Bob back one.

Front 19

In ArrayPD, how would we add ("Zoe" , 7) to this list:

Jay

1

Bob

8

Ian

2

Ann

3

Eve

6

Back 19

Add it to bottom of the list

Front 20

In SortedPD, how would we add ("Zoe" , 7) to this list:

Jay

1

Bob

8

Ian

2

Ann

3

Eve

6

Back 20

If there's something in it's place we move him, and the rest of the list forward one, and put Zoe in her place

Front 21

This loop from removeEntry is supposed to move all the entries after theDirectory[index] back one, but when you test it (with CAPACITY=5), it crashes. Why? How can you fix it?

for (int i = index; i < size; i++)

theDirectory[i] = theDirectory[i+1];

Back 21

size should be size - 1 instead of size

Front 22

his loop from addOrChangeEntry is supposed to move entries to open up a space for a new entry at insert_index. Fill in the missing parts of the for loop.

for (x; y; z)

theDirectory[i+1] = theDirectory[i];

Back 22

int i = size - 1 ; i >= insert_index ; i--

Front 23

What is the O() of the following function? 7 * log (n) + 2 * n - 11 2

Back 23

Largest term: 2 * n Forget about the constant: O(n)

Front 24

What is the worst case O() running time of ArrayBasedPD.removeEntry? Is your answer for n=size or n=theDirectory.length?

Back 24

O(n) n = size If the array has length 1000 but only 100 are being used, you will only look at 100.

Front 25

What is the BEST case O() running time of ArrayBasedPD.removeEntry? Which entry?

Back 25

O(1) First entry.

It takes one look to find that name.

Copy the last back to index 0, and decrement size. Done.

Front 26

What is the WORST case O() running time of SortedPD.removeEntry? Which entry?

Back 26

O(n) First entry.

Front 27

Suppose a method has O(log(n)) running time. It takes 30ms (milliseconds) for n=1000. What is the constant? Indicate which log you are using.

Back 27

t = c log10(n)

30 = c log10(1000)

30 = c 3

c = 10

Front 28

What is the estimated running time of the method in #6 for n=10000?

Back 28

t = c log10(n)

t = 10 log10(10000)

t = 10 4

t = 40 ms

Front 29

How would you time (in seconds) a method static method fib of the fib class, given a long variable called "start" that gets the system time like so:

long start = System.nanoTime();

Back 29

long start = System.nanoTime(); //first get the current time

fib.fib(n); //run fib

long end = System.nanoTime(); //get

return (end - start) / 1000.0; //return the difference in time divided by 1000 to convert to seconds

Front 30

A method takes about 20 microseconds. How many times to you have to measure its running time to get an average with three significant figures of accuracy?

Back 30

10^6 / t^2

10^6 / 20^2

10^6 / 400

10000 / 4

2500

Front 31

Define what first should be in the first iteration of binary search

Back 31

int first = 0;

Front 32

Define what last should be in the first iteration of binary search

Back 32

int last = size-1;

Front 33

How do we get the variable in the middle?

Back 33

int middle = (first + last) / 2

Front 34

What condition should we have in the loop for binary search?

Back 34

while ( first <= last )

Front 35

What happens if the name is less than the middle in value? Greater than? The same?

What do we return if it's not in the list?

Back 35

int cmp = name.compareTo(theArray[middle].getName());

if (cmp < 0)

last = middle - 1;

else if (cmp > 0)

first = middle + 1;

else

return middle;

We return -first - 1, if it's not in the list, first being the last one if it's greater than all words in the list or the first one if it's less than all the words in the list.

Front 36

Can we use binary search to find a name in a sorted doubly linked list of n entries in O(log n) time? If not, why not?

Back 36

NO You can't get to the middle in O(1) time. Takes O(n) to get to the middle.

Front 37

What is the O() for adding a new entry at a KNOWN location is a linked list? (You are given a pointer to the next or previous entry.) Does that make SortedDLLPD.addOrChangeEntry faster than SortedPD.addOrChangeEntry? Why or why not?

Back 37

O(1) No, because find is still O(n) for a linked list.

Front 38

Write a loop to print out all the values in a doubly linked list with first entry, head, and last entry, tail. The entries are of type DLLNode, with methods getKey(), getValue(), getNext(), and getPrevious().

Back 38

for (DLLNode entry = head; entry != null; entry = entry.getNext() ) System.out.println(entry.getValue());

Front 39

Write code to add an entry with key name and value number at the HEAD of a doubly linked list. Draw the diagram to help you. You can assume there is at least one entry already in the list. DLLNode has methods setNext(newNext) and setPrevious(newPrevious) and you are given the variable head.

Back 39

DLLNode entry = new DLLNode(name, number);

entry.setNext(head);

head.setPrevious(entry);

head = entry;

Front 40

Write code to remove the last entry (tail) of a doubly linked list. You can assume that the list has at least two elements

Back 40

tail = tail.getPrevious();

tail.setNext(null);

Front 41

A DLLNode has methods getKey(), getValue(), getNext(), and getPrevious(). DLLNode variables head and tail point to the first and last elements of a linked list of DLLNode objects, sorted by key. Implement a find method which returns the DLLNode whose key equals name, if it is there, or the next largest key, if it is not. If neither applies, return null.

Back 41

DLLNode entry;

for (entry = head; entry != null && entry.getKey().compareTo(name) < 0; entry = entry.getNext());

return entry;

Front 42

Starting with an empty stack s, perform s.push(3), s.push(1), s.push(4), s.push(1), s.pop(), s.push(5), s.pop(). What will s.peek() return?

Back 42

4

Front 43

Write code to print out the contents of stack s from top to bottom and leave s empty afterwards. Use System.out.println.

Back 43

while (!s.empty()) System.out.println(s.pop());

Front 44

If a stack is implemented using an array E[] theArray and an int top, the index of the top element, implement the push method. You can assume a reallocate() method.

Back 44

E push (E item) {

top++;

if (top == theArray.length)

reallocate();

theArray[top] = item;

return item;

}

Front 45

Implement push for linked stack with Node variable top pointing to the top Node in the stack.

class Node {

E data;

Node next;

Node (E data, Node next) { this.data = data; this.next = next; } }

Back 45

E push (E item) {

top = new Node(item, top);

return item;

}

Front 46

Implement pop (for same as #5). Don't forget to throw an EmptyStackException.

Back 46

E pop() {

if(empty())

throw new EmptyStackException();

E data = top.data;

top = top.next;

return data;

}

Front 47

If stack is implemented with a List theList, implement peek

Back 47

E peek() {

if(empty())

throw new EmptyStackException();

return theList.get(theList.size() - 1);

}

Front 48

When solving the Tower of Hanoi, the goal 4ab stands for ``Move a pile of 4 disks from peg a to peg b.'' Break this goal into three subgoals.

Which one of the subgoals of the previous answer would you push first onto the goal stack?

Back 48

3ac -- Move all but bottom to other peg

1ab -- Move bottom to correct peg

3cb -- Move others on top

The third one, because that's the last step in the transition process

Front 49

List has implementations ArrayList and LinkedList which implement the list as either a (partially filled) array or a (doubly) linked list. What is the (worst) O() running time of get(i) for a LinkedList of size n?

Back 49

The worst one is the one in the middle because you have head and tail.That will take n/2 .next's or getNext()'s. n/2 is O(n)ANSWER: O(n)

Front 50

Suppose SortedPD uses LinkedList to store the entries but SortedPD.find still uses binary search. (Start at the middle, etc. Of course, it would use get(middle) instead of array[middle].) What would be the (worst) O() running time of find?

Back 50

O(n log n), to get to the middle, you have to go through n over some contant c (n/c) as many times as you need to get to the middle (log2(n)), thus to find someone in a doubly linked list using binary search is O(n log n)

Front 51

SortedDLLPD addOrChangeEntry(name, number) has to add a new entry. It gets a pointer to the next entry from find(name), but that might be null. First set previous, the previous entry (or null). Then insert the new entry.

If we set the return value of find to "next", what two conditions should we check for when setting the previous, and what goes in those conditions

Back 51

if (next != null)

previous = next.getPrevious(); ; //

else

previous = tail;//getting a null means our name was greater than all the elements

Front 52

SortedDLLPD addOrChangeEntry(name, number) has to add a new entry. It gets a pointer to the next entry from find(name), but that might be null. First set previous, the previous entry (or null). Then insert the new entry.

If we set the return value of find to "next", and assuming we have the previous from next, how do we connect it to our "previous" and "next" Node variables

Back 52

newEntry.setNext(next); newEntry.setPrevious(previous);

Front 53

SortedDLLPD addOrChangeEntry(name, number) has to add a new entry. It gets a pointer to the next entry from find(name), but that might be null. First set previous, the previous entry (or null). Then insert the new entry.

If we set the return value of find to "next", and assuming we have the previous from next, AND we set NewNode to be connected to both next and previous, how do we check to see if we should redefine head and tail?

Back 53

if (next != null)

next.setPrevious(newEntry);

else

tail = newEntry; // Zora

if (previous != null)

previous.setNext(newEntry);

else

head = newEntry

Front 54

LinkedQueue uses a linked list with the following Node class. It has Node variables front and back and int variable size. Implement offer.

class Node {

E item;

Node next;

Node (E item) {

this.item = item;

this.next = null;

}

}

Back 54

boolean offer (E obj) {

Node newNode = new Node(obj);

if (back != null)

back.next = newNode;

else

front = newNode;

back = newNode;

size++;

return true;

}

Front 55

Write a method that takes a queue as input and returns a String that is the contents of the queue separated by spaces. There can be an extra space at the end.

Back 55

String queueToString (Queue queue) {

String s = "";

for (String string : queue)

s = s + string + " ";

return s;

}

Front 56

The methods of AbstractQueue work by calling the methods that YOU WROTE yesterday. How can AbstractQueue implement remove() by calling the poll() and size() you implemented? Remember, remove() should throw NoSuchElementException if there is no element to remove.

Back 56

E remove () {

if (size() == 0)

throw new NoSuchElementException();

return poll();

}

Front 57

ArrayQueue uses an E[] array theItems and int variables front, back, and size. Implement poll. Don't forget the empty case.

Back 57

E poll() {

if(size() == 0)

return null;

E obj = theItems[front]; //get what's at front

front = (front + 1) % theItems.length;

/* or you could do this ***

front++;

if(front == theItems.length)

front = 0;

*/

size--;

return obj;

}

Front 58

Suppose ArrayQueue has an array theItems of length 5 with the following contents:

null, "had", "a", "little", "lamb"

Suppose front==1 and back==4. (Zero based indexing!!!) After offer("fleece"), what are the contents of the array and the values of front and back? Would your answer be different if that null had been "Mary"?

Back 58

"fleece", "had", "a", "little", "lamb"

front==1 back==0

NO, Mary was in the queue and got polled using the method in theprevious question, which does NOT set the location to null afterwards.So Mary is still there.

Front 59

Suppose ArrayQueue has an array theItems of length 5 with the following contents:

"fleece", "had", "a", "little", "lamb"

front==1 back==0

After offer("white), what are the contents of the array and the values of front and back?

Back 59

"had", "a", "little", "lamb", "fleece", "white", null, null, null, null

front=0back=5

Front 60

When the Jumble solver reads the word "computer" from the dictionary, what key and value does it use to store it in its Map?

Back 60

key = cemoprtu

value = computer

Front 61

When the Jumble solver is asked to unscramble "ewting", what key does it look up in the Map?

Back 61

key = egintw

Front 62

Suppose DummyList is an implementation of Map using a singly linked list sorted by key with a dummy first node. If the variable thisNode points at a node in the list, is it possible to remove this node in O(1) time? If yes, show how. In not, explain why not.

Back 62

No because you need the pointer to the node BEFORE the one you want to remove.(Otherwise, you need to start at the dummy and that takes O(n).)

Front 63

Suppose the Jumble solver uses DummyList for its Map. What is the O() to store one new word into the Map? What is the O() to store all the words in the file into the Map?

Back 63

O(n) 2

O(n^2 ) (n times O(n))

Front 64

Pick up a coin and start flipping it. Stop when you get the first tails. What is the expected number of heads you flipped before you flipped that tails?

Back 64

1

Front 65

How many levels do you expect a skip list with n entries to have? Why?

Back 65

log2(n)Because only 1/2 make it to the next level each time, so gold coin idea.Each list has 1/2 of the one before.

Front 66

When searching for an entry in a skip list, why do you never move forward to an entry on a level=3 if that entry also appears on level=4?

Back 66

You start where you left off.You would have moved forward to it then, there would be no reason to go up a level.

Front 67

When searching for an entry in a skip list with at least 5 levels, how many times do you expect to move forward on level=3? Why?

Back 67

Because you only move forward to entries on that level who threw TAILS.Why not someone with HEADS? Because they would be on level=4.

Front 68

Suppose the Jumble solver uses SkipList for its Map. What is the (expected) O() to store one new word into the Map? What is the expected O() to store all the words in the file into the Map?

Back 68

O(log n)

O(n log n) (n times O(log n))

Front 69

How much more space than DummyList do you expect SkipList to use? Why?

Back 69

Twice as much.

Because on average, you throw one heads, so you are in one extra list.

Front 70

Add 6 to the following binary search tree

3

1 4

2 5

9

Back 70

3

1 4

2 5

9

6

Front 71

Remove 3 from the following binary search tree

3

1 4

2 5

9

Back 71

4

1 5

2 9

OR

2

1 4

5

9

Front 72

How do you add an item into the heap?

Back 72

Into the first available position and make it fight it's parent until it wins

Front 73

How do you remove the root from a heap?

Back 73

You take the last added number and bring it to the top, after that you have it's children fight amongst each other and have the winner challenge it's parent switching places if it wins. This continues as the number moves down.

Front 74

Give an example of a tree and key for which the following add method does NOT work. Assume the key is not there yet.

Node add (Node root, K key, V value) { ,v>,v>

if (root == null) ,v>,v>

return new Node(key, value);,v>,v>,v>

if (key.compareTo(root.key) < 0) ,v>,v>,v>

add(root.left, key, value);,v>,v>,v>

else,v>,v>,v>

add(root.right, key, value); ,v>,v>,v>

return root; ,v>,v>,v>

},v>,v>,v>

,v>,v>,v>

Back 74

Any tree will not work because the method never actually adds the new element.

Front 75

The array theArray[] and int size represent a COMPLETE binary tree. If theArray[i] is an item in the tree with i>0, where is its parent?

Back 75

(i-1)/2

Front 76

Same situation for theArray[], size, and theArray[i]. What test tells you that theArray[i] has a left child? (Don't mention null!!)

Back 76

if (2 * i + 1 < size)

Front 77

Node node is a pointer to a Node in a linked list with a previous pointer. Implement a method which determines the number of nodes which come before node.

Back 77

int n = 0;

while (node.previous != null) {

n++;

node = node.previous;

}

return n;

Front 78

The NodeComparator class has a value method which returns a value for a Node. Implement a compare method for ordering by increasing value. (Hint: think about compareTo for String.)

Back 78

int value (Node node) { /* returns value of node */ }

int compare (Node nodeA, Node nodeB) {

return value(nodeA) - value(nodeB);

}