• ¿Documento equivocado? Cámbialo gratis
  • Escrito por estudiantes que aprobaron
  • Inmediatamente disponible después del pago
  • Leer en línea o como PDF
Vender
¿Dónde estudias?
Tu idioma
Document preview thumbnail
Vista previa 4 fuera de 33 páginas
Examen

Cs6515 Exam 3 Study Guide

Document preview thumbnail
Vista previa 4 fuera de 33 páginas

CS6515 EXAM 3 STUDY GUIDE

Vista previa del contenido

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

Información del documento

Subido en
28 de noviembre de 2024
Número de páginas
33
Escrito en
2024/2025
Tipo
Examen
Contiene
Preguntas y respuestas
$9.50

¿Documento equivocado? Cámbialo gratis Dentro de los 14 días posteriores a la compra y antes de descargarlo, puedes elegir otro documento. Puedes gastar el importe de nuevo.
Escrito por estudiantes que aprobaron
Inmediatamente disponible después del pago
Leer en línea o como PDF

Seller avatar
Los indicadores de reputación están sujetos a la cantidad de artículos vendidos por una tarifa y las reseñas que ha recibido por esos documentos. Hay tres niveles: Bronce, Plata y Oro. Cuanto mayor reputación, más podrás confiar en la calidad del trabajo del vendedor.
STUDYFIELD
4.2
(20)
Vendido
97
Seguidores
14
Artículos
3222
Última venta
3 semanas hace




Por qué los estudiantes eligen Stuvia

Creado por compañeros estudiantes, verificado por reseñas

Calidad en la que puedes confiar: escrito por estudiantes que aprobaron y evaluado por otros que han usado estos resúmenes.

¿No estás satisfecho? Elige otro documento

¡No te preocupes! Puedes elegir directamente otro documento que se ajuste mejor a lo que buscas.

Paga como quieras, empieza a estudiar al instante

Sin suscripción, sin compromisos. Paga como estés acostumbrado con tarjeta de crédito y descarga tu documento PDF inmediatamente.

Student with book image

“Comprado, descargado y aprobado. Así de fácil puede ser.”

Alisha Student

Preguntas frecuentes