Exam 2 Top Hats Flashcards
Consider some iterator, iter, which was created on a list of Integers.
Consider the code snippet below:
while (true) {
Integer X = iter.next();
System.out.println(“Next value is “ + X);
}
What will happen if this code segment is executed?
All of the values in the list will be printed, followed by an Exception
Consider a list, L, containing (in order): 10, 20, 30
Now consider the following code segment:
Iterator<Integer> one = L.iterator();
Iterator<Integer> two = L.iterator();
Integer X = one.next();
Integer Y = two.next();
What are the values X and Y?</Integer></Integer>
X = 10, Y = 10
What are the the worst-case runtimes of Contains(x), Add(x) and Remove(x) if we implemented Set ADT using an (unsorted) array
O(n), O(n), O(n)
Which of the following may work as a hash function for strings?
a - Return a random number.
b - Return 0 if the string is of even length and return 1 if it’s of odd length.
c - Add together all the ASCII values of the characters.
b,c
What are the the worst-case runtimes of Contains(x), Add(x) and Remove(x) if we implemented Set ADT using a sorted array?
O(log n), O(n), O(n)
Which tasks can be efficiently solved using the Hash Table implementation of Set ADT?
a - Removing duplicates from the array of integers
b - Quickly checking if student name is in the class roster
c - Testing if all the elements of a given array are unique
d - Given an array of people’s names and a given family name s - counting how many times s appears in the array.
a,b,c
Algorithm findArrayMax(A, n):
input: a NONEMPTY array, A with n elements
output: A’s maximum element
Recursive array max: stop condition?
if n == 1 return A[0]
Algorithm findArrayMax(A, n):
input: a NONEMPTY array, A with n elements
output: A’s maximum element
if n == 1:
return A[0]
*
Recursive array max: recursive step *
if A[n-2] < A[n-1]:
A [n-2] = A[n-1]
return findArrayMax(A, n-1)
else:
return findArrayMax(A, n-1)
You are implementing algorithm power(x,y) for computing xy.
What is your base case?
y = 1 and 0
If y == 1, return x
If y == 0, return 1
You are implementing algorithm power(x,y) for computing xy. (x and y are positive integers)
What is your recursive step?
power(x,y) = x*power(x,y-1)
Consider the recursive algorithms for computing factorial and for a search in an unsorted array (sequential search).
Which of the following claims are true?
a - The recursive versions of these algorithms are preferable to the iterative versions because the recursive versions are asymptotically faster.
b - The recursive versions of these algorithms are preferable to the iterative versions because the recursive versions have less overhead in their execution.
c - The iterative versions of these algorithms are preferable to the recursive versions because the iterative versions are asymptotically faster.
d - The iterative versions of these algorithms are preferable to the recursive versions because the iterative versions have less overhead.
d
Here is an algorithm for counting the number of times the item is found in a sorted array A:
pos = binarySearch(A, item)
if pos!== -1:
return 0
count = 1
i = pos+1
while (i < A.length):
if (A[i] == item):
count++
i++
else: break
i = pos-1
while (i >=0):
if (A[i] == item):
count++
i–
else: break
What is the time complexity of this algorithm?
O(n)
Consider the following code:
displayNode (Node current) {
if (current != null) {
print (current.data)
displayNode (current.next)
}
}
Let head be a head of a Linked List: 1->2->3->4
What will be printed after we call
displayNode (head)
1 2 3 4
Consider the following recursive step for the divide and conquer power function, pow(N):
int recAns = pow(x,N/2);
return (recAns*recAns);
When is the recursive case correct?
This recursive case is correct for some values of N
Consider the “sorted “ vs. the “unsorted partition” in the array in the middle of Insertion Sort. Which statements about the elements in the sorted partition are true?
a - The data in a sorted partition is sorted and each item at location k will stay at location k for the rest of the sort.
b - The data is sorted but the position of an element currently at location k can still change.
c - The data is not actually sorted yet and will become sorted only after the last iteration.
The data is sorted but the position of an element currently at location k can still change.
Consider the last iteration of the outer loop of Insertion Sort. How many comparisons must be done for this iteration?
It could be from 1 to N-1 comparisons, depending upon where the item will end up in the array.
If we perform Insertion Sort and the elements we are sorting are stored in a Linked List: which input will give the best-case performance, and which one the worst-case performance?
Best-case: when the input is sorted in reverse, worst-case: when the input is sorted ascending.
What is the main difference between a shell sort and the sort that it is a generalization of?
A shell sort takes bigger “steps”
If the input of the algorithm is already sorted, which of the following sorting algorithms will run in time O(n)?
Bubble Sort, Insertion Sort
Consider the simple Quick Sort algorithm discussed in lecture (leftmost element chosen as the pivot). If the input data is sorted prior to the call of Quick Sort – which of the statements below are true?
a - The algorithm will run in time O(N2). This will be the worst-case input for the algorithm
b - The algorithm will run in time O(N log N).
c - The algorithm will run in time O(N): this is the best-case input for this algorithm.
a
We know that with the simple pivot (leftmost item), a worst case is when the input data is already sorted prior to the algorithm. If rather than the leftmost item for the pivot, we instead use the rightmost item as the pivot, how will the Quick Sort run-time be affected?
It will still be the worst-case of the Quick Sort algorithm.
What are the values of the overlap function for each position in P=”AAAB”?
0 1 2 0
Given pattern:
ABCABCXB
What are the values of the overlap function for positions 5, 6 and 7.
A B C A B C X B
0 1 2 3 4 5 6 7
0 0 0 1 2
3,0,0
Here is a snapshot after first iteration of the KMP algorithm. We matched characters from 0 to 6 and now we have a mismatch.
What is the start of the next alignment in T and which characters of pattern P and text T will be compared next according to the KMP algorithm?
We start with T[7] and compare T[7] and P[0]
In the Las Vegas version of the Rabin-Karp string matching algorithm (when hashes match, check the characters), which are true? (Note: select all that apply)
a - It is guaranteed to be correct)
b - It is guaranteed to have a run-time of O(N)
c - It is very likely to be correct
d - It is very likely to have a run-time of O(N)
e - It is guaranteed to have a run-time of O(MN)
a,d,e
