• Wrong document? Swap it for free
  • Written by students who passed
  • Immediately available after payment
  • Read online or as PDF
Sell
Where do you study
Your language
Document preview thumbnail
Preview 4 out of 33 pages
Exam (elaborations)

Cs6515 Exam 3 Study Guide

Document preview thumbnail
Preview 4 out of 33 pages

CS6515 EXAM 3 STUDY GUIDE

Content preview

Name: Score:


21 Multiple choice questions

Term 1 of 21
What is Rudrata Cycle problem?

An edge between complimentary vertices
- x and x' have a variable edge between them.

Find a CYCLE that visits each VERTEX exactly once.
-No Known Polynomial Time algorithm

Find a PATH that contains each EDGE exactly once.
-Can be solved in Polynomial Time

Same as Rudrata cycle except find a PATH.

,Term 2 of 21
What vertices do we choose to be in the IS?

1. Create a graph representation of 3SAT input
- 1 vertex for each literal and each clause.
2. Add Clause Edges
-An edge between each literal in a clause
3. Add variable edges
-An edge between x and x'

1. No Clause Edges between vertices.
-Vertices cannot be neighbors of each other.
2. No Variable Edges
-Vertices cannot be compliment of each other
- x and x' cannot both be in IS.

NP-Complete problems are the hardest in the set NP.
NP-Hard is not necessarily in NP.
NP-Hard problems are at least as hard as everything in the set NP.

1. Max-Independent-Set
2. Clique
3. Vertex Cover
4. SAT
5. 3SAT
6. Independent Set

,Term 3 of 21
What are the claims of 3SAT reduction to Independent Set?

NP-Complete problems are the hardest in the set NP.
NP-Hard is not necessarily in NP.
NP-Hard problems are at least as hard as everything in the set NP.

- 3SAT input, f, has a satisfying assignment <==> G has an independent set of size ≥ g
- g = m = # of clauses

1. Max-Independent-Set
2. Clique
3. Vertex Cover
4. SAT
5. 3SAT
6. Independent Set

The hardest problems in the NP class.
A problem is NP-Complete if it is in NP and in NP-Hard.

Term 4 of 21
What is a variable edge?

Find a PATH that contains each EDGE exactly once.
-Can be solved in Polynomial Time

NP = Non-Deterministically Polynomial
-A problem where the Solution can be VERIFIED in Polynomial-Time

An edge between vertices in the same clause

An edge between complimentary vertices
- x and x' have a variable edge between them.

Term 5 of 21
What is a clause edge?

A type of punctuation used to indicate a clause

A graphical representation of all clauses in a legal contract

A boundary that separates different clauses in a document

An edge between vertices in the same clause

, Term 6 of 21
What is Euler Path Problem?

Find a CYCLE that visits each VERTEX exactly once.
-No Known Polynomial Time algorithm

An edge between complimentary vertices
- x and x' have a variable edge between them.

Same as Rudrata cycle except find a PATH.

Find a PATH that contains each EDGE exactly once.
-Can be solved in Polynomial Time

Term 7 of 21
How to prove S is an independent set?

1. Prove the problem is in NP
-Given problem and solution, Verify solution in Polynomial Time.
2. Prove problem is as hard as any NP-Complete problem. (K nown → New)
-Show reduction from known NP-Complete problem to this problem.
-Use a problem similar to this one.
-Prove forward and backward implication.

1. Create a graph representation of 3SAT input
- 1 vertex for each literal and each clause.
2. Add Clause Edges
-An edge between each literal in a clause
3. Add variable edges
-An edge between x and x'

-S has exactly 1 vertex per clause
-Both x₁ and x₁' are not in S.
-|S| = m = g

1. Max-Independent-Set
2. Clique
3. Vertex Cover
4. SAT
5. 3SAT
6. Independent Set

Document information

Uploaded on
November 28, 2024
Number of pages
33
Written in
2024/2025
Type
Exam (elaborations)
Contains
Questions & answers
$9.50

Wrong document? Swap it for free Within 14 days of purchase and before downloading, you can choose a different document. You can simply spend the amount again.
Written by students who passed
Immediately available after payment
Read online or as PDF

Seller avatar
Reputation scores are based on the amount of documents a seller has sold for a fee and the reviews they have received for those documents. There are three levels: Bronze, Silver and Gold. The better the reputation, the more your can rely on the quality of the sellers work.
STUDYFIELD
4.2
(20)
Sold
97
Followers
14
Items
3222
Last sold
3 weeks ago




Why students choose Stuvia

Created by fellow students, verified by reviews

Quality you can trust: written by students who passed their tests and reviewed by others who've used these notes.

Didn't get what you expected? Choose another document

No worries! You can instantly pick a different document that better fits what you're looking for.

Pay as you like, start learning right away

No subscription, no commitments. Pay the way you're used to via credit card and download your PDF document instantly.

Student with book image

“Bought, downloaded, and aced it. It really can be that simple.”

Alisha Student

Working on your references?

Create accurate citations in APA, MLA and Harvard with our free citation generator.

Working on your references?

Frequently asked questions