Analysis and Design of Algorithms
Coursework
Instructions
• This coursework is individual. You must not copy others answers.
• For some of the coursework problems, two or more students cannot have exactly
the same answers, if this happens they may get a zero mark and this will be
investigated as a case of misconduct.
• The solutions must be handwritten, scanned, numbered and submitted on Moodle.
If you can create one PDF containing all the scanned images that will encouraged. If
you prefer, you can submit a physical copy in my office.
• When you write down solutions, try to make them clear and easy to understand.
• Sloppy answers will receive fewer points.
Exercise 1: Big O Notation [30 Marks]
Explain with 3 different examples of your choice the application of each of the above rules.
For example, if we say that
We can apply the above rules to prove this in the following order:
In the same way, choose 3 different examples of your choice to demonstrate how all of the
above rules can be used.
In you answer in addition to the solution steps, you can also provide a short textual
description to demonstrate that you understand the rule. This will attract better grades.
Exercise 2: Heaps and Sorting [40 Marks]
Replace all the keys in the heap below with values of your choice such that it still satisfies
the heap property.
Redraw the heap with the new values of your choice and prove that it is still a heap.
How would you represent your heap using an array? For example, we can represent a heap
as follows:
Draw the array for your heap as shown above for the example heap. How many elements
does it have? What are the values of w and z in your case?
Apply the following algorithm on your heap and explain each step via drawing a few
diagrams showing the changes to the heap if any and the final output. For example, you can
draw intermediate representation of the heap as a tree or draw the array.
Explain how would you compute the complexity of the above algorithm?
Write the pseudocode of an algorithm that uses heaps to solve a real-life problem of your
choice.
Exercise 3: Big O Notation [30 Marks]
Consider below an illustration of an example Huffman code for the input string X = "a fast
runner need never be afraid of the dark". The table below shows the frequency of each
character of X and the tree shows the Huffman Tree (next page) for the string X.
Build a new string Y as follows:
Y = "a fast runner like [YOUR FULL NAME] need never be afraid of the dark"
Construct the frequency table and draw the Huffman tree for the new string Y in the same
way as done for the sting X.
Pick any five random character in the string Y, obtain their codes from the Huffman tree.
Explain the steps of the following algorithm in relation to the Huffman tree you build for the
string Y. You should consider values in your tree for the steps in this algo.
