COMPSCI 1103, 2103 Algorithm Design and Data Structures for Engineers Semester 2, 2016
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Primary Examination, Semester 2, 2016
Algorithm Design and Data Structures for Engineers
COMPSCI 1103, 2103
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?
int x,*y; y = new int; x = 15; *y = 25; cout << x << " " << *y << endl; x = *y; cout << x << " " << *y << endl; *y = 50; cout << x << " " << *y << endl; |
[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.
class Animal { public: void print(); // Prints location of animal . string location; }; class Dog : public Animal { void print(); // Prints location and name of weight . string name; }; |
i. What problem occurs when the following statements are executed? Note: the following operations are all legal.
Dog vdog; Animal vanimal; vdog.name = "Marmaduke"; vdog .location = "Fisher Street"; vanimal = vdog; |
[2 marks]
ii. Consider a different code fragment shown in the following.
Dog vdog; Animal vanimal; vanimal .location= "Mt Barker"; vdog = vanimal; |
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. . .
Algorithm Design and Data Structures for Engineers
Primary Examination, Semester 2, 2016
Question 8
You define a tree node as follows:
struct Node {
int data;
Node *left;
Node *right;
}
(a) What is a tree in the context of algorithms and data structures?
[1 mark]
(b) What is the definition of a binary search tree?
[3 marks]
(c) Write a function bool search(struct Node *root) that takes as in- put a binary search tree root, and returns whether 0 exists in the tree.
[3 marks]
[Total for Question 8: 7 marks]
2022-10-11