# Shared Flashcard Set

## Details

cs173 final exam
warnow fa2018
76
Computer Science
11/12/2018

Term
 Wheel graph with W5
Definition
 5 vertecies total, including the center. Looks like a square.
Term
 Hamiltonian path
Definition
 Path between two vertices that goes through each vertex once.
Term
 Hamiltonian Cycle
Definition
 Path that starts and ends at the same vertex and goes through each vertex once.
Term
 Circuit
Definition
 Closed loop where vertices may repeat. Edges cannot repeat
Term
 Path
Definition
 Open (meaning not same endpt) line where vertices cannot repeat. Edges cannot repeat (Open)
Term
 Cycle
Definition
 Vertices cannot repeat. Edges cannot repeat (Closed loop)
Term
 Eulerian Walk
Definition
 Visits every edge exactly once (can repeat vertices and be open)
Term
 Eulerian Cycle
Definition
 Graph that starts and ends at the same point and every edge is visited once only
Term
 Clique
Definition
 A subset of a graph where each vertex is adjacent to each other (basically a complete graph inside a graph)
Term
 independent set
Definition
 anticlique (a set of vertices in a graph, no two of which are adjacent)
Term
 Dominating set
Definition
 Every vertex is adjacent to something in the dominating set (*usually find min dom set)ex:A - B - CB would be min dom set
Term
 vertex coloring
Definition
 assignment of colors to vertices so no edge connects two of the same color
Term
 matching
Definition
 Set of edges that don't share endpoints (usually found as maximum matching.[image]
Term
 Connected graph
Definition
 vertecies are all joined by edges: ex:*-*-* is a path graph connecte*-* * is disconnected
Term
Definition
 Two vertices are called adjacent if they are connected by an edge.Two edges are called incident, if they share a vertex.
Term
 handshaking theorem
Definition
 total degree of all the vertices is twice the number of edges
Term
 chromatic number
Definition
 minimum vertex coloring
Term
 clique number
Definition
 number of vertices in a maximum clique
Term
 matching number
Definition
 maximum matching
Term
 Tree graph
Definition
 Graph without cycles
Term
 Big O formal definition
Definition
 f is O(g)if ∃C > 0 and k ≥ 0 such that |f(n)| ≤ C|g(n)| for all n > k.
Term
 big o with limits definition
Definition
 [image]
Term
 C(0,0)
Definition
 1
Term
 C(n,k)
Definition
 n!/(k!(n-k)!)
Term
 Decision problems
Definition
 Problem with yes or no values
Term
 Optimization problem
Definition
 Given a graph G, there is a ____ of size ___. Returns the best possible #.
Term
 CNF
Definition
 Conjunctive Normal Formconjunctions of clauses with clauses of disjunctions. In other words, a statement is a series of ORs connected by ANDs.
Term
 SAT (Satisfiability)
Definition
 descision problem where the input is a boolean formula and the output is a YES or NO statement
Term
 Karp reduction
Definition
 Suppose you have two decision problems, π and π.Suppose π' ∈ P, and that A is a polynomial time algorithm to solve π'.F maps Pi to Pi'YES-instances of π map to YES-instances of π'NO-instances of π map to NO-instances of π'The function F takes polynomial time to compute
Term
 X-CNF (ex: 2-CNF)
Definition
 All clauses have at most X literals
Term
 2-SAT, 3-SAT, X-SAT
Definition
 Is the input X-CNF formula satisfiable?
Term
 Permutation vs combination
Definition
 Order matters (permutation) vs doesnt (combination)
Term
 Permutation P(n,k)
Definition
 n!/(n-k)!
Term
 NP definition
Definition
 Non-deterministic Polynomial TimeNP is the set of decision problems for which you can prove YES-instances are YES-instances in polynomial time.
Term
 co-NP
Definition
 NO maps to NO
Term
 P
Definition
 P is the set of decision problems that can be solved in polynomial time.
Term
 P = NP or != NP
