Midterm 1 Flashcards by sophie courville

What is the inductive hypothesis when trying to prove loop invariance of the binary search algorithm?

A[lo pointer index] <= target <= A[hi pointer index]

How well did you know this?

Not at all

Perfectly

What must be shown about loop invariant? (to prove correctness of an algorithm)

Initialization
Maintenance
Termination

*Show the inductive hypothesis is true for all 3 of these

How well did you know this?

Not at all

Perfectly

What is the exact definition of an asymptotic upper bound?

There exists an n0 such that, for all n <= n0, f(n) > g(n)

*Use substitution!!!

How well did you know this?

Not at all

Perfectly

What does O(1) mean?

We say t(n) is O(1), if there exists 2 positive constants n0 and c such that for all n >= n0, t(n) <= c

So, it means that t(n) is bounded

How well did you know this?

Not at all

Perfectly

What is the definition of big Theta?

Let f(n) and g(n) be 2 functions, where n >= 0.

We say t(n) is big Theta of g(n) if there exists 3 positive constants n0, c1 and c2, such that for all n >= n0,
c1 * g(n) <= f(n) <= c2 * g(n)

How well did you know this?

Not at all

Perfectly

What is the definition of a collision?

When 2 keys have the same Hash codes

How well did you know this?

Not at all

Perfectly

What operations do right shift and left shift convert to?

Right shift (») = division by 2^k
Left shift («) = multiplication by 2^k

How well did you know this?

Not at all

Perfectly

How to convert binary to base 10 and inversely:

10111

10111 = (1x2^4) + (0x2^3) + (1x2^2) + (1x2^1) + (1x2^0)

How well did you know this?

Not at all

Perfectly

How to quickly compute 10111 mod 8?

8 = 2^3 → return the last 3 bits

10111 mod 8 = 111

How well did you know this?

Not at all

Perfectly

What is a heap vs a BST?

Heap:
- Complete binary tree
- Heap property: value of a node >= value of its children (maxHeap)
- root has max value in a (maxHeap)
- represents priority queues

BST:
- each node has max 2 children
- v >= v of left subtree
- v <= v of right subtree
- worst case, tree is unbalances → O(n)

How well did you know this?

Not at all

Perfectly

What is running time of union-find?

It is quasi-constant

m union or find operations take O(m a(n) )

*Union-find = union by size + path compression

How well did you know this?

Not at all

Perfectly

What index in an array do the children of a node take in a complete binary tree?

parent node = floor (k/2)

children = 2k and 2k+1

How well did you know this?

Not at all

Perfectly

What is the size of the largest possible subtree of a complete binary tree of size n?

2n/3 → if the last row is exactly 1/2 full

How well did you know this?

Not at all

Perfectly

In a complete binary tree, what nodes would be found at level L?
What would be the total number of nodes in the tree

Nodes 2^l → 2^(l+1) - 1

Total of nodes = 2^(h+1) - 1

How well did you know this?

Not at all

Perfectly

What is the exact height of a complete binary tree expressed in terms of the number of nodes?

h = log (n + 1) - 1

How well did you know this?

Not at all

Perfectly

What is the running time of 1 iteration of maxHeapify?

T(n) = O(log n)

T(n) <= T(2n/3, size of largest subtree you can call maxHeapify on) + O(1)

How well did you know this?

Not at all

Perfectly

What algorithm allows to take an array and build a maxHeap out of it?

n = length[A]

for (i = floor(n/2) → down to i = 1)
call maxHeapify (A, i)

*not down to i = 0, because the floor of 1/2 is already 0

This starts at the lowest node that is node a leaf, checks that it is larger that the root of its 2 subtrees (2 leafs in this case) by calling maxHeapify.
- It does the same for every node until the root

What is the loop invariant property of the algortihm allowing to build a heap (to prove its correctness)?

At the start of each iteration of the for loop, each node i+1, i+2, …, n is the root of a max-heap.

Show maintenance:
- By this LI, subtrees at children of node i are max heaps.
- MaxHeapify(i) renders node i a max heap root (while preserving the max heap root property of higher-numbered nodes).
- Decrementing i reestablishes the loop invariant for the next iteration. (for loop)

Termination:
- Loop is bounded by number of calls to MaxHeapify
- At termination, i =0. Then, each node 1,2,…,n is the root of a max-heap. In particular, node 1 is.

What is the running time of Build max heap?
Loose and Tight upper bounds?

running time = cost of maxHeapify (O (log n) ) * # calls to maxHeapify (O(n))

Loose upper bound = o (n log n)
- Cost of maxHeapify = O (log n)
- # calls to maxHeapify = O (n)

Tight upper bound = O (n)
- cost of maxHeapify is only O (log n) for the root
- # nodes with height h <= ceiling(n/ 2^h+1 )
- maxheapify

What is the running time of heap sort?

O (n log n)

What is in order traversal? What type of tree is it used with?

Print the nodes in the left subtree (A), then node x, and then the nodes in the right subtree (B) → useful for binary search trees as it prints the nodes in increasing order of value

