Intro to Algorithms

Lesson 1: A Social Network Magic Trick

Objective: Become familiar with Algorithm Analysis.

• Eulerian Path
• Correctness of Naïve
• Russian Peasants Algorithm
• Measuring Time
• Steps for Naive, Steps for Russian
• Divide and Conquer

Lesson 2: Growth Rates in Social Networks

Objective: Use mathematical tools to analyze how things are connected.

• Chain, Ring and Grid Networks
• Big Theta
• Planar Graphs
• Nodes, Edges, Regions
• Growth Rate of Edges in Planar Graph
• Hypercube
• Randomly Generated Graphs
• N Squared
• Tangled Hypercube

Lesson 3: Basic Graph Algorithms

Objective: Find the quickest route to Kevin Bacon.

• Properties of Social Networks
• Clustering Coefficient
• Connected Components
• Running Time of Connected Components
• Checking Pairwise Connectivity
• Pairwise Shortest Path
• Depth vs. Breadth First Search
• Recursion Replacement
• Marvel "Social" Network
• Finding Bridge Edges

Lesson 4: It’s Who You Know

Objective: Learn to keep track of your Best Friends using heaps.

• Degree Centrality
• Top K Via Partitioning
• Three Partitioning Cases
• Properties of a Heap
• Patch Up a Heap
• Down Heapify
• Heap Sort

Lesson 5: Strong and Weak Bonds

Objective: Work with Social Networks that have edge weights.

• Make a Tree
• Strength of Connections
• Weighted Social Networks
• How to Find the Shortest Path
• Dijkstra’s Shortest Path Algorithm
• Floyd-Warshall Intro
• Randomizing Clustering Coefficient
• Bounds on the Estimate

Lesson 6: Hardness of Network Problems

Objective: Explore what it means for a Social Network problem to be
"harder" than other.

• Tetristan
• Exponential Running Time
• Degrees of Hardness
• Reduction: Long and Simple Path
• Polynomial Time Decidable Problems
• Non-deterministic Polynomial Time Decidable Problem
• Clique Problem in NP
• Find the Strangers
• Graph Coloring is NP-Complete

Lesson 7: Review and Application

• Interview with Peter Winker (Professor, Dartmouth College) on Names and Boxes Problem && Puzzles and Algorithms

• Interview with Tina Eliassi-Rad (Professor, Rutgers University) on
  Statistical Measures in Network && Social Networks in Security and Protests

• Interview with Andrew Goldberg (Principal Researcher, Microsoft Research) on Practical Algorithms

• Interview with Vukosi Marivate (Graduate Student, Rutgers University) on Social Algorithms

• Interview with Duncan Watts (Principal Researcher, Microsoft) on Pathway That Can Use Two Nodes

• Intro to Graph Search Animation