> For the complete documentation index, see [llms.txt](https://stephanosterburg.gitbook.io/scrapbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://stephanosterburg.gitbook.io/scrapbook/math/algorithms-udacity/social-network.md).

# Social Network

## Eulerian Path <a href="#header-title" id="header-title"></a>

The degree of a node in a graph is the number of edges connected to that node. For more information see <http://en.wikipedia.org/wiki/Degree_(graph_theory)><br>

$$A \longrightarrow B \longrightarrow D \longrightarrow A \longrightarrow C \longrightarrow D$$

$$A & D$$ need to have odd number endings, eg $$C \longrightarrow D$$ starts with 1 but end with 3.

## Need for Math

Theory stuff (Math) helps

1. Formalize what you are doing
2. Analyze correctness
3. Analyze efficiency

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


a = 12
b = 10
print(naive(a, b))
```

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

        y = y << 1  # bit shift to the left
        x = x >> 1  # bit shift to the right
                    # eg 17 >> 1 ==> 8

    return z
```

### Divide and Conquer

```
def rec_russian(a, b):
    if a == 0: return 0
    if a % 2 == 0: return 2 * rec_russian(a/2, b)
    return b + 2 * rec_russian((a-1)/2, b)
```