Algorithms Specialization Notes

I have finished three first algorithm courses in this specialization on Coursera. My main motivation was to fill up my foundational knowledge of computer science. Generally, I enjoyed all courses and their videos though sometimes I could only capture concepts and ideas behind all proofs. However, I am sure that I understand the motivations and steps to practice all algorithms, and translate them into real code.

Course 1 – Divide and Conquer, Sorting and Searching, and Randomized Algorithms

This course made me feel like getting back to the time when I was in the sixth grade. By that time, we “played” games with Arithmetic, Least Common Divisor, Least Common Divisor, etc. I know some methods to approach a specific problem but there is no exact way to solve it… and you need to be creative for each problem. When it comes to algorithms, it’s not just about “solutions” anymore, it’s more about “solutions and efficiency”.

This course covers the big-O notation and asymptotic analysis in every detail. I had heard about this term many times but I did not understand it all until I learned this course.

The algorithm steps are easy to understand however understanding all maths for proofs is challenging.

Course 2 – Graph Search, Shortest Paths, and Data Structures

Course 1 is more like an introduction to the world of algorithms, then Course 2 is much more interesting.

Course 2 digs into graph problems, which are very new to me such as: breadth-first and depth-first search, computing strong components, Dijkstra’s shortest-path algorithms. However, the important thing is that I can feel their implementations in many common apps such as Google Maps, search engine sorting pages, etc.

And then data structures are more clear why we need to make decisions based on what operations we need for data and how we can arrange them to get most of their structure. For example, a hashtable is a very efficient data structure to store key-value data and look up values based on keys. Then I found out the array concept in PHP is implemented as with Hashtable:

Course 3 – Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming

As mentioned in the title, this course teaches two other common paradigms: Greedy Algorithms and Dynamic Algorithms. I don’t remember exactly but it looks like I’ve solved/seen similar problems using these two paradigms. In the following, I note some interesting points I have come across.

The course mentions Optimal Caching Problem, “furthest in the future”, LRU (Least Recently Used) that is used in Memcached to improve its speed.

Many companies use Minimum Spanning Tree to solve the vehicle routing problem optimization problem and earn millions $$$:

Binpacking and knapsack are also mentioned in this course. They also interesting problems and merchants, logistic and warehouse companies are eager to have solutions too:

Summary

I am excited to learn these courses. They give more insights into how each primitive function works and makes itself fast. I also have more ideas and tools when dealing with complex problems, especially with big datasets or resource constraints.

I will spend time to finish the last one in this specialization: Shortest Paths Revisited, NP-Complete Problems and What To Do About Them.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s