Ever played the Kevin Bacon game? This class will show you how it works by giving you an introduction to the design and analysis of algorithms, enabling you to discover how individuals are connected.

By the end of this class you will understand key concepts needed to devise new algorithms for graphs and other important data structures and to evaluate the efficiency of these algorithms.

This class assumes an understanding of programming at the level of CS101, including the ability to read and write short programs in Python; it also assumes a comfort level with mathematical notation at the level of high school Algebra II or the SATs.

See the Technology Requirements for using Udacity.

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

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

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

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

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

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

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

Michael Littman is a Professor of Computer Science at Brown University. He also teaches Udacity’s Algorithms course (CS215) on crunching social networks. Prior to joining Brown in 2012, he led the Rutgers Laboratory for Real-Life Reinforcement Learning (RL3) at Rutgers, where he served as the Computer Science Department Chair from 2009-2012. He is a Fellow of the Association for the Advancement of Artificial Intelligence (AAAI), served as program chair for AAAI's 2013 conference and the International Conference on Machine Learning in 2009, and received university-level teaching awards at both Duke and Rutgers. Charles Isbell taught him about racquetball, weight-lifting and Ultimate Frisbee, but he's not that great at any of them. He's pretty good at singing and juggling, though.

View more courses in

Software Engineering

This class is self paced. You can begin whenever you like and then follow your own pace. It’s a good idea to set goals for yourself to make sure you stick with the course.

This class will always be available!

Yes! The point is for you to learn what YOU need (or want) to learn. If you already know something, feel free to skip ahead. If you ever find that you’re confused, you can always go back and watch something that you skipped.

Collaboration is a great way to learn. You should do it! The key is to use collaboration as a way to enhance learning, not as a way of sharing answers without understanding them.

Udacity classes are a little different from traditional courses. We intersperse our video segments with interactive questions. There are many reasons for including these questions: to get you thinking, to check your understanding, for fun, etc... But really, they are there to help you learn. They are NOT there to evaluate your intelligence, so try not to let them stress you out.

Learn actively! You will retain more of what you learn if you take notes, draw diagrams, make notecards, and actively try to make sense of the material.