Intro

In the previous post I have described the second week of "Data Structures and Algorithms" course on Coursera. In this post I am going to cover the third week of that course.

What's has been covered

During the third week authors covered greedy algorithms, it is a very straight-forward way of solving a certain class of problems. I am not going to describe it here, just keep in mind that it is one of the most basic technic of solving algorithmic problems. The most important thing to remember is that it is important to prove that a greedy algorithm always produces an optimal solution before using this algorithm.

Authors described common algorithmic problems with the following examples:

  • Given a few digits, arrange them in the largest possible
  • Find the minimum number of refuels during a long journey by car
  • Partition a number of children into groups according to their age
  • Knapsack problem
  • ... and some more ...

Programming assignment consists of the following problems:

  • Changing Money - implement an algorithm to find the minimum number of coins needed to change the input value
  • Maximizing the Value - implement an algorithm to find the most valuable combination of items
  • Maximizing Revenue in Online Ad Placement - implement an algorithm to distribute the ads among the slots to maximize the total revenue
  • Collecting Signatures - you are given a set of segments on a line and your goal is to mark as few points on a line as possible so that each segment contains at least one marked point
  • Maximizing the Number of Prize Places in a Competition - implement an algorithm to represent a given positive integer 𝑛 as a sum of as many pairwise distinct positive integers as possible.
  • Maximizing Your Salary - tweek the algo from lection to work with two-digit numbers.

Summary

In this post I have covered the third week of "Data Structures and Algorithms" course on Coursera. It was more challenging than the previous one, but I didn't have any problems solving the assignment, in fact, all the problems were complex enough to make you think for 10-15 minutes before you understand how to efficiently solve it. In the next post I will cover the fourth week of this course.


;