Udacity CS215: Algorithms

Crunching Social Networks
Instructor: Michael Littman, Brown University
Zeitraum: Oktober 2012
Status: habe ich gemacht, inkl. Exams und Zertifikat

Anmerkung: Fand ich ganz nett.

Course Syllabus

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
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.

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