This assignment consists of two parts. The First part is to be completed individually. The second part can be completed in groups of size up to three. Further instructions about group work will be provided separately.


You should prepare your answers electronically, in a Word document or pdf le. Where mathematical formulas, diagrams etc are needed you can use handwriting and insert them into the document as pictures, but any substantial amount of text should be typeset and not handwritten. You should have the individual and group parts in di erent les; there are separate submission points for the two parts on Blackboard.


In line with university policy, marking will be done anonymously. Please do not include your name or other personally identi able information in your submission.




Part A (Individual, 30 marks)


Consider the following pseudocode:


f(int n, int d) {


println(space(d) + “n=” + n + ” begins”); if (n > 1) {


f(n/2, d+1);


println(space(d+1) + “hi”);


f(n/2, d+1);




println(space(d) + “n=” + n + ” ends”);




where println(s) prints the string s on its own line, space(d) is a string of d spaces, and the + in the println means string concatenation. For example, if n=4 and d=2, the commands


println(space(d) + “n=” + n + ” begins”); println(space(d+1) + “hi”);


will print  
__n=4 begins  
(where the space character is replaced by   just so you can see it.)  
(a) Write down the output printed by f(4, 0). [5 marks]
(b) Let T (n) be the number of lines printed by f(n,0). Write down a recurrence formula for
  T (n), including the base case. You can assume n is a power of 2. [5 marks]
(c) Solve the recurrence to  nd out how many lines are printed by f(n,0), as a function of
  n. (You must not use the Master Theorem.) [20 marks]

Welcome to one of the bestassignmenthelpcompanies  online .

·         Do you want to order for a customized assignment help task?

·          Click on the order now button 

·         Set up your topic, Fix the number of pages, Fix your Order instructions 

·         Set up your deadline, upload the necessary files required to complete the task, Complete the payment.

 We delivery high quality and non plagiarized tasks within the stipulated time given