Intro

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

What's has been covered

During this weeek authors covered the divide and conquer algorithms. This approach is used in such algorithms as Merge Sort and Binary Search.

The following problems has been covered in lectures:

  • Linear Search
  • Binary Search
  • Polynomial Multiplication
  • Master Theorem
  • Selection Sort
  • Merge Sort
  • Quick Sort
  • Randomized Quick Sort
  • Randomized Quick Sort with partitioning into three segments

Programming assignment consists of the following problems:

  • Implementing Binary Search - just implement binary search
  • Finding Majority Element - I didn't manage to solve this using divide and conquer, I used Boyer–Moore majority vote algorithm
  • Improving Quick Sort - change standard implementation of quick sort to work faster with arrays full of equal elements
  • How Close a Data is To Being Sorted? - find the number of inversions in array, a challenging one.
  • Organizing a Lottery - strange problem.
  • Finding the Closest Pair of Points - classic problem.

Summary

In this post I have covered the fourth week of "Data Structures and Algorithms" course on Coursera. I didn't know about the quick sort with three partitions, which works much faster under certain conditions. I didn't manage to find a majority element using divide and conquer, so I used a better and faster algo to solve this problem. In the next post I will cover the fifth week of this course.


;