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

stars

4,536 ratings

•

882 reviews

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 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!

By Ялунин А А

•Mar 8, 2021

A lot of repetitions of the same thing. It seems like one idea could be taught in <3 minutes but instead we recover previous material and repeat the same thing resulting in >10min. Still a great course. Lack of solutions for programming assignment. I spent a day trying to find on web a good implementation of karger's algo for min cut problem and didn't find what I was looking for, they all make same mistakes in implementations like copy the entire graph, sample not uniformly or copy all edges to list from set just to sample one.

By Frank J M

•Feb 25, 2019

lectures were great. Pace was just right. It is great being able to repeat parts of the lecture to improve your understanding. I only wish the Part 1: Basics books covered the week on graphs and the contraction algorithm. The Algorithms Illustrated book was a great companion for the course. Not having a book companion made the graphs and contraction algorithm material a little more difficult.

I like the the lectures are not copies of the book. The flow of topics match, but the explanations in lecture are often different.

By Benoit P

•Dec 29, 2016

This is a great course. The teacher is very clear, and the material is very interesting. The programming assignments are interesting: the problems asked are very simple, but the input is generally too large to use brute force: you really have to implement the algorithms presented in the videos. This makes you realize how much smart algorithms can make a difference.

The level of the class is relatively high, compared to other Coursera courses I've taken. If you want some serious training on algorithms, look no further.

By Jason H

•Jul 29, 2018

This is the place to start upgrading your programming skills to the next level. If you have some prior programming experience solving problems with data, but have never rigorously looked at the efficiency of your algorithm and wondered "Can this be better?" this course is designed for you. You'll learn to think and talk like a software engineer and not just a computer programmer. The course has some very practical problems to solve, which will give you a sense of empowerment to tackle big data sets with ease.

By Rohit S

•Jun 9, 2020

This course was very helpful.

I learned a lot from this course.

I learned why algorithms are important how they help to optimize time and space complexity , moreover I learned how to analyse time and space complexity of any given algorithm.

I learned various sorting algorithms and various other algorithms used for solving problems such as finding number of inversion and finding minimum cut.

This course will not only help me in my academics but also add to my resume, which will help me to get a job.

By Charlie Z

•Jan 28, 2018

Roughgarden creates a great mental model for algorithms. He explains the ideas that connect them and how they are organized. He doesn't waste your time, hitting the key components in both the math proofs and in explaining the algorithm implementation. The way he teaches in like induction; he uses a super simple example (base case) and abstracts that out to get the general case.

After the course, I *get* algorithms now... (instead of memorizing them, I can see how to deduce them). Thank you!

By Mohamad S D

•Jan 12, 2019

I was always looking for a good material to study this complicated topic , and after a lot of purchases and digging , I finally found this course , these sequence of courses will not give you every detail about every algorithm in the universe but it will give you the knowledge that will enable you to walk alone in the street of algorithms . Really great course , I'm still in course no 2 of the 4 courses but i'm very happy of what i've seen so far and looking forward to finish them all isA

By Hrishikesh A

•Dec 14, 2016

Tim gives great insights and draws attention to the right things at right time! Exercise and quizzes are very helpful and makes you think in right direction. Also the in-video-quizzes are well thought of to make you think about the topic being described in the video and thus makes it easy to understand the contents. This is just the right course anyone should take to improve/learn algorithm and data structures course. I've got got aaha! moments multiple times. Can't thank Tim enough!!

By Berk B

•Apr 26, 2017

I had a great time taking this course. It was a very good course in algorithms that explained the core concepts really well rather than just providing a high level overview. The assignments take some time but it aligns with what the instructor is teaching. The instructor is absolutely excellent because he takes the time to go through the math and iterations which helps to develop a deeper intuition for these algorithms. Looking forward to completing his other courses when I got time.

By Manuel V

•Aug 8, 2019

This course immersed me in the fundamentals of one of the most interesting and useful problem solving methods in computer science.

Each problem assignment is so carefully thought out, that it forced me to apply what I learned and constantly ask myself "could I do better?"

Very well combined with historical reviews and mentions of the "protagonist of the week", which enriches the learning and made me get closer to the way of thinking of those who pushed our beloved computer science.

By Haluk

•Mar 8, 2021

I learned more from this course than any other study I have done in 3 years I have been studying programming. Great professor, great content. I advise anyone who is interested in programming to take this course to see how computer scientists think, and how they use math in theoretical sense. Being a math major myself, I immensely enjoyed how the course was structured around proofs and theorems, and at the same time I found it easy to digest.

By Ravi P

•Sep 6, 2020

What a wonderful journey.Tim Roughgarden is one of the best instructor I have ever encountered, this course is very totally worth it and goes very well and indepth, the problem covered and the material discussed were just WOW!.

But I won't suggest this course to any beginner as this course is sort of high-level and also requires you to have a strong fundamental knowledge. Overall best course looking forward to the 2nd course now.

By Yohan S

•Jan 4, 2018

This was perfect introductory class for me to begin my learning on algorithm. As the instructor said at the introduction, many of the algorithms were fun and challenging and the explanation of the instructor was great. Although the fact which the Programming Assignments do not check the actual code but the final output was the only downside of this class, everything else is great for checking one's understanding of the course.

By Sophie Z

•Jun 25, 2017

This course not only taught me some basic concepts of algorithm but also taught me how to analyse the underneath disciplines as well as how to manipulate them. The analysis using probability seems complicated at first, however, the instructor managed to illustrate it in an easy way. I especially love the assignments, they are very enlightening. The test cases in the forum is also of great help in my debugging process.

By Ethan h

•Dec 11, 2017

I would probably still be fascinated by algorithms without the enthusiasm of these lectures, but it certainly helps. The discussion forums don't seem to be too busy these days, but enough people have taken this course over the years that I'm sure any stumbling blocks along the way have already been navigated somewhere in the archives. Anyone who enjoys puzzle-solving and analysis should appreciate this course.

By Ellen Y

•May 6, 2017

The instructor speaks very clearly and describes everything in a good amount of detail. There were quizzes throughout lectures that keep you engaged and test your understanding, and I liked that I could use the problem sets as a way to practice since there's no penalty for multiple tries. I really enjoyed the course and would highly recommend it to anyone looking for a solid understanding of algorithms.

- Google Data Analyst
- Google Project Management
- Google UX Design
- Google IT Support
- IBM Data Science
- IBM Data Analyst
- IBM Data Analytics with Excel and R
- IBM Cybersecurity Analyst
- Facebook Social Media Marketing
- IBM Full Stack Cloud Developer
- Salesforce Sales Development Representative
- Salesforce Sales Operations
- Soporte de Tecnologías de la Información de Google
- Certificado profesional de Suporte em TI do Google
- Google IT Automation with Python
- DeepLearning.AI Tensorflow
- Popular Cybersecurity Certifications
- Popular SQL Certifications
- Popular IT Certifications
- See all certificates

- Skills for Data Science Teams
- Data Driven Decision Making
- Software Engineering Skills
- Soft Skills for Engineering Teams
- Management Skills
- Marketing Skills
- Skills for Sales Teams
- Product Manager Skills
- Skills for Finance
- Android Development Projects
- TensorFlow and Keras Projects
- Python for Everybody
- Deep Learning
- Excel Skills for Business
- Business Foundations
- Machine Learning
- AWS Fundamentals
- Data Engineering Foundations
- Data Analyst Skills
- Skills for UX Designers

- MasterTrack® Certificates
- Professional Certificates
- University Certificates
- MBA & Business Degrees
- Data Science Degrees
- Computer Science Degrees
- Data Analytics Degrees
- Public Health Degrees
- Social Sciences Degrees
- Management Degrees
- Degrees from Top European Universities
- Master's Degrees
- Bachelor's Degrees
- Degrees with a Performance Pathway
- Bsc Courses
- What is a Bachelor's Degree?
- How Long Does a Master's Degree Take?
- Is an Online MBA Worth It?
- 7 Ways to Pay for Graduate School
- See all degrees