Divide and Conquer, Sorting and Searching, and Randomized Algorithms
- 4.8
-
![]()
![]()
![]()
![]()
![]()
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
Related Topics for further study
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
IntermediateCourse Format
- Online self-paced
- Video lectures
- Assignments
Similar Courses
- Algorithms, Part I
- Algorithms, Part II
- Data Structures and Algorithms Specialization
Related Education Paths
- Data Structures and Algorithms Specialization
- Computer Science Essentials for Software Development
- Python for Everybody Specialization
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 examplesPros 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
Tim Roughgarden
4.8 Raiting
Python 3: Project-based Python, Algorithms, Data Structures
- 4.7
-
![]()
![]()
![]()
![]()
![]()
Learn programming with Python 3; visualize Algorithms and Data Structures and implement them in projects with Python You will get: 1) 14+ hours of animation heavy instructional video...
Learn Data structures & Algorithms using Python for Freshers
- 4.3
-
![]()
![]()
![]()
![]()
![]()
Learn to master Data structure Algorithm by understanding concepts through time complexity and implementation in Python3 This course contains of these below mentioned topic:...
Algorithms: Design and Analysis, Part 1
- 0.0
-
![]()
![]()
![]()
![]()
![]()
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....
Python 4 in 1: Basics, Data Structures, API, REGEX, Scraping
- 0.0
-
![]()
![]()
![]()
![]()
![]()
Learn python Basic syntax, Regular Expression, Data structure & Algorithm, Web Scraping using BeautifulSoup & Scrapy This will help you understanding the usage of python in different circumstance....
