Udacity CS215 : Introduction to Algorithms

For the past two months, I was learning Data structures and Algorithms. I'm almost at end of my learning process.

Topics, which I completed till date (Dec 17,2014).

1. Arrays

2. String

3. LinkedList

4. Trees

5. Priority Queue & Heaps

6. Searching Algorithms

7. Sorting Algorithms

8.Recursion

 Still I have to complete Graphs part. After doing a lot of research, I found that Udacity's 215 (Intro to Algorithms)  is one of the best resource to learn Graph Algorithms.

Topics covered in this course :

Lesson 1: A Social Network Magic Trick

• 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

• 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

• 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

• 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

• 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

• 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

Objective: Become familiar with Algorithm Analysis.

Objective: Use mathematical tools to analyze how things are connected.

Objective: Find the quickest route to Kevin Bacon.

Objective: Learn to keep track of your Best Friends using heaps.

Objective: Work with Social Networks that have edge weights.

Objective: Explore what it means for a Social Network problem to be "harder" than other.

• 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

Today I've completed Lesson 1. I took 3 hours for course content and 1 hour for solving the practice question. This course is pretty neat. I learned about Eulerian Path, Naive approach for multiplication, Russian approach for multiplication, Eulerian tour, correctness and time complexity analysis. 

The Instructor uses python language for solving problems. Since I took Programming foundations with Python course, its some what easy for me to understand and go through the code. I feel I'm comfortable with Java than Python, So I solved the problem sets in Java. 

I've posted the solutions here.