Definition
 Does NP contain problems that CANNOT be solved inpolynomial time?YES -> P != NPNO -> P = NPP is a subset of NP regardless
Term
 P, NP, NP Complete, NP Hard graph
Definition
 [image]
Term
 Construction problem
Definition
 Given a graph G, here are the vertecies from the set of ______
Term
 preposition
Definition
 statement that is true or false, but not both
Term
 p ⊕ q truth table
Definition
 True if only ONE is true, false if both are T/F[image]
Term
 converse of p->q
Definition
 q->p
Term
 contrapositive of p->q
Definition
 ¬q → ¬p
Term
 tautology
Definition
 compound statement that is always true
Term
Definition
 statement that is always false
Term
 contingency
Definition
 statement that is neither a tautology or contradiction (can be either true or false)
Term
 DeMorgans Laws (2)
Definition
 (p ∧ q) ≡ ¬p ∨ ¬q¬(p ∨ q) ≡ ¬p ∧ ¬q
Term
 p ∨ (q ∧ r) ≡ (distribute)
Definition
 (p ∨ q) ∧ (p ∨ r)
Term
 satisfiable/unsatisfiable
Definition
 satisfiable - can make the compound preposition true (same as tautology)unsatisfiable - cant make it true.
Term
 universal quantifierexistential quantifier
Definition
 universal quantifier - ∀existential quantifier - ∃
Term
 ¬∀xP (x) ≡
Definition
 ∃x ¬P (x)
Term
 A∩B
Definition
 intersection, objects that belong to set A and set B
Term
 A∪B
Definition
 Union - objects that belong to set A or set B
Term
 A⊆B
Definition
 subset-A is a subset of B. set A is included in set B.
Term
 Power set P(A)
Definition
 All subsets of A
Term
 A\B
Definition
 Same thing as A-B - Objects in A but not in B
Term
 Ac
Definition
 Complement - all the objects that do not belong to set A
Term
 handshaking theorem
Definition
 The sum of degrees of the vertices of a graph is twice the number of edges
Term
 Injective function
Definition
 One-to-One FunctionA function for which every element of the range of the function corresponds to exactly one element of the domain.Ex: passes both vertical line test and horizontal line test
Term
 surjective function
Definition
 Onto functionEvery element of b is mapped to an element of a (if f(2) = 3 then there has to be a f(x) = 2)
Term
 The notation f : X → Y means
Definition
 f is a function from X to YYou can think of f as an algorithm with input coming from X and output in Y
Term
 Prove a closed form by contradiction
Definition
 Find the smallest k, s.t., P(k) is false while P(k-1) is true. Then prove P(k-1)->P(k)
Term
 partial order
Definition
 reflexive, anti-symmetric, and transitive
Term
 proper subset
Definition
 set is a subset of that is not equal to
Term
 Reflexive set
Definition
 Every element is related to itself
Term
 Symmetric set
Definition
 if a->b (related) then b->a (related)
Term
 Transitive set
Definition
 if aRb and bRc then aRc
Term
 Equivalence relation
Definition
 symmetric, reflexive, transitive
Term
 image of a function
Definition
 subset of the functions codomain, which is the output (basically just output)
Term
 codomain (functions)
Definition
 set of outputs a function can have (range)
Term
 p->q alternatively
Definition
 ¬p ∨ q
Term
 π α π' (reduction)
Definition
 π is no harder than π'
Term
 The empty set is a subset of the reals/naturals (T/F)
Definition
 True!
Term
 Induction - Picking arbitrary N
Definition
 Pick the largest base case. For weak induction, pick N >= 1
Term
 A set is countable if ____
Definition
 finite or countable infinite.
Term
 Two-satisfiability
Definition
 A special case of CNF is where each clause has at mosttwo literals! That is, expression that are written in the form (A1 ∨ B1) ∧ (A2 ∨B2) ∧ . . .(Ak ∨ Bk)
Supporting users have an ad free experience!