Graph Search and Analysis

Question 1

Graph Search

Answer 1

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

Question 2

Graph Search Algorithm

Answer 2

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

Question 3

Big-O Notation

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

Answer 3

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

Question 4

Big OMEGA Notatio

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

Answer 4

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))

Question 5

Big-THETA Notation

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

Answer 5

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

Question 6

Factoring

Answer 6

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

Question 7

Primality

Answer 7

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

Question 8

Different ways of understanding log N

Answer 8

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

Question 9

When answering most questions in this class remember that …

Answer 9

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

Question 10

We are constantly wondering “if there is anything better”

Answer 10

In terms of how to improve the runtime of the algorithm

Question 11

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

Answer 11

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.

Question 12

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

Answer 12

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

Question 13

Questions to ask about any algorithm

Answer 13

IS this algorithm correct?

How long does the algorithm take?

Can we do better?

Question 14

Modular Arithmetic

Answer 14

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.

Question 15

Equivalence classes

Answer 15

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

Question 16

Substitution Rule

Answer 16

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)

Question 17

Two’s Complement

Answer 17

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

Question 18

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

Answer 18

GCD and modular exponentiation

Question 19

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

Answer 19

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)

Question 20

Euclid’s Algorithm for greatest common divisor

Answer 20

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)

Question 21

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

Answer 21

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.

Question 22

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

Answer 22

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)

Question 23

Exmaple of Euclids algorithm and lemma

compute gcd(25,11)

Answer 23

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

Question 24

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

Answer 24

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

Question 25

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)

Answer 25

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

Question 26

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)

Answer 26

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

Question 27

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.

Answer 27

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.

Question 28

Factoring is HARD and Primality is EASY

Answer 28

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

Question 29

Trick to cut down number of integers to check.

Answer 29

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)

Question 30

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)

Answer 30

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

Question 31

Formal explanation of Fermats Little Theorem

Answer 31

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.

Question 32

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

Answer 32

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.

Question 33

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.

Answer 33

….