CSCI2100D 2018-19: Midterm Exam
Time allowed: 105 minutes Student No.:
Q1. [10 marks] Sort the functions below in ascending order of growth rate and justify
your answer briefly.
– f1(n) = n + n/2 + n/4 + n/8 + n/16 + · · ·
– f2(n) = n + (n − 1) + (n − 2) + · · · + 3 + 2 + 1
– f3(n) = n ∗ (n − 1) ∗ (n − 2) ∗ · · · ∗ 3 ∗ 2 ∗ 1
– f4(n) = n
1.5
– f5(n) = 2
n
– f6(n) = log2
n
Q2. [12 marks] Fill in the C language code from line 7 to 9 in the function below and
analyze the time complexity of the function in O notation.
– int find(int n, int A[], int value)
Find a given value in a sorted array A of size n. Numbers in A satisfy:
A[0] < A[1] < A[2] < · · · < A[n − 1]
If A[i] = value : return i;
Otherwise : return -1.
1 int find (int n , int A [] , int value ){
2 int left , right , mid ;
3 left = 0;
4 right = n - 1;
5 while ( left <= right ){
6 mid = ( left + right ) / 2;
7 if( A [ mid ] == value ) ____________________
8 ________________________________________
9 ________________________________________
10 }
11 return -1;
12 }
Q3. [18 marks] A prime number (or a prime) is a natural number greater than 1 that is not
divisive by other numbers except 1 and itself. For example, 2, 3, and 17 are three prime
numbers. Given a positive integer n as input, the problem is to find all prime numbers in
[2, n]. In the following, we provide three valid algorithms implemented in C language to
solve this problem. Give the time complexity of each algorithm in O notation.
– void algo(int n, int isPrime[])
The array isPrime contains the result.
isPrime[i] = 0 : i is not a prime;
isPrime[i] = 1 : i is a prime.
– Algorithm1
1 void algo1 (int n , int isPrime []){
2 int i , j ;
3 for ( i =2; i <= n ; i ++){
4 isPrime [ i ] = 1; // assume i is a prime
5 for( j =2; j < i ; j ++)
6 if( i % j ==0) isPrime [ i ] = 0;
7 }
8 }
– Algorithm2: Only line 5 is changed compared to Algorithm 1.
1 void algo2 (int n , int isPrime []){
2 int i , j ;
3 for ( i =2; i <= n ; i ++){
4 isPrime [ i ] = 1; // assume i is a prime
5 for( j =2; j *j <= i ; j ++)
6 if( i % j ==0) isPrime [ i ] = 0;
7 }
8 }
– Algorithm3: For each integer j (j > 1), 2j, 3j, 4j, · · · are not prime numbers.
1 void algo3 (int n , int isPrime []){
2 int i , j ;
3 for ( i =2; i <= n ; i ++) isPrime [ i ] = 1;
4 for ( j =2; j < n ; j ++)
5 for( i = j *2; i <= n ; i += j )
6 isPrime [ i ] = 0; // j is a factor of i
7 }
Q4. [20 marks] Compute the set difference of two linked lists.
– In this problem, we use a singly linked list to maintain a sequence of distinct integers
in ascending order. Now, we have two linked lists denoted as A and B as input,
which represent two sets of sorted integers.
– List SetDifference(List headA, List headB)
Create a new sorted list as the set difference A\B, that is, if an integer is in list A
but not in list B, then insert it into the result linked list.
1 typedef struct linked_list_node {
2 int value ;
3 struct linked_list_node * next ;
4 } Node ;
5 typedef Node * List ;
6
7 List SetDifference ( List headA , List headB ){
8 List head = NULL ;
9
10 return head ;
11 }
– Implement the function SetDifference in C language efficiently and analyze the
time complexity of your algorithm. For your time complexity analysis, you can
assume that there are n integers in A andm integers in B. An algorithm withO(n ·m)
time complexity is regarded not very efficient, thus cannot get full marks.
Q5. [20 marks] Given a sequence of characters composed of ‘(’, ‘)’, ‘[’ and ‘]’, design an
algorithm to determine whether it is a valid sequence.
– Definition:
∗ An empty sequence is valid;
∗ A ‘(’ immediately followed by a ‘)’ is valid, but is invalid in the reverse order, i.e., (
) is valid, and ) ( is invalid;
∗ A ‘[’ immediately followed by a ‘]’ is valid, but is invalid in the reverse order, i.e.,
[ ] is valid, and ] [ is invalid;
∗ A valid sequence contained in a pair of ( ) or [ ] is still valid;
∗ A concatenation of two valid sequences is still valid;
∗ A single character that is unpaired is invalid;
∗ A sequence having a pair of ( ) and a pair of [ ] with partial overlap is invalid, e.g.,
( [ ) ], and [ ( ] ).
– Valid Sample 1 : ( )
Valid Sample 2 :
Valid Sample 3 : ( ( ) [ ] ) [ ( ) ] ( )
– Invalid Sample 1 : ( ( ( ( ) ) ) ]
Invalid Sample 2 : ( [ ) ]
Invalid Sample 3: [ ( ]
– Show your algorithm in pseudo-code and analyze its time complexity. You can
assume that the input sequence is stored in a character array Seq of size n, and print
“valid” or “invalid” as the output.
Q6. [20 marks] Binary Tree Traversal. An Inorder traversal of a binary tree visits the
left subtree, the root, and the right subtree. A Preorder traversal visits the root, the left
subtree, and the right subtree. A Postorder traversal visits the left subtree, the right
subtree, and the root.
– Write down the tree node sequence by Inorder, Preorder and Postorder traversal of
the given tree, respectively.
– For one binary tree, we perform Inorder and Preorder traversal on it and obtain the
tree node sequences shown below. Reconstruct and draw the binary tree.