Stanford University
В любой момент
17 часов
Стоимость курса
49 USD/мес.
Подробности и регистрация

Divide and conquer, sorting and searching, and randomized algorithms

Высший рейтинг на Coursera
Навыки, которые вы получите:
Algorithms Randomized algorithm Divide and conquer algorithms Sorting algorithm

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

The Program 

Introduction; «big-oh» notation and asymptotic analysis

  1. Why Study Algorithms?
  2. Integer Multiplication.
  3. Karatsuba Multiplication.
  4. About the Course.
  5. Merge Sort: Motivation and Example.
  6. Merge Sort: Pseudocode.
  7. Merge Sort: Analysis.
  8. Guiding Principles for Analysis of Algorithms.
  9. The Gist.
  10. Big-Oh Notation.
  11. Basic Examples.
  12. Big Omega and Theta.

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

  1. O (n log n) Algorithm for Counting Inversions I.
  2. O (n log n) Algorithm for Counting Inversions II.
  3. Strassen’s Subcubic Matrix Multiplication Algorithm.
  4. O (n log n) Algorithm for Closest Pair I.
  5. O (n log n) Algorithm for Closest Pair II.

The QuickSort algorithm and its analysis; probability review

  1. Quicksort: Overview.
  2. Partitioning Around a Pivot.
  3. Correctness of Quicksort.
  4. Choosing a Good Pivot.
  5. Analysis I: A Decomposition Principle.
  6. Analysis II: The Key Insight.
  7. Analysis III: Final Calculations.
  8. Probability Review I.
  9. Probability Review II.

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

  1. Randomized Selection. Algorithm.
  2. Randomized Selection. Analysis.
  3. Deterministic Selection. Algorithm.
  4. Deterministic Selection. Analysis I.
  5. Deterministic Selection. Analysis II.
  6. Omega (n log n) Lower Bound for Comparison. Based Sorting.
  7. Graphs and Minimum Cuts.
  8. Graph Representations.
  9. Random Contraction Algorithm.
  10. Analysis of Contraction Algorithm.
  11. Counting Minimum Cuts.
Нам нужен ваш фидбек!
Честный и беспристрастный