Data Structures & Algorithms Assignment

Task A: Searching

In this task, you are to write a MATLAB function and accompanying test harness to evaluate 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" (clotted) lines to match the performance that you expected to see given the published asymptotic behaviours of these algorithms and/or your own deductions. 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.

Along with your code, you are to write a maximum of 300 words. Use 150 words to describe how your selected algorithm works, using figures (e.g., diagrams such as flow-charts), equations, and pseudocode, if these help. Next, you may 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 expected and observed outcomes, try to explain why these differences occurred.

[300 words + code and graphs]

Task B: LCRS and K-ary Trees

You are to propose a set of theorems that describe the structure of LCRS trees (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, you a to present theorems that predict 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, and number of nodes in each level. Theorems should relate these metrics to their equivalent values in the other tree type (e.g., if there are I 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 proof by induction to confirm your theorems. A proof by induction shows that the theorem 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 400 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 in your inductive proofs.

[400 words + equations]

Task C: Sorting

You are to write a MATLAB function and accompanying test harness to evaluate the performance of one of the following three comparison-based array sort algorithms: (i) Comb Sort, (ii) Gnome Sort, (iii) Pancake Sort. Use the examples in Canvas for guidance (functions and test harnesses for Selection and Bubble sort are to be provided). The test harness examples provided evaluate performance, in units of comparisons and moves, up to N = 102.4 in the best, average and worst case for arrays in random order (and are thus non-exhaustive).

In your test Harness, remember to adjust the "expected" (dotted) lines to match the performance that you would expect to see given the published asymptotic behaviours of these algorithms and/or your own deductions. It is recommended that you avoid a recursive implementation, since this will make counting comparisons and moves more difficult and will also cause MATLAB to run very slowly.

Along with your code, you are to write a maximum of 300 words. Use 150 words to describe how your selected algorithm works, using figures (e.g., diagrams such as flow-charts), equations, and pseudocode, if these help. Next, you may 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 selection, bubble and theoretically optimal, i.e. 0(rtlogn), sort algorithms. If there are discrepancies between expected and observed outcomes, try to explain why these differences occurred.

[300 words + code and graphs]

Task D: Asymptotic Notations

In this task, you are to write a brief report that attempts to explain in as straightforward a way possible, using appropriate equations, line graphs (figures), and code 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, infinity, summation and product notation, basic set theory, basic logic, has some exposure to universal and existential quantifier notation (V, 3), and knows one or two simple algorithms

The asymptotic notations to be explained are big-0 (0), little-0 (a), big-Omega (0), little-Omega (co), and big-Theta (0), along with the concepts of tight and loose bounds, and how these notations relate to the ideas of best, average and worst-case performance.

Include code listings for the examples used, which should adhere to good-practice guidelines.

[500 words + equations, graphs and code fragments]

Attachment:- Assignment Questions.rar