COMP3121代写、代写Java，Python编程

日期：2022-09-27 10:17

COMP3121/9101 22T3 — Assignment 1

Due 29th September 2022 at 5pm Sydney time

Your solutions must be typed, machine readable PDF files. All submissions will be checked for

plagiarism!

For each question requiring you to design an algorithm, you must justify the correctness of your

algorithm. If a time bound is specified in the question, you also must argue that your algorithm

meets this time bound.

Partial credit will be awarded for progress towards a solution.

Question 1 The Cheapest Fridge

[30 marks] Song wants to buy a fridge with volume at least V cubic centimetres. The shop sells

a large variety of fridges. More precisely, for each positive integer x, the shop sells a fridge for x

dollars with the following dimensions:

width 3x centimetres,

depth 2x+ 1 centimetres and

height 2x centimetres.

1.1 [12 marks] Design an algorithm which runs in O(log V ) time and finds the minimum amount

that Song must spend to buy a suitable fridge.

1.2 [18 marks] Design an algorithm which runs in O(log(log V )) time and finds the minimum

amount that Song must spend to buy a suitable fridge.

You may choose to skip 1.1, in which case your answer to 1.2 will be marked as your answer to 1.1

also.

Question 2 Counting Occurrences

[30 marks] Answer the following:

Be very careful with the requested time bounds.

2.1 [6 marks] Let X = [x1, . . . , xn] be a sorted array of n positive integers. Design an algorithm

to count the number of occurrences of each distinct integer in X in worst case O(n) time.

2.2 [12 marks] Let Y = [y1, . . . , yn] be an unsorted array of n positive integers. Design

an algorithm to count the number of occurrences of each distinct integer in Y in expected O(n)

time.

2.3 [12 marks] Let Z = [z1, . . . , zn] be a sorted array of n positive integers. You are also given

an integer k ≤ n, the number of distinct integers in this array. Design an algorithm to count the

number of occurrences of each distinct integer in Z in worst case O(k log n) time.

Question 3 Counting Inversions Between Arrays

[20 marks] Let A and B be two arrays of length n, each containing a random permutation of

the numbers from 1 to n. An inversion between the two permutations A and B is a pair of values

(x, y) where the index of x is less than the index of y in array A, but the index of x is more than

the index of y in array B.

1

COMP3121/9101 22T3 — Assignment 1 (UNSW Sydney)

Design an algorithm which counts the total number of inversions between A and B that runs in

O(n log n) time.

Question 4 Red & Yellow Flowers

[20 marks] You are given an array of n flowers that are either red or yellow. Your goal is to find

the number of subarrays where there are more red flowers contained within the subarray, than

there are yellow flowers outside the subarray.

Subarrays must be contiguous.

4.1 [6 marks] Describe a method that runs in O(n) time, which pre-processes the input array

such that you can then calculate the number of red flowers within any contiguous subarray in O(1)

time.

4.2 [14 marks] Design an algorithm that achieves your goal in O(n log n) time.