# Algorithm and Complexity Assignment (Python) Use Python language for this Assignment. Find the Resources (Week to week lecture) for this Assignment. Avoid

Algorithm and Complexity Assignment (Python) Use Python language for this Assignment. Find the Resources (Week to week lecture) for this Assignment. Avoid Plagiarism.

Book: Data Structures and Algorithms in Python

Please check the attached zip file for resources –

This assignment is on this topic –

· Stack and Queue

· Linked List and Circular List

· Optimize merge

· Matrix

· Search Trees

· Optimizing Storage

· Map colouring

Please be specific to every answer. HIT220 – Assignment 2

Cat Kutay

Aug 2020

1 Rubric

1. This document is available https://www.overleaf.com/read/cgwdgmvhppzr

2. Submit as a pdf by on Learnline

3. Hand drawings can be scanned and inserted

4. Marking rubric for each question:

Marks will be awarded for accuracy, completeness, and well communicated reasoning which demon-

strates your depth of understanding of the subject matter.

Unless marks otherwise divided up:

a Advanced questions only given marks if correct. Otherwise:

b Full marks are possible if provide working code

c three quarter marks are possible if provide pseudo code

d For these marks:

i. Half marks will be given for right answer

ii. Half marks will be given for working shown with clear explanation of working

All questions total marks are shown. Not all parts are of equal value.

2 Questions

1. (4 points) Stack and Queue

When working with data in a queue, write the following for the different data structures that are

proposed:

a You are given an array of k single-linked-lists of length n, where each linked-list is sorted in ascending

order. Write code or pseudo code to merge all the linked-lists into one sorted ascending linked-list

and return it.

b Write the algorithm using (a) iteration and (b) recursion. What is the Big O complexity of each

version of the algorithm

c Implement a queue using two stacks. What methods do you need to implement for a Queue? What

is the worst-case run time complexity of the method to remove an element?

Advanced Write a method

1

def contains(queueName: Queue, search: str):

return bool

which will take a Queue and a String, and returns True if the Queue contains this string of characters

in the same sequence. Return false if not found in the Queue. The elements in the Queue must

remain in their original order once this method is complete.

2. (3 points) Optimize Merge

a Given an array arr[] of n integers, construct an output array prod[] such that prod[i] is equal to the

product of all the elements of arr[] except arr[floor(i/2)]. Note: floor() is the largest integer < n/2.
b You are to provide code that does not use the division operator and completes in O(n) time.
Advanced Can you improve the space complexity to O(1)
3. (2 points) Matrix
a Given an n x m matrix write the code to output the transpose of the matrices as an m x n matrix
First consider how to store a matrix in your code
b Given an n x m matrix write the code to output the diagonal elements of the matrix as a vector or
sequence of values.
c Given an n x n matrix where each of the rows and columns are sorted in ascending order, return
the kth smallest element in the matrix.
Note that it is the kth smallest element in sorted order of the entire matrix, not the kth distinct
element in the matrix array of arrays∣∣∣∣∣∣
1 5 9
10 11 13
12 13 15
∣∣∣∣∣∣ The 8th element is 13 as the elements of the matrix are [1,5,9,10,11,12,13,13,15].
4. (4 points) Search Trees
The insertion of data into a tree can be done in various ways to ensure the height of the tree is minimum,
and that searching the tree for an item is not more than O(log n).
a Draw separate trees with 8 nodes that are either: balanced; binary tree; neither of these.
b Write in pseudo code or code to traverse the tree and verify if it is balanced and/or binary. First
consider how you will represent the edges and nodes as data in your program and used this in your
code.
c Then consider which search method you will use, and name it in your code.
Advanced Assume your tree is binary. Now:
(a) Write pseudo code or code to carry out a breadth first search of a binary tree
(b) What is the complexity of the search?
(c) What data structure did you use for the storage of nodes as your run the search above?
5. (3 points) Optimizing storage [Advanced]
a We are looking to store water for fire management, and we have located a suitable area, but want
to map out the storage, based on the height map of the surrounding area.
b Given n non-negative integers representing an elevation map where the width of each bar is 1, write
code or pseudo code to calculate the maximum amount of water this elevation can trap between
any two peaks. See example below.
Page 2
c Note you cannot tilt the elevation map.
6. (4 points) Map colouring
Using the Bush Fire Map [2 points]:
Figure 1: input heights = [0,1,0,2,1,0,1,3,2,1,2,1]. Output = 4.
a Draw a graph of the regions on the map
b Store the graph of this map in code
c Write an algorithm in code or pseudo code to find if the map is 4-colourable
d Are you using an exhaustive or greedy algorithm method? Explain.
Advanced 2 points Use your code to advise each region where they can get extra fire trucks from, in an emergency.
Assume the trucks are on average based in the centre of each region during fire season. Rough
estimate of distance is sufficient.
Page 3
Figure 2: Bush Fire regions
Page 4