Algorithms

Crunching Social Networks

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,…

Class Summary

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.

What Should I Know?

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.

What Will I Learn?

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.

Syllabus

Unit 1: A Social Network Magic Trick

Becoming familiar with algorithm analysis

Unit 2: Growth Rates in Social Networks

Using mathematical tools to analyze how things are connected

Unit 3: Basic Graph Algorithms

Finding the quickest route to Kevin Bacon

Unit 4: It’s Who You Know

Keeping track of your best friends using heaps

Unit 5: Strong and Weak Bonds

Working with social networks with edge weights.

Unit 6: Hardness of Network Problems

Exploring what it means for a social network problem to be harder than other.

Unit 7: Conclusion

Using your knowledge

Course Instructors

Michael Littman is a Professor of Computer Science at Rutgers University and (soon) Brown University. He served as department chair at Rutgers for the past several years and leads a machine-learning research group. Michael's computer science classes on topics such as algorithms, discrete math, and artificial intelligence earned him university-level teaching awards at both Duke and Rutgers. He is a Fellow of the Association for the Advancement of Artificial Intelligence.

On his first day at work, Job boosted office efficiency by 100% (plus or minus) by writing scripts to automate some of the more mundane tasks that the TAs are required to do. When he's not working, you can find Job upside-down in a mound of powder, his skis probably lost hundreds of feet up the mountain.