Welcome, Guest You have to register before you can post on our site. Username   Password   Remember me

 Search Forums

 Forum Statistics » Members: 160 » Latest member: zezima » Forum threads: 473 » Forum posts: 1,512 Full Statistics

 Online Users There are currently 7 online users.» 1 Member(s) | 6 Guest(s)alexbusol

 Latest Threads Decision Trees Problem Forum: Final Exam Last Post: ACCD Yesterday, 05:10 AM » Replies: 3 » Views: 57 P, NP, Np-Complete Helpfu... Forum: Final Exam Last Post: elyssekimmel Yesterday, 01:43 AM » Replies: 0 » Views: 48 Dynamic table filling Forum: Final Exam Last Post: alexbusol 12-13-2017, 07:23 PM » Replies: 2 » Views: 64 Answer for Amortized Anal... Forum: Final Exam Last Post: awlay 12-13-2017, 06:40 PM » Replies: 1 » Views: 76 Number 15 on P and NP Forum: Final Exam Last Post: awlay 12-13-2017, 06:32 PM » Replies: 0 » Views: 45 Linear Selection Equation... Forum: Final Exam Last Post: ianbway 12-13-2017, 06:11 PM » Replies: 5 » Views: 110 Amortized analysis readin... Forum: Final Exam Last Post: ACCD 12-13-2017, 05:16 AM » Replies: 1 » Views: 81 Need help with Amortized ... Forum: Final Exam Last Post: ACCD 12-12-2017, 06:37 AM » Replies: 2 » Views: 113 MRT practice problems wit... Forum: Final Exam Last Post: jaw653 12-12-2017, 03:56 AM » Replies: 0 » Views: 54 What will be on the final... Forum: Final Exam Last Post: smmitchell2 12-10-2017, 03:49 PM » Replies: 2 » Views: 107

Decision Trees Problem
Posted by: ACCD - Yesterday, 04:11 AM - Forum: Final Exam - Replies (3)
 How to solve this problem and get 3? In an efficient decision tree (no redundant comparisons) for the comparison sorting of 3 numbers, what is the largest possible depth of a leaf? Assume the root is at depth 0, a child of the root is at depth 1, and so on. A leaf in a decision tree is the final ordering.

Posted by: elyssekimmel - Yesterday, 01:43 AM - Forum: Final Exam - No Replies
 For anyone still confused on how all these relate, I found that this short video explains it well: https://www.youtube.com/watch?v=OY41QYPI8cw

Dynamic table filling
Posted by: alexbusol - 12-13-2017, 06:53 PM - Forum: Final Exam - Replies (2)
 Can somebody please explain the how do we get dynamic table's dimensionality, largest index and the direction it is filled (ie low to high, high to low)?

Number 15 on P and NP
Posted by: awlay - 12-13-2017, 06:32 PM - Forum: Final Exam - No Replies
 I'm not sure if the answer is A or B for number 15 on the problem set: 15. Which one of the following is not a valid way to prove a problem is in N P : show that a solution can be verified in polynomial time on a non-deterministic computer. show that a solution can be verified in polynomial time on a deterministic computer. show that a solution can be found in polynomial time on a deterministic computer. show that a solution can be found in polynomial time on a non-deterministic computer. I think the answer is B because in this case you are only proving that the verification algorithm for the problem runs in polynomial time. You do not, however, know if you can non-deterministically guess before it and therefore that might take exponential time and the algorithm could not be NP. C would place the problem in P which is in NP. D is the definition of NP. A is the verification step on a non-deterministic computer which should prove that the entire algorithm is in NP since in the step before it, it guesses correctly for everything. At least that's my reasoning. Am I wrong and it's A? And if so, why?

Answer for Amortized Analysis Question 5
Posted by: ipnanayakkara - 12-13-2017, 05:02 PM - Forum: Final Exam - Replies (1)
 As requested on google doc. Question: Quote:Consider a dynamic fillable array which grows from size n to size 2 n + 1 each time the array is filled. Which is a valid equation for calculating the total cost incurred when insertion 2 i is made? Assume the individual cost of an insert when there is room is 1 and the individual cost of an insert when there is no room is 2 i . 3 n - 6 3 n - 1  3 n - log n - 2 2 n - 1 2 n 3 n - 3 Answer: Operation                                                                                                        Cost ©                                                Total Cost 1) Insert initial (write array =1)                                                                            (1)                                                         1 2) Need to resize and insert (New size = 2(1) +1 = 3)      (oldvalue +newvalue)1+1 (2)                                                         3 3) Regular insert (write array =1)                                                                         (1)                                                         4 4) Need to resize and insert (New size = 2(3) +1 = 7)                                     3+ 1(4)                                                         8 5) Regular Insert (write array =1)                                                                        (1)                                                         9 6) Regular Insert (write array =1)                                                                        (1)                                                        10 7) Regular Insert (write array =1)                                                                        (1)                                                        11 8) Need to resize and insert (New size = 2(7) +1 = 15)                                   7+1 (8)                                                        19                                                    Looking at only when it resizes (OP 2, 4, 8): Assuming 3n - log n - 2 is true When OP = 2; Cost = 3(2) - log 2 - 2 =   6 - 1 - 2 =  3 (Calculated in table) When OP = 4; Cost = 3(4) - log 4 - 2 = 12 - 2 - 2 =  8 (Calculated in table) When OP = 8; Cost = 3(8) - log 8 - 2 = 24 - 3 - 2 = 19 (Calculated in table) So therefore the equation has to be right

Linear Selection Equation(s)
Posted by: julian - 12-13-2017, 04:36 PM - Forum: Final Exam - Replies (5)
 Anyone willing to share the equation for linear selection upper/lower bounds? I think the one I have is not correct: elements greater than m-of-m ≤ ceil [ group size / 2] * ceil [ n / group size ] + ceil [ n / group size ] + floor [ group size / 2] Any feedback is much appreciated.

Posted by: alexbusol - 12-12-2017, 08:47 PM - Forum: Final Exam - Replies (1)
 Does anyone have any good readings on amortized analysis? I've always kind of struggled with it Thanks in advance