Welcome, Guest 
You have to register before you can post on our site.

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, NpComplete Helpfu...
Forum: Final Exam
Last Post: elyssekimmel
Yesterday, 01:43 AM
» Replies: 0
» Views: 48

Dynamic table filling
Forum: Final Exam
Last Post: alexbusol
12132017, 07:23 PM
» Replies: 2
» Views: 64

Answer for Amortized Anal...
Forum: Final Exam
Last Post: awlay
12132017, 06:40 PM
» Replies: 1
» Views: 76

Number 15 on P and NP
Forum: Final Exam
Last Post: awlay
12132017, 06:32 PM
» Replies: 0
» Views: 45

Linear Selection Equation...
Forum: Final Exam
Last Post: ianbway
12132017, 06:11 PM
» Replies: 5
» Views: 110

Amortized analysis readin...
Forum: Final Exam
Last Post: ACCD
12132017, 05:16 AM
» Replies: 1
» Views: 81

Need help with Amortized ...
Forum: Final Exam
Last Post: ACCD
12122017, 06:37 AM
» Replies: 2
» Views: 113

MRT practice problems wit...
Forum: Final Exam
Last Post: jaw653
12122017, 03:56 AM
» Replies: 0
» Views: 54

What will be on the final...
Forum: Final Exam
Last Post: smmitchell2
12102017, 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.



Dynamic table filling 
Posted by: alexbusol  12132017, 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  12132017, 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 nondeterministic 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 nondeterministic 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 nondeterministically 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 nondeterministic 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  12132017, 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  12132017, 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 mofm ≤ ceil [ group size / 2] * ceil [ n / group size ] + ceil [ n / group size ] + floor [ group size / 2]
Any feedback is much appreciated.



Need help with Amortized Analysis. 
Posted by: ACCD  12112017, 08:43 PM  Forum: Final Exam
 Replies (2)


Consider a dynamic fillable array which grows by doubling in size. Which is a valid equation for calculating the total cost incurred when insertion 2 i + 1 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 + 1.
How to get 3n3 ?
Thanks!



What will be on the final? 
Posted by: ACCD  12102017, 12:56 PM  Forum: Final Exam
 Replies (2)


Will the Prerequisite exam stuff be on the final?
So final will have:
Sorting
Recurrence Equations
SelfBalancing Search Trees
Binomial and Fibonacci Heaps
Disjoint Sets
Graphs and Graph Algorithms
Dynamic Programming
Linear Selection and Linear Sorting
Amortized Analysis
P,NP and NPCompleteness
Final will have 30 question, can bring two double side note sheet.
Final will be Dec 14 (Thursday) 11:30 am  2:00 pm.
Is that right?



