DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
  1. DZone
  2. Data Engineering
  3. AI/ML
  4. Algorithm of the Week: A Look At Coursera's Design and Analysis of Algorithms: Part I

Algorithm of the Week: A Look At Coursera's Design and Analysis of Algorithms: Part I

Henrik Warne user avatar by
Henrik Warne
·
Mar. 05, 13 · Interview
Like (0)
Save
Tweet
Share
9.54K Views

Join the DZone community and get the full member experience.

Join For Free
Last year I finished the Coursera course Design and Analysis of Algorithms I, given by Professor Tim Roughgarden of Stanford. This was my second on-line course from Coursera (last fall I took Introduction to Databases, which I wrote about here), and I thought it would be interesting to compare  the two.

When I went to university (M.Sc. in Computer Science and Engineering), I took both an algorithm course and a data structures course, so a lot of the material in this course wasn’t new to me. However, that was over 20 years ago, so I thought it would be good with a refresher course. There were also several topics that were new to me, in particular some of the graph algorithms (case in point: Karger’s min-cut algorithm presented in the course had not been invented when I went to university).

The course lasted 5 weeks and consisted of video lectures, multiple-choice quizzes and programming problems. The topics covered were:

  • Merge sort
  • Big-O Notation
  • Algorithm for counting inversions
  • Strassen’s sub-cubic matrix multiplicaiton
  • The Master Method
  • Quicksort
  • Randomized selection
  • Graphs and minimum cuts
  • Graph search – Breadth first and Depth first
  • Topological sort
  • Graphs – Strogly connected components
  • Dijkstra’s shortest-path algorithm
  • Data structures: heaps
  • Data structures: hash tables

VIDEO LECTURES

The video lectures (about 2 hours per week) were very good and easy to follow, and Professor Roughgarden is quite good at explaining the different concepts and algorithms. My only wish is that I had the option of reading the material (as presented in a text book) instead of watching it. The slides used in the videos are available for download, but they don’t have enough information to be read on their own.

For me it is faster to read than to listen to someone explaining something, it is easier to skim things I already know, and it is easier to go back and forth in a text when something isn’t clear. Also, I like the visual structure of the material on the pages – something I don’t get from a video. But the main reasons is that it would be faster. Taking the course is quite a big time commitment, especially when you work full time and have a family, and if things can be sped up it’s a big plus.

This is a of course a matter of personal taste, and I suspect many people prefer having the material presented in a lecture format. Also, it is possible to speed up the videos (1.25 or 1.5 times the normal speed), which I did make use of sometimes. But for me it still does not beat reading from a book.

The topics I already knew quite well were merge sort, big-O notation, quicksort, and hash tables (in particular hash tables – I use them almost daily when coding). I thought all of these topics were well presented.

I had never heard about the Master Method before, but found both the formula (for finding the big-O performance of recursive algorithms) and the derivation of it quite interesting. I also liked the graph algorithms, in particular the algorithm for finding strongly connected components in a directed graph (the algorithm uses the neat trick of reversing all the edges as one of its steps). The lecture on heaps was interesting – I studied heaps in my class at university, but I had completely forgotten about them. So there it really was a case of  needing a refresher (and heap sort now makes total sense too).

Quizzes

There were  5 multiple-choice quizzes, with 26 questions in total, and you were only allowed 2 tries per quiz (your best attempt counts towards your total score). This is in contrast to the quizzes in the database course, where you basically had unlimited attempts (the limit was set to 100). However, the database quizzes had many wrong answers, and often several correct answers, and for each new attempt, the answer options were randomly generated (and shuffled). Thus, even though you had seen the question before, you still had to work it through (you couldn’t just rely on remembering the correct answer from a previous attempt).

The questions were quite challenging, and even though I got them all correct in the end, I used my two attempts on all of them. When comparing the two approaches, I actually prefer the database course way with unlimited attempts. Then you are motivated to keep trying, even if you don’t get them all right on the first two tries.

Programming Assignments

There were also 5 programming assignments, and they were all great for really understanding the different algorithms. You could use any language you wanted (I used Java).

The first one dealt with inversions in an integer array. An inversion is a pair of two array indices, i and j with i<j, such that the value in the array at position i is greater than the value in the array at position j. If the array is sorted there are no inversions, and for all other cases there is at least one inversion. The problem consisted of an array of size 100,000, with all the numbers from 1 to 100,000 appearing exactly once, and the program had to calculate how many inversions the given array contained. This problem could be solved with an algorithm closely related to merge sort.

For the second programming problem, you had to implement quicksort, and use it to sort an integer array of size 10,000. You had to answer how many comparisons were used when sorting the array. The number of comparisons depends on the pivot elements used, and there were 3 cases to investigate: using the first element of the sub-array as the pivot, using the last element of the sub-array as the pivot, and using the median of the first, last and middle element of the sub-array as the pivot. Not surprisingly, using the median element resulted in the fewest number of comparisons.

In the third problem, you implemented the randomized contraction algorithm to find the minimum cut of a 40-node undirected graph. This was an interesting problem where you had to implement “folding” of two nodes into one, and handle the resulting change in edge structure. Unfortunately, unlike the previous two problems, the range of possible answers was very low, so it was possible to guess the answer (since 8 attempts were allowed).

The fourth programming problem was by far the most difficult problem, judging from the  discussions in the forum. You had to find the sizes of the five largest strongly connected components of a directed graph consisting of almost one million nodes. A strongly connected component is a group of nodes where there is a path from each node in the component to all the other nodes in that component. It has a nice recursive solution, but a lot of people had all sorts of problems due to the size of the graph, both speed problems and stack overflows.

The last programming assignment made use of a hash table (which you didn’t have to implemet yourself) to see if 9 given target sums could be found by adding two numbers from a list of 100,000 integers. Quite a neat use of a hash table, and also the easiest of the five programming problems.

Conclusion

As with the database course, this course consisted of three components: video lectures, multiple-choice quizzes and programming assignments. It’s a good model that makes sure you learn the material well, and it was really well done in both courses. Another aspect of these on-line courses is that they follow a schedule – new videos are added each week, and quizzes and assignments are due each week. That system works really well to keep you going. The main difference in the courses was the length – the algorithm course was considerably shorter. For me, that was actually better, because you need to put in quite a few hours of work each week, and a shorter course is more managable. Part two of the  course will apparently be offered in the fall of 2012.

Even though the course required quite a bit of work, I didn’t find it particularly difficult (I ended up getting full marks on it) – mostly because the teaching and exercises are first rate. I learned a lot, both from this course and from the database course, and I highly recommend both of them.

Algorithm Database Design Merge sort Data structure

Published at DZone with permission of Henrik Warne, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • A Real-Time Supply Chain Control Tower Powered by Kafka
  • Why Does DevOps Recommend Shift-Left Testing Principles?
  • Choosing the Best Cloud Provider for Hosting DevOps Tools
  • Using JSON Web Encryption (JWE)

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends: