Question

2. A general medical practitioner (GP) has compiled an electronic computer file of patient information. Among the information contained in the file are details of the height of each patient. The GP has developed a simple algorithm showing how the file can be read [until the end of the file (EOF) is reached] to find and write the height of the tallest patient. The pseudocode for the algorithm is:

start tall = 0

do until EOF

read height

If tall < height

tall = height

end If

end do

a) (*) Draw a flowchart (following the conventions used in class) that represents the pseudo code. [6 marks]

b) (*) What is the likely complexity of your program using big-O notation? Clearly point out what the primary parameters are and define your terms. [2 marks]

c) Your colleague is working on two algorithms, X and Y, that determines whether two people are a certain distance apart. They use a number of different inputs, n. They are seeking your advice. If they tell you that algorithm X has a worst-case runtime complexity of O(n) and algorithm Y has a worst-case runtime complexity of O(n2 ), which algorithm would you recommend and why? [2 marks]

d)Your colleague then adds that the average-case time complexity for X is Ɵ(logn) and for Y is Ɵ(n). Does this change your advice at all, and why? [2 marks] Your answers should be no longer than a sentence or two.

e) Write a recursive function sum_factor(n), using the pseudocode principles covered in the lecture, to sum up the numbers i between 1 and n where i is a factor of n, (that is i completely divides n). You need to write a function is_factor(n,i) that returns 1 if i is a factor of n and 0 otherwise. You need to invoke/call this function from sum_factor(n) algorithm. You may assume that n will be greater than 0 – error checking is not needed. [8 marks] Please note: Submission of actual code (e.g., in Ruby or Python or any other programming language) will be awarded zero marks – we are seeking pseudocode. Answers using iteration will be marked on pseudocode alone and cannot receive full marks.

write tall

end

Answer 1

Hey There,

- I understood your question and I have given the answer to the best of my knowledge.

- Here as mentioned in the question I have given direct answers with explanation.

- If you need further explanation then do let me know in the comments box I will be more than happy to help.

Answer:

a). Flowchart:

  

b). Complexity

- To end the program user needs to enter a value that is less than the tall variable. So we don't know how much time it will happen. So the worst-case complexity will be  O(n).

- However in the best case the complexity can be O(1). If the user enters a smaller value in the first attempt then our program will end.

c). X has the worst-case runtime complexity of O(n) while Y has the worst-case time complexity is O(). So we can clearly see that X's algorithm will perform much better as it will take less time to run the code.

- We know that O(n) is efficient than O() so I will definitely recommend the X's algorithm as it will be more efficient and It will take less time.

d). The average complexity of X is Ɵ(long) while for Y it is Ɵ(n). We know that "logn" is better than "n".

- So this will not change my advice at all.

e) Recursive function:

-

1. Program starts
2. Declare a global variable sum = 0
3. define is_factor(int n, int i) function:
    if n mod i equals to 0 then:
        return 1
    else
        return -1
4. Start sum_factor(n, 1) function:
    if i <= n then:
        call is_factor(n, i) function
        store the output in result variable
        if result equals 1 then:
            sum = sum + i;
        else:
            call sum_factor(n, i+1)
    end the function
5. Start main function:
    Call sum_factor with given number value
    sum_factor(n, 1);
    display the value of sum variable
    end of main
  

Hope it helps:)