COMPSCI 1103, 2103 Algorithm Design and Data Structures Semester 2, 2017
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Algorithm Design and Data Structures
COMPSCI 1103, 2103
Primary Examination, Semester 2, 2017
Programming Fundamentals
Question 1
(a) What does the following code snippet print out?
int a = 5; int b = 7; int * c = &a cout << a << ", " << b << endl; *c = 9; cout << a << ", " << b << endl; c = &b; *c = 1; cout << a << ", " << b << endl; |
(b) Read the following code snippet and identify the problem with it.
int a[5] = {10, 20, 30, 40, 50}; for (int i = 0; i <= 5; i++) { cout << *(a + i) << endl; } |
(c) Declare and initialise (to zero) a two-dimensional array of floats on the heap. Please provide the corresponding C++ code. [3 marks]
(d) Explain the difference between: Pass by Value, Pass by Pointer, Pass by Reference when declaring C++ functions. Give an example of each and explain how they work. [3 marks]
(e) List three differences between the following two memory areas:
· The Stack
· The Heap [3 marks]
(f) What will the following code snippet print out? Explain your answer.
int a; cout << a << endl; |
(g) One strategy for developing algorithms is a Greedy approach. Explain
what defines an algorithm as “greedy” and give an example of an al- gorithm that employs a greedy strategy. [3 marks]
[Total for Question 1: 19 marks]
Inheritance and Object Oriented Programming
Question 2
(a) What is an abstract class? Explain how to create an abstract class and
what consequences it has for object creation. [2 marks]
(b) What is the difference between the keywords private and protected? [2 marks]
(c) Please clearly describe, in the context of C++, the difference between: · redefining
· overloading
· overriding
You may use diagrams where necessary. [4 marks]
(d) What does the friend keyword do? Explain how to use the friend keyword and what it allows. [2 marks]
(e) Consider the following code snippet.
int compare(int a, int b) { return a > b; } |
Write C++ code to declare a function pointer and direct it to use function compare. [2 marks]
(f) A game programmer decides to make a game called block-jumper.
There are three kinds of objects in the game: The player, enemies & blocks. Each object has an x & y location, and a function draw which takes two parameters (x & y). The programmer decides to create a parent class called GameEntity.
i. Draw a class diagram showing all four classes, the functions, vari- ables and inheritance relationships. [4 marks]
ii. The player has three health points. The enemies have a gold value (given to the player when killed) and an attack function. Update your class diagrams to reflect these changes. [3 marks]
[Total for Question 2: 19 marks]
Recursion
Question 3
(a) What are the three conditions necessary for controlled recursion? [3 marks]
(b) Consider the mathematical expression:
1 + 3 + 5 + 7 + . . . + (2n _ 1) = n2
Using recursion write a function that calculates n2 for a given n using the left-hand side of the above expression. [4 marks]
(c) What is tail recursion? Explain how it works and what problem tail recursion helps mitigate. [2 marks]
(d) What is Dynamic Programming? Explain how it differs from normal recursion and what the main benefit is. [3 marks]
[Total for Question 3: 12 marks]
Complexity Notation
Question 4
(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) Please prove that 2n3 + 5n2 + 100000 is in Θ(n3 ). [4 marks]
(d) Please prove that n2 + 60 is not in O(n). [1 mark]
(e) Given that f (n) e O(n2 ) and g(n) e O(n log n), please formally prove
that f (n) + g(n) e O(n2 ).[4 marks]
(f) 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]
[Total for Question 4: 14 marks]
Sorting and Searching
Question 5
(a) Please illustrate the process of sorting the list {2, 8, 6, 1, 9} using bub-
ble sort. [2 marks]
(b) Please illustrate the process of merging the two sorted lists {2, 3, 6, 8}
and {1, 2, 9, 12} using mergesort. [2 marks]
(c) i. Given a list of n integers, you are asked to sort them in ascend- ing order using quicksort. Please write down the pseudo-code of quicksort with the last element as pivot. You must give the details of the partitioning process. [5 marks]
ii. The performance of quicksort depends on the selection of the pivot value. What is the best-case performance of quicksort? [1 mark]
iii. What kind of pivot value will result in the best-case performance? Please provide some analysis. [2 marks]
iv. What kind of pivot value will result in the worst-case performance? Please provide some analysis. [2 marks]
(d) Describe bucket sort for a list of int using pseudo-code. [4 marks]
(e) Given that sorting a large dataset is often time-consuming, is it a good
idea to sort before searching? [2 marks]
(f) 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] and L[2n/3]
· The above value determines which sublist to focus on (it should
be noted that there are three sublists with size n/3)
· Run the same algorithm recursively on the sublist
Please write down the pseudo code for this algorithm and analysis the computational complexity. [6 marks]
[Total for Question 5: 26 marks]
Linked Lists
Question 6
Define a linked list containing n nodes as follows:
struct Node {
int data;
Node *link;
}
(a) Please describe how to swap two adjacent elements by adjusting only
the links (and not the data) using:
i. Singly linked lists [2 marks]
ii. doubly linked lists [2 marks]
(b) In a singly linked list, each node only has link to the next node. What
does the following function do? Please analyse the complexity of the function.
void print(Node *head){
if(!head)
return;
print(head -> link);
std::cout << head -> data << std::endl;
} [4 marks]
(c) Stacks and Queues are often implemented based on linked lists.
i. What is a stack and what are the common operations? [3 marks]
ii. What are the common operations of the Queue ADT? [2 marks]
iii. Please give an application of the stack. [2 marks]
(d) A deque is a data structure consisting of a list of items, on which the following operations are possible:
· push(x): Insert item x on the front end of the deque. · pop(): Remove the front item from the deque and return it. · inject(x): Insert item x on the rear end of the deque. · eject(): Remove the rear item from the deque and return it.
How do you use the singly linked list to implement a deque which support the basic operations above to be done with O(1) complexity?
Please provide C++ code segments and analysis to support your de- sign. [8 marks]
[Total for Question 6: 23 marks]
Question 7
Define a tree node as follows:
struct Node {
int data;
Node *left;
Node *right;
}
(a) What is a binary search tree? [1 mark]
(b) Starting with an empty tree, show the process of adding the list {3, 6, 1, 2, 5, 4} (in order) to the tree. [3 marks]
(c) Write a function bool search(struct Node *root, int obj) that takes as input a binary search tree root and a value of obj. The function re- turns whether obj exists in the tree or not. [3 marks]
[Total for Question 7: 7 marks]
2022-06-21