Reference no: EM132491217

MODOO2641 Data structures and algorithms

Part A Knuth Transforms

You are to propose a set of formulas that describe the structure of LCRS trees (i.e., k-ary trees organised into the shape of binary trees with the left-child, right-sibling rule, also known as filial-heir chains) in relation to their equivalent k-ary tree. In particular, present formulas that compute metrics of interest following forward and reverse Knuth transforms (i.e., the process of converting a k-ary tree into a LCRS tree and vice versa). Metrics of interest include numbers of edges, leaves, nodes, and interior nodes, tree height, tree and node balance, number of nodes in each level, and number of null links. Theorems should relate these metrics to their equivalent values in the other tree type (e.g., if there are l leaf nodes in a 3- ary tree, what is the min, max, and actual number in the equivalent LCRS tree?). You may wish to start with perfect k-ary trees and then proceed to generalise to k-ary trees that are complete, and then to neither perfect nor complete trees. You may also wish to start with a particular value of k (e.g., k = 3), and then verify that your theorems hold for other values of k, or adjust them accordingly to make them generalisable. You are to use induction-style demonstrations to confirm your formulas. Show that your formula holds when the independent variable is 1, then that it holds where the independent variable is n and finally where it is n + 1. Try to avoid using excessively small values of n. Typeset your formulas in Word using the equation editor and refer to them in the accompanying text (maximum 500 words, not including equations and figures) that describes concisely and accurately what each of the theorems tells us. Provide illustrations of trees for n and n + 1 induction-style demonstrations.

Part B [Practical and Theory]: Searching

Write a function and accompanying test harness to empirically measure the performance of one of the following three array search algorithms: (i) Fibonacci Search, (ii) Exponential Search, (iii) Ternary Search. Use the code examples in Canvas for guidance (functions and test harnesses for Linear, Jump, and Binary search are provided). The test harness examples provided evaluate performance, in units of comparisons, up to n = 1024 in the best, average and worst case only for successful searches, and you are only required to examine this outcome (i.e., not unsuccessful searches). In your test harness, remember to adjust the "expected" (dotted) lines to match the exact performance that you expected to see given your own thought experiments about how it works. It is recommended that you avoid a recursive implementation, since this will make counting comparisons more difficult and will also cause MATLAB to run very slowly, if you choose to use MATLAB (see below). Along with your code, you are to write a maximum of 300 words. Use up to 150 words to describe how your selected algorithm works, using figures (e.g., diagrams such as flow-charts), equations (e.g., for exact and asymptotic behavior), and pseudocode, Describe the scenarios that lead to each outcome (best, worst, average). Next, write up to 150 words to evaluate how closely the algorithm's empirical performance matched what you expected to see, and how its performance compares to linear, jump, and binary search algorithms. If there are discrepancies between your expected and observed outcomes, explain why these differences occurred.

Part C [Theory Only]: Landau Notations
Write a brief report that attempts to explain, in as straightforward a way possible and using appropriate equations, line graphs (figures), and pseudocode example(s), what the different asymptotic notations (sometimes called the Landau or Bachmann-Landau) tell us about an algorithm. You are to imagine that your reader is a first year undergraduate student in Computer Science who understands interval notation, sequences and series, limits, line functions, summation and product notation, basic set theory, basic logic, has some exposure to universal and existential quantifier notation (∀, ∃), and knows one or two simple algorithms. The asymptotic notations to be explained are big-O (Ο), little-O (??), big-Omega (Ω), little- Omega (ω), and big-Theta (θ), along with the concepts of tight and loose bounds, and how these notations relate to the ideas of best, average and worst-case performance. A good answer would identify an algorithm or family of related algorithms that yields different answers for each notation, and clearly explains why this is the case. In particular, you are warned against paraphrasing explanations from books and websites, since these tend not to be understandable to non-specialists, although reading these explanations will help you formulate your own clearer description, which should be a maximum of 500 words in length, not including equations, figures, and pseudocode examples.

Part D [Practical and Theory]: Subset Partitions

Implement an algorithm that it suitable for generating a list of partitions of a set. For instance, the set
A = {a, b, c} produces the set of partitions { {{a}, {b}, {c}}, {{a}, {b, c}}, {{a, b}, {c}}, {{a, c}, {b}}, {a, b, c} }, which has cardinality 5. You may confirm that you algorithm works correctly by comparing the number of partitions produced for a set of a given cardinality with the corresponding line on a Bell number triangle (i.e., you might like to implement a bellNumber() function first). Once implemented, determine the time complexity of the algorithm and demonstrate empirically how its computation grows as a function of the cardinality of the set to be partitioned in the best, worst, and average case. How would you classify the algorithm? Along with your code, you are to write a maximum of 300 words. Use up to 150 words to describe how your selected algorithm works, using figures (e.g., diagrams such as flow-charts), equations. Next, write up to 150 words to evaluate the performance of the algorithm through static analysis and through experimentation with sets of different cardinalities (n).