代写CS304留学生、代做C++编程设计、代写c/c++、data代做

日期：2020-03-31 11:10

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; i<n; i++){

7 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; i<n; i++){

19 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; i<n; i++){

46 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 }