Algorithms-Homework

Homework assignments of Introduction to Algorithms

Homework 1

2019.9.5

• Insertion Sort
• Linear Search
• Loop Invariants

Homework 2

9.13

• Algorithms Analysis
  • Asymptotic Notation
  • Solving Recurrences
    • Substitution
    • Recursion Tree
    • Master Method

Homework 3

9.25

• Heap Sort
• Quick Sort
• Random Partition
• Online-Judge
  • H3-1 数字统计
  • H3-2 考试排名

Homework 4

10.3

• Stable Sort
• Random Select
• Online-Judge
  • H4-1 抽奖
  • H4-2 数组排序

Homework 5

10.17

• Hash Table
  • The multiplication method
  • Open Addressing
    • Linear probing
    • Quadratic probing
    • Double hashing
• Binary Search Tree
• Red Black Tree

Homework 6

10.3

• Augmenting Data Structures
  • Interval Tree
• Fibonacci Heap
• Data Structures for Disjoint Sets
  • Linked-list representation & Weighted-union heuristic
• Online-Judge
  • H6-1 在线比赛
  • H6-2 朋友圈

Homework 7

11.12

• Dynamic Programming
  • DP in Graph
  • 0-1 Knapsack
  • DP in Tree
• Greedy Algorithms

Homework 8

11.24

• Amortized Analysis
  • Aggregate Analysis
  • The Accounting Method
  • The Potential Method
• DFT & FFT

Homework 9

12.26

• Graph Theory
  • Euler Tour
  • Bellman-Ford’s Algorithm
  • Johnson’s Algorithm
  • Ford-Fulkerson’s Algorithm

Homework 10

12.26

• NP-Completeness
  • Proof
  • The Subgraph-Isomorphism Problem
  • The Hamiltonian-Path Problem
  • 2-SAT
• Approximation Algorithms
  • The Bottleneck Traveling-Salesman Problem
  • Maximum Spanning Tree