wangshusen

This lecture introduces the binary search which finds an element in a sorted array. Binary search has O(log n) time complexity. In the end, we discuss how to support both search and insertion. Slides: https://github.com/wangshusen/AdvancedAlgorithms

Monte Carlo refers to algorithms that rely on repeated random sampling to obtain numerical results. This lecture teaches Monte Carlo using 5 examples: 0:15 Uniform sampling for estimating π 7:37 Buffon's needle problem 13:20 Area of a region 19:39 Monte Carlo integration 29:29 Estimating expectations Slides: https://github.com/wangshusen/AdvancedAlgorithms

This lecture introduces the random permutation (aka random shuffling) problem. We can use Fisher-Yates algorithm for randomly shuffling a sequence. This lecture introduces the two versions of the Fisher-Yates shuffle. The original version [Fisher-Yates 1938] has quadratic time complexity. The modern version [Durstenfeld 1964] has linear time complexity. Slides: https://github.com/wangshusen/AdvancedAlgorithms Reference: 1. Fisher, Ronald A.; Yates, Frank. Statistical tables for biological, agricultural and medical research, 1938. 2. Durstenfeld, R. Algorithm 235: Random permutation. Communications of the ACM, 7 (7): 420, 1964.

This lecture studies dense matrix and sparse matrix data structures. Dense matrices can be stored in row-major order or column major-order. Sparse matrices can be Compressed Sparse Column (CSC) or Compressed Sparse Row (CSR) format. Slides: https://github.com/wangshusen/AdvancedAlgorithms

This lecture introduces the very basics of matrix computation: additions, multiplications, time complexities. If you are familiar with matrix computation, you don't need to watch this video. Slides: https://github.com/wangshusen/AdvancedAlgorithms

Skip list a data structure that performs search, insertion, and deletion in log(n) time. Skip list is built upon a linked list. The height of nodes grows randomly. Slides: https://github.com/wangshusen/AdvancedAlgorithms

Array, vector, and list are the most frequently used data structures. This lecture compares them and discusses what they are good at and bad at. Before watching this lecture, the audience shall be familiar with C++. Slides: https://github.com/wangshusen/AdvancedAlgorithms