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