Graph Search and Analysis Flashcards by Terry Le

Graph Search

Many graph algorthms use the same basic framework to navigate through a graph. We will call this algorithm: Graph Search

Shows which vertices can be retrivable from a certain vertex

Can be undirected or direct graph

How well did you know this?

Not at all

Perfectly

Graph Search Algorithm

Instance: a graph G(V,E)

Instance: Starting Vertex s

Output: a list of all vertices reachable from s by a directed path in G

How well did you know this?

Not at all

Perfectly

Big-O Notation

f(n) = O(g(n))

if f(n) = O(g(n)) then for a constant C, f(n) is strictly less than or equal to C(g(n))

How well did you know this?

Not at all

Perfectly

Big OMEGA Notatio

f(n) = OMEGA(g(n))

if f(n) = OMEGA (g(n)) then g(n) = O(f(n)) where for a constant C, g(n) is strictly less than or equal to C(f(n))

How well did you know this?

Not at all

Perfectly

Big-THETA Notation

f(n) = THETA(g(n))

if f(n) = THETA (g(n)) then

How well did you know this?

Not at all

Perfectly

Factoring

Given a number N, express it as a product of its prime factors

How well did you know this?

Not at all

Perfectly

Primality

Given a number N, determine whether it is a prime.

How well did you know this?

Not at all

Perfectly

Different ways of understanding log N

log N is the power to which you need to raise 2 in order ot obtain N
The number of times you need to divide by 2 or halve N to get down to 1.
It is the number of bits in the binary representation of N
It is the depth of the complete binary tree with N Nodes
It is the sum 1 + 1/2 + 1/3 +….. + 1/N to within a constant factor

How well did you know this?

Not at all

Perfectly

When answering most questions in this class remember that …

the answer should be expressed as a function of the size of the input.

How well did you know this?

Not at all

Perfectly

We are constantly wondering “if there is anything better”

In terms of how to improve the runtime of the algorithm

How well did you know this?

Not at all

Perfectly

It is often useful to remember that while for small values of n studying algorithms seems trivial but we are interested in how theese algorithms do for large values of n

By studying in detail at the level of the elementary operations on the indiviudal bits, it can uncover how the hardware, transtiors and wires, are manipulated for the implemntation of the algorithm.

How well did you know this?

Not at all

Perfectly

Bit shifting (padding a 0 to the right) is a simple way of multiplying the value by the bast.

By bit shifting binary, we double or multiply by 2 the current value of the binary sequence.

How well did you know this?

Not at all

Perfectly

Questions to ask about any algorithm

IS this algorithm correct?

How long does the algorithm take?

Can we do better?

How well did you know this?

Not at all

Perfectly

Modular Arithmetic

System for working with restricted ranges of integers

x modulo N is the remainder when x is divided by N, or x =qN + r, 0 =< r less than N, then x modulo N is equal to r.

How well did you know this?

Not at all

Perfectly

Equivalence classes

For example, three equivalence classes of modulo 3 any member of an equivalence class is substitutable for any other; when the numbers 5 and 11 are no different. 0 class, 1 class, and 2 class are equivalent to the next class of remainders that are 0 , 1, and 2

How well did you know this?

Not at all

Perfectly

Substitution Rule

Using Associativity, commutativity, and Distributivity, together with the subsitution rule, implies that while performing arithmetic operations, it is legal to reduce intermediate results to their remainder modulo N at an stage.

For example: 2^{354} = 2{5(69)} = 32^{69} = 1^{69} = 1 (mod 31)

Two’s Complement

Modular arithmetic is well demonstrated by 2’s complement used to storing signed integers. It is used to represent numbers in the range [-2^{N-1} , 2^{N-1}-1]

Positive integers will have a leading 0 in the sequence.

Negative integers will have a leading 1 in the sequence. Negative numbers are constructed by first flipping all the bits and then adding 1 to the right most position

Essentially its -2^{N-1} -x

For cryptography, modular exponentiation and greatest common divisor will be key

GCD and modular exponentiation

In order to make sure numbers that are being handled/computed never grow too large, we performa intermediate computations modulo N

So for x^y mod N, we take advantage of properties of log to break up x^y as a product of x^{a_2) * x^{b_2) * x^{c_2) …. * x^{z_2) , which can be the binary sequence of the factors of y matching the preferred base (in this case 2)

Euclid’s Algorithm for greatest common divisor

Euclid’s rue: If x and y are positive integers with x greater than or equal to y, then gcd (x,y) = gcd (x mod y, y)

