Simple Algorithms

Question 1

What does binary search set as the input sequence?

Answer 1

The partition.

Question 2

What is the first thing binary search does with the list of items within the input sequence?

Answer 2

Finds the index of the middle item and checks whether or not this is the target item.

Question 3

How does binary search know to discard part of the input sequence each time?

Answer 3

As the input sequence is ordered, binary search compares the target item with the middle item of the input sequence - if the target item is greater, then the lower half of the input sequence can be discarded and vice versa.

Question 4

Does binary search operate on an ordered or an unordered input sequence?

Answer 4

Ordered.

Question 5

What is the complexity of binary search?

Answer 5

O(log n).

Question 6

Does bubble sort operate on an ordered or an unordered input sequence?

Answer 6

Either, but assume unordered.

Question 7

What is the complexity of bubble sort?

Answer 7

O(n^2).

Question 8

How many times does bubble sort iterate over a list?

Answer 8

n-1 times, where n is the length of the list.

Question 9

What does bubble sort do on each iteration of the list?

Answer 9

Compares each pair of adjacent items and swaps them if they are out of order.

Question 10

In the short bubble sort, what happens if no exchanges are made in an iteration?

Answer 10

The sort is terminated.

Question 11

What is the complexity of selection sort?

Answer 11

O(n^2).

Question 12

Does selection sort operate on an ordered or an unordered input sequence?

Answer 12

Either, but assume unordered.

Question 13

What does selection sort do on each iteration of a list?

Answer 13

Compares the element at index i with each element in the list, swapping the element at index i with the first lesser element it finds, then increases the index before iterating again.

Question 14

How many times does selection sort iterate over a list?

Answer 14

n-1 times, where n is the length of the list.

Question 15

By using in-place sorting in selection sort, how many lists are ‘in memory’?

Answer 15

Two, a sorted list to the left of the element at index i, and an unsorted list to the right of the element at index i.

Question 16

What is the complexity of insertion sort?

Answer 16

O(n^2).

Question 17

Does insertion sort operate on an ordered or an unordered input sequence?

Answer 17

Either, but assume unordered.

Question 18

How many times does insertion sort iterate over a list?

Answer 18

1 time.

Question 19

What does insertion sort do on an iteration of a list?

Answer 19

Compares the element at index i with the next element in the list, the lesser of the two is considered sorted. The algorithm then compares the next element at index i with the element at index i+1, the lesser of the two is then compared to the element at i-1, and the list is sorted backwards.

Question 20

By using in-place sorting in insertion sort, how many lists are ‘in memory’?

Answer 20

Two, a sorted list to the left of the element at index i, and an unsorted list to the right of the element at index i.