CS 6515 final, CS 6515 Final, CS 6515 Final Review Questions and Correct Answers the Latest Update
1 view 0 purchase
Course
CS 6515
Institution
CS 6515
Kite Reduction
Prove Kite is in np by verifying that
- check for the clique - O(n^2)
- check for the tail of degree <= 2 nodes O(n)
- check for that the tail is connected to the clique with Explore (O(n)
Reduce Clique to kite by adding a tail of length g to each vertex in graph G O(...
CS 6515 final, CS 6515 Final, CS 6515 Final
Review Questions and Correct Answers the
Latest Update
Kite Reduction
✓ Prove Kite is in np by verifying that
✓ - check for the clique - O(n^2)
✓ - check for the tail of degree <= 2 nodes O(n)
✓ - check for that the tail is connected to the clique with Explore (O(n)
✓
✓ Reduce Clique to kite by adding a tail of length g to each vertex in graph G O(n^2)
✓
✓ Transform back to Clique by removing all vertexs of degree <= 2 (prune the tails)
✓
✓ If there is no solution to kite then there is no clique in G
✓ If there is a solution to kite, removing the tail is then a solution to clique
Common Subgraph
✓ Prove common subgraph is in NP by
✓ - Check that the remaining vertexs is > b (O(n) for each graph
✓ - Check that Graph G1' and G2' are identical O(nm)
✓
✓ Reduce Clique to Common Subgraph by
✓ - Creating a copy of G1 , G2 and connecting each vertex to each other vertex in
G2 . O(2)
✓ - Call Common Subgraph on G1, G2, and the same goal k
✓
✓ O(1) take G1 and provide that as the solution to clique if there is a common
subgraph.
✓
✓ If there isnt a common subgraph to the clique we created G2 then G1 is not a
clique.
DFS
✓ Input : Graph G(V,E) directed or undirected
✓ Output : Prev[z] the parent index of vertex z
✓ pre[z] the pre number ""
✓ post[z] the post number ""
✓ ccum[z] the connected components
✓ can be strongly connected if verticies are passed in highest post number after
running dfs on a reversed directed graph
✓ Runtime: O(N+M)
Dijkstra's
✓ Input : Graph(V,E) directed or undirected
✓ Output :
✓ dist[u] the distance from s to u if s can reach u inf otherwise
✓ prev[z] the parent index of z
✓ non-negative weights
✓ O((n+m)logn) - adding weights adds work
BFS
✓ Input : Graph(V,E) directed or undirected , vertex s C V
✓ Output :
✓ dist[u] : the distance from s to u if s can reach u
✓ prev[z] : the parent index of vertex z
✓ O(n+M)
✓ - use this for unweighted single source shortest path
✓ Input : Graph G = (V,E), directed acyclic graph (DAG)
✓ Output :
✓ topo[i] : the vertex number of the i'th vertex in topological order from left to right,
source to sink
✓
✓ O(n+M)
✓ works by running DFS on the DAG and using the post order number to sort the
vertices from highest post to lowest post
Explore
✓ Input: Graph G = (V,E) , directed or undirected, v C V
✓ Output :
✓ visited[u] is set to true for all nodes u reachable from V
✓ - anything else available for DFS
✓
✓ O(m) as part of DFS
✓ O(n+m) if ran by itself and visited[] needs to be created
✓
✓ Subroutine of DFS
✓ Use this if you only care about a single source
✓ If you are to modify a black box algorithm, this would likely be the one
Strongly Connected Components
✓ Input : Graph G = (V,E), directed
✓ Output:
✓ GSCC = (V,E) where GSCC is a meta graph with each SCC in G forming a vertex C
V and each edge between SCCS C E
✓ VSSC will look like 1,2,3,4 which are ccums
✓ ESSC will look like (1,2) (2,3) (3,4) which are edges between VSSC
Smart Grades Latest update
1
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller Examify. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $13.49. You're not tied to anything after your purchase.
