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
3. LinkedList
4. Trees
5. Priority Queue & Heaps
6. Searching Algorithms
7. Sorting Algorithms

 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. 

No comments :

Post a Comment