🌱 Udacity - algorithms

Algorithms

Lesson 1

Eulerian path

Need for math

Theory stuff

formalize what you are doing
analyze correctness
analyze efficiency

def naive(a, b):
    x = a
    y = b
    z = 0
    while x > 0:
        z = z + y
        x = x - 1
    return z

Correctness

ab = xy + z z=ab

Running Time

As n grows time grows linearly.

naive(10,3)

round	x	y	z
1	10	3	0
2	9	3	3
3	8	3	6
4	7	3	9
5	6	3	12
6	5	3	15
7	4	3	18
8	3	3	21
9	2	3	24
10	1	3	27
11	0	3	30

10 additions 11 cycles

Russian Peasant Algorithm (Ancient Egyptian Multiplication)

def russian(a,b):
    x = a; y = b
    z =0
    while x > 0:
        if x % 2 == 1: z = z + y
        y = y << 1
        x = x >> 1
    return z

bit shift : move all binary bits; could be left or right

bit shift 17 >> 1

17 in binary 0b10001 bit shift 0b1000

Running time

russian(10,3)

round	x	y	z
1	10	3	0
2	5	6	0
3	2	12	6
4	1	24	30
5	0	48	30

2 additions 5 cycles

Simplifying assumptions

Simple statement takes unit time x = x + 1
Sequence of simple statement s is the sum of them of the individual statements if y = 4 : z = z / 2
Loop takes time equal to the body x iterations for i in range (4):

Ho many time scan you divid a number `x` in half (rounding down) before it hits zero?

x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 16 |
- | - | - | - | - | - | - | - | - | - | - | -- | -- | -- |
# of halfings | 0 | 1 | 2 | 2 | 3 | 3 | 3 | 3 | 4 | 4 | 4  | 4  | 5  |

log₂ x + 1

Divide and Conquer

Break a problem into roughly equal sized subproblems
Solve separately
Combine results

Recursive Russian

# Russian, expressed recursively (divide and conquer)
def rec_russian(a,b):
    if a == 0:
        return 0
    if a % 2 == 0: # if even
        return 2*rec_russian(a/2, b)
    return b + 2*rec_russian((a-1)/2, b) # if odd

Recurrence Relation

T(a) : 1 : 3 + T(a/2) : 3 + T((a/2)/2)

https://classroom.udacity.com/courses/cs215/lessons/48680773/concepts/486986720923

Lesson 2

Overview

Tools to analyze growth rate

Big Theta Big Oh

Graph (a.k.a Network) is a discrete structure mad of nodes (vertices) and edges (links)

Chain Network

essentially a line, direct chain, grandpa->dad->son

n = 5 (nodes) m = 4 (edges)

m = n - 1

Ring Network

Loop at the end of a chain network

n = 5 m = 5

https://classroom.udacity.com/courses/cs215/lessons/48369875/concepts/487430030923

Grid Network

n = 20 m = 31

m = 2n - 2(√n)

Big OH - Asymptotic growth

O(g(n)) : the set of functions that grow equally quickly as g(n)

ϵ : is in

f(n)ϵO(g(n)) : iff C_{1<_sub>, C_{2<_sub>, N_{0<_sub>; any value of N_{0<_sub>, 0<= C_{1<_sub>, g(n) <= f(n) <= C_{2<_sub> g(n)}}}}}}

N_{0
: some threshold}

Θ : big theta

ω : little omega

Ω : omega

2n-2√nϵO(n)

https://classroom.udacity.com/courses/cs215/lessons/48369875/concepts/487273400923

Other Functions

f(n)ϵ o(g(n)) => f(n)<g(n) : f(n) grows less slowly than g(n)

f(n)ϵ O(g(n)) => f(n)<=g(n) : f(n) might grow as fast but could be smaller than g(n)

f(n)ϵ Θ(g(n)) => f(n)=g(n) : f(n) growth is equal g(n)

f(n) Ω(g(n)) => f(n)>=g(n) : f(n) could grow faster or equal to g(n)

f(n)ϵ ω(g(n)) => f(n)>g(n) : f(n) grows faster than g(n)

Θ : big theta - asymptotic notation growth rate

Planar Graph

Edges don’t cross

Regions inside and outside the graph.

n = 5 m = 5 <= 9 r = 3

Euler’s Formula for planar graph relationship : n - m + r = 2

n = 10
m = 15
r = ?
n - m + r = 2
r = 2 -  n + m
r = 7

Growth rate of planar graph

regions must be bounded by 3 edges & can be counted 2x (once for each region it is part of) : 3r <= 2m : r <= (2/3)m

m + 2 = n + r <= n + (2/3)m 3m + 6 <= 3n + 2m m + 6 <= 3n m <= 3n - 6 ϵ Θ(n)

linear growth rate

Recap

Graph types: : chain : ring : grid : planar

m ϵ Θ(n) : edges grow linearly with the number of nodes

Complete graph, clique n nodes

n = 5 m = 10

m = (n * (n-1)) / 2

https://classroom.udacity.com/courses/cs215/lessons/48369875/concepts/486468070923

Quadratic growth rate

Hypercube

n: power of 2

every nod has a label and every label is a bit pattern

Tree graph

is connected
doesn’t have any cycles or loop

Randomly generated Graphs

Eros Renyi Model

n = nodes p = connectivity probability

Generate n nodes
For each node pair i,j connect i,j with probability p

Recursive Graphs

n nodes
create graph on n/2 nodes
create graph on other n/2 nodes
generate edges between the 2 smaller graphs

Recurrence Relations

T = # of edges

T(1) = 0 T(n) = 2T(n/2) + 1

depth level = log(n) edges = Θn(log(n))

Problem set 2 Question 2

https://discussions.udacity.com/t/problem-set-2-question-2/32649

T(n) = 2T(n/2) + Θ(log(n)) T(n) = 2T(1/2)(n) + Θ(log(n)) T(n) = Θ(n) + Θ(log(n)) T(n) = Θ(nlog(n))

https://classroom.udacity.com/courses/cs215/lessons/48698673/concepts/487491070923

Used Grapher.app to chart Quiz Function Comparison after 2 days of trying.

Useful help

https://discussions.udacity.com/t/problem-set-2-combination-lock-which-one-is-correct/43652

https://www.youtube.com/watch?v=yisN77RMAAA

Erdos Renyi n(n-1)*2 *p

algorithms