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

Username
  

Password
  





Search Forums

(Advanced Search)

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.

Print this item

  P, NP, Np-Complete Helpful Explanation
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

Print this item

  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)?

Print this item

  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 :


  1. show that a solution can be verified in polynomial time on a non-deterministic computer.

  2. show that a solution can be verified in polynomial time on a deterministic computer.

  3. show that a solution can be found in polynomial time on a deterministic computer.

  4. 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?

Print this item

  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 .

  1. 3 n - 6

  2. 3 n - 1 

  3. 3 n - log n - 2

  4. 2 n - 1

  5. 2 n

  6. 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

Print this item

  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.

Print this item

  Amortized analysis reading
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

Print this item

  MRT practice problems with answers
Posted by: jaw653 - 12-12-2017, 03:56 AM - Forum: Final Exam - No Replies

I know I like practicing with answers, this website has some MRT practice problems with answers. http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/master.pdf

Print this item

  Need help with Amortized Analysis.
Posted by: ACCD - 12-11-2017, 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 3n-3 ?

Thanks!

Print this item

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

Will the Prerequisite exam stuff be on the final?

So final will have:

Sorting 
Recurrence Equations 
Self-Balancing Search Trees
Binomial and Fibonacci Heaps 
Disjoint Sets 
Graphs and Graph Algorithms 
Dynamic Programming 
Linear Selection and Linear Sorting
Amortized Analysis 
P,NP and NP-Completeness 

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?

Print this item