[SOLVED] C algorithm python graph FIT104553 Algorithmic Problem Solving Workshop 10.

FIT104553 Algorithmic Problem SolvingWorkshop 10.
Ob jectives
The objectives of this workshop are:
To understand the uses of stacks.
To practice using backtracking to solve problems.
MARKS: You must follow all restrictions outlined to receive any marks. Assuming restrictions are followed, marks for this workshop will be determined by the tester.
Preparation
Revise backtracking and stacks, as discussed in the lectures.
Task 0
Download test files and create Python file
Name Python file FIT1045 workshop10.py. Task 1: Using Stacks
stacks
Write a function reducestack that takes as input a stack of integers and returns the length of a reduction of the stack. To reduce the stack, you may remove pairs of adjacent numbers as they occur they need not be adjacent in original list. For example, calling reduce5,3,4,2,2,4,5 would return 3 because of the following operations:
5,3,4,2,2,4,5 remove the two 2s
5,3,4,4,5 remove the two 4s
5,3,5 nothing else can be removed, return the length of the stack
You must only use stack operations in this task i.e. when manipulating the list, you may use pop and append.
Task 2: Backtracking
backtracking; manipulating graphs
In the lectures you were given the following code:
def solutionscompleted, options, partial:
function code from FIT1045 Lecture 17, slide 42
if completedpartial:
return partial
else:
res
for o in optionspartial:
augmentedpartialo
ressolutionscompleted, options, augmented
return res
1

def backtrackingtaskx:
def optionspartial:

def completedpartial:

return solutionscompleted, options, startingpartial
This code provides a framework for many although not all of the backtracking problems you will see in this unit; however, you may not fully understand everything it does. Ensure you understand what each line of code is doing before you implement it. Remember, if you use code from the lectures you must cite it. It is sufficient to include a comment such as code forfunctionadapted from Lecture , slide .
Part APalindromic Bitlists
Write a function palindrome binaryn which returns a list of bitlists of length n, where every bitlist is a palindrome. The returned list of bitlists must be in lexicographical order think about the order of your options. You must use backtracking to solve this problem i.e. do not use brute force.
Part BAll Paths
Write a function all pathsM, u, v which takes as input an adjacency matrix of a graph, M, and two vertices u, v and returns a list of all paths from u to v in M. A path is a list of vertices. Note that a path cannot use the same vertex twice, but two different paths can use some of the same vertices. The returned list of paths must be in lexicographical order. You must use backtracking to solve this problem i.e. do not use brute force.
Part CStairs
Write a function stairsstaircase which takes information regarding a staircase, and returns the number of different ways it is possible to climb the staircase. The function must:
take a bitlist of length2 representing a staircase as input.
the first and last elements of the staircase are always 1, as they represent the start and finish points.
elements in staircase that are not the first and last may be 0 or 1, where 0 represents an unsafe stair, and 1 a safe stair.
it is possible to climb the staircase by jumping one step, two steps, or three steps; but it is not possible to jump the same number of steps twice in a row.
Example: calling stairs1,1,0,1,1 returns 3 as it is possible to jump startfirstthirdfinal, startfirst final, or startthirdfinal. Calling stairs1,0,1,0,1 returns 0 as it is not possible to climb the staircase, given the restrictions.
You must use backtracking to solve this problem i.e. do not use brute force. Extension Task 3: Converting Numbers
Write a function converta, b, c which takes three positive integers, a, b, and c, and returns the fewest number of operations needed to convert a to b. There are three permitted operations:
a1a2ac
Example: calling convert3,20,2 returns 4 as a can be converted to b using the following minimum series of operations :
aa2aa1
2

aa2
aa2 thus, a20b
This problem can be solved using backtracking. However, you will find that if you try to use the backtracking framework given to you in lectures, you will always get a stackoverflow error think about why this might be by drawing out the trace tree. You will need to come up with a different way of utilising the strengths of backtracking.
3