Make like a tree
H*A*S*H
Potpourri
Searching and Sorting
Binary Everywhere
100
What is the height of this tree?
https://en.wikipedia.org/wiki/Tree_(abstract_data_type)#/media/File:Tree_(computer_science).svg
3. Tree height is equal to the number of edges in the longest path between the root and a leaf
100
What is the worst-case time complexity for both inserting or deleting from a hash table?
O(n)
100
Given set A = {10, 20, 30, 40}, Set B = {5, 10, 15, 20, 25, 30, 35, 40}, and the universal set is U = ℝ:
is A ⊆ B?
Yes
100
Given the array [11, 4, 7, 20, 10], list the first three swaps that will occur using an insertion sort algorithm.
1. 11 swapped with 4 (our sorted subarray is now 4)
[4, 11, 7, 20, 10]
2. 11 is swapped with 7 (our sorted subarray is now 4, 7)
[4, 7, 11, 20, 10]
3. 11 is swapped with 10 (our sorted subarray is now 4, 7, 10)
[4, 7, 10, 20, 11]
100
What is the average (and also best) case time complexity of a binary search tree?
O(log n)
200
What is the depth of node with value 7 in this graph?
https://en.wikipedia.org/wiki/Tree_(abstract_data_type)#/media/File:Tree_(computer_science).svg
1. Depth of a node is equal to the number of edges between a node and the root.
200
Name the algorithm feature that means for a particular input, that algorithm will ALWAYS produce the same output.
Determinisim
200
What is the degree of node 3 on this graph?
https://en.wikipedia.org/wiki/Degree_(graph_theory)#/media/File:UndirectedDegrees_(Loop).svg
3
200
What is the time complexity of a binary sort?
O(log n)
200
Is the following an example of pre-order, in-order, or post-order tree traversal?
Pre-order. easy give away is that we start at the root
300
Is the following tree a binary search tree?
No, there are values in the left subtrees with values greater than the value of the root's key value
300
What are the two most common methods of handling collisions in hash tables?
Chaining and linear probing
300
Let P (x) be the predicate “x must take a discrete
mathematics course” and let Q(x) be the predicate “x is a computer science student”.
The universe of discourse for both P (x) and Q(x) is all
students.
Express the statement “Every computer science student must take a discrete mathematics course”
∀x(Q(x) → P (x))
300
Given the following array, what are the indices returned in the search for target 13 in a binary search?
[-1, 4, 5, 11, 13 ]
2,3,4
300
What are the two additional constraints on that a binary heap compared to a binary search tree?
1) Shape Property
a binary tree of height (i) in which all leaf nodes are located on level (i) or level (i-1), and all the leaves on level (i) are as far to the left as possible
2) Order (heap) property
The data value stored in a node is less than or equal to the data values stored in all of that node’s descendants (or greater, if a max heap)
400
Which tree search method uses a queue as its main data structure (HINT: as opposed to a stack)
Breadth first. BFS uses a queue data structure to keep track of nodes to visit next. When it visits a node, it enqueues all unvisited neighbors.
400
What are the three states of flags in linear probing, and why are they needed?
Empty, occupied, deleted.
The algorithm may stop searching once an empty cell has been reached, but may need to keep searching in the case of deletion.
400
What are the four basic operations a priority queue can perform?
Construct, insert (add), remove (delete), peek (return)
400
What is the name and time complexity of the algorithm that first sorts elements that are far apart, before reducing the interval between elements being compared?
Shell sort, O(n log n)
400
Delete node 10 from the following binary heap, and provide the final tree after heapifying
5
/ \
4 3
/
2
500
Djikstra's algorithm is an example of what form of tree traversal?
Breadth-first
500
Given the following hash tables, using a linear insertion and a compression function of %7, what index would inserting 9, 7, and 24 go?
Index Value
0 14
1
2
3 10
4 17
5
6 20
Index Value
0 14
1 7
2 9
3 10
4 17
5 24
6 20
500
Evaluate the following algorithm's complexity using the appropriate case of the Master Theorem:
T(n) = 3T(n/2) + log(^2)n
a = 3, b = 2, k = 0, p = 2
bk = 1. So, a > bk [Case 1]
T(n) = θ(nlogba )
T(n) = θ(nlog^(_2)3)
500
Name the algorithm that sorts by creating sub-arrays of values either larger or smaller than a target value, and then recursively sorts those sub-arrays by the same method, before merging?
Quick sort
500
Insert node 7 into the following max binary heap:
10
/ \
5 3
/ \
2 4
1.
10
/ \
5 3
/ \ /
2 4 7
2. 7 is greater than its parent
10
/ \
5 7
/ \ /
2 4 3