Divide and Conquer, Sorting and Searching, and Randomized Algorithms

Product type

Divide and Conquer, Sorting and Searching, and Randomized Algorithms

Coursera (CC)
Logo Coursera (CC)
Provider rating: starstarstarstar_halfstar_border 7.2 Coursera (CC) has an average rating of 7.2 (out of 6 reviews)

Need more information? Get more details on the site of the provider.

Description

When you enroll for courses through Coursera you get to choose for a paid plan or for a free plan

  • Free plan: No certicification and/or audit only. You will have access to all course materials except graded items.
  • Paid plan: Commit to earning a Certificate—it's a trusted, shareable way to showcase your new skills.

About this course: 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).

Who is this class for: Learners with at least a little bit of programming experience who want to learn the essentials of algorithms. In a University computer science curriculum, this course is typically taken in the third year.

Created by:  Stanford University
  • Taught by:  Tim Roughgarden, Professor

    Computer Science
Basic Info Course 1 of 4 in the Algorithms Specializatio…

Read the complete description

Frequently asked questions

There are no frequently asked questions yet. If you have any more questions or need help, contact our customer service.

Didn't find what you were looking for? See also: .

When you enroll for courses through Coursera you get to choose for a paid plan or for a free plan

  • Free plan: No certicification and/or audit only. You will have access to all course materials except graded items.
  • Paid plan: Commit to earning a Certificate—it's a trusted, shareable way to showcase your new skills.

About this course: 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).

Who is this class for: Learners with at least a little bit of programming experience who want to learn the essentials of algorithms. In a University computer science curriculum, this course is typically taken in the third year.

Created by:  Stanford University
  • Taught by:  Tim Roughgarden, Professor

    Computer Science
Basic Info Course 1 of 4 in the Algorithms Specialization Level Intermediate Commitment 4 weeks of study, 4-8 hours/week Language English How To Pass Pass all graded assignments to complete the course. User Ratings 4.8 stars Average User Rating 4.8See what learners said Задания курса

Каждый курс — это интерактивный учебник, который содержит видеоматериалы, тесты и проекты.

Помощь сокурсников

Общайтесь с тысячами других учащихся: обсуждайте идеи, материалы курса и помогайте друг другу осваивать новые понятия.

Сертификаты

Получите документы о прохождении курсов и поделитесь своим успехом с друзьями, коллегами и работодателями.

Stanford University The Leland Stanford Junior University, commonly referred to as Stanford University or Stanford, is an American private research university located in Stanford, California on an 8,180-acre (3,310 ha) campus near Palo Alto, California, United States.

Syllabus


WEEK 1


Week 1
Introduction; "big-oh" notation and asymptotic analysis.


13 videos, 3 readings expand


  1. Материал для самостоятельного изучения: Welcome and Week 1 Overview
  2. Материал для самостоятельного изучения: Overview, Resources, and Policies
  3. Материал для самостоятельного изучения: Lecture slides
  4. Video: Why Study Algorithms?
  5. Video: Integer Multiplication
  6. Video: Karatsuba Multiplication
  7. Video: About the Course
  8. Video: Merge Sort: Motivation and Example
  9. Video: Merge Sort: Pseudocode
  10. Video: Merge Sort: Analysis
  11. Video: Guiding Principles for Analysis of Algorithms
  12. Video: The Gist
  13. Video: Big-Oh Notation
  14. Video: Basic Examples
  15. Video: Big Omega and Theta
  16. Video: Additional Examples [Review - Optional]

Graded: Problem Set #1
Graded: Programming Assignment #1

WEEK 2


Week 2
Divide-and-conquer basics; the master method for analyzing divide and conquer algorithms.


11 videos, 2 readings expand


  1. Материал для самостоятельного изучения: Week 2 Overview
  2. Video: O(n log n) Algorithm for Counting Inversions I
  3. Video: O(n log n) Algorithm for Counting Inversions II
  4. Video: Strassen's Subcubic Matrix Multiplication Algorithm
  5. Video: O(n log n) Algorithm for Closest Pair I [Advanced - Optional]
  6. Video: O(n log n) Algorithm for Closest Pair II [Advanced - Optional]
  7. Video: Motivation
  8. Video: Formal Statement
  9. Video: Examples
  10. Video: Proof I
  11. Video: Interpretation of the 3 Cases
  12. Video: Proof II
  13. Материал для самостоятельного изучения: Optional Theory Problems (Batch #1)

Graded: Problem Set #2
Graded: Programming Assignment #2

WEEK 3


Week 3
The QuickSort algorithm and its analysis; probability review.


9 videos, 1 reading expand


  1. Материал для самостоятельного изучения: Week 3 Overview
  2. Video: Quicksort: Overview
  3. Video: Partitioning Around a Pivot
  4. Video: Correctness of Quicksort [Review - Optional]
  5. Video: Choosing a Good Pivot
  6. Video: Analysis I: A Decomposition Principle
  7. Video: Analysis II: The Key Insight
  8. Video: Analysis III: Final Calculations
  9. Video: Probability Review I
  10. Video: Probability Review II

Graded: Problem Set #3
Graded: Programming Assignment #3

WEEK 4


Week 4
Linear-time selection; graphs, cuts, and the contraction algorithm.


11 videos, 3 readings expand


  1. Материал для самостоятельного изучения: Week 4 Overview
  2. Video: Randomized Selection - Algorithm
  3. Video: Randomized Selection - Analysis
  4. Video: Deterministic Selection - Algorithm [Advanced - Optional]
  5. Video: Deterministic Selection - Analysis I [Advanced - Optional]
  6. Video: Deterministic Selection - Analysis II [Advanced - Optional]
  7. Video: Omega(n log n) Lower Bound for Comparison-Based Sorting [Advanced - Optional]
  8. Video: Graphs and Minimum Cuts
  9. Video: Graph Representations
  10. Video: Random Contraction Algorithm
  11. Video: Analysis of Contraction Algorithm
  12. Video: Counting Minimum Cuts
  13. Материал для самостоятельного изучения: Optional Theory Problems (Batch #2)
  14. Материал для самостоятельного изучения: Info and FAQ for final exam

Graded: Problem Set #4
Graded: Programming Assignment #4
Graded: Final Exam
There are no reviews yet.

    Share your review

    Do you have experience with this course? Submit your review and help other people make the right choice. As a thank you for your effort we will donate $1.- to Stichting Edukans.

    There are no frequently asked questions yet. If you have any more questions or need help, contact our customer service.