Reference no: EM132930413 , Length: word count:3000

5003CEM Advanced Algorithms - Coventry University

Code Submission and Report
Learning Outcome 1: Design and implement algorithms and data structures for novel problems
Learning Outcome 2: Specify and implement methods to estimate solutions to intractable problems
Learning Outcome 3: Design and implement a basic concurrent application

TASKS:

STD 1
Binary search
Implement binary search in Python or C++. Please find the pseudocode for this implementation below.

BINARY_SEARCH(sequence, value)
middle ← GET_MIDDLE(sequence)
WHILE value != sequence[middle]
IF length(sequence) > 1
IF value > sequence[middle]
sequence ← sequence[middle .. length(sequence)]
ELSE
sequence ← sequence[0 .. middle]
ELSE
IF value != sequence[middle]
RETURN FALSE
middle ← GET_MIDDLE(sequence)
RETURN TRUE

STD 2
Double Linked List
Implement the insertion of an element in a double linked list in Python. You can find pseudocode in lecture Week 5 from Slide 78 for deleting an element in a double linked list. You should insert "Wed" in the implementation of the double linked list.

Note that the code shown here is also on Aula with the assessment: doubleLinkedList-withoutSolution.py

class Node:
def __init__(self, dataval = None):
self.data = dataval
self.next = None
self.prev = None

class SLinkedList:
def __init__(self):
self.head = None
self.tail = None

def listprint(self):
printval = self.head
while printval is not None:
print (printval.data)
printval = printval.next

def AtBeginning(self,newdata):
NewNode = Node(newdata)

def AtEnd(self, newNode):
if self.head is None:
self.head = newNode
return
last = self.head
while(last.next):
last = last.next
last.nexts = newNode

list = SLinkedList()
list.head = Node("Mon")

e2 = Node("Tue")
e3 = Node("Thur")
e4 = Node("Fri")
e5 = Node("Sat")
e6 = Node("Sun")
list.head.next = e2
e2.next = e3
e3.next = e4
e3.prev = e2
e4.next = e5
e4.prev = e3
e5.next = e6
e5.prev = e4
e6.prev = e5
list.AtEnd(e5)

list.listprint()

STD 3
Quicksort with middle value as pivot
Implement quicksort with the middle value as a pivot in either Python or C++.

ADV 1
BST traversal: pre-order, in-order, post-order.
For this task, which is to be completed in Python, use the code BST_BASIC-insert+pretty-print.py, on Moodle with this assessment specification.
Implement pre-order, in-order, and post-order traversal using three different methods.
If your instance of the BinaryTree class is called bst, call the methods using:
bst.pre_order()
bst.in_order()
bst.post_order()
Each call should return its result as a list.

ADV 2
Concurrent Powers
The following code returns the results of the integers in a list of values to the power of input po. Rewrite this as concurrent code in Python, using concurrent.futures. In the concurrent version, it is not necessary for results to be printed in the same sequence as is output by the code below.

values = [2,3,4,5,6,7,8,9,10]

def powers(val,po):
return val ** po

def non_concurrent_powers(po):
for val in values:
res = powers(val,po)
print('%s to the power of %s is %s' % (val,po,res), '\n')

This code is in the file non_concurrent_powers.py, on Moodle with this assessment.

Attachment:- Advanced Algorithms.rar