## Thursday, December 18, 2014

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