cse 2321 final

help

for what values of m and n are K_m,n contains an Euler circuit?

for even integers and m, n >=1 will K_m,n contain a Euler circuit. for all vertices to have even degrees, m must be even so vertices on the n-side have even degree m, and vice versa for n.

why is every tree a bipartite graph?

since trees are acyclic, trees can always be partitioned into two sets of vertices where no two vertices within the same set are connected by an edge, making the tree bipartite.

how do you determine the number of edges in an adjacency graph of G if G is a simple graph

add up the sum and divide by 2

what is a DAG

directed acyclic graph

a directed graph where no cycle exists

what is BFS

breadth-first search

an algorithm for traversing or searching tree or graph data structures

what is DFS

depth-first search

an algorithm for traversing or searching tree or graph data structures

difference between bfs and dfs?

dfs searches the longest path from 1 vertex before backtracking while bfs looks at all the neighbors before moving onto the next

what is topological sort

sort vertices of a directed acyclic graph so that for every edge (v_i, v_j), vertex v_i precedes v_j

hamilton path

a simple path in a graph that passes through every vertex exactly once

hamilton circuit

simple circuit in a graph that passes through every vertex exactly once

hamiltonian

graph which contains hamilton circuitthe

theorem for Euler circuit

let G be directed. G has Euler circuit iff indeg(v) = outdeg(V) for all V
simple terms: connected multigraph with at least two vertices has a circuit iff each of its vertices has even degree

theorem for Euler path

let G be directed. there are exactly 2 vertices for which indeg ≠ outdeg
simple terms: connected multigraph has exactly two vertices of odd degree

why are quantifiers necessary for a predicate? explain with an example

quantifiers make predicates into full true or false statements. they’re necessary to show the extent of which the predicate true. for example, P(x): x > 0, but what x? the universal quantifier∀x∈R clarifies what x values are being discussed.

explain why A x ∅ is an empty set. (A is a set)

cartesian product A x B is the set of all ordered pairs where a∈A and 𝑏∈𝐵. in this case b ∈ ∅. there is no b pair with any a, thus no pairs can be formed. thus A x ∅ = ∅

explain why n^2/3(logn)² is asymptotically more powerful than (logn)¹⁰⁰

(logn)¹⁰⁰ is only logarithmic growth while n^2/3(logn)² has a power growth of 2/3. any power growth is more powerful than just a log growth.

write the difference between an axiom and a theorem. provide an example of each.

an axiom is a statement that’s assumed to be true that’s used in a proof to establish the truth of a theorem while a theorem is a statement that can be proven.
ex axiom: for any real number a, a=a
ex theorem: for all real numbers a and b, if a = b, then b = a.

(T/F) if all birds can win, then 9 + 1 = 11

true since both propositions are false

(T/F) 12 is a prime number or 2 + 3 = 5

true since at least one proposition is true (2 + 3 = 5)

(T/F) if 5 + 3 = 10, then the sun rises in the west

true since both propositions are false

(T/F) 4 < 2 if and only if 6 > 3

false because one proposition is false

(T/F) 5 is a prime number and 14 is a multiple of 17

true because both propositions are true

asymptotic running time of insertion sort

θ(n²)

asymptotic running time of binary search

θ(log n)

asymptotic running time of linear search

θ (n)