C++ 作业代写 - c++编程作业代做 - take home代写 - CS304

CS304 take home exam

C++ 作业代写 Do the take-home individually and do not copy from classmates/web. See the syllabus for penalties applied to duplicate assignments···

Comment 1: C++ 作业代写

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 :

yourprogram
Aprintout of your program
Thetable and comments on the results, if you have done the bonus

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?

p=&i;
p=*&i;
p=&*i;
i=*&*p;
i=*&p;
i=&*p;
p=&*&i;
q=*&*p;
q=**&p;
q=*&p;
q=&*p;

Question 2: explain the meaning of the following expressions:C++ 作业代写

f(n)is O(1)
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 C++ 作业代写

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

usingone additional stack
usingno 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:

countthe number of nodes in a binary tree
countthe number of leaves in a binary tree
findthe height of the tree

Question 11: for which trees do preorder and inorder traversals generate the same sequence?C++ 作业代写

Question 12: which sorting algorithms are stable? Give a practical example of where a stable sort is

useful
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 C++ 作业代写

In this assignment, we will compare the BSTs and Heaps operations in two respects:

INSERTand DELETEHIGHEST
Sorting
We’ve seenin 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:
Implementthe class Heap and the class BST, each containing an Insert() and DeleteHighest()
Generatea random sequence (of size n) of numbers. Store the sequence in a List (you will also need to implement a List class).
Insertthe n numbers generated in the Heap
Insertthe same random numbers in a
Iterativelyapply deleteHighest on both the Heap and the Tree, storing the deleted elements in two different
Comparesthe two Lists to make sure the sequence of DeleteHighest was the

Wenow need to compare how the two ADTs can sort elements C++ 作业代写

Re-insertthe random numbers generated in step 2 above back in the Heap and in the
ApplyheapSort on the heap then copy the heapArray in a
ApplyInorder traversal on the Tree and store the resulting sequence in a
Comparethe two Lists to make sure the sequence of sorted elements was the

Fora 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:

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 C++ 作业代写

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;

//Generating n rand numbers and storing them in List operations
Listoperations (n); // an List object of size n
srand(time(0));
for(int i=0; i<n; i++){
intnumber = rand() % 100;
insert(number% 100); 9 }

10 C++ 作业代写

cout<< “Random elements:” << endl;
display(); 13
HeapH(n); // Heap object of size n
TreeT; // Tree object

//Insert the random elements in the Heap and the Tree
for(int i=0; i<n; i++){
insert(operations.getElement(i));
insert(operations.getElement(i)); 21 }

Listlist1(n); // used to store the result of deleteHighest from Heap
List list2(n);// used to store the result of deleteHighest from Tree 25
//Applying deleteHighest on Heap and Tree
while(!H.isEmpty())
insert(H.deleteHighest()); 29
while(!T.isEmpty())
insert(T.deleteHighest()); 32
//Displaying and comparing the two lists
cout<< “Deleted from the Heap:” << endl;
display();
cout<< “Deleted from the tree:” << endl;
display();
if (list1.compare(list2))
cout<< “Equal lists” << endl << endl;
elsecout << “Not equal” << endl << endl; 41
//Restoring the Heap and the Tree
HeapH2(n);
TreeT2;
for(int i=0; i<n; i++){
insert(operations.getElement(i));
insert(operations.getElement(i)); 48 }

49 C++ 作业代写

//Sorting Heap and Tree and storing results in two lists
ListheapList(n);
HeapSort();
heapToList(heapList);// copy the Heap array into a list “heaplist”
ListtreeList(n);
inorder(treeList); //stores inorder sequence in list “treelist” 56
//Displaying and comparing the two sorted lists
cout<< “Heapsort Display:” << endl;
display();
cout<< “Inorder Display:” << endl;
display();
if (list1.compare(list2))
cout<< “Equal lists” << endl << endl;
elsecout << “Not equal” << endl << endl; 65 }

合作平台：天才代写幽灵代写写手招聘 paper代写