Explore

Divide and Conquer, Sorting and Searching, and Randomized Algorithms

Approx. 17 hours to complete

Save Course

Go to Course

Course Summary

This course teaches the Divide and Conquer algorithmic paradigm for solving problems. It covers various algorithms such as merge sort, quicksort, and binary search.

Key Learning Points

Learn how to apply the Divide and Conquer algorithmic paradigm
Understand various algorithms such as merge sort, quicksort, and binary search
Develop problem-solving skills

Learning Outcomes

Ability to apply Divide and Conquer algorithmic paradigm
Proficiency in various sorting algorithms
Enhanced problem-solving skills

Prerequisites or good to have knowledge before taking this course

Basic programming knowledge
Familiarity with data structures

Course Difficulty Level

Intermediate

Course Format

Online self-paced
Video lectures
Assignments

Similar Courses

Algorithms, Part I
Algorithms, Part II
Data Structures and Algorithms Specialization

Related Education Paths

Notable People in This Field

Donald Knuth
Clifford Stein
Jon Bentley

Related Books

Description

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

Outline

Week 1
Why Study Algorithms?
Integer Multiplication
Karatsuba Multiplication
About the Course
Merge Sort: Motivation and Example
Merge Sort: Pseudocode
Merge Sort: Analysis
Guiding Principles for Analysis of Algorithms
The Gist
Big-Oh Notation
Basic Examples
Big Omega and Theta
Additional Examples [Review - Optional]
Welcome and Week 1 Overview
Overview, Resources, and Policies
Lecture slides
Problem Set #1
Programming Assignment #1

Week 2
O(n log n) Algorithm for Counting Inversions I
O(n log n) Algorithm for Counting Inversions II
Strassen's Subcubic Matrix Multiplication Algorithm
O(n log n) Algorithm for Closest Pair I [Advanced - Optional]
O(n log n) Algorithm for Closest Pair II [Advanced - Optional]
Motivation
Formal Statement
Examples
Proof I
Interpretation of the 3 Cases
Proof II
Week 2 Overview
Optional Theory Problems (Batch #1)
Problem Set #2
Programming Assignment #2

Week 3
Quicksort: Overview
Partitioning Around a Pivot
Correctness of Quicksort [Review - Optional]
Choosing a Good Pivot
Analysis I: A Decomposition Principle
Analysis II: The Key Insight
Analysis III: Final Calculations
Probability Review I
Probability Review II
Week 3 Overview
Problem Set #3
Programming Assignment #3

Week 4
Randomized Selection - Algorithm
Randomized Selection - Analysis
Deterministic Selection - Algorithm [Advanced - Optional]
Deterministic Selection - Analysis I [Advanced - Optional]
Deterministic Selection - Analysis II [Advanced - Optional]
Omega(n log n) Lower Bound for Comparison-Based Sorting [Advanced - Optional]
Graphs and Minimum Cuts
Graph Representations
Random Contraction Algorithm
Analysis of Contraction Algorithm
Counting Minimum Cuts
Week 4 Overview
Optional Theory Problems (Batch #2)
Info and FAQ for final exam
Problem Set #4
Programming Assignment #4
Final Exam

Summary of User Reviews

This course on Algorithms: Divide and Conquer covers various topics related to designing efficient algorithms. Users have praised the course for its clear explanations and practical examples. Overall, the course has received positive feedback from users.

Key Aspect Users Liked About This Course

Clear explanations and practical examples

Pros from User Reviews

In-depth coverage of algorithm design techniques
Hands-on assignments to reinforce learning
Well-structured course content
Instructors are knowledgeable and responsive
Course is accessible for beginners

Cons from User Reviews

Some users found the course pacing to be slow
Course can be challenging for those without a strong math background
Some assignments are difficult to complete without additional resources
Course material can be dry at times
Limited interaction with other students

Recommended for you

Algorithms: Design and Analysis, Part 1

Welcome to the self paced course, Algorithms: Design and Analysis! Algorithms are the heart of computer science, and the subject has countless practical applications as well as intellectual depth....

Save Course

Algorithmic Design and Techniques

Learn how to design algorithms, solve computational problems and implement solutions efficiently. This course will cover theories, including: how to sort data and how it helps for searching;...

Save Course