Exam

Question 1

Analysis of Selection Sort

Answer 1

Best case:
Array in sorted order
Comparisons: O(n^2)
Time: O(n^2)

Average case:
Comparisons: O(n^2)
Time: O(n^2)

Worst case:
Array in reverse order
Comparisons: O(n^2)
Time: O(n^2)

Question 2

Analysis of Merge Sort

Answer 2

Best case:
Comparisons: O(n log n)
Time: O(n log n)

Average case:
Comparisons: O(n log n)
Time: O(n log n)

Worst case:
Comparisons: O(n log n)
Time: O(n log n)

Question 3

Analysis of Insertion Sort

Answer 3

Best case:
Array in sorted order
Comparisons: O(n)
Time: O(n)

Average case:
Comparisons: O(n^2)
Time: O(n^2)

Worst case:
Array in reverse order
Comparisons: O(n^2)
Time: O(n^2)

Question 4

Analysis of Quick Sort

Answer 4

Best case:
Comparisons: O(n log n)
Time: O(n log n)

Average case:
Comparisons: O(n log n)
Time: O(n log n)

Worst case:
When the list is sorted and left most element is chosen as the pivot
Comparisons: O(n^2)
Time: O(n^2)

Question 5

Analysis of Shell Sort

Answer 5

Best case:
Comparisons: O(n log n)
Time: O(n log n)

Average case:
Comparisons: O(n^4/3)
Time: O(n(log(n))^2)

Worst case:
Comparisons: O(n^3/2)
Time: O(n(log(n))^2)

Question 6

Given a list of size n, for which gap value is shell sort the same as insertion sort?

Answer 6

1

Question 7

Analysis of Sequential Search

Answer 7

Best case:
O(1)

Average case:
O(n)

Worst case:
O(n)

Comparisons:
n

n+1/ 2

Question 8

Analysis of Binary Search

Answer 8

Best case:
O(log n)

Average case:
O(log n)

Worst case:
O(log n)

Comparisons:
log n
2 log n (average)
n (best)

Question 9

Pros and Cons of Selection Sort

Answer 9

Pros:
Simple implementation

Cons:
Inefficient on large lists

Question 10

Pros and Cons of Merge Sort

Answer 10

Pros:
Quicker for larger lists
Unlike insertion sort, it doesn’t go through the list multiple times

Cons:
Comparatively slower than other algorithms for smaller data sets

Question 11

Pros and Cons of Insertion Sort

Answer 11

Pros:
Simple implementation
Extremely efficient on small lists
More efficient than bubble and selection sort

Cons:
Much less efficient on large lists

Question 12

Pros and Cons of Quick Sort

Answer 12

Pros:
An in-place sorting algorithm does not use additional memory space while sorting.

Cons:
Not very stable

Question 13

Binary Search Tree Analysis

Answer 13

Average:
O(log n)

Worst:
O(n)

Question 14

Hash Table Analysis

Answer 14

Average:
O(1)

Worst:
O(n)

Question 15

Calculate the number of comparisons insertion sort

Answer 15

Best Case:
n - 1

Worst Case:
n(n-1)/2

Question 16

Calculate the number of comparisons selection sort

Answer 16

n(n-1)/2

Question 17

Benefits of Hash search over Binary Search

Answer 17

Hash search has O(1) for:
Search
Insert
Delete

Binary only has O(log n)

Question 18

Benefits of Binary Search over Hash Search

Answer 18

Binary Search can get all keys in sorted order by just doing an inorder traversal
Binary Search is easier to implement whereas Hash Search general requires importing libraries

Question 19

An important advantage of quadratic probing over Linear Probing

Answer 19

Quadratic Probing is far less prone to clustering whereas Linear Probing forms groups by placing elements one after another thus clustering occurs which can slow down the algorithm

Question 20

What is BFS (Breadth First Search) used for?

Answer 20

• Shortest Path in an unweighted graph
• Underpins other algorithms
• Peer-to-peer networking
• Cycle detection

Question 21

What is DFS (Depth First Search) used for?

Answer 21

• Finding connected components in subgraphs
• Maze solving and generation
• Solving problems which have only one possible solution
• cycle detection
• Scheduling

Question 22

Prim’s algorithm is:

Answer 22

• Built from a starting vertex

- Similar to BFS

Question 23

Kruskal’s algorithm is:

Answer 23

• Built by picking edges anywhere in a graph

- Priority queue

Question 24

How do you know if an Euler’s PATH exists in a graph?

Answer 24

if and only if there are no more than 2 vertices with an odd number of edges

Question 25

How do you know if an Euler’s CYCLE exists in a graph?

Answer 25

if and only if all vertices have an even number of edges