The University of Melbourne School of Computing and Information Systems COMP90038 Algorithms and Complexity Assignment 1, Semester 1 2020

To improve your understanding of the time complexity of algorithms and recurrence relations. To develop problem-solving and design skills. To improve written communication skills; in particular the ability to present algorithms clearly, precisely and unambiguously.

[4 marks] Consider the following pseudocode:

*x *← 0

for *k *← 1 to *n *do

for *j *← *k *to 2*n *do

*x *← *x *+ 1

- How many times is the inner-most statement (
*x*←*x*+1 ) executed? Justify your answer using the summation notation and rules as described in Appendix 1 of Levitin. - Express the time complexity of the code segment using the appropriate Big
*O/*Ω*/*Θ That is, you should make the strongest possible claim about the complexity of the code segment.

- [4 marks] Consider the following recurrence relation:

where *c *is a positive constant. Assume that *n *= 3* ^{m}*.

Solve the recurrence. Your answer should show how you derive the closed form.

- [8 marks] A manager wants to purchase two different products from a list of
*n*products with a fixed budget*k*. Assume the prices of the*n*products are distinct, which are stored in an array*A*sorted in increasing order of price.

Design an algorithm to find how many different combinations that the manager can choose from. For example, if there are five different products, of which the prices are *A *= [1*,*2*,*3*,*4*,*6] the budget *k *= 4, the algorithm should return 2 as only the combinations of (1*,*2) and (1*,*3) do not exceed the budget.

Note, that the algorithm would be incorrect if it returned a value of 1 corresponding to the product in *A*[3] = 4 as this would not meet the criteria of ‘two different products’ given the budget constraint.

Full marks will be given if your algorithm runs in time. Your algorithm should be presented in unambiguous pseudocode or Python code.

- [4 marks] Your colleague has partially implemented an algorithm to test if a strongly connected graph is bipartite (can be 2-coloured). Pseudocode for her algorithm is presented below.

Your colleague has won the lottery and decided to leave university, so it is up to you to finish the algorithm. Unfortunately, she did not define the data structure for the variable *X*. However, you can tell from the documentation that the data structure was supposed to be either a *stack *or a *queue*.

function IsBipartite(G[0*...n *− 1][0*...n *− 1]) *. *Input is an adjacency matrix *n *× *n*

numSeen = 0

colour[0*...*n-1] ← [-1, ···, -1]

X ← EmptyQueueOrStack( ) PushOrEnqueue(X, <0, RED>) while numSeen < n do i, c ← PopOrDequeue(X) if colour[i] = -1 then

numSeen ← numSeen + 1

colour[i] ← c

nextColour ← RED if c = RED then nextColour ← BLUE

for *j *← 0 to *n *− 1 do if G[i][j] = 1 then if colour[j] = c then return false

PushOrEnqueue(X, <j, nextColour>)

return true

- Will a
*stack*data structure or*queue*data structure produce the correct answer? - Provide an adjacency matrix for a small graph that causes the other data structure to either return the wrong result or not terminate. (Hint: a 3 node graph is sufficient)

- [10 marks] You are an employee of The Department of Environments and Fire Assessment. You have been assigned a task to write an algorithm to calculate the size of the
*largest connected burnt area*in the state of Victoria as a result of the devastating recent bushfires.

A number of simplifying assumptions have been made in this task:

- We will represent the environment using a 2D array (or an abstract map of the area under consideration). Here, the actual scale is not relevant in the problem formulation.
- Each cell in the 2D array contains a binary variable indicating whether the cell has been burnt or not. For example the value of cell
*c*= 1 if the area represented by that site has been burnt. In contrast, the value of cell_{i,j }*c*= 0 if the area represented by that site has not been burnt_{i,j } - A ‘connected burnt area’ is defined as a collection of connected cells where
*c*= 1 (ie., burnt) for all cells. Two cells_{i,j }*c*and_{m,n }*c*are connected if either of the cells is a north, south, east, or west neighbour of the other._{x,y }

For example, in the 2D array below, the size of the largest connected burnt area is 5.

Your algorithm should be presented in unambiguous pseudocode or Python code. *Note*: it may be necessary to modularise your solution using multiple functions.

Full marks will only be awarded if your algorithm is correct with appropriate time complexity. Here, we have not provided a clear definition of ‘appropriate time complexity’. We do this, as we want you to think carefully about the design of your solution – lots and lots of nested for loops is not the correct approach to use.

*Hints:*

- For each cell
*c*, determine which of the other cells it is connect to._{i,j} - How could a graph traversal algorithm be used in this context?

Assignment Writing Help

- Science Assignment Help
- Math Assignment Help
- Chemistry Assignment Help
- Physics Assignment Help
- Biology Assignment Help
- Psychology Assignment Help
- History Assignment Help
- Geography Assignment Help
- English Assignment Help
- Humanities Assignment Help
- Nursing Assignment Help
- Social Science Assignment Help
- Arts and Architecture Help
- Statistics Assignment Help
- Law Assignment Help
- Computational Mathematics Assignment Help

Engineering Assignment Services

- Programming Assignment Help
- Database Help
- Data Structure Assignment Help
- Operating Systems Assignment Help
- Computer Network Assignment Help
- UML Diagram Assignment Help
- IT Assignment Help
- Game Programming Help
- Computer Science Assignment Help
- Information Systems Assignment Help
- Chemical Engineering Assignment Help
- Civil Engineering Assignment Help
- Electrical, Electronics Help
- Mechanical Engineering Assignment Help
- Petroleum Engineering Assignment Help
- Biochemical and Biotechnology Help

Do My Assignment Help

- Accounting Assignment Help
- Finance Assignment Help
- Economics Assignment Help
- Marketing Assignment Help
- Human Resources Assignment Help
- Operations Management Assignment Help
- Strategy and Planning Help
- Project Management Help
- Case Studies Writing Help
- Political science
- Referencing Help
- Assignment Help Websites
- Online Assignment Help
- Do My Assignment
- Do My Homework
- Health Informatics

Write My Essay Services

- Essay Writing Help
- Business Essay Writing Help
- Assignment Writing Services
- Plagiarism Free Essay Writing
- Essay Editing Service
- Dissertation Writing Services
- Thesis Writing Help
- Custom Writing Help
- Write My Essay
- Write My Paper
- Paper Writing Service
- Academic Writing Help
- College Essay Writing
- Cheap Essay Writing