Reference no: EM132880979

Algorithm Design and Complexity Analysis

Problem 1: 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) ∈ Og(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 n such that f (n) ≤ cg(n) for all n ≥ n₀. or showing that there are no such values. Using limits, for instance, we need to show that lim_n→∞ f(n)/g(n) < ∞ for f(n) ∈ O( g(n)), or showing that lim_n→∞ f(n )/ g(n ) = ∞ for f(n) ∈/ 0(g(n)). Note that there will be no marks if only true/false answer is given.
a) √(4n² + 2n ∈Ô (n).
b) n100 ∈ O(eⁿ).
c) log_e(n²) ∈ Ω(√n).

Problem 2: Arrange the following functions in an in- creasing order of their growth rates.

f₁ = 1000n,

f₂(n) = (log n)²

f₃(n) = n!

f₄(n) = nlogn,

f₅(n) = 2ⁿ,

Problem 3 In the following questions we assume that m grows more slowly than log n.

a) Design an in-place algorithm (description + pseudo code + complexity analysis) to find m smallest elements (possibly repeated) in an array of real num- bers of size n with time complexity 0(mm). Note that no extra data structures are allowed.

a) 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(n log m). Extra data structures are allowed.

Problem 4 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 Let A be an array of size n contalns a list of records in which the field "gender" has value either M or F. Suppose that n is even for simplicity.

a) Design an in-place recursive decrease-and-conquer algorithm (description + pseudo code) of complexity O(n²) 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 N than 3f, then all the uncoupled N are grouped at the end of the array. For example, lf the list is

(ID 1, F ),(ID 2, F j,(ID 3, M),(ID 4, F ),(ID 6, M),(ID6,M ), ID7 ,F ),(/D8, F),

then the output could be

(ID5,3f),(/D7,F),(/D3, M ),(ID8,F), (ID6,M ), ID 1, F ), ID2,F ),(/D4, F).

Note that inefficient algorithm, in particular, algorithms with complexity fl(n 3) will attract a zero mark.

a) 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) 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 IS {n ) in big-Theta notation?

Problem 6 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 c, credit points and also a list P; 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 T_i 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.

a) Scenario 1: the PRQs are nonequivalent, that is, each course can be taken only if ALL PRQs have been completed. Apply your algorithm to the toy example in Fig. Qf and complete the output table (see Fig. B.

b) Scenarlo 2: the PRQs are equivalent, that is, if Pi ≠ Φ, then the course i can be taken as long as ONE of the PRQs in P; has been completed. Design a dynamic programming algorithm to achieve your task. Apply your algorithm to the toy example in Fig. Q2 and complete the output table (see Fig. B Note that you should also explain explicitly the recurrence formula and the backtrace (given i, list the sequence of courses that a student needs to take before enrolling in course i with minimum sum of credits).

Note that to achieve full marks, the algorithms should have complexity O(mm + n² ) in Part a) and O(n + m) in part b) or better. Inefficient algorithms, e.g. with complexity exponential in n or m, will attract a zero mark.

Problem 7 The year is 2040, and you are now on a voyage to a newly discovered Earth-like planet, named DST, whlch is the habitat to many mysterious and previously unknown specles. After years of digging and researching, your biologist and palaeontologist colleagues have collected a large number of DNA sequences from all living or dead animals they encountered, and now ask for your help in building an evolutionary tree, which represents the ancestral relationships among all animals.

The root of the evolutionary tree is the predicted ancestor of all species. Each node in the tree represents the DNA sequence (or rather, a DNA strand consisting of six bases A, C, G, T, H, I) of one species. The distance between any two strands S_u and Sv, is d(s_u ,s_v ) defined as the minimum number of base deletions, insertions, and substitutlons required to turn S into S,. The tree must satisfy the following two evolution rules (see Fig. B.
1. (Rule 1) Each species evolves away from the ancestors: if u is an ancestor of r, then d (S_u, S_v) ≥ d(Sx, S_y) for every palr of parent and child (z, y) along the path of the tree from u down to c (including u and r).

2. (Rule 2) Sibling species evolve away from each other: if r and in are not parent and child and their closest common ancestor is u, then d ( !S , S z) d(S p y y ) for every palr of parent and child (z, y) along the paths of the tree from u down to e and from u down to in (includlng u, u, and in themselves).

a) Given a root r, develop an efficient algorithm that biil1ds an evolutionary tree rooted at r and satisfying Rule 1 and Rule 2. Include an algorithm description and an unambiguous pseudo code. Provide a complexity analysis of your algorithm with respect to the input size n and é, where P is the maximum length of each DNA sequence. Note that incorrect or inefficient algorithms will not receive a full mark, in particular, exponential-time complexity algorithms may attract a zero mark.

b) Prove that your algorithm produces an evolutionary tree satisfying Rule 1 and Rule 2. Hint: if you are on the right track, the proof should take a short paragraph only.

e) Implement your algorithm and run it on the dataset provided in Fig. Q4 (see also Fig. B. Suppose that beefalo is the predicted ancestor of all other species. Submit the code together with a drawing of the (rooted) evolutionary tree for this example (with nodes labelled by names or images of the creatures).

Problem 8 Research a problem of your own interest in any field (science, engineering, technology) that can be solved by a computer algorithm.

a) Write a 1- to 2-page report on an existing algorithm that is among the most efficient ones solving that particular problem and include in your report: (1) the problem statement, (2) why is the problem important/interesting, (3) the algorithm description, (4) a pseudo code, and (5) a complexity analysis. Note that the problem/algorithm should NOT be among those already discussed in the pre¬recorded lectures. You should include a few (1-5) references that you used when researching the problem/algorithm, but the writing should be your own. A simi¬larity score of 25% and above between your report and any existing source may indicate plagiarism. Marks will be decided based on the correctness, clarity, and the sophistication of the problem/algorithm discussed. If the report is not well written or the problem/algorithm is trivial or straightforward, you may not receive a full mark.

b) Propose your own improvement of that algorithm, either in space or time complexity. It should be your own idea and not from any existing source. You should state clearly at first what the improvement is, and then explain how you do it.

Attachment:- Algorithms and Analysis.rar