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
- 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
- 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
- Degree Centrality
- Top K Via Partitioning
- Three Partitioning Cases
- Properties of a Heap
- Patch Up a Heap
- Down Heapify
- Heap Sort
- 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
- 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
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