I just finished Week 1 of an online course on Algorithms in Coursera. In this course, around 2 hours long videos are published in each week, on Fridays. Lectures are split into smaller videos of 10-15 minutes in length and each of them contains one or two quizzes. Also for each week, one programming assignment and several exercises are published which have to be submitted before a deadline and will be graded automatically.
The video lectures are very simple and easy to follow and Professor Robert Sedgewick of Princeton University does an awesome job of explaining the fundamental concepts of Algorithms in a simple and effective manner. Robert Sedgewick is the co-author of “Algorithms” – one of the most popular books on Algorithm.
In the past, I have used various algorithms like quick sort and binary search and other data structures such as Queues and Stacks from Java’s collection library, but this course offers an excellent opportunity to understand the various implementation details of those fundamental algorithms and also to make use of this understanding and knowledge to make more informed decision when choosing algorithms and data structures in the future.
In the first week, the focus is on “Union-Find” and “Analysis of Algorithms”. In the first part called “Union-Find”, dynamic connectivity problem which has wide range of applications in areas ranging from social-network graph to electrical conductivity of a material is explained. How to find whether two elements in a set are connected and also how to connect two elements in a set using different approaches are explained using simple examples.
In the second part called “Analysis of Algorithm”, the reasons to analyze algorithms is explained. The primary practical reason to analyze algorithm is to avoid performance bugs, ie, when a programmer’s lack of understanding about performance characteristics resulted in a poor performance for the client of the application. A scientific method to study and compare the performance of algorithms as proposed by the legendary computer scientist Donald Knuth is also briefly explained. Later on, a structured way to understand and hypothesize about the “Order of growth” of an algorithm is presented.
The programming exercise for the week involved finding the percolation threshold for an N x N grid using Monte Carlo simulation. The program had to be written in Java and a utility class with the implementation of weighted quick find was already provided.