DoA

Question 1

Time complexity of merge sort

Answer 1

O(nlogn)

Question 1

Time complexity of Binary search

Answer 1

O(logn)

Question 2

Time complexity of insertion sort

Answer 2

O(n^2)

Question 3

Give a recurrence T (n) = · · · for the worst-case running time of Binary search

Answer 3

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

Question 4

Give a recurrence T (n) = · · · for the worst-case running time of Merge sort

Answer 4

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

Question 5

Give a recurrence T (n) = · · · for the worst-case running time of Insertion sort

Answer 5

T(n) = T(n-1) + ϴ(n)
T(1) = ϴ(1)

Question 6

Radix

Instead of using countingsort to sort digitals in the radixsort, one can use any in-place sorting algorithm
and the radixsort will still sort correctly. TRUE or FALSE? Why?

Answer 6

False

Radix sort relies on stable sorting algorithms for each digit place. While it’s true that you can use any stable sorting algorithm, not every in-place sorting algorithm is stable.

Question 7

Explain Binary search tree (BST)

Answer 7

A BST is a hierarchical data structure consisting of nodes, where each node has a key, and at the most 2 children.

The keys in the left subtree of a node are less than its key, and the keys in the right subtree are greater than its key.

Question 8

Explain AVL-tree

Answer 8

An AVL tree is a self-balancing binary search tree that maintains a height-balanced property, ensuring that the height difference between the left and right subtrees of any node (called the balance factor) is at most 1.

Question 9

Explain min-heap
And shortly how to make insertions in it.

Answer 9

A tree where every node is smaller than its children.

The tree is always filled up from left to right.

Insertions happens into the next empty space and if the inserted node is smaller than its parent: swap

Question 10

Explain max-heap
And shortly how to make insertions in it.

Answer 10

A tree where every node is greater than its children.

The tree is always filled up from left to right.

Insertions happens into the next empty space and if the inserted node is greater than its parent: swap

Question 11

True or false?
2n + n^3 = O(2n).

Answer 11

False
Instead it is:
2n + n^3 = O(n^3).

Question 12

Time complexity of counting sort

Answer 12

O(n+k)

Where ‘n’ Represents The Number Of Elements And ‘k’ Represents The Range Of The Inputs.

Question 13

Time complexity of radix sort

Answer 13

O(nd)

where ‘n’ is the size of the array and ‘d’ is the number of digits in the largest number

Question 14

Give a recurrence T (n) = · · · for the worst-case running time of selection sort

Answer 14

T(n) = T(n-1) + O(n)
T(1) = O(1)

Question 15

Time complexity of selection sort

Answer 15

O(n^2)

Question 16

Time complexity of In-Order-Walk

Answer 16

ϴ(n)

Question 17

Give a recurrence T (n) = · · · for the worst-case running time of in-order-walk

Answer 17

T(1) = ϴ(1)
T(n) = T(k) + ϴ(1) + T(n-k-1)

Question 18

Time complexity of depth first search

Answer 18

O(V + E)

Where V is the number of nodes and E is the number of edges.

Question 19

Time complexity of breadth first search

Answer 19

O(V + E)

Where V is the number of nodes and E is the number of edges.

Question 20

Give a recurrence T (n) = · · · for the worst-case running time of quick sort

Answer 20

T(1) = O(1)
T(n) = T(i) + T(n — i — 1) + cn

Question 21

Time complexity of quick sort

Answer 21

O(n^2)

Question 22

Time complexity of bubble sort

Answer 22

O(n^2)