Divide and Conquer, Sorting and Searching, and Randomized Algorithms

Location type
Logo Coursera
Provider rating: starstarstarstar_borderstar_border 6.3 Coursera has an average rating of 6.3 (out of 4 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. Send an Email to info@springest.com

Didn't find what you were looking for? See also: Algorithms, Computer Science, Programming, Hour of Code, and Ruby on Rails.

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. Send an Email to info@springest.com