Graph Search and Analysis Flashcards
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
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
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))
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))
Big-THETA Notation
f(n) = THETA(g(n))
if f(n) = THETA (g(n)) then
Factoring
Given a number N, express it as a product of its prime factors
Primality
Given a number N, determine whether it is a prime.
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
When answering most questions in this class remember that …
the answer should be expressed as a function of the size of the input.
We are constantly wondering “if there is anything better”
In terms of how to improve the runtime of the algorithm
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.
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.
Questions to ask about any algorithm
IS this algorithm correct?
How long does the algorithm take?
Can we do better?
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.
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
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 1525 - 3411 =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, 32 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.
ai mod p are distinct since IF ai = aj (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} = {a1 mod p, a2 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)
- pick some a.
- Use Fermat’s test : is a^{N-1} = 1 mod N}?????
- 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.
….
