- All DegreesExplore Bachelor’s & Master’s degrees
- BusinessExplore MBA & Business degrees
- Computer Science & EngineeringExplore Computer Science & Engineering degrees
- Data ScienceExplore Data Science degrees
- MasterTrack™Earn credit towards a Master’s degree
- University CertificatesAdvance your career with graduate-level learning

Back to Divide and Conquer, Sorting and Searching, and Randomized Algorithms

stars

5,036 ratings

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)....

KS

Sep 13, 2018

Well researched. Topics covered well, with walkthrough for exam.le cases for each new introduced algorithm. Great experience, learned a lot of important algorithms and algorithmic thinking practices.

DT

May 26, 2020

Thank you for teaching me this course. I learned a lot of new things, including Divide-and-Conquer, MergeSort, QuickSort, and Randomization Algorithms, along with proof for their asymptotic runtime

Filter by:

By Lucas P F

•May 12, 2021

Hard, as expected, yet challenging and with a good teacher, made me feel like a student again. Sometimes the background in statistics and probability played against me. It should be recommended to have some background on those subjects before starting the course

By Parsa N

•Apr 29, 2020

Interesting course and huge amount of knowledge

By Jerry V A

•Apr 30, 2020

i loved it so much

By TAI C W

•Jan 1, 2020

The idea and the content are excellent in terms of mathematic analysis. I would recommend people who want to do software engineering or computer science to pick up this course. However, I couldn't give stars higher than three because the videos aren't cut well; After week 2, a lot of written explanations in the video don't follow the audio; i.e., The teacher speaks faster than his writing. That is extremely confusing, and I have to go back to the lecture and read the subtitles back and forth a lot of times, to fully absorb the ideas. Otherwise, it's an outstanding lesson, and I recommend students to download the optional textbooks to get a better understanding.

By ALI “ H

•Jul 19, 2020

for programming assignment please ask two question for each assignment

for example you ask to count no. of comparison in quicksort contain 10000 distinct integer. I urge mr. professor to provide this question as an example with just 20 integer only along with answer. So that we can check our program answer with this example and after then we will solve it with 10000 integer.

Thanks for this informative explanation and i m happy to learn other part also.

Sorry for my bad english.

I dont know wether my feedback is right or wrong

but Its just a humble request from a student to a teacher

By Asem A

•Oct 10, 2019

the course is great at the level of information , but has some issues:

1 - The sound of videos and instructor is not good.

2 - Some times the lectures were boring and not entertaining at all .

3 - you have to do an extra extra extra work to understand the related materials due to bad illustration during the course .

4 - if your math background is not ok or outdated don't rely on the course materials or the instructor illustration because they are not good

By Mohammadmahdi H

•Dec 17, 2020

The bad handwriting of the instructor is not a trivial issue as he pretends. He also talks very fast that makes it hard for people whose native language is not English to follow.

By Daniel Y

•Nov 7, 2020

This course requires mathematical backgrounds. The professor talks super fast and sometimes he makes you asleep..

By safa k

•Dec 17, 2020

I wish the lecture videos were shorter and clearer

By Ian P

•Jun 27, 2018

He's a personable instructor, but I think there are too few examples, the course is too devoid of interesting history, and the language and assignments can be unnecessarily obtuse. I'll happily work through a challenging course, but it feels like a waste of time if most of your effort is spent translating.

By Abdulmalek A

•Sep 7, 2021

Too theory focused. The instructor focuses too much on maths and not enough on the practicality of algorithms. Even the programming assignments are too basic and uninteresting.

Although I did learn a lot about divide and conquer algorithm analysis and randomized algorithms.

By Joseph A

•Aug 10, 2021

The concepts were not well explained. I had to read other materials and watch some YouTube videos to understand most of them.

By Amir A

•Jun 15, 2020

it can be better if the professor tried to learn more algorithm instead of focus deeply on them

By Farrukh M

•Jan 1, 2019

Very basic. Only good for people without CS degree.

By Deleted A

•Aug 13, 2020

Only for geniuses

By Dhananjay S

•Mar 30, 2021

This is really not so easy course , i understood after completing the course. I am beginner and from beginner's perspective this is really hard course because in assignments i was taking 8 days and in the last assignment (WEEK-4) ,i took whooping 18 days because i didn't had knowledge of data structure which was very much required to do karger min-cut algorithm.But in the end this course is really pushing you to stretch your thinking capabilities and this is really very good because to figure out about something which you don't have any idea is really mind-boggling ,also it's very frustating but after the problem is done we feel like we have won battle and that feeling is invincible.Tim is not really spoon feeder that's why for 9 minutes video i had to give 3 hours ,this happened may be because i am beginner or the course itself is hard.In the end i thank Professor Tim Roughgarden for creating such amazing course which forces people to think for days in order to solve assignments.Thank you Tim once again.

By Nadim H

•Sep 11, 2017

Challenging and highly informative course. Professor Roughgarden has a concise and candid lecturing style that I found easy and pleasant to follow.

Make sure you're comfortable with one programming language, and have some experience in writing programs. There is a lot of math, and while not super advanced, make sure you've brushed up on: logarithmic identities, infinite sums, and counting (permutations and combinations). The course dives into some probability, but Professor Roughgarden will walk you through some optional (and very instructive) review lectures.

I'm looking to finishing the specialization, but I'll take some time off to review my discrete mathematics, and strengthen my programming first. This is my first MOOCS course, and I'm hoping all my future experiences will be as great. I highly recommend the course and Professor Roughgarden's lectures.

By zeinab s

•May 2, 2019

I audited this course and I believe this course is going to help me build my future career. I'm in transition between my original degree (engineering) to computer science, and I want to build a great foundation of my knowledge. For me, with little computer knowledge, this course was great. The syllabus is complete and covers essential material. The instructor explains everything clearly. although he talks a bit fast for me (I'm not native but I'm studying in an english language school).

It is a good combination of the algorithms and the math behind them. not too much math. The homework at the end of each week is also helpful to practice what you learned in videos. (Although I couldn't see the answers)

in Overall, it's a great course, and I recommend it to anyone with a passion for computer science.

By Steve J

•Sep 20, 2018

I found this course to be an ideal mix of abstract theory and practical application. Professor Roughgarden is quite adept at presenting in depth analyses of algorithms in a way that does not shy away from formal mathematics but also does not require a degree in mathematics to understand. For me, whose prior math coursework was mainly focused on areas of math not as prevalent in computer science as other in disciplines (e.g. calculus vs. discrete math), Professor Roughgarden's approach is ideal and opened up the door to a much deeper understanding of algorithms than I've acquired on my own over a multi-decade career in programming.

Highly recommend this course for anyone who, like me, has a lot of experience with programming, but no formal training on algorithms.

By Cliff C

•Nov 25, 2017

Loved the clarity and enthusiasm. The proofs and algorithm implementations shared in this class are often simpler and more elegant than the proofs and implementations I've found in other textbooks.

Just a few examples: 1. The proof of Quicksort's expected comparisons count was great. The course used a beautiful, simple proof summing the values of indicator variables whereas other proofs I've seen use a messy inductive approach. 2. The implementation of partition was much simpler than most other partition implementations I've seen, which tend to walk from the left and right swapping items.

The simplicity of the proofs and algorithm implementations make the material more beautiful. Thank you!

By Yazeed A

•May 27, 2021

The course content and explanations are fantastic. The instructor has a nice intuitive lecturing style. However, it is relatively difficult compared to other Coursera courses, especially the optional exercises (which I think is a plus). My only issue with the course is the programing assignments. They are good practice for the material. However, other Coursera courses have better integrated assignments. Perhaps the current design is a necessary evil if they wish to keep the course accessible to all programing languages. I'm currently using Python. However, I feel like I should be using a lower level language like C, especially on an optimization focused course like this.

By Kalema A B

•Jul 11, 2020

This was my first time diving into algorithms, it was indeed challenging as my math skills had been long kept in the dark since my Computer Eng. Diploma, it sent me doing research that in turn expanded my understanding of the concepts, I almost felt frustrated especially with the analysis videos, probability concepts were a challenge and I intend to take a detailed math refresher course as I continue with the remaining courses, hopefully after this I will keep my math alive for life. Thanks for the challenge in this course, it kept me pacing and it was indeed worth it, i hope to research other algorithm in sorting and other concepts discussed here, Thanks.

By Alexander L

•Nov 11, 2019

Very interesting. I learned a lot of new things. 5 stars!

Just a few things that could be improved:

-- The video and its audio are not really synchronized (maybe because the video is pretty old)

-- The Quicksort programming assignment was like: 1 hour to program a working Quicksort + 4 hours figuring out how the course creator wants me to count the compares of it as that's dependent from the implementation.

Nowadays there are better solutions to validate whether someone solved a programming task. geeksforgeeks.org and hackerrank.com for example just execute the program with test input.

But all in all: Very positive experience.

By Angel M P

•Sep 4, 2020

The Course is very challenging and also very rewarding! The professor motivate you showing real applications about the algorithms he talk about. This course review the math analysis of the algorithms and also require that you implement some of these algorithms. The course required me dedicate many hours during week (some weeks more than 15 hours) but each programming assignment done is very rewarding and I could learn better some of these topics which I took last semester at my university. Thanks professor Tim Roughgarden!! and thanks to all the team behind this course!

By francisco i

•Dec 24, 2016

Excellent course. What I valued most about this course was the clarity with which proofs and algorithms are explained. In learning algorithms one really profits from a great professor. Keep in mind that this course involves mathematics for proofs and I believe one has to be really curious about algorithms and dive into proofs to take full advantage of this course. Regarding assignments they are challenging but definitely approachable if you have some experience in programming. My advice: do not get discouraged, this is all about resilience!

- AWS Cloud A Practitioner's Guide
- Basics of Computer Programming with Python
- Beginners Python Programming in IT
- Developing Professional High Fidelity Designs and Prototypes
- Get Google CBRS-CPI Certified
- Introduction to MATLAB Programming
- Learn HTML and CSS for Building Modern Web Pages
- Learn the Basics of Agile with Atlassian JIRA
- Managing IT Infrastructure Services
- Mastering the Fundamentals of IT Support

- Basics of Computer Programming with Python
- Beginners Python Programming in IT
- Building a Modern Computer System from the Ground Up
- Getting Started with Google Cloud Fundamentals
- Introduction to Cryptography
- Introduction to Programming and Web Development
- Introduction to UX Design
- Learn HTML and CSS for Building Modern Web Pages
- Mastering the Fundamentals of IT Support
- Utilizing SLOs & SLIs to Measure Site Reliability

- Building an Agile and Value-Driven Product Backlog
- Foundations of Financial Markets & Behavioral Finance
- Getting Started with Construction Project Management
- Getting Started With Google Sheets
- Introduction to AI for Non-Technical People
- Learn the Basics of SEO and Improve Your Website's Rankings
- Mastering Business Writing
- Mastering the Art of Effective Public Speaking
- Social Media Content Creation & Management
- Understanding Financial Statements & Disclosures