1. Introduction

Python implementation of basic algorithms in Introduction to Algorithms class. Here is the video 1 and video 2.

2. Data structure

• 2.1 Array

  • Applications
    • 53. Maximum Subarray
    • 152. Maximum Product Subarray

• 2.2 Linked list

  • Applications
    • 206. Reverse Linked List
    • 83. Remove Duplicates from Sorted List
    • 237. Delete Node in a Linked List

• 2.3 Stack

  • FILO: elements are added from the front and removed from the front
  • Applications
    • 20. Valid Parentheses
    • 394. Decode String
    • Recursive
    • DFS in graph

• 2.4 Queue

  • FIFO: elements are added from the back and removed from the front
  • Applications
    • BFS in graph
    • PriorityQueue
      • 23. Merge k Sorted Lists

• 2.5 Hash

  • It is set: unique and non-order
  • (key, value), the key point of Hash is index of key
  • Applications
    • Unique n numbers with range [0, m)
      • Solution 1: Quicksort with time complexity O(nlogn) and space complexity O(1)
      • Solution 2: Countsort with time complexity O(n + m) and space complexity O(m)
      • Solution 3: hash
        • Mod operation
    • 128. Longest Consecutive Sequence
    • 1. Two Sum

• 2.6 Tree

  • Useful for dynamic set(i.e., insert or delete element) query
  • Applications
    • 144. Binary Tree Preorder Traversal - non recursive
    • 226. Invert Binary Tree
    • 106. Construct Binary Tree from Inorder and Postorder Traversal

• 2.7 Heap

  • It is always complete binary tree: root i, left 2*i, right 2*i+1
  • Applications
    • 347. Top K Frequent Elements
    • 23. Merge k Sorted Lists

• 2.8 Graph

  • G = (V, E)
  • Storage
    • Adjacency matrix, Adjacency table, edge lists
  • Traversal
    • DFS by stack
    • BFS by queue
    • Topological sorting in DAG
      • Time complexity: O(V+E)
      • It is used to schedule jobs from the given dependencies among jobs
      • There may exist several topological sorting results for one graph
      • Applications
        • 207. Course Schedule
  • Shortest path
    • Dijkstra
      • From source node s to any other node
      • Key
        • Relax operation to maintain shortest distance from s to any other node
        • Weight must be positive
      • Time complexity: O(n^2)
      • Applications
        • 787. Cheapest Flights Within K Stops
    • Floyd
      • All pairs shortest path

3. Algorithm

3.1 Algorithm attributes

• Finite (有穷性)
• Determinate (确定性)
• Feasible (可行性)
• Input & output

3.2 Algorithm complexity

• Time
  • Basic operation times
  • O(nlgn)
    • Expectation time of quicksort
    • Lower-bound of comparison-based sorting algorithms
• Space
  • Memory usage
• Difference
  • Space can be reused
  • Time and space can be interchanged (e.g. Hash)
• O(1) < O(lgn) < O(n^(1/2)) < O(n) < O(nlgn) < O(n^2) < O(n^3) < O(2^n) < O(n!)

3.3 Algorithm design technique

• 3.3.1 Exhaustive (穷举法)

  • N-queen
  • N permutation

• 3.3.2 Divide and Conquer

  • Binary search
  • MergeSort

• 3.3.3 Dynamic Programming

  • Principle
    • Cache: 1d array, 2d matrix, 3d tensor, map
    • bottom-up
  • Scenario
    • [1] Most: big (最大), small (最小), long (最长), optimum (最优), counting (计数)
    • [2] Recursive formula: f(n) = F(n-1)
  • Applications
    • 509. Fibonacci Number
    • 198. House Robber 0/1 knapsack without conditions
    • 416. Partition Equal Subset Sum, 0/1 knapsack
    • 72. Edit Distance
    • 70. Climbing Stairs, counting
    • 322. Coin Change
    • Dynamic Programming Practice Problems

• 3.3.4 Greedy

  • Topological sorting
  • Dijkstra
    • Local optimal is global optimal
  • Prim
  • Kruskal

4. Lectures

• Lecture 1: introduction, analysis of algorithms, insertion sort, merge sort.
• Lecutre 2: asymptotic notation, solving recurrences: substitution, recurrsion tree, master.
• Lecutre 3: divide and conquer, binary search, merge sort, x to the power of n, matrix multiplication of Fibonacci numbers, Strassen matrix multiplication.
• Lecutre 4: quick sort, randomized quick sort.
• Lecutre 5: comparison sorting, decision tree model, sort in linear time: couting sort, radix sort, stable sorting algorithm
• Lecutre 6: find the k-th element: quick select, worst-case linear-time order statistics
• Lecutre 7: Hash, hash function, load factor, collision: chaining, open addressing
• Lecutre 8: universal hashing
• Lecutre 9: binary search tree, bst sort, Jensen's equality, convex, expected random build bst height is O(lgn)
• Lecutre 10: red-black tree, rb-insert, rotation
• Lecutre 11: dynamic order statistics, data structure augmentation, interval tree
• Lecutre 12: dynamic programming two hallmarks, longest common subsequence
• Lecutre 13
• Lecutre 14
• Lecutre 15
• Lecutre 16
• Lecutre 17
• Lecutre 18
• Lecutre 19
• Lecutre 20
• Lecutre 21
• Lecutre 22

5. Coding interview Book

• Codes
• Chapter 1
  • 1.1 How to test a algorithm?
    • First: it works
    • Second: robust to boundary value or invalid value
    • Third: optimize it by considering time and space complexity
  • 1.2 How to solve a hard problem?
    • First: think it at a whole
    • Second: from n=1, n=2; make an example; visualize it