inordertraversal (treeNode x)
if x != nil
inorderTraversal (x.leftChild);
print x.value;
inorderTraversal (x.rightChild);

What is the definition of an AVL BST?

BST such that the heights of the two child subtrees of any node differ by at most one.

*To satisfy the definition, the height of an empty subtree is -1

What are worst case examples of AVLs

AVL trees with a minimum number of nodes are the worst case examples.
- every node’s subtrees differ in height by one
- we cannot make these trees any worse / any more unbalanced without breaking the AVL property (if we change something, we either get a more balanced tree of break the AVL property)

*If we can bound the height of these worst case examples of AVL trees, then we’ve pretty much bounded the height of all AVL trees

Use this to prove that the max height is O (log n)

How do AVL ensure insertion conserves the AVL property?
What is the running time?

Add as in any BST
Restore AVL depending on which case occurs

Case 1: The INSERTION was “outside” → 1 rotation
- To the left subtree of the left child
Case 2: The INSERTION was “inside” → break zigzag → final rotation

running time = insertion time (O (h)) + rotations (O (1)) → O(log n)

What are the 5 properties of Red Black properties?

1. Every node is either red or black. 2. The root is black. 3. All leaves (nil) are black. 4. If a node is red, then its children are black (i.e. no 2 consecutive red nodes). 5. For each node, all paths from the node to descendant leaves contain the same number of black nodes (i.e. same black height). *Leafs do not have data, they are Nil (sentinels) → when inserting a node, you replacing a Nil by your node and adding 2 Nils under it

How much space does a Red Black tree take up?

BST + 1 bit/node which is either red or black - All other attributes of BSTs are inherited (key, left, right, parent) *no path (from the root to a leaf) is more than twice as long as any other path.

True or False: "no path (from the root to a leaf) is more than twice as long as any other path" is a property of balanced binary search trees.

True - The only path twice as long is if you have height of 2

What is the definition of height vs black height for a Red Black Tree?

Height h(x) = # EDGES in a longest path to a leaf. Black-height bh(x) = # black NODES on path from x to leaf, not counting x (counting Nils) *bh(Nil) = 0

For a node x, what are the black heights of its children?

Each child of x has height h(x) - 1 and black-height either: - Child is red → bh(x) - Child is black → bh(x) - 1

If the height of a balanced binary tree is x, how many nodes does it have? How many internal node?

2^(x+1) - 1 nodes total 2^(x) - 1 internal nodes (remove 1 level for the Nil/leafs)

When inserting a node into a red black tree, which properties can be violated?

- The root is black. (if add a new node in an empty tree) - If a node is red, then its children are black (no 2 consecutive red nodes)

What are the different cases of insert fixup in Red Black tree insertion?

Z = root → color black Case 1: Z.uncle = red → recolor Case 2: Z.uncle = black(triangle) → rotate z.parent Case 3: Z.uncle = black(line) → rotate z.grandparent and recolor

Given an empty AVL tree, how would you construct AVL tree when a set of numbers is given without performing any rotation?

Find the median recursively of every half and make it the root

Which of the following is an application of Red-black trees and why? a) used to store strings efficiently b) used to store integers efficiently c) can be used in process schedulers, maps, sets d) for efficient sorting

c) can be used in process schedulers, maps, sets RB tree is used for Linux kernel in the form of completely fair scheduler process scheduiling algorithm. It is used for faster insertions, retrievals.

When would it be optimal to prefer RB trees over AVL trees? And inversely?

RB trees → When there are more insertions or deletions AVL trees → when more search

What conditions should a hash function respect?

1. Each key should be equally likely to has to any m slots (no bias) 2. Nearby keys in U should map to different values 3. Independent of any pattern of U 4. Can be computed quickly O(1)

In the division method, how should the d be chosen?

Division method: h(k) = k mod d - Chose d prime not too close from a power of 2 *This method is good as it is easy to implement, but depends highly on d

What is the expected search time for an element in the Chaining method?

O (1 + a) a = n/m

In double hashing, how should the values be chosen?

h(k, i) = (h'(k) + i*h''(k)) mod m) - h''(k) must be relatively prime to m → probe sequence covers full permutations of [0 → m-1] - m has to be prime - 1 < h''(k) < m - uniform hashing, each key should be equally likely to have any of the m! permutations

What information can be gathered from in-order vs post-order vs pre-order tree traversal?

In-order: left child → node → right child - left to right the whole tree no matter the height - with the pre-order, you can know which one is the root node and from there, using in-order know which nodes are in the right vs left subtree (do this "recursively" with smaller subtrees) Pre-order: node → left child → right child - root first (top to bottom) Post-order: left child → right child → node - leafs first from left to right

What is the procedure for deletions in heaps?

In heaps, often delete the root (priority queue) → bring the last element as the new root and heapify from there

What is the result of the sum of a geometric series?

Sum from i = 0 → n of x^i = (x^n+1 - 1)/x - 1