Shreyas’ Notes

Algorithmic Thinking

COMP 182

spring, freshman year

Logic and Proofs §

Propositions §

please don’t confuse AND/conjunction/\wedge with OR/disjunction/\vee.

pp qq pqp \wedge q pqp \vee q pqp \oplus q pqp \rightarrow q qpq \rightarrow p pqp \leftrightarrow q ¬p\neg p ¬q\neg q
F F F F F T T T T T
F T F T T T F F T F
T F F T T F T F F T
T T T T F T T T F F

Tautology: always true

Contradiction: always false

Satisfiable: not a contradiction. not always false. not impossible.

SAT: propositional satisfiability. NP-complete.

Propositional equivalence §

pp and qq are logically equivalent if pqp \leftrightarrow q (p=qp = q) is a tautology.

De Morgan’s laws:

prove equivalences using:

Predicates and Quantifiers §

variables.

e.g. x{1,2,3}x \in \{1, 2, 3\}, P(x):=x{1,2,3}P(x) := x \in \{1, 2, 3\}

quantifiers:

demorgan’s laws:

xyyx\forall x \forall y \equiv \forall y \forall x, xyyx\exists x \exists y \equiv \exists y \exists x

xy≢yx\forall x \exists y \not \equiv \exists y \forall x

negating nested quantifiers:

  1. s/\exists/\forall/g
  2. s/\forall/\exists/g
  3. negate the proposition

Proofs and Proof Techniques §

proofs: valid arguments that establish the truth of statements

Rules of Inference §

Proof techniques §

Sets §

unordered collection of unique items

cardinality of a finite set: number of elements in the set

infinite sets: countable, uncountable

x(xAxB)AB\forall x(x \in A \rightarrow x \in B) \rightarrow A \subseteq B

P(A)=2A={x:xA}\mathscr{P}(A) = 2^A = \{x : x \subseteq A\}

P()={}\mathscr{P}(\varnothing) = \{\varnothing\}

Proper subsets (\subset): subsets excluding the set itself

Set operations §

Set identities §

Functions §

non-empty sets DD (domain) and RR (codomain)

function: assignment — from every element in DD to exactly one element in RR

range (elements actually used as values) \subseteq codomain

f:ABf: A \rightarrow B and f:CDf: C \rightarrow D are equal functions when:

when f:ARf: A \rightarrow \mathbb{R} and g:ARg: A \rightarrow \mathbb{R}

Injections, surjections, bijections §

Inverse and composition §

Relations and their properties §

a binary relation from AA to BB is a subset of A×BA \times B.

(a,b)R(a, b) \in R, aRbaRb

(a,b)∉R(a, b) \not \in R, aba \not R b

composing — aRbbSc    a(RS)caRb \wedge bSc \implies a(R \circ S)c

Representing relations §

Relation closures §

"SS is the closure of RR wrt PP" — relation SS is the smallest set that satisfies property PP such that RSR \subseteq S

[RR is a relation on set AA]:

Equivalence relations §

two element are equivalent (aba \sim b) if they’re related by an equivalent relation.

RR is an equivalence relation on AA, aAa \in A. equivalence class of aa ([a][a]) is {bA:(a,b)R}\{b \in A: (a,b) \in R\}

partition of AA.

bipartition: n=2n = 2.

fundamental theorem of equivalence relations: the set of all equivalence classes of a relation RR on AA form a partition of AA.

Partial Orders §

set AA + partial order RR = partial-ordered set aka “poset” (A,R)(A, R)

aa and bb are elements of a poset (A,)(A, \preceq)aa and bb are comparable if either aba \preceq b or bab \preceq a. else, they are incomparable.

if (A,)(A, \preceq) is a poset where every two elements of AA are comparable, AA is a totally ordered set and \preceq is a total order.

Hasse diagrams are graphical reps of partial orders. excludes reflexivity and arrows that can be obtained by transitivty.

aa is a maximal element if there’s no cA,cac \in A, c \neq a such that aca \preceq c

bb is a minimal element if there’s no cA,cbc \in A, c \neq b such that cbc \preceq b

minimal and maximal elements do not have to exist or be unique.

aa is the greatest element if cA,ca\forall c \in A, c \preceq a.

bb is the least element if cA,bc\forall c \in A, b \preceq c.

greatest and least elements do not have to exist, but they must be unique.

a totally ordered set (A,)(A, \preceq) is a well-ordered set if every non-empty subset of AA has a least element

Matrices §

Graphs §

Undirected graphs §

Pair (V,E)(V, E) where:

Directed graphs §

aka digraphs

Pair (V,E)(V, E) where:

Jargon §

Special graphs §

Connectivity §

Graph Isomorphism §

Q: subgraph isomorphism vs subgraph

Representing graphs §

n:=n := number of nodes

m:=m := number of edges

Sequences and Summations §

sequence: a function from a subset of the set of integers to a set SS. ana_n, {an}\{a_n\}

recurrence relation for a sequence is an equation that expresses ana_n in terms of one or more of the previous terms of the sequence

summation:

series: sum of a sequence from n=0n = 0 or n=1n = 1 as necessary

Algorithm Efficiency §

finite sequence of precise instructions for performing a computation

Big O notation §

f(x)=O(g(x))f(x) = \mathcal{O}\left(g(x)\right) if there exist positive constants CC and kk such that f(x)Cg(x)f(x) \leq Cg(x) for all xkx \geq k

Big Omega notation §

f(x)=Ω(g(x))f(x) = \Omega\left(g(x)\right) if there exist positive constants CC and kk such that f(x)Cg(x)f(x) \geq Cg(x) for all xkx \geq k

f(x)=Ω(g(x))g(x)=O(f(x))f(x) = \Omega(g(x)) \Leftrightarrow g(x) = \mathcal{O}(f(x))

Big Theta notation §

… aka “order of”

f(x)=Θ(g(x))f(x) = \Theta\left(g(x)\right) if there exist positive constants C1C_1, C2C_2, and kk such that C1g(x)f(x)C2g(x)C_1 g(x) \leq f(x) \leq C_2 g(x) for all xkx \geq k

f(x)=Θ(g(x))f(x) = \Theta(g(x)) iff f(x)=O(g(x))f(x) = \mathcal{O}(g(x)) and f(x)=Ω(g(x))f(x) = \Omega(g(x)).

Complexity of algorithms §

efficiency:

ignore multiplicative and additive constants

for a given input size nn:

if there exists a polynomial-time worst-case algorithm for a problem, the problem is tractable. else, it’s intractable.

halting problem:

post correspondence problem

BFS §

[see also: COMP 140’s BFS section]

[see also: COMP 140’s Queue section]

Mathematical Induction §

[P(1)k(P(k)P(k+1))]nP(n)[P(1) \wedge \forall k (P(k) \rightarrow P(k + 1))] \rightarrow \forall n P(n)

Important fact: The set of positive integers is well-ordered.

  1. Basis step: Show that P(1)P(1)

  2. Inductive step: Show that kP(k)P(k+1)\forall k P(k) \rightarrow P(k + 1)

    The assumption that P(k)P(k) is called the inductive hypothesis

Strong Mathematical Induction §

  1. Basis step: Show that P(1)P(1)

  2. Inductive step: Show that k[P(1)P(2)P(k)]P(k+1)\forall k [P(1) \wedge P(2) \wedge \cdots \wedge P(k)] \rightarrow P(k + 1)