General

Question 1

For the classic Breadth First Search, (a.) what kind of loop do we implement? (b.) What is the terminating condition for said loop?

Answer 1

a. While Loop
b. existence of elements within queue

Question 2

What are two primary functions of a Breadth First Search algorithm?

Answer 2

a. Check to see if a path exists between A and B
b. Find shortest path between A and B

Question 3

How do you avoid infinite loops when implementing a Breadth First Search?

Answer 3

Maintain and update a ‘searched’ array.

if name not in searched: 
    searched.append(name)

Question 4

What are three key variables to initialize/maintain in the classic binary search?

Answer 4

1. high
2. mid
3. low

Question 5

What is a pivot? How do you decide the pivot?

Answer 5

It is a randomly selected element within an unsorted list. It is used for quicksort.

Question 6

What is the basic outline for quicksorting?

Answer 6

Recursive divide and conquer algorithm:

quicksort(smaller) + [pivot] + quicksort(larger)

Question 7

Describe BFS process

Answer 7

Assume graph exists.

1. initialize queue
2. initialize processed array
3. insert parent node into queue
4. while queue has elements
   
   • target = queue.pop
   • if target not in processsed array
   • perform logic ==> t/f
   • and if false, queue += graph[target]

Question 8

binary search uses what kind of loop?

Answer 8

While loop (while low < high). The trick is that the ‘guess’ is based on the ‘high’ and ‘mid’ values, which are scoped outside the loop and change on every iteration. The ‘mid’ value is scoped within the loop itself.

Question 9

When performing a merge in merge sort, what is the type of loop used? What is the condition necessary to terminate iteration?

Answer 9

While Loop, the terminating condition is when the iterators associated with each sub-array are less than the lengths of the sub-arrays. So

while i < len(left) and j < len(right):

Question 10

What is the last step of a merge sort (after the merge)?

Answer 10

The last step is adding any remaining elements from sub-arrays. You perform two while loops (not nested). Ex:

while i < len(left):

` arr[k] = left[i]`

` k+=1`

` i+=1`