ALGORITHMS AND COMPLEXITY

HIT220 - Week 3 Exercises

Cat Kutay Aug 2020

Recursion

1. Read the pseudo code for BFS and consider how to adapt this process to a verification of a k-mapping. That is, given the k-coloring number for a graph, check if this is valid. We will look at this in class

2. Describe a recursive algorithm for finding the maximum element in a se- quence, S, of n elements. What is your running time and space usage?

Example recursive algorithm is Power:

1 def power(x, n):

2 ”””Compute the value x n for integer n.””” 3 if n == 0:

4 return 1

5 else:

6 return x.power(x, n − 1)

Select your own recursive function and write this up as pseudo code

3. Write a recursive function that will output all the subsets of a set of n elements (without repeating any subsets).

4. (if time) In the Towers of Hanoi puzzle, we are given a platform with three pegs, a, b, and c, sticking out of it. On peg a is a stack of n disks, each larger than the next, so that the smallest is on the top and the largest is on the bottom. The puzzle is to move all the disks from peg a to peg c, moving one disk at a time, so that we never place a larger disk on top of a smaller one. See Figure 4.15 for an example of the case n = 4. Describe a recursive algorithm for solving the Towers of Hanoi puzzle for arbitrary n.

See https://www.mathsisfun.com/games/towerofhanoi.html

Lists

1. Give an algorithm for finding the second-to-last node in a singly linked list in which the last node is indicated by a next reference of None

1

2. Give a complete implementation of the stack ADT using a singly linked list that includes a header sentinel.

3. Describe a fast recursive algorithm for reversing a singly linked list.

4. Write a method for a class acting on a doubly linked list called swap(p,

q) that causes the underlying nodes referenced by positions p and q to be exchanged for each other. Relink the existing nodes; do not create any new nodes (Hint: The class contains a Position subclass that efficiently describe the location of the operation)

Example code for Class attached