avatar
Articles
294
Tags
364
Categories
10
主页 | Home
随机 | Random
目录 | Categories
回忆 | Archives
关于我 | About
朋友圈 | Link
打赏支持 | Support
EdNovas的小站
Search
主页 | Home
随机 | Random
目录 | Categories
回忆 | Archives
关于我 | About
朋友圈 | Link
打赏支持 | Support

Algorithm算法

Created2021-10-01|Updated2022-10-25|编程
|Word count:7|Reading time:1min|Post View:
Author: EdNovas
Link: https://ednovas.xyz/2021/10/01/algorithm/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
编程

EdNovas云————高性价比，节点覆盖80+国家，多地区奈飞迪士尼等流媒体解锁

Mocca Store————便宜稳定奈飞迪士尼等北美流媒体，办公设计学习软件会员

cover of previous post
Previous Post
Regular Expression 正则表达式
cover of next post
Next Post
Assembly language 汇编语言基础
Related Articles
cover
2021-10-01
Regular Expression 正则表达式
cover
2021-09-23
Assembly language 汇编语言基础
Comment
Catalog
  1. 1. Cut property
    1. 1.1. Definition in class
    2. 1.2. Proof in class
  2. 2. Greedy MST Algorithm
  3. 3. Prim’s Algorithm
    1. 3.1. Example
    2. 3.2. Proof
    3. 3.3. Pseudocode
  4. 4. Kruckal’s Algorithm
    1. 4.1. Example
    2. 4.2. Proof by Contradiction
    3. 4.3. Proof spanning tree then prove the constructed spanning tree is of minimal weight
    4. 4.4. Pseudocode
  5. 5. Boruvka’s Algorithm
    1. 5.1. Pseudocode
    2. 5.2. Proof
    3. 5.3. Example
  6. 6. Disjoint Set (Union-Find)
    1. 6.1. Find
    2. 6.2. Union
    3. 6.3. Example
    4. 6.4. Pseudocode
  7. 7. Proposition
    1. 7.1. Proof
    2. 7.2. W-Q-U Runtime
  8. 8. Union-Rank
    1. 8.1. Path Compression
  9. 9. BFS (solution for unweighted graph)
    1. 9.1. Example
  10. 10. Path Relaxation Property
  11. 11. Weighted DAG (Directed Acyclic Graph)
    1. 11.1. Example
    2. 11.2. Algorithm
    3. 11.3. Proof of Correctness
    4. 11.4. Edge Relaxtion
  12. 12. Dijkstra’s Algorithm(A greedy algorithm)
    1. 12.1. Conceptual Version
    2. 12.2. Example
    3. 12.3. Code
    4. 12.4. Code compare with Prim
    5. 12.5. Runtime
    6. 12.6. Claim
    7. 12.7. Correctness
  13. 13. Bellman-Ford Algorithm
    1. 13.1. Code
    2. 13.2. Correctness
  14. 14. Floyd-Marshall Algorithm
    1. 14.1. Problem
    2. 14.2. Subproblem
    3. 14.3. Flow Network Example
    4. 14.4. Maximum flow Problem
    5. 14.5. Min-cut Problem
    6. 14.6. Residural Graph G_f
  15. 15. Ford-Fulkerson Algorithm
    1. 15.1. Flow Value Lemma
    2. 15.2. Weak Duality
    3. 15.3. Max-flow min-cut theorem
    4. 15.4. Bad case for Ford-Fulkerson Algorithm
    5. 15.5. Shortest augmenting path
    6. 15.6. Lemma
      1. 15.6.1. Proof
    7. 15.7. Theorem
  16. 16. Blocking-flow Algorithm
    1. 16.1. Select medians and order statics
    2. 16.2. A naive solution
  17. 17. Quickselect
    1. 17.1. Quickselect Worst-case Analysis
    2. 17.2. Pick a Good Pivot
    3. 17.3. Runtime
  18. 18. Probability
    1. 18.1. Coin Example
    2. 18.2. Dice Example
    3. 18.3. Events
    4. 18.4. Random Variables
    5. 18.5. Events Based on Random Variables
    6. 18.6. Expected Value
      1. 18.6.1. Linearity of Exapectation
    7. 18.7. Independence
    8. 18.8. Recall Quickselect
    9. 18.9. Randomized Quickselect
      1. 18.9.1. Pick a Good Pivot
    10. 18.10. Sketch of Bound on Expected Runtime
  19. 19. Dictionary
    1. 19.1. Warm-up
    2. 19.2. Definition
    3. 19.3. Operations
  20. 20. Unordered list
  21. 21. Ordered list
  22. 22. Balanced binary search tree
  23. 23. Direct-address table
  24. 24. Hash tables
    1. 24.1. Collision
    2. 24.2. Not a natrual number
    3. 24.3. Handling collisions
    4. 24.4. Chaining
    5. 24.5. Operations
    6. 24.6. Load factor
    7. 24.7. Assumption: Simple uniform hashing
    8. 24.8. Expected time for unsuccessful search
    9. 24.9. Expected time for successful search
    10. 24.10. Design hash function
      1. 24.10.1. Division method
      2. 24.10.2. Multiplication method
    11. 24.11. Universal hashing
      1. 24.11.1. Average case
      2. 24.11.2. Construct
    12. 24.12. Open addressing
      1. 24.12.1. Average-case
    13. 24.13. Linear probing
    14. 24.14. Quadratic probing
  25. 25. Double hashing
  26. 26. Amortized Analysis
  27. 27. The peril of per-operation worst-case analysis
  28. 28. Aggregate analysis
  29. 29. Accounting method
  30. 30. Incrementing Binary Counter Example
  31. 31. Dynamic tables
  32. 32. Brute-force substring search
    1. 32.1. Worst case
  33. 33. Rabin-Karp fingerprint search
    1. 33.1. Challenge 1
      1. 33.1.1. Horner Method
    2. 33.2. Challenge 2
  34. 34. Efficiently computing the hash function
  35. 35. Rabin-Karp substring search example
  36. 36. Rabin-Karp analysis
  37. 37. Substring search————Knuth-Morris-Pratt
    1. 37.1. Determinishtic finite state automaton(DFA)
    2. 37.2. Java implementation
    3. 37.3. DFA construction
    4. 37.4. Build DFA from pattern
    5. 37.5. DFA construction in linear time
      1. 37.5.1. Java implementation
  38. 38. KMP substring search analysis
  39. 39. Greedy Algorithms
    1. 39.1. Interval scheduling
    2. 39.2. Therem
    3. 39.3. Proof
    4. 39.4. Analysis
    5. 39.5. Interval partitioning
  40. 40. Scheduling to minimizing lateness
  41. 41. Optimal caching
  42. 42. Keep updating……
©2020 - 2024 By EdNovas
Framework Hexo|Theme Butterfly
已经到底啦！再往下划要坏掉啦！
Algolia