Other algorithm questions

Question 1

Definition of Big O

Answer 1

Let g(n) be a function.

Then O(g(n)) is the set of functions:

O(g(n)) = {f (n) : There exist positive constants c and n0
such that 0 ≤ f (n) ≤ cg(n) for all n ≥ n0}

Question 2

Definition of Θ-notation

Answer 2

Let g(n) be a function.

Then Θ(g(n)) is the set of functions:

Θ(g(n)) = {f (n) : There exist positive constants c1, c2 and n0 s.t. 0 ≤ c1g(n) ≤ f (n) ≤ c2g(n) for all n ≥ n0}

Question 3

Definition of Ω-notation

Answer 3

Let g(n) be a function.

Then Ω(g(n)) is the set of functions:

Ω(g(n)) = {f (n) : There exist positive constants c and n0
such that 0 ≤ cg(n) ≤ f (n) for all n ≥ n0}

Question 4

What is a loop invariant?

Answer 4

A loop invariant is a property that is true before iteration i and is also true before iteration i+1.

Question 5

Equations for:

Number of Levels?
Number of nodes on the ith level?
Array length of nodes on ith level?

In a Merge Sort.

Answer 5

Num of Levels = ⌈log n⌉ + 1
Num of Nodes at ith level = 2^(i-1)
Array length at ith level = ⌈n/2^(i-1)⌉

Question 6

What is a full tree for a k-ary tree?

Answer 6

A tree is full if every internal node has exactly k children.

Question 7

What is a complete tree?

Answer 7

A tree is complete if all levels except possibly the last is entirely filled.

Question 8

What is a perfect tree?

Answer 8

A tree is perfect if all levels are entirely filled.

Question 9

What is the heap property?

Answer 9

Every element of the tree is larger than any of its children if they exist.

Question 10

What does Heapify() do?

Answer 10

Checks if the children of an element are greater than the element. If the child is great than the element the two nodes will be exchanged.

Question 11

What is the best way to select a pivot for Quicksort?

Answer 11

Select the pivot at random.