Estrutura de Dados Prova Final

Prévia do material em texto

Page � PAGE \* MERGEFORMAT �2�
======================================================
cs311 Take Home Final Exam - R Yoshii For Fall 14
======================================================
Deadline: Thursday of the Final's week before 2pm to Cougar Courses.
You must submit this MS Word file – do not convert to other file types.
This exam acts as a review of the fundamental concepts we have covered in cs311. Even if you forget the details a month from now, as long as these fundamentals stay with you, we have done our job. 
As you answer the questions you may discover that you yourself have more questions about the things you thought you already knew. 
It allows us to reflect upon the things we have learned. 
It allows us to apply what you have learned to the tasks that lie in your future.
INSTRUCTION
Please read through the whole exam first and ask me to clarify questions as soon as possible. Do not wait until the last minute.
Do not rely on your memory. Re-read the lecture notes carefully.
Type your answers next to each blue prompt in this file. 
Yellow highlight means SHORT answers. 
Do not remove anything I have typed. Do not remove prompts!!
To get partial credit, 
EXPLAIN as much as you can. Answers without explanations (e.g. “Yes”) will not be accepted.
IN MOST CASES 3-4 short sentences should be enough.
Write down all assumptions you have made.
Most importantly, this is an exam!!!!
You may NOT discuss the problems with
other students and friends. If you have questions, please ask me.
I cannot enforce this effectively but
I trust you, and also similar answers
will stand out. And cheating will be
punishable as a “Felony” (i.e. 0 score!!!!)
This is a way for YOU to find out how much
YOU understand the material. Assess yourself.
WARNING: 
READ VERY CAREFULLY.
USE MY LECTURE NOTES.
USE HOMEWORK ANSWERS.
ANSWER ALL PARTS OF EACH QUESTION!!!!!!!!!!!!!
RE-READ THE WHOLE THING AT THE END.	
ADD THIS TO THE END OF YOUR CS3!! BINDER
Fill in the Blue parts now.
===================================================
NAME: Lucas Henrique Silva
DATE SUBMITTED: 12/04/14
DID YOU DO THIS ALL BY YOURSELF? yes
TOTAL: 51.5 /60pts = /30% of your grade
Add the percent to the HW% and look up the total and grade in the syllabus.
====================================================
Section 1 12 points	: 	 -2.5
Section 2 10 points	:
Section 3 14 points	: -4
Section 4 5 points	: -2
Section 5 6 points	:	
Section 6 3 points	: 
Section 7 4 points	:
Section 8 6 points	:
Total				:-8.5 = 51.5
�
SECTION 1. Algorithm Analysis [1 pt per prompt = 12 points]
1) What is the purpose of using asymptotic notation
 such as O, Omega and Theta instead of analyzing
 the exact number of comparisons done by a sorting algorithm?
 i.e. why do we use O(n^2) instead of saying 2n^2 + 3n + 4 
 What are we interested in?
 *Answer: Because you can’t predict the exactly number of comparisons, and you will not test all the entrances , so you can predict the worse case, the best case and the average case. We are interested in know some number so we can base on. Basic growth rate as N grows -1
2) Is computing the Average time complexity for a real-world problem simple?
 Or is it difficult?
 Explain why. 
 *Answer: It is a difficult one, because to get the average case you have to have all the results to calculate the average, so you would need all the entrances, you would have to figure all the possible entrances to calculate.
3) Your friend is very excited about having found an algorithm that sorts 
 any list in Theta(N^1.8) comparisons. 
 He thinks this is so fast that he will get a Ph.D. tomorrow. 
 Please teach him why he is wrong.
 *Answer: He is wrong because is already proved some algorithms which have a better performance than Theta(N^1.8) such as the Merge Sort Algorithm that is always Theta(N Log N).
4) Your friend says she can find an algorithm that searches
 for an element in any sorted list in much less than Theta(log N). She thinks
 she will get a big raise tomorrow.
 Please teach her why she is wrong. 
 *Answer: FN is? -1
ied in this class. 
 In what ways can each be called Divide and Conquer? 
 
 *Name: Merge Short 
 *Reason: Because every comparison the algorithm divide and deal with a part until this part is just one element, after that the algorithm get everything together, putting everything together already done, until every single subdivision became a total again.
 *Name: Quick sort 
 *Reason: The algorithm divides the array into two smaller sub arrays, sort choosing a pivot, and do this process in every single array until last just a number in the array, after that start to put everything that is already process together until became just one again. 
6) Describe 2 Space vs. Time decision cases we discussed in this class.
 In what ways can each be called Space vs. Time?
 *Example case in choosing an algorithm:		Merge Sort vs. Quick sort
 *Reason: The merge uses more space, however is faster than the Quick sort.
 *Example case in choosing a data structure:		Array vs. Vector
 *Reason: The array is faster to use, however uses more space than the vector, because you have to allocate a bigger space that you will use and the vector you just use what you need. Why faster? -0.5
SECTION 2. Sorting [2pts per prompt = 10 points]
Your mean employer has five sorting programs. But they are labeled
by their descriptions - no names.
Read each label then say which of the following it is:
 Heap Sort 
 Insertion Sort 
 Merge Sort 
 Quick Sort 
 Radix Sort 
 1) "Although I take O(n^2) time in the worst case, on the average
I only use theta(nlogn) and I do not need as much space as another divide and conquer algorithm.
 
 *Answer: This is Quick Sort
 2) "I am a good choice if you want consistent theta(nlogn) time
 and could use the disk (instead of RAM) for needed space."
 *Answer: This is Merge sort
 3) "I use theta(nlogn) time in the worst case. The data structure
 I use is also useful for efficiently implementing priority queues."
 *Answer: This is Heap sort
 4) "Even though my average complexity is theta(n^2), I am a good
 choice if you want to sort small files, or large files that
 are very nearly in order."
 *Answer: This is Insertion Sort 
 5) "I am a good choice if you want to quickly sort a large number of
 K digit numeric IDs. "
 *Answer: This is Radix 
SECTION 3. Object-Oriented Programming [2pts per prompt = 14 points]
 
In HW3P2, we placed data members of the base class in protected.
Why did we do that? Answer each.
 
*Why not private? Because we don’t want to this member be accessible in that class.
*Why not public? Because we want to protect the member to be access outside the class.
You had to overload = in HW3P3 to make it work with slists.
Some of you also overloaded == in HW3 as extra credit. Answer for each.
*Why did we have to overload=? i.e. What’s wrong with the one provided by C++? Because would copy the addresses of the old structure pointing to the same address as this original structure , so we would have two structures pointing to the same place.
*Why did we have to overload==? i.e. What’s wrong with the one provided by C++? Because the one provide by the C++ would compare the address of the pointers, so would never be the same unless that you are comparing the same structure with itself, would not compare what is inside the structure.
Does not work on objects -2
3) Why did you have to write a copy constructor for linked lists?
Also, give two cases in which your copy constructor is automatically invokedin relation to calling regular functions.
*What’s wrong with the one provided by C++?: Because you would provide the original list and after the function is done, the original link list would be modified.
*Use1: When you use a variable value , passing x=y. return -2
*Use2: You give the object as a parameter to a function.
SECTION 4. Binary Search Trees [1 pt per prompt = 5 points]
void BST::traverse(Vertex *V) // post order traversal recursively
{ 
 if (V != NULL) 
 {
 traverse(V->Left); 
 traverse(V->Right); 
 cout << V->elem << endl; 
 }
}
1) Modify the above slightly (just re-order) to do the Depth First traversal recursively. What is this traversal called? i.e. ____ order traversal.
*Code:
{ 
 if (V != NULL) 
 {
 traverse(V->Left); 
cout << V->elem << endl; 
 traverse(V->Right); 
 
 }
}
*Name of the traversal: INOrder 
Has to be Pre-order -2
2) Your friend says: "When I delete an internal node with 2 children from
a binary search tree, I always replace it with the MAXIMUM of the node's RIGHT sub-tree."
Explain to her why she is wrong with an example tree.
*Answer: Because you use the maximum of the left sub-tree or the minimum of the right sub-tree
 *Example tree part: IN this tree if you delete the 6 you will use the 5 to replace not the 11, if you utilize the 11 the tree would be wrong.
			6
		4		10
	3		5 8		11
3) Why would we want to balance search trees? 
(i.e. What is wrong with unbalanced trees?)
*Answer: Because you would have a shallow tree that have a better performance.
SECTION 5. GRAPHS: Islands and Bridges [2pts per prompt = 6 points]
You want to find a way to connect 300 islands with two-way bridges (i.e. lines, not arrows).
You know the distances between the islands. 
You want to minimize the total lengths of the bridges.
1) What algorithm would you use to solve this problem? (Algorithm for finding what?)
 *Answer: The Algorithm is Dikistra, utilizing the distances and get the Minimum speeding tree. 
2) How many bridges will you end up with if you used this algorithm?
 *Answer Formula: n-1
 *Answer Actual number: 299
 
SECTION 6. ENCYPTION (Fill in the blanks)[1 pt per blank = 3 points]
Using RSA, if people want to send messages to Mary, they have to use her __public____ encryption key. She uses her ____private__ decryption key to decode them. ___Prime__ numbers play an important role in constructing these keys.
SECTION 7. MEMORY [1pt per prompt = 4pts]
 
1) What are garbage cells? Why do we need to do “garbage collection”?
*What: Cells that you are not using anymore but they are allocated 
*Why: To delete those cells ( that you are not using anymore) so them can be used again
2) Name two ways to avoid fragmentation as you allocate cells of different sizes.
*Way1* Coalescing
*Way2* Worse fit 
SECTION 8 NP vs. P Consulting Job [2pts per prompt = 6 points]
1) Your boss says "I want you to find the shortest path that
 passes through all the Mars alien bases.
 The objective is to infect each base
 and thus you cannot return to the same base ever again.
 I want an algorithm to do it in Polynomial time."
 
 *What would you say to him? Explain: No possible because this is problem NP, The selsman.
10 years from today, while taking shower, you find a polynomial time algorithm for bin packing. Congratulations!! What implication does this have on your answer to the question above? What famous question have you answered?
*Answer: That you can translate all the another NP problems to P, because you just need to resolve one problem to resolve the others.
*Question answered: P==NP?
================== THE END ===================================================
Re-read all answers to make sure you are satisfied.
Upload to the Cougar Courses.
I hope to finish grading this before next Tuesday. Then I will email you.
You have your own spreadsheet and the syllabus to figure out the grade.
Have a nice vacation and hope to see you soon! Visit me any time.