辅导CS304留学生、讲解C++编程设计、辅导c/c++、data讲解
解析Java程序|讲解R语言编程
CS304 take home exam – due Friday April 17 at 11:59 PM.
Worth 43% of final mark (includes assignment 5)
Comment 1:
Do the take-home individually and do not copy from classmates/web. See the syllabus for penalties applied to duplicate
assignments.
Comment 2:
You still have the opportunity to erase your midterm mark if you perform better on this take-home.
Submission:
Part 1: submit a pdf, word document, or scan/photograph of your written answers.
Part 2: Hand-in :
1. your program
2. A printout of your program
3. The table and comments on the results, if you have done the bonus part.
Part 1 (50%) – written answers
Question 1: if i is an integer and p and q are pointers to integers, which of the following assignments causes a
compilation error?
Question 2: explain the meaning of the following expressions:
a) f(n) is O(1)
b) f(n) is theta(1)
Question 3: find functions f1 and f2 such that both f1(n) and f2(n) are O(g(n)), but f1(n) is not O(f2)
Question 4: find the complexity of the function used to find the kth smallest integer in an unordered array of integers:
int selectkth(int a[], int k, int n) {
int i, j, mini, tmp;
for (i = 0; i < k; i++) {
mini = i;
for (j = i + 1; j < n; j++)
if (a[j] < a[mini])
mini = j;
tmp = a[i];
a[i] = a[mini];
a[mini] = tmp;
}
return a[k - 1];
}
Question 5: write a C++ function that inserts a node into the middle of a doubly linked list
Question 6: write a C++ function that puts the elements on stack S in ascending order, using one additional stack and
some additional non-array variables.
Question 7: write a C++ function to transfer elements from stack S1 to stack S2 so that the elements from S2 are in the
same order as on S1
a) using one additional stack
b) using no additional stack but some additional non-array variables
Question 8: write a recursive C++ function that calculates and returns length of a linked list.
Question 9: write a recursive C++ function that uses only addition, subtraction, and comparison to multiply two numbers
Question 10: write C++ functions to:
a) count the number of nodes in a binary tree
b) count the number of leaves in a binary tree
c) find the height of the tree
Question 11: for which trees do preorder and inorder traversals generate the same sequence?
Question 12: which sorting algorithms are stable? Give a practical example of where a stable sort is
a) useful
b) necessary
Question 13: demonstrate the insertion of keys 5, 28, 19, 15, 20, 33, 12, 17, 10, into a hash table using separate chaining
collision resolution, a TableSize of 9, and a hash function h(k)=k%9
Question 14: what is the relationship between the sum of the degrees of all vertices, and the number of edges of graph
G=(V,E)?
Part 2 (50%) C++ programming question
In this assignment, we will compare the BSTs and Heaps operations in two respects:
a) INSERT and DELETEHIGHEST
b) Sorting
A) We've seen in class how the two Priority Queue operations "insert" and “deleteHighest" can be implemented with a
heap, in O(n log n) . In this assignment, you are asked to implement the same two operations also on a BST (we’ve also
seen in class how to insert in a BST). You should then compare the behaviour of the two ADTs for these two operations.
Here are the steps:
1. Implement the class Heap and the class BST, each containing an Insert() and DeleteHighest() operations.
2. Generate a random sequence (of size n) of numbers. Store the sequence in a List (you will also need to
implement a List class).
3. Insert the n numbers generated in the Heap structure.
4. Insert the same random numbers in a BST.
5. Iteratively apply deleteHighest on both the Heap and the Tree, storing the deleted elements in two different
Lists.
6. Compares the two Lists to make sure the sequence of DeleteHighest was the same.
B) We now need to compare how the two ADTs can sort elements
7. Re-insert the random numbers generated in step 2 above back in the Heap and in the Tree.
8. Apply heapSort on the heap then copy the heapArray in a List.
9. Apply Inorder traversal on the Tree and store the resulting sequence in a List.
10. Compare the two Lists to make sure the sequence of sorted elements was the same.
C) For a couple of extra bonus marks and only if your program is working perfectly, compare the speed of the two ADTs
for the 3 operations, storing the results in the table below:
N 10,000 100,000 1,000,000 10,000,000
Insert delH sort Insert delH sort Insert delH sort Insert delH sort
BST
Heaps
Ideally, for each value of n, you should run the program 3 times and take the average times and put them in the table.
For timing purposes, you will need to insert a timer before and after the loop inserting elements in the two ADTs, before
and after the loops deleting elements from the two ADTs, and before and after sorting each ADT.
Please use the following sample main (without the bonus); it indicates to you what public class functions need
implementing.
1 int main(){
2 int n = 100;
3 // Generating n rand numbers and storing them in List operations
4 List operations (n); // an List object of size n
5 srand(time(0));
6 for (int i=0; i7 int number = rand() % 100;
8 operations.insert(number % 100);
9 }
10
11 cout << "Random elements:" << endl;
12 operations.display();
13
14 Heap H(n); // Heap object of size n
15 Tree T; // Tree object
16
17 // Insert the random elements in the Heap and the Tree
18 for (int i=0; i19 H.insert(operations.getElement(i));
20 T.insert(operations.getElement(i));
21 }
22
23 List list1(n); // used to store the result of deleteHighest from Heap
24 List list2(n); // used to store the result of deleteHighest from Tree
25
26 // Applying deleteHighest on Heap and Tree
27 while (!H.isEmpty())
28 list1.insert(H.deleteHighest());
29
30 while (!T.isEmpty())
31 list2.insert(T.deleteHighest());
32
33 // Displaying and comparing the two lists
34 cout << "Deleted from the Heap:" << endl;
35 list1.display();
36 cout << "Deleted from the tree:" << endl;
37 list2.display();
38 if (list1.compare(list2))
39 cout << "Equal lists" << endl << endl;
40 else cout << "Not equal" << endl << endl;
41
42 // Restoring the Heap and the Tree
43 Heap H2(n);
44 Tree T2;
45 for (int i=0; i46 H2.insert(operations.getElement(i));
47 T2.insert(operations.getElement(i));
48 }
49
50 // Sorting Heap and Tree and storing results in two lists
51 List heapList(n);
52 H2.HeapSort();
53 H2.heapToList(heapList); // copy the Heap array into a list "heaplist"
54 List treeList(n);
55 T2.inorder(treeList); // stores inorder sequence in list "treelist"
56
57 // Displaying and comparing the two sorted lists
58 cout << "Heapsort Display:" << endl;
59 heapList.display();
60 cout << "Inorder Display:" << endl;
61 treeList.display();
62 if (list1.compare(list2))
63 cout << "Equal lists" << endl << endl;
64 else cout << "Not equal" << endl << endl;
65 }