DFS Programming

1. Know essential characteristics of DFS:
   • Last In, First Out
   • parent
   • time in/out
2. Write examples carefully tracing the excecution of the standard DFS algorithm.

Programming Skills

1. Expose all changing parameters as inputs to a function to make it debuggable. (Get rid of global variables.)
2. Write test cases. Simple to complex.
3. Debugging with tests, not single-stepping with the python debugger or using the Python tutor visualizer).

Programming 1

• Write a recursive DFS algorithm that can return information about parent, time in, and time out for each vertex.
• Write at least three test cases for your code.

Programming 2

• Binary search frequently implemented recursively. See below for the ChatGPT version, which takes in a sorted list of number (arr), the number to find (target) and the lowest and highest possible indices that could contain the target (inclusive). It returns the index at which the target element is found, or -1 if the array does not contain the target.

def binary_search(arr, target, low, high):
    if low > high:
        return -1  # Element not found

    mid = (low + high) // 2

    if arr[mid] == target:
        return mid  # Element found at index 'mid'
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, high)
    else:
        return binary_search(arr, target, low, mid - 1)

Programming 2a

Change the binary search code to use a stack instead of recursion, keeping low and high on your stack. Write at least three tests!

Programming 2b

Do you need an answer stack in your binary search? How could you know by looking at the recursive code, before you wrote anything?

Programming 3

There is a recursive algorithm for very efficiently finding the power of a number. (Shown below, courtesy of ChatGPT.)

def power(x, n):
    if n == 0:
        return 1

    half_power = power(x, n // 2)

    if n % 2 == 0:
        return half_power * half_power
    else:
        return x * half_power * half_power

Programming 3a

Do you need an answer stack in your power function? How could you know by looking at the recursive code, before you wrote anything?

Programming 3b

Rewrite the power algorithm to use a stack. Write at least three tests.

Programming 4: Stack based DFS with parent

Using the strategy of pushing (parent,child) pairs onto the stack, write a non-recursive DFS that can set the parent. No time in/out needed.

You need at least three tests showing your code works.

Debugging 5

You might try an inner loop like the one below, which turns out to be buggy. The idea is that when you start processing a vertex, you leave that vertex on the stack and mark it as visited. Then when you get back to that vertex on the stack again, you record the time_out.

Write some code that demonstrates that this does not work.

while todo:
    current = todo.pop()

    now += 1
    print(f'now = {now}')

    if current in time_in:
        time_out[current] = now
        continue
    else:
        time_in[current] = now
        visited[current] = True
        todo.append(current)
    for v in sorted(edges[current], reverse=True):
        if not visited[v]:
            todo.append(v)
            parent[v] = current
            print(f'parent[{v}] = {current}')

Optional

• Converting a recursive function to use an explicit stack.