CS6515 - Algorithms- Exam 1 EXAM
comprehensive questions and verified answers|
FREQUENTLY MOST TESTED QUESTIONS AND
VERIFIED SOLUTIONS/GET IT 100% ACCURATE!!
Save
Terms in this set (98)
when fitting graph on a table, if the number of moves
decrease the w() from edge to edge, then there is a
How do you tell if a graph
negative edge;
has negative edges?
check from 1 to n
Why is all pairs Dist(y,z) Because it builds a two dim table!
n^2?
what is the run time of O(nm)
bellman ford algoirthm?
O(n^2m)
How about if you had to
do it for all edges?
FLoyd-Warshall run time? O(n^3)
what is the base case for D(0,s,t)
the bellman ford
algorithm?
, how does bellman ford bellman == can only find it if it can be access from the
and floyd differ when it "s" or start vertex
comes to detecting
negative weight cycles?
1. Define the Input and Output.
2. Define entries in table, i.e. T(i) or T(i, j) is...
3. Define a Recurrence relationship - Based on a
Steps to solve a Dynamic subproblem to the main problem. (hint: use a prefix of
Programming Problem the original input 1 < i < n).
4. Define the Pseudocode.
5. Define the Runtime of the algorithm. Use Time
Function notation here => T(n) = T(n/2) + 1...
Input = x1, x2, ..., xn
1) Subproblem = x1, x2, ..., xi ; O(n)
2) Subproblem = xi, xi+1, ..., xj ; O(n^2)
DP: Types of Subproblems Input = x1, x2, ..., xn; y1, y2, ..., ym
(4) 1) Subproblem = x1, x2, ..., xi; y1, y2, ..., yj ; O(mn)
Input = Rooted Binary Tree
1) Subproblem = Smaller rooted binary tree inside the
Input.
Given r = common ratio and a = first term in series
=> a + ar + ar^2 + ar^3 + ... + ar^(n-1)
DC: Geometric Series
=> a * [(1 - r^n) / (1-r)]
Given d = common difference and a = first term in
series => a + (a + d) + (a + 2d) + ... + (a + (n-1)d
DC: Arithmetic Series
Sum = n/2 [2a + (n-1)d]
comprehensive questions and verified answers|
FREQUENTLY MOST TESTED QUESTIONS AND
VERIFIED SOLUTIONS/GET IT 100% ACCURATE!!
Save
Terms in this set (98)
when fitting graph on a table, if the number of moves
decrease the w() from edge to edge, then there is a
How do you tell if a graph
negative edge;
has negative edges?
check from 1 to n
Why is all pairs Dist(y,z) Because it builds a two dim table!
n^2?
what is the run time of O(nm)
bellman ford algoirthm?
O(n^2m)
How about if you had to
do it for all edges?
FLoyd-Warshall run time? O(n^3)
what is the base case for D(0,s,t)
the bellman ford
algorithm?
, how does bellman ford bellman == can only find it if it can be access from the
and floyd differ when it "s" or start vertex
comes to detecting
negative weight cycles?
1. Define the Input and Output.
2. Define entries in table, i.e. T(i) or T(i, j) is...
3. Define a Recurrence relationship - Based on a
Steps to solve a Dynamic subproblem to the main problem. (hint: use a prefix of
Programming Problem the original input 1 < i < n).
4. Define the Pseudocode.
5. Define the Runtime of the algorithm. Use Time
Function notation here => T(n) = T(n/2) + 1...
Input = x1, x2, ..., xn
1) Subproblem = x1, x2, ..., xi ; O(n)
2) Subproblem = xi, xi+1, ..., xj ; O(n^2)
DP: Types of Subproblems Input = x1, x2, ..., xn; y1, y2, ..., ym
(4) 1) Subproblem = x1, x2, ..., xi; y1, y2, ..., yj ; O(mn)
Input = Rooted Binary Tree
1) Subproblem = Smaller rooted binary tree inside the
Input.
Given r = common ratio and a = first term in series
=> a + ar + ar^2 + ar^3 + ... + ar^(n-1)
DC: Geometric Series
=> a * [(1 - r^n) / (1-r)]
Given d = common difference and a = first term in
series => a + (a + d) + (a + 2d) + ... + (a + (n-1)d
DC: Arithmetic Series
Sum = n/2 [2a + (n-1)d]
