ECE 406 Algorithms notes

ECE 406 Algorithms notes.md

#Class #2 Wed. Jan 9, 2013

End of last class

f = O(g) if there exist constants c and N s.t.

(notation: ∀ === for all)

f(n) ≤ g(n) ∀ n ≥ N

f = Ω(g) if g = O(f)

f = Θ(g) if f = O(g) and f = Ω(g)

Say we have

f(n) = 5n² + 10n

Claim: f(n) = O(n²)

Proof: need to find c and N s.t.

5n² + 10n ≤ cn² ∀ n ≥ N

divide by n²:

5 + 10 / n ≤ c

take c = 15, N = 1

Claim: f = Ω (n²)

Proof: find c and N s.t.

5n² + 10n ≥ cn² ∀ n ≥ N

take c = 5, N = 1

5n² + 10n ≥ 5n² ∀ n ≥ 1

=> f(n) = Θ (n²)

##Algorithms with Numbers

Much of cryptography relies on the fact that certain problems are easy, while other problems are hard.

Two problems:

factoring: Given N, express it as a product of prime factors. primality: Given N, determine whether or not it is prime.

Factoring is hard: The fastest algorithm is exponential in the # of bits in N Primality is easy: It can be performed efficiently.

##Addition

Two numbers x and y are in binary:

11001 (25) + 01110 (16) = 100111 (41)

Two n-bit numbers can be added in O(n) time.

##Multiplication

12 * 10 = 120

Consider the following rule:

x * y =

• 2( x * ⌊ y / 2 ⌋ ) if y is even
• x + 2( x * ⌊ y / 2 ⌋ ) if y is odd

e.g.

12 * 8 = 2 * 12 * ⌊ 8 / 2 ⌋ = 2 * 12 * 4

12 * 9 = 12 + 2 * 12 * ⌊ 9 / 2 ⌋ = 12 + 2 * 12 * 4

function multiply (x,y) {
  if (y = 0) return 0
  
  z = multiply( x, floor( y / 2 ) )
  
  if (y is even):
    return 2z
  else
    return x + 2z

Run-time:

• first, in each call y is divided by 2: ⌊ y / 2 ⌋ has 1 fewer bit than y

=> this implies n recursive calls (since we have n bits) until y = 0

In each recursive call:

• 1 division by 2 (right shift)
• 1 multiplication by 2 (left shift)
• 1 even/odd test (look at last bit to determine whether even or odd)
• we have at most, 1 addition (we saw earlier that addition is O(n))

∴ we have O(n) bit operations/recursion

∴ runtime of O(n²)

Can we do better?

YES - we will see in the divide and conquer algorithm, we can do better.