Any integer that divides both x-y and y must also divide x and y , so gcd ((x,y) greater than or equal to gcd (x-y, y)

Suppose d is the gcd (a,b). How do you prove/check this? Need to confidently know that the factor dervied is the LARGEST/GREATEST

If d divides both a and b, and d=ax+by forsome integers x and y, then d = gcd (a,b)

By first two conditions, d is a common divisors of a and b, so it cannot exceed the actual gcd. Thus d must be less than or equal to gcd(a,b). On the other hand, the result of gcd(a,b) must be a common divisor of a and b, so it must divide ax + by =d. This implies that gcd(a,b) less than or equal to d. Putting together everything d=gcd(a,b)

Under any circumstane gcd(a,b) can always be expressed in this checkable form.

For any positive integers, a and b, the extended Euclid algorithm returns integers x, and y such that gcd(a,b) = d = ax+by.

Ignoring x and y, the expression/equation is the same as previous equation. So still need to always compute d = gcd(a,b) to start.
next use recursive nature of algorithm to hint at using induction. When b=0, algorithm ends. So use induction with b.

Base case b=0. Then continue with induction for values of b greater than 0. gcd (a,b) is gcd (b, a mod b). Since a mod b < b, we can apply inductive hypothesis to this recursive call and conclude that x’ and y’ returned are correct. Thus:

gcd (b,a mod b) = bx’ + (a mod b) y’

(not complete)

Exmaple of Euclids algorithm and lemma

compute gcd(25,11)

25 = 2 * 11 + 3
11 = 3 * 3 + 2
3 = 1 * 2 + 1
2 = 2 * 1 + 0

At each stage, the numbers (11, 3, 2, 1) are reduced smaller and smaller. Thus

gcd(25,11) = gcd (11,3) = gcd(3,2) = gcd (2,1) = gcd(1,0) =1

Moving backwards from the example of finding gcd(25,11). Given (2,1) then (3,2) then (11,3) then (25,11), find x and y such that 25x + 11y = 1

Show how to reconstruct

1= 1 - 0

1 = 2 - (2 -2*1) = -1 *2 + 3 * 1
Using substitution

1 = -1 2 + 3 * (3 - 1 * 2) = 3 * 3 - 4 * 2
Continue substitution 2= 11-33 and 3 = 25 -2*11

1 = 3 * 3 - 4 * (11 - 3 * 3) = -4 *11 + 15 * 3 =
-4 * 11 + 15 (25 - 2 * 11) = 15 * 25 - 24 * 11

Now we get:
15 * 25 - 24 * 11 = 1, So x =15, y = -34

Modular Division axiom: Every number a (a != 0) has an inverse , 1/a and dividing by a is the same as multiplying by the inverse. In modular arithmetic we do something similar too. -a and a x is Multiplicative inverse of a modulo N if ax = 1 (mod N)

There can be at MOST one such x modulo N., and that is dneoted as a^{-1} . Though inverse doesn't always exist. For example: 2x != 1 mod 6 for any x. Since a and N are both even and thus a mod N is always even, since a mod N = a - kN for some k. We can be certain that gcd(a,N) divide ax mod N

The only case that a is not invertible is when gcd (a, N) =1 (we say a and N are relatively prime), the extended Euclid algorithm gives us integers x and y such that ax + Ny =1. This means ax = 1(mod N)

Example: Suppose you need to compute 11^{-1} mod 25. Using extended Euclid Algorithm, we find 15*25 - 34*11 =1. Reducing both sides modulo 25, we have -34 = 16 mod 25 is the inverse of 11 mod 25

Modular Remainder Theorem For any a mod N, a has a multiplicative inverse modulo N if and only IF it is relatively prime to N.

If this inverse exists it can be found in O(n^3), where n is the number of bits of N through Extended Euclid Algorithm (EEA) This resolves issue of modular division: when working modulo N, we can divide by numbers relatively prime to N and only by these . And to actually carry out the division, we multiply by the inverse.

Factoring is HARD and Primality is EASY

We cannot factor large numbers but can easily test huge numbers for primality !

Trick to cut down number of integers to check.

1) Even numbers are never prime 2) You can declare N prime if you test all the numbers up to sqrt (N) . Since if N can be factored as N = K * L then it is impossible for both to be greate than sqrt(N)

Primality Testing first explore Fermats Little Theorem: if p is prime, then for every a greater than or equal to 1 and a less than p: a^{p-1} = 1 mod (p)

Suppose that S is the set of all integers modulo p, that is S= {1, 2, ... p-1}. Notice that by multiplying the set S by a (modulo p) jsut permutes (shuffles ) them. Multiplying both sides of equation by (p-1)! we get: S = {3 *1 mod7, 3*2 mod7, .... 3*6 mod 7} Now multiplying all the numbers in each representation then gives 6! = 3^6 * 6! (mod 7) Divide by 6! we get 3^6 = 1 (mod 7), which is the desired outcome of a=3 and p=7

Formal explanation of Fermats Little Theorem

S = {1, 2, .. p-1} We will show that all elements of S are multiplied by a modulo p, and the resulting numbers are all distinct and nonzero. Since they lie in the range [1,p-1] they are just permutations of S. a*i mod p are distinct since IF a*i = a*j (mod p), then dividing both sides by a gives i = j (mod p) . They are nonzero becuase a* i = 0 similiarly implies i =0 . And we can divide by a,because by assumption it is a nonzero and therefore relatively prime to p. S = {1,2,.. p-1} = {a*1 mod p, a*2 mod p..., a*(p-1) mod p} Multiply together its elements in each of the representations to get: (p-1)! = a^{p-1} * (p-1)! (mod p) Divide both sides by (p-1)! , which is allowed since p is assumed to be relatively prime , gives the theorem.

Fermat's Little Theorem suggests a "factorless" test for determining whether a number N is prime. (loook at page 35 for diagram) 1. pick some a. 2. Use Fermat's test : is a^{N-1} = 1 mod N}????? 3. a) IF pass then its PRIME b) if fail , then composite

Problem is however, that the theorem is NOT an -f-and only-if condition; it doesn't say what happens when N is NOT prime.

LEMMA: If a^{N-1} != 1 mod N for some a relatively prime to N, then it must hold for at least half of the choices of a < N.

....