Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

# Divide and Conquer, Sorting and Searching, and Randomized Algorithms

### Overview

Unlock Unlimited Opportunities: Get 50% Off Your First Month of Coursera Plus
The primary topics in this part of the specialization are: asymptotic ("Big-oh") notation, sorting and searching, divide and conquer (master method, integer and matrix multiplication, closest pair), and randomized algorithms (QuickSort, contraction algorithm for min cuts).

### Syllabus

• Week 1
• Introduction; "big-oh" notation and asymptotic analysis.
• Week 2
• Divide-and-conquer basics; the master method for analyzing divide and conquer algorithms.
• Week 3
• The QuickSort algorithm and its analysis; probability review.
• Week 4
• Linear-time selection; graphs, cuts, and the contraction algorithm.

Tim Roughgarden

## Reviews

4.7 rating, based on 68 Class Central reviews

4.8 rating at Coursera based on 5213 ratings

Start your review of Divide and Conquer, Sorting and Searching, and Randomized Algorithms

• This course helped me get a job. Before doing this course, I had trouble clearing technical interviews. Infact, I couldn't even clear the phone interviews. "Algorithms: Design and Analysis, Part 1" was instrumental in clearing my first technical intâ€¦
• I took courses on algorithms and data structures when I went to university, and I really enjoyed both of them. Since then I have been working as a software developer for more than 20 years, so I thought it would be interesting with a refresher. I aâ€¦
• Martin RoÅ¾novjÃ¡k
This was my very first course of algorithms, I had had some experience with programming before. The course was moderately challenging - I would say right at my limits but not overwhelming thus making the most out of its content - I wish I would learâ€¦
• Wei En
Professor Roughgarden has done a great job in explaining the content. I've finally understood what big-O notation, etc. means, after taking this course. The lack of interactive visuals (which I find to be necessary for studying how an algorithm works) may bother you.

The exercises are quite well done and provide a few challenging questions. Additionally, there are theory problems in the course pages which are optional and gets students to think creatively.

In general, this is a great introduction to algorithms, if you're not particularly bothered by the lack of interactive visuals.
• Eli Bendersky
The teacher is pretty good â€“ I actually enjoyed watching the lectures and wasn't bored, which is unusual with me when it comes to lectures. I really liked the "optional" videos (watched them all). Not sure whether they would have been taught in theâ€¦
• Tian Qiu
This a good intro to algorithms course for those who already have some exposure to programming. The aim of the course is to introduce some classic algorithms and show us the toolbox of algorithms design and analysis by giving very detailed analysisâ€¦
• It is one of the must course one should do to achieve expertise in Data Structure and Algorithms. The instructor Tim Roughgarden, one of the best instructor i have ever seen. The methodology and material is awesome. And i will advise to complete all the assignments to get the best of the course.
• square-B
I thought this was a great learning experience. I would certainly recommend Coursera and this class specifically, to anyone. Be prepared as this course will take up A LOT of your time and it can be VERY challenging. Having said that, if you put in the work and tough it out, you will learn a lot. I know I did.
• This is an introductory course on the principles of computational algorithms, but, it's very hard. The related mathematics is challenging and the concepts are difficult to understand. However, the teacher has cleverly cut the materials into small pieces and provide them in a gradual and clear way, so students can master the materials finally if they have taken great efforts to study it.
• Shubham Agarwal
Great course. Worth spending time. Not only videos by Tim are awesome but also the programming assignment and problem sets. If properly and seriously done, can improve your algorithmic skill to a great extent in just one and half month.
• Luiz Cunha
In my top 3 MOOC.
Great content and delivery by Prof. Roughgarden on a rather dry topic.
The videos are great quality.
The assignments are very challenging but interesting.
I just wished this MOOC would be longer
• I took the Algorithms specialization during my winter break of my 2nd year as an Computer Science student in college, after taking introductory data structures + algorithms classes and developing a competitive programming hobby.

Tim Roughgarden is an amazing instructor, and the Algorithms specialization is one of my all-time favorite MOOCs.

• Anna K
This course requires too much time to watch the videos.. Several hours of videos per 1 week, and the lecturer gets repetitive and some information is not necessary.. Sorry, did not fly with me...
• Anonymous
The course is very good, but it is focused on providing proofs of correctness and running time of algorithms, and so it is more theoretical than applied. Still, I learned a lot about algorithms in this course!
• Anonymous
Hard but worth every penny. Got to learn more from this course than every other algorithms courses i've taken. Don't expect to be spoonfed, and expect to do background reading. Wonderful!
• Anonymous
Excellent course, great teacher and challenging assignments fun to do. I definitely enjoyed the course and learned a lot.
• Sai Charan
This course will introduce you to the basic elements of academic information seeking - we will explore the search process from defining a strategy to evaluating and