2023年11月25日

Java数据结构代写 | COMP2100/6442 Lab 5 – BTrees

本次澳洲代写主要为结构相关assignment的算法代写

 

Problem 1 (3 marks – at most 1/2 page). Determine if the following statements are true or false AND provide a formal proof using either limits or the definitions of the big-O,big-Omega, and big-Theta notations. For instance, to prove that f (n) 2 O(g(n)) or f (n) ÝO(g(n)), using the definitions of big-O, we need to demonstrate the existence of a constant c and a sufficient large n0 such that f (n) · cg(n) for all n ¸ n0, or showing that there are no such values. Using limits, for instance, we need to show that limn!1 f (n)/g(n) Ç1 for f (n) 2 O(g(n)), or showing that limn!1 f (n)/g(n) Æ 1 for f (n) Ý O(g(n)). Note that there will be no marks if only true/false answer is given.

a) [1 mark]p4n2Å2n 2£(n).
b) [1 mark] n100 2O(en).
c) [1 mark] loge(n2) 2­(on).

Problem 2 (3 marks – at most 2 sentences). Arrange the following functions in an in-creasing order of their growth rates.
f1(n) Æ 1000n,
f2(n) Æ (logn)2,
f3(n) Æ n!,
f4(n) Æ nlogn,
f5(n) Æ 2n.
Problem 3 (4 marks – at most 1 page). In the following questions we assume that m grows more slowly than logn.
a) [2 marks] Design an in-place algorithm (description + pseudo code + complexity analysis) to find m smallest elements (possibly repeated) in an array of real numbers of size n with time complexity O(nm). Note that no extra data structures are allowed.
a) [2 marks] Design another algorithm (description + pseudo code complexity analysis) to find m smallest elements (possibly repeated) in an array of real numbers of size n with time complexity O(nlogm). Extra data structures are allowed.
Problem 4 (2 marks – at most 1/2 page). Design a non-recursive algorithm (algorithm description + pseudo code) that takes as input the root of a binary search tree and return the maximum key stored in the tree.

Problem 5 (5 marks – at most 1.5 pages). Let A be an array of size n contains a list of records in which the field “gender” has value either M or F. Suppose that n is even for simplicity.

a) [2 marks] Design an in-place recursive decrease-and-conquer algorithm (description + pseudo code) of complexity O(n2) that swaps the elements of the array so that their genders alternate between M and F as much as possible. If there are more M than F, then all the uncoupled M are grouped at the end of the array. Similarly,if there are more F than M, then all the uncoupled F are grouped at the end of the array. For example, if the list is (ID1,F), (ID2,F), (ID3,M), (ID4,F), (ID5,M), (ID6,M), (ID7,F), (ID8,F),then the output could be (ID5,M), (ID7,F), (ID3,M), (ID8,F), (ID6,M), (ID1,F), (ID2,F), (ID4,F).
Note that inefficient algorithm, in particular, algorithms with complexity ­(n3) will attract a zero mark.

a) [2 marks] Determine the recurrence relation for the number of comparisons C(n) required by your algorithm and solve it using the backward substitution method.

What is the complexity class of C(n) in big-O notation?

b) [1 marks] Determine the recurrence relation for the number of swaps S(n) required by your algorithm and solve it using the backward substitution method. What is the complexity class of S(n) in big-Theta notation?

Problem 6 (9 marks – at most 2 pages). Two years after graduation, you are hired by RMIT’s School of Computing Technologies as a software engineer. Your first task is to develop a Course Management software that can answer common students’ questions automatically. One of the common questions, frequently asked by students who don’t want to complete the whole program but are only interested in a few courses, is about the number of minimum credits one needs to accumulate before taking a certain course.
The input is a curriculum which consists of n courses, indexed by integers from 0 to n¡1. Each course i has ci credit points and also a list Pi of prerequisites (PRQs). Let m be the number of pairs (i, j), 0 · i Æ j · n¡1, where i is a PRQ of j. Your task is to design two algorithms (description + pseudo code + complexity analysis) that return the total number of credits Ti a student has to accumulate before each course
i Æ 0,1, . . . ,n¡1, can be taken, under two different scenarios in Part a) and Part b). Your algorithm must output the minimum number of credits required as PRQs for every course (see Fig. 1).