Algorithms

Question 1

Loop invariant

Answer 1

an assertion about the loop that is relevant to the purpose of the loop and that holds true before and after each iteration through the loop

Question 2

Sequential Search vs. Binary Search

Answer 2

Sequential Search is faster when the list is NOT sorted in ascending or descending order. Binary search employs the “half-half-half” method to find the target. This works best if the list is already sorted

Question 3

Iterations for Binary Search (sorted)

Answer 3

for 2^k - 1 elements, binary search requires at most k iterations. With an array of n elements, this is log(base2)n iterations

Question 4

Iterations for Sequential Search

Answer 4

n/2 (elements) < # iterations < n (elements)

Question 5

Selection Sort

Answer 5

number of required comparisons is about n^2. Iterate for k from n down to 2: find the largest among the first k elements and swap it with the kth element

Question 6

Insertion Sort

Answer 6

number of required comparisons is about n^2. iterate for k from 2 up to n. Keep the first (k-1) elements sorted and insert the k-th element among them where it belongs

Question 7

Insertion Sort vs. Selection Sort:

Answer 7

Insertion Sort, on average, requires more moves than selection sort. NEITHER, however, ALWAYS requires more moves than the other

Question 8

While vs. if in recursion

Answer 8

if usually replaces while loops for recursion methods, such is the entire PURPOSE of recursion

Question 9

Merge sort comparison

Answer 9

nlogn

Question 10

Merge sort method:

Answer 10

divide the array into two approximately equal halves; sort recursively each half, then merge them together into one sorted array

Question 11

Technique of Sequential Search:

Answer 11

consists of checking every one of its elements, one at a time and in sequence, until the desired one is found.[1] (Almost always slower than binary search)

Question 12

Insertion Sort Technique:

Answer 12

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. On a repetition, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain. It does NOT switch the elements.

Question 13

Selection Sort Technique:

Answer 13

This is the one that DOES switch the elements.

Question 14

Insertion Sort Run Times and storage complexities

Answer 14

Wort number of comparisons: n^2
Best comparisons: n
Average: n^2

Question 15

Selection Sort Run Times and storage complexities:

Answer 15

Worse number of comparisons: n^2
Best comparisons: n^2
Average: n^2

Question 16

Merge Sort Technique:

Answer 16

divide and conquer (usually with recursion).

Question 17

Merge Sort run times and storage complexities:

Answer 17

worst AND best case run time = nlogn

Average = nlogn