Programming Fundamentals

Question 1

(a) You use the new keyword to allocate a dynamic variable and provide a

pointer to that variable.

i. Where does the memory for this new variable come from? [1 mark]

ii. Is the following claim true? The pointer to the new variable must be stored in the stack. [2 marks]

iii. Please explain why we do not have to manually delete local vari- ables in C++, but have to do so for heap variables allocated using new. [1 mark]

(b) What is the output of the following code fragment?

[3 marks]

(c) “Heap variables are only available when the called function’s activa- tion record is on the stack and they are destroyed when you leave the function.” Is this statement true or false?  Provide an explanation of how heap variables are defined and used to support your answer. [3 marks]

(d) Why do we separate the interface of an abstract data type (ADT) from its implementation? [3 marks]

(e) Explain what is test driven development. [2 marks]

[Total for Question 1: 15 marks]

Inheritance and Object Oriented Programming

Question 2

(a)    i. What is inheritance? [2 marks]

ii. Using an example, explain how inheritance facilitates code reuse. [4 marks]

(b) Clearly describe, in the context of C++ inheritance, using diagrams

where necessary:

i. Overloading [2 marks]

ii. Overriding [2 marks]

iii. Redefining [2 marks]

(c) Consider the following two classes.

i. What problem occurs when the following statements are executed? Note: the following operations are all legal.

[2 marks]

ii. Consider a different code fragment shown in the following.

Is the operation corresponding to the last statement legal? Briefly explain.

[2 marks]

[Total for Question 2: 16 marks]

Recursion

Question 3

(a) What are the three requirements for successful recursion in C++? [3 marks]

(b) Provide an example of infinite recursion.  Infinite recursion often re-

sults in stack overflow.  Please explain what is the meaning of stack overflow and why it happens with infinite recursion. [4 marks]

(c) Write a recursive function sumCube that returns the sum of cubes of a given positive integer. For e.g. sumCube(4) = 13 + 23 + 33 +43 [6 marks]

(d) Explain how stack memory is managed when sumCube(3) is executed.

[4 marks]

[Total for Question 3: 17 marks]

Algorithmic Strategies

Question 4

(a) Give an example of a brute force strategy and where you might use it. [4 marks]

(b) What is a Divide-and-Conquer strategy? Give an example. [4 marks]

(c) What is a Greedy strategy? Give an example. [4 marks]

[Total for Question 4: 12 marks]

Complexity Notation

Question 5

(a) What is the definition of f (n) being in O(g(n))? [1 mark]

(b) What is the definition of f (n) being in Ω(g(n))? [1 mark]

(c) What is the definition of f (n) being in Θ(g(n))? [1 mark]

(d) Prove that n5 + 100n3 + 10000 is in Θ(n5 ). [4 marks]

(e) We know that kn is in O(n) for any constant k . Is the following claim

correct? Briefly explain.

n                    n

kn =       O(n) = O(n2 )

k=1                k=1

[3 marks]

(f)  f is a function that satisfies the following:

● f is in O(n),

● f is in Ω(1),

● f is neither in Θ(1) nor in Θ(n).

Can you give an example of such a function f? Please also prove that the function you named indeed satisfies all of the above. [5 marks]

[Total for Question 5: 15 marks]

Sorting and Searching

Question 6

(a) Given a list of n integers, you are asked to sort them in descending order using quicksort. Please write down the pseudo code of quicksort. [5 marks]

The performance of quicksort depends on the selection of the pivot value.

i. What is the worst-case performance of quicksort? [1 mark]

ii. What kind of pivot value will result in the worst-case performance? [2 marks]

iii. What is the best-case performance of quicksort? [1 mark]

iv. What kind of pivot value will result in the best-case performance? [2 marks]

(b) Consider the following sorting algorithm (called “TwoMinSort”):

Let L be a list of distinct integers.

● Scan L to find the minimal value min and the second minimal value min\

● Swap the positions of min and L[0]

● Swap the positions of min\  and L[1]

● Run “TwoMinSort” recursively on elements from L[2] to L[n]        Please analyze the above algorithm and state its time complexity in Big-O notation. [5 marks]

(c) Consider the following modified version of binary search:

Let L be a list of sorted values and let n be the number of elements in L:

● Check L[n/3]

● The above values determine which sublist to focus on (it should be noted that one sublist has size n/3 while the other sublist has size 2n/3)

● Run the same algorithm recursively on the sublist

What is the time complexity of the above algorithm?  Please support your answer with a brief proof. [5 marks]

(d) Given that binary search (which requires a sorted list) is faster than searching unsorted lists, is it a good idea to sort before searching? [4 marks]

[Total for Question 6: 25 marks]

Linked Lists

Question 7

Define a linked list containing n nodes as follows:

struct  Node  {

int  data;

Node  *link;

}

(a)  Stacks and Queues are often implemented based on linked lists.

i. What is a stack? [1 mark]

ii. What is a queue? [1 mark]

iii. What does FIFO represent in the context of algorithms and data structures? [1 mark]

(b) How do you use singly linked list to efficiently implement a stack? [4 marks]

(c) How do you use singly linked list to efficiently implement a queue? [4 marks]

(d) Given a singly linked list, if you have access to a pointer that points to the middle of the linked list (besides the head pointer and the tail pointer), then what is the complexity for deleting a node at the end of the linked list? [2 marks]

[Total for Question 7: 13 marks]

Please go on to the next page. . .