Algorithms Specialization

Algorithms Specialization

English | MP4 | AVC 1280×720 | AAC 44KHz 2ch | 170 Lessons (37h 00m) | 4.16 GB

Learn To Think Like A Computer Scientist. Master the fundamentals of the design and analysis of algorithms.

Algorithms Specialization (Stanford University)

Algorithms are the heart of computer science, and the subject has countless practical applications as well as intellectual depth. This specialization is an introduction to algorithms for learners with at least a little programming experience. The specialization is rigorous but emphasizes the big picture and conceptual understanding over low-level implementation and mathematical details. After completing this specialization, you will be well-positioned to ace your technical interviews and speak fluently about algorithms with other programmers and computer scientists.

About the instructor: Tim Roughgarden has been a professor in the Computer Science Department at Stanford University since 2004. He has taught and published extensively on the subject of algorithms and their applications.

Applied Learning Project
Learners will practice and master the fundamentals of algorithms through several types of assessments. Every week, there is a multiple choice quiz to test your understanding of the most important concepts. There are also weekly programming assignments, where you implement one of the algorithms covered in lecture in a programming language of your choosing. Each course concludes with a multiple-choice final exam.

SKILLS YOU WILL GAIN

  • Algorithms
  • Dynamic Programming
  • Greedy Algorithm
  • Divide And Conquer Algorithms
  • Randomized Algorithm
  • Sorting Algorithm
  • Graphs
  • Data Structure
  • Hash Table
  • Spanning Tree
  • Np-Completeness
Table of Contents

i-introduction
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

ii-asymptotic-analysis
the-gist
big-oh-notation
basic-examples
big-omega-and-theta
additional-examples-review-optional

iii-divide-conquer-algorithms
o-n-log-n-algorithm-for-counting-inversions-i
o-n-log-n-algorithm-for-counting-inversions-ii
strassens-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

iv-the-master-method
motivation
formal-statement
examples
proof-i
interpretation-of-the-3-cases
proof-ii

v-quicksort-algorithm
quicksort-overview
partitioning-around-a-pivot
correctness-of-quicksort-review-optional
choosing-a-good-pivot

vi-quicksort-analysis
analysis-i-a-decomposition-principle
analysis-ii-the-key-insight
analysis-iii-final-calculations

vii-probability-review
probability-review-i
probability-review-ii

viii-linear-time-selection
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

ix-graphs-and-the-contraction-algorithm
graphs-and-minimum-cuts
graph-representations
random-contraction-algorithm
analysis-of-contraction-algorithm
counting-minimum-cuts

x-graph-search-and-connectivity-week-1
graph-search-overview
breadth-first-search-bfs-the-basics
bfs-and-shortest-paths
bfs-and-undirected-connectivity
depth-first-search-dfs-the-basics
topological-sort
computing-strong-components-the-algorithm
computing-strong-components-the-analysis
structure-of-the-web-optional

xi-dijkstra-s-shortest-path-algorithm-week-2
dijkstras-shortest-path-algorithm
dijkstras-algorithm-examples
correctness-of-dijkstras-algorithm
dijkstras-algorithm-implementation-and-running-time

xii-heaps-week-3
data-structures-overview
heaps-operations-and-applications
heaps-implementation-details-advanced-optional

xiii-balanced-binary-search-trees-week-3
balanced-search-trees-operations-and-applications
binary-search-tree-basics-part-i
binary-search-tree-basics-part-ii
red-black-trees
rotations-advanced-optional
insertion-in-a-red-black-tree-advanced

xiv-hashing-the-basics-week-4
hash-tables-operations-and-applications
hash-tables-implementation-details-part-i
hash-tables-implementation-details-part-ii

xv-universal-hashing-week-4
pathological-data-sets-and-universal-hashing-motivation
universal-hashing-definition-and-example-advanced-optional
universal-hashing-analysis-of-chaining-advanced-optional
hash-table-performance-with-open-addressing-advanced-optional

xvi-bloom-filters-week-4
bloom-filters-the-basics
bloom-filters-heuristic-analysis

xvii-two-motivating-applications-week-1
application-internet-routing
application-sequence-alignment

xviii-introduction-to-greedy-algorithms-week-1
introduction-to-greedy-algorithms
application-optimal-caching

xix-a-scheduling-application-week-1
problem-definition
a-greedy-algorithm
correctness-proof-part-i
correctness-proof-part-ii
handling-ties-advanced-optional

xx-prim-s-minimum-spanning-tree-algorithm-week-1
mst-problem-definition
prims-mst-algorithm
correctness-proof-i
correctness-proof-ii
proof-of-cut-property-advanced-optional
fast-implementation-i
fast-implementation-ii

xxi-kruskal-s-minimum-spanning-tree-algorithm-week-2
kruskals-mst-algorithm
correctness-of-kruskals-algorithm
implementing-kruskals-algorithm-via-union-find-i
implementing-kruskals-algorithm-via-union-find-ii
msts-state-of-the-art-and-open-questions-advanced-optional

xxii-clustering-week-2
application-to-clustering
correctness-of-clustering-algorithm

xxiii-advanced-union-find-week-2
lazy-unions-advanced-optional
union-by-rank-advanced-optional
analysis-of-union-by-rank-advanced-optional
path-compression-advanced-optional
path-compression-the-hopcroft-ullman-analysis-i-advanced-optional
path-compression-the-hopcroft-ullman-analysis-ii-advanced-optional
the-ackermann-function-advanced-optional
path-compression-tarjans-analysis-i-advanced-optional
path-compression-tarjans-analysis-ii-advanced-optional

xxiv-huffman-codes-week-3
introduction-and-motivation
problem-definition
a-greedy-algorithm
a-more-complex-example
correctness-proof-i
correctness-proof-ii

xxv-introduction-to-dynamic-programming-week-3
introduction-weighted-independent-sets-in-path-graphs
wis-in-path-graphs-optimal-substructure
wis-in-path-graphs-a-linear-time-algorithm
wis-in-path-graphs-a-reconstruction-algorithm
principles-of-dynamic-programming

xxvi-the-knapsack-problem-week-4
the-knapsack-problem
a-dynamic-programming-algorithm
example-review-optional

xxvii-sequence-alignment-week-4
optimal-substructure
a-dynamic-programming-algorithm

xxviii-optimal-binary-search-trees-week-4
problem-definition
optimal-substructure
proof-of-optimal-substructure
a-dynamic-programming-algorithm-i
a-dynamic-programming-algorithm-ii

xxix-the-bellman-ford-algorithm-week-1
single-source-shortest-paths-revisted
optimal-substructure
the-basic-algorithm-i
the-basic-algorithm-ii
detecting-negative-cycles
a-space-optimization
internet-routing-i-optional
internet-routing-ii-optional

xxx-all-pairs-shortest-paths-week-1
problem-definition
optimal-substructure
the-floyd-warshall-algorithm
a-reweighting-technique
johnsons-algorithm-i
johnsons-algorithm-ii

xxxi-np-complete-problems-week-2
polynomial-time-solvable-problems
reductions-and-completeness
definition-and-interpretation-of-np-completeness-i
definition-and-interpretation-of-np-completeness-ii
the-p-vs-np-question
algorithmic-approaches-to-np-complete-problems

xxxii-faster-exact-algorithms-for-np-complete-problems-week-2
the-vertex-cover-problem
smarter-search-for-vertex-cover-i
smarter-search-for-vertex-cover-ii
the-traveling-salesman-problem
a-dynamic-programming-algorithm-for-tsp

xxxiii-approximation-algorithms-for-np-complete-problems-week-3
a-greedy-knapsack-heuristic
analysis-of-a-greedy-knapsack-heuristic-i
analysis-of-a-greedy-knapsack-heuristic-ii
a-dynamic-programming-heuristic-for-knapsack
knapsack-via-dynamic-programming-revisited
ananysis-of-dynamic-programming-heuristic

xxxiv-local-search-algorithms-week-4
the-maximum-cut-problem-i
the-maximum-cut-problem-ii
principles-of-local-search-i
principles-of-local-search-ii
the-2-sat-problem
random-walks-on-a-line
analysis-of-papadimitrious-algorithm

xxxv-the-wider-world-of-algorithms-week-4
stable-matching-optional
matchings-flows-and-braesss-paradox-optional
linear-programming-and-beyond-optional
epilogue

Homepage