Algorithm And Complexity Assignment

Algorithm And Complexity Assignment

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

We write papers for students

Tell us about your assignment and we will find the best writer for your paper.

Get Help Now!

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

The post Algorithm And Complexity Assignment appeared first on Essay Solving.