Test 1 Questions

Question 1

The time complexity of an algorithm can be Ω(n) and O(n^2)

T/F

Answer 1

TRUE

Question 2

Interpolation search is ___ on average than binary search.

Answer 2

Faster

Question 3

Given an unsorted array of n integers, the median element in the array can be found ____ time in the average-case

Answer 3

Θ(n)

Question 4

Quicksort uses a ____ pivot selection

Answer 4

Randomized.

Question 5

Is there an algorithm that can factor an integer into its prime factors in polynomial time?

Answer 5

Yes

Question 6

The asymptotic time complexity for adding two n-bit integers is:

Answer 6

Θ(n)

Question 7

Timsort is a hybrid of

Answer 7

Merge and Insertion Sort.

Question 8

Timesort is a ___ sorting algorithm

Answer 8

Stable - Like Merge and Insertion Sort.

Question 9

In a binary heap (tree), any two leaf nodes have either the same depth or depths differing by one.

T/F

Answer 9

TRUE

Question 10

Given an array of 1 million records which only a few are out of order and are not far from their correct position, the best choice of sorting algorithm is :

Answer 10

Insertion Sort

Because the array is almost sorted.

Question 11

What is the selection problem?
What is the name of an algorithm that solves the selection problem?

Answer 11

Find the i-th element in an unsorted array.
Quickselect.

Question 12

What algorithm have Θ(n ^ (lg2^3)) time complexity?

Answer 12

Divide and Conquer Multiplication.

Question 13

What is meant by a decrease and conquer algorithm?
Name 3 Decrease and conquer algorithms

Answer 13

With every recursive call the size of the input decreases.

1. Binary Search
2. Square Root Alg
3. Euclid’s Alg

Question 14

What’s the recurrence relation for quicksort?

Answer 14

T(n)= 2T(n/2) + n

Question 15

Give the name of another sorting algorithm with the same recurrence relation with quicksort?

Answer 15

Merge Sort

Question 16

Describe a better way to pick a pivot in quicksort.

Answer 16

1. Get 1st, Last, and Middle element/index and use the median of those.
2. Randomly pick a pivot.

Question 17

If a heap is used to represent a priority queue, and the first element is removed, the heap property is restored by moving the last element to the root of the tree, and then running MAX-HEAPIFY on the new root element. What is the worst-case complexity of restoring the heap property this way?

Answer 17

Θ(log n)

Question 18

Name a sorting algorithm that has better best-case complexity than worst-case complexity and give both its best and worst-case complexity.

Answer 18

Max-Heapify

Best: Θ(1)
Worst: Θ(log n)

Question 19

What’s an “in-place” algorithm? Give an example.

Answer 19

Uses at most O(1) more space than the original array.

Heap Sort

Question 20

What’s a “stable” algorithm? Give an example.

Answer 20

Doesn’t change the duplicate’s original ordering relative to each other.

Merge Sort.

Question 21

Give an example of a hybrid sorting algorithm.

Answer 21

You can use quickselect and once the array get to a smaller size, switch to Insertion Sort.