Intro

Udacity: Intro to Algorithms

with  Michael Littman
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.

Why Take This Course?
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

### 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
6 Student
reviews
Cost Free Online Course
Pace Self Paced
Provider Udacity
Language English
Hours 6 hours a week
Calendar 16 weeks long

Disclosure: To support our site, Class Central may be compensated by some course providers.

FAQ View All
What are MOOCs?
MOOCs stand for Massive Open Online Courses. These are free online courses from universities around the world (eg. Stanford Harvard MIT) offered to anyone with an internet connection.
How do I register?
To register for a course, click on "Go to Class" button on the course page. This will take you to the providers website where you can register for the course.
How do these MOOCs or free online courses work?
MOOCs are designed for an online audience, teaching primarily through short (5-20 min.) pre recorded video lectures, that you watch on weekly schedule when convenient for you.  They also have student discussion forums, homework/assignments, and online quizzes or exams.

Reviews for Udacity's Intro to Algorithms 2.7 Based on 6 reviews

• 5 stars 33%
• 4 star 0%
• 3 star 0%
• 2 stars 33%
• 1 stars 33%

Did you take this course? Share your experience with other students.

• 1
2.0 10 months ago
partially completed this course.
What math you need is not clear. High-school algebra at least. However the pace, poor explanations, ambiguous code requirements, and a total lack of support makes this course incredibly difficult if you have no experience with algorithms at all. It really feels like an algorithms refresher course. This is not a good course for beginners.
2.0 10 months ago
is taking this course right now.
Not much of an intro - he goes way too fast & you need a LOT MORE than high school algebra for this!
5.0 2 years ago
by partially completed this course.
0 person found
5.0 10 months ago
by completed this course.
1.0 3 years ago
by dropped this course.
1 person found