ACM Extensive Problem Set
ACM Extensive Problem Set
There are many problem sets available online, most of which can be evaluated online, hence the name Online Judge. Except for USACO, which is prepared for IOI, almost all the others are university ACM competition problem sets.
USACO
http://ace.delos.com/usacogate
A well-known online problem set in the United States, specifically prepared for informatics competition participants.
TJU
Tongji University online problem set, the only Chinese problem set, suitable for NOIP participants.
ZJU
Zhejiang University online problem set.
JLU
Jilin University online problem set (often inaccessible).
PKU
Peking University online problem set.
URAL
Ural Federal University online problem set.
SGU
Saratov State University online problem set.
ELJ
http://acm.mipt.ru/judge/bin/problems.pl?lang=en
Moscow Institute of Physics and Technology.
SPOJ
Gdańsk University of Technology in Poland.
UVA
Online problems from Universidad de Valladolid in Spain.
ACM Contact Suggestions
A suggestion from an expert:
Generally, aim to write programs under 50 lines without debugging, and debug programs under 100 lines within two minutes. ACM mainly tests algorithms, and most of the time should be spent thinking about algorithms, not writing programs and debugging.
Here’s a plan for you to practice:
Phase One:
Practice classic commonly used algorithms, type each of the following algorithms ten to twenty times, while simplifying your code,
because they are so commonly used that you should practice until you can write them without thinking, finishing in 10-15 minutes, or even being able to type them with the monitor turned off.
- Shortest Path (Floyd, Dijkstra, Bellman-Ford)
- Minimum Spanning Tree (first write Prim, Kruskal requires union-find, which is harder to write)
- Large Numbers (high precision) addition, subtraction, multiplication, division
- Binary Search (code can be within five lines)
- Cross Product, check line segment intersection, then write a convex hull.
- BFS, DFS, while also mastering hash tables (must be familiar, flexible, and code should be simple)
- Mathematical concepts: Euclidean algorithm (within two lines), line segment intersection points, polygon area formulas.
- Call the system's qsort, many techniques, gradually master.
- Conversion between arbitrary bases.
Phase Two:
Practice slightly more complex but still commonly used algorithms.
For example: - Bipartite Graph Matching (Hungarian), Minimum Path Cover
- Network Flow, Minimum Cost Flow.
- Segment Tree.
- Union-Find.
- Familiarize yourself with various typical dynamic programming problems: LCS, Longest Increasing Subsequence, Triangulation, Memoization DP.
- Game Theory algorithms. Game trees, binary methods, etc.
- Maximum Clique, Maximum Independent Set.
- Determine if a point is inside a polygon.
- Difference Constraint System.
- Bidirectional BFS, A* algorithm, Minimum Dissipation Priority.
Phase Three:
The first two phases lay the foundation, and the third phase is to train for quickly establishing models and thinking of new algorithms during competitions. This requires practicing comprehensive problem types regularly. - Review papers on OIBH (there are hundreds, I’ve only read a little, haha).
- Regularly scan difficult problems on ZOJ, don’t always do those easy ones (the moderator of the Central University ACM often says I choose easy ones to do :-P).
- Participate in online competitions more often, feel the atmosphere of competition, and assess your own strength.
- Don’t just consider a problem solved once you pass it; ask others if there are better algorithms and try them out.
- Keep good records of the problems you’ve solved. :-)
ACM ICPC Learning Plan
A plan given by an expert—
Generally, aim to write programs under 50 lines without debugging, and debug programs under 100 lines within two minutes. ACM mainly tests algorithms, and most of the time should be spent thinking about algorithms, not writing programs and debugging.
Here’s a plan for you to practice:
Phase One: Practice classic commonly used algorithms, type each of the following algorithms ten to twenty times, while simplifying your code,
because they are so commonly used that you should practice until you can write them without thinking, finishing in 10-15 minutes, or even being able to type them with the monitor turned off.
- Shortest Path (Floyd, Dijkstra, Bellman-Ford)
- Minimum Spanning Tree (first write Prim, Kruskal requires union-find, which is harder to write)
- Large Numbers (high precision) addition, subtraction, multiplication, division
- Binary Search (code can be within five lines)
- Cross Product, check line segment intersection, then write a convex hull.
- BFS, DFS, while also mastering hash tables (must be familiar, flexible, and code should be simple)
- Mathematical concepts: Euclidean algorithm (within two lines), line segment intersection points, polygon area formulas.
- Call the system's qsort, many techniques, gradually master.
- Conversion between arbitrary bases.
Phase Two: Practice slightly more complex but still commonly used algorithms.
For example: - Bipartite Graph Matching (Hungarian), Minimum Path Cover
- Network Flow, Minimum Cost Flow.
- Segment Tree.
- Union-Find.
- Familiarize yourself with various typical dynamic programming problems: LCS, Longest Increasing Subsequence, Triangulation, Memoization DP.
- Game Theory algorithms. Game trees, binary methods, etc.
- Maximum Clique, Maximum Independent Set.
- Determine if a point is inside a polygon.
- Difference Constraint System.
- Bidirectional BFS, A* algorithm, Minimum Dissipation Priority.
Relevant Knowledge
Graph Theory
Path Problems
0/1 Edge Weight Shortest Path
BFS
Non-negative Edge Weight Shortest Path (Dijkstra)
Characteristics of problems solvable by Dijkstra
Negative Edge Weight Shortest Path
Bellman-Ford
Yen's Optimization of Bellman-Ford
Difference Constraint System
Floyd
General Path Problems
Transitive Closure
Minimax Distance / Maximin Distance
Euler Path / Tour
Cycle-Cycle Algorithm
Euler Path / Tour of Mixed Graphs
Hamilton Path / Tour
Construction of Hamilton Path / Tour for Special Graphs
Spanning Tree Problems
Minimum Spanning Tree
k-th Smallest Spanning Tree
Optimal Ratio Spanning Tree
0/1 Fractional Knapsack
Degree Constrained Spanning Tree
Connectivity Problems
Powerful DFS Algorithms
Undirected Graph Connectivity
Cut Points
Cut Edges
Biconnected Components
Directed Graph Connectivity
Strongly Connected Components
2-SAT
Minimum Vertex Cover
Directed Acyclic Graph
Topological Sorting
Relationship between Directed Acyclic Graph and Dynamic Programming
Bipartite Graph Matching Problems
General Graph Problems and Conversion Ideas to Bipartite Graph Problems
Maximum Matching
Minimum Path Cover for Directed Graphs
Minimum Cover for 0/1 Matrices
Perfect Matching
Optimal Matching
Stable Marriage
Network Flow Problems
Simple Characteristics of Network Flow Models and Their Relationship with Linear Programming
Max Flow Min Cut Theorem
Maximum Flow Problems
Maximum Flow Problems with Upper and Lower Bounds
Circulation Flow
Minimum Cost Maximum Flow / Maximum Cost Maximum Flow
Properties and Determination of Chordal Graphs
Combinatorial Mathematics
Common Ideas for Solving Combinatorial Mathematics Problems
Approximation
Recursion / Dynamic Programming
Probability Problems
Polya's Theorem
Computational Geometry / Analytical Geometry
Core of Computational Geometry: Cross Product / Area
Main Force of Analytical Geometry: Complex Numbers
Basic Shapes
Points
Lines, Line Segments
Polygons
Convex Polygons / Convex Hulls
Introduction of Convex Hull Algorithms, Wrapping Method
Graham's Scan
Introduction of Horizontal Sequences, Patch for Collinear Convex Hulls
Perfect Convex Hull Algorithm
Related Determination
Intersection of Two Lines
Intersection of Two Line Segments
Determination of a Point Inside Any Polygon
Determination of a Point Inside a Convex Polygon
Classic Problems
Minimum Enclosing Circle
Approximate O(n) Minimum Enclosing Circle Algorithm
Diameter of a Point Set
Rotating Calipers, Antipodal Points
Triangulation of Polygons
Mathematics / Number Theory
Greatest Common Divisor
Euclidean Algorithm
Extended Euclidean Algorithm
Congruence Equations / Binary Linear Indeterminate Equations
Systems of Congruence Equations
Linear Systems of Equations
Gaussian Elimination
Solving Linear Systems over mod 2 Fields
Exact Solutions for Integer Coefficient Systems
Matrices
Calculation of Determinants
Using Matrix Multiplication to Quickly Calculate Recursion Relations
Fractions
Fraction Trees
Continued Fraction Approximations
Number Theory Calculations
Finding the Number of Divisors of N
Finding phi(N)
Finding the Sum of Divisors
Fast Number Theoretic Transform
……
Prime Number Problems
Probabilistic Primality Testing Algorithms
Probabilistic Factorization
Data Structures
Organizational Structures
Binary Heap
Leftist Tree
Binomial Tree
Winner Tree
Skip List
Style Icon
Skew Heap
Reap
Statistical Structures
Fenwick Tree
Virtual Binary Tree
Segment Tree
Rectangle Area Union
Circle Area Union
Relational Structures
Hash Tables
Union-Find
Application of Path Compression Ideas
Data Structures in STL
Vector
Deque
Set / Map
Dynamic Programming / Memoization
Differences in Thinking Between Dynamic Programming and Memoization
Longest Subsequence Series Problems
Longest Non-decreasing Subsequence
Longest Common Subsequence
Longest Common Non-decreasing Subsequence
Dynamic Programming Solutions for a Class of NP Problems
Tree Dynamic Programming
Knapsack Problems
Optimization of Dynamic Programming
Quadratic Inequality
Convexity of Functions
State Design
Planning Direction
Linear Programming
Common Ideas
Binary
Minimum Representation
Strings
KMP
Trie Structure
Suffix Tree/Suffix Array
LCA/RMQ
Finite State Automaton Theory
Sorting
Selection/Bubble
Quick Sort
Heap Sort
Merge Sort
Radix Sort
Topological Sort
Sorting Networks
Proficient in Data Structures and Common Algorithm Aggregation
(1)
It is impossible to remember so many algorithms completely.
Common algorithms can be written out directly.
Uncommon ones can be understood by looking at the book for 10 minutes (because they were memorized before).
For algorithms that were never memorized before, it is hard to say; difficult ones may take several days to study.
That should be enough.
The commonly used algorithms that should be proficient include:
Various sorting algorithms (insertion sort, bubble sort, selection sort, quick sort, heap sort, merge sort)
Insertion and deletion of linear lists (general linear lists, stacks, queues)
Traversal of binary trees (pre-order, in-order, post-order)
Traversal of graphs (depth-first, breadth-first)
Binary search, sorted binary trees, hash searching (methods for handling conflicts).
(2)
When analyzing something, you can look at it from different perspectives. Many times, it’s like life; you feel that the way you viewed problems as a child was naive, and now you see problems more comprehensively, and the methods are different. Why? It’s just growth, and it’s the same with algorithms. For example, writing a program may seem very simple, but there can be interesting ways to express it, and how to do it more efficiently, etc.
(3)
In college, solidify the basic professional courses, such as: data structures, discrete mathematics, operating systems, etc. When encountering some basic data structures and algorithms, such as searching and sorting, you should be able to write the corresponding code immediately based on the principles; this is how I understand it. For deeper topics, it is also based on your proficiency.
(4)
"Analysis of Algorithm and Data Structure Test Questions" 2nd Edition, Mechanical Industry Press
If you want to practice, there are many questions here to practice, but in reality, very few can be used unless you are doing some high-end stuff. However, you can also combine it with your own projects.
(5)
Data structures may not be used in daily life, but they can cultivate your awareness of efficiency when programming. A person who has studied data structures may write programs that are more efficient than someone who has not studied them.
(6)
Master the algorithms needed for ACM.
It should be noted that ACM competitions are highly competitive, so you should connect with your actual applications.
What suits you is good; some people are not suited for algorithms and prefer system architecture, so don’t be envious of what others have.
Play to your strengths; that is what is important.
Phase One: Practice classic commonly used algorithms, type each of the following algorithms ten to twenty times, while simplifying your code,
because they are so commonly used that you should practice until you can write them without thinking, finishing in 10-15 minutes, or even being able to type them with the monitor turned off.
- Shortest Path (Floyd, Dijkstra, Bellman-Ford)
- Minimum Spanning Tree (first write Prim, Kruskal requires union-find, which is harder to write)
- Large Numbers (high precision) addition, subtraction, multiplication, division
- Binary Search (code can be within five lines)
- Cross Product, check line segment intersection, then write a convex hull.
- BFS, DFS, while also mastering hash tables (must be familiar, flexible, and code should be simple)
- Mathematical concepts: Euclidean algorithm (within two lines), line segment intersection points, polygon area formulas.
- Call the system's qsort, many techniques, gradually master.
- Conversion between arbitrary bases.
Phase Two: Practice slightly more complex but still commonly used algorithms.
For example:
- Bipartite Graph Matching (Hungarian), Minimum Path Cover
- Network Flow, Minimum Cost Flow.
- Segment Tree.
- Union-Find.
- Familiarize yourself with various typical dynamic programming problems: LCS, Longest Increasing Subsequence, Triangulation, Memoization DP.
- Game Theory algorithms. Game trees, binary methods, etc.
- Maximum Clique, Maximum Independent Set.
- Determine if a point is inside a polygon.
- Difference Constraint System.
- Bidirectional BFS, A* algorithm, Minimum Dissipation Priority.
Relevant Knowledge
Graph Theory
Path Problems
0/1 Edge Weight Shortest Path
BFS
Non-negative Edge Weight Shortest Path (Dijkstra)
Characteristics of problems solvable by Dijkstra
Negative Edge Weight Shortest Path
Bellman-Ford
Yen's Optimization of Bellman-Ford
Difference Constraint System
Floyd
General Path Problems
Transitive Closure
Minimax Distance / Maximin Distance
Euler Path / Tour
Cycle-Cycle Algorithm
Euler Path / Tour of Mixed Graphs
Hamilton Path / Tour
Construction of Hamilton Path / Tour for Special Graphs
Spanning Tree Problems
Minimum Spanning Tree
k-th Smallest Spanning Tree
Optimal Ratio Spanning Tree
0/1 Fractional Knapsack
Degree Constrained Spanning Tree
Connectivity Problems
Powerful DFS Algorithms
Undirected Graph Connectivity
Cut Points
Cut Edges
Biconnected Components
Directed Graph Connectivity
Strongly Connected Components
2-SAT
Minimum Vertex Cover
Directed Acyclic Graph
Topological Sorting
Relationship between Directed Acyclic Graph and Dynamic Programming
Bipartite Graph Matching Problems
General Graph Problems and Conversion Ideas to Bipartite Graph Problems
Maximum Matching
Minimum Path Cover for Directed Graphs
Minimum Cover for 0/1 Matrices
Perfect Matching
Optimal Matching
Stable Marriage
Network Flow Problems
Simple Characteristics of Network Flow Models and Their Relationship with Linear Programming
Max Flow Min Cut Theorem
Maximum Flow Problems
Maximum Flow Problems with Upper and Lower Bounds
Circulation Flow
Minimum Cost Maximum Flow / Maximum Cost Maximum Flow
Properties and Determination of Chordal Graphs
Combinatorial Mathematics
Common Ideas for Solving Combinatorial Mathematics Problems
Approximation
Recursion / Dynamic Programming
Probability Problems
Polya's Theorem
Computational Geometry / Analytical Geometry
Core of Computational Geometry: Cross Product / Area
Main Force of Analytical Geometry: Complex Numbers
Basic Shapes
Points
Lines, Line Segments
Polygons
Convex Polygons / Convex Hulls
Introduction of Convex Hull Algorithms, Wrapping Method
Graham's Scan
Introduction of Horizontal Sequences, Patch for Collinear Convex Hulls
Perfect Convex Hull Algorithm
Related Determination
Intersection of Two Lines
Intersection of Two Line Segments
Determination of a Point Inside Any Polygon
Determination of a Point Inside a Convex Polygon
Classic Problems
Minimum Enclosing Circle
Approximate O(n) Minimum Enclosing Circle Algorithm
Diameter of a Point Set
Rotating Calipers, Antipodal Points
Triangulation of Polygons
Mathematics / Number Theory
Greatest Common Divisor
Euclidean Algorithm
Extended Euclidean Algorithm
Congruence Equations / Binary Linear Indeterminate Equations
Systems of Congruence Equations
Linear Systems of Equations
Gaussian Elimination
Solving Linear Systems over mod 2 Fields
Exact Solutions for Integer Coefficient Systems
Matrices
Calculation of Determinants
Using Matrix Multiplication to Quickly Calculate Recursion Relations
Fractions
Fraction Trees
Continued Fraction Approximations
Number Theory Calculations
Finding the Number of Divisors of N
Finding phi(N)
Finding the Sum of Divisors
Fast Number Theoretic Transform
……
Prime Number Problems
Probabilistic Primality Testing Algorithms
Probabilistic Factorization
Data Structures
Organizational Structures
Binary Heap
Leftist Tree
Binomial Tree
Winner Tree
Skip List
Style Icon
Skew Heap
Reap
Statistical Structures
Fenwick Tree
Virtual Binary Tree
Segment Tree
Rectangle Area Union
Circle Area Union
Relational Structures
Hash Tables
Union-Find
Application of Path Compression Ideas
Data Structures in STL
Vector
Deque
Set / Map
Dynamic Programming / Memoization
Differences in Thinking Between Dynamic Programming and Memoization
Longest Subsequence Series Problems
Longest Non-decreasing Subsequence
Longest Common Subsequence
Longest Common Non-decreasing Subsequence
Dynamic Programming Solutions for a Class of NP Problems
Tree Dynamic Programming
Knapsack Problems
Optimization of Dynamic Programming
Quadratic Inequality
Convexity of Functions
State Design
Planning Direction
Linear Programming
Common Ideas
Binary
Minimum Representation
Strings
KMP
Trie Structure
Suffix Tree/Suffix Array
LCA/RMQ
Finite State Automaton Theory
Sorting
Selection/Bubble
Quick Sort
Heap Sort
Merge Sort
Radix Sort
Topological Sort
Sorting Networks
Proficient in Data Structures and Common Algorithm Aggregation
(1)
It is impossible to remember so many algorithms completely.
Common algorithms can be written out directly.
Uncommon ones can be understood by looking at the book for 10 minutes (because they were memorized before).
For algorithms that were never memorized before, it is hard to say; difficult ones may take several days to study.
That should be enough.
The commonly used algorithms that should be proficient include:
Various sorting algorithms (insertion sort, bubble sort, selection sort, quick sort, heap sort, merge sort)
Insertion and deletion of linear lists (general linear lists, stacks, queues)
Traversal of binary trees (pre-order, in-order, post-order)
Traversal of graphs (depth-first, breadth-first)
Binary search, sorted binary trees, hash searching (methods for handling conflicts).
(2)
When analyzing something, you can look at it from different perspectives. Many times, it’s like life; you feel that the way you viewed problems as a child was naive, and now you see problems more comprehensively, and the methods are different. Why? It’s just growth, and it’s the same with algorithms. For example, writing a program may seem very simple, but there can be interesting ways to express it, and how to do it more efficiently, etc.
(3)
In college, solidify the basic professional courses, such as: data structures, discrete mathematics, operating systems, etc. When encountering some basic data structures and algorithms, such as searching and sorting, you should be able to write the corresponding code immediately based on the principles; this is how I understand it. For deeper topics, it is also based on your proficiency.
(4)
"Analysis of Algorithm and Data Structure Test Questions" 2nd Edition, Mechanical Industry Press
If you want to practice, there are many questions here to practice, but in reality, very few can be used unless you are doing some high-end stuff. However, you can also combine it with your own projects.
(5)
Data structures may not be used in daily life, but they can cultivate your awareness of efficiency when programming. A person who has studied data structures may write programs that are more efficient than someone who has not studied them.
(6)
Master the algorithms needed for ACM.
It should be noted that ACM competitions are highly competitive, so you should connect with your actual applications.
What suits you is good; some people are not suited for algorithms and prefer system architecture, so don’t be envious of what others have.
Play to your strengths; that is what is important.
Phase One: Practice classic commonly used algorithms, type each of the following algorithms ten to twenty times, while simplifying your code,
because they are so commonly used that you should practice until you can write them without thinking, finishing in 10-15 minutes, or even being able to type them with the monitor turned off.
- Shortest Path (Floyd, Dijkstra, Bellman-Ford)
- Minimum Spanning Tree (first write Prim, Kruskal requires union-find, which is harder to write)
- Large Numbers (high precision) addition, subtraction, multiplication, division
- Binary Search (code can be within five lines)
- Cross Product, check line segment intersection, then write a convex hull.
- BFS, DFS, while also mastering hash tables (must be familiar, flexible, and code should be simple)
- Mathematical concepts: Euclidean algorithm (within two lines), line segment intersection points, polygon area formulas.
- Call the system's qsort, many techniques, gradually master.
- Conversion between arbitrary bases.
Phase Two: Practice slightly more complex but still commonly used algorithms.
For example:
- Bipartite Graph Matching (Hungarian), Minimum Path Cover
- Network Flow, Minimum Cost Flow.
- Segment Tree.
- Union-Find.
- Familiarize yourself with various typical dynamic programming problems: LCS, Longest Increasing Subsequence, Triangulation, Memoization DP.
- Game Theory algorithms. Game trees, binary methods, etc.
- Maximum Clique, Maximum Independent Set.
- Determine if a point is inside a polygon.
- Difference Constraint System.
- Bidirectional BFS, A* algorithm, Minimum Dissipation Priority.
Relevant Knowledge
Graph Theory
Path Problems
0/1 Edge Weight Shortest Path
BFS
Non-negative Edge Weight Shortest Path (Dijkstra)
Characteristics of problems solvable by Dijkstra
Negative Edge Weight Shortest Path
Bellman-Ford
Yen's Optimization of Bellman-Ford
Difference Constraint System
Floyd
General Path Problems
Transitive Closure
Minimax Distance / Maximin Distance
Euler Path / Tour
Cycle-Cycle Algorithm
Euler Path / Tour of Mixed Graphs
Hamilton Path / Tour
Construction of Hamilton Path / Tour for Special Graphs
Spanning Tree Problems
Minimum Spanning Tree
k-th Smallest Spanning Tree
Optimal Ratio Spanning Tree
0/1 Fractional Knapsack
Degree Constrained Spanning Tree
Connectivity Problems
Powerful DFS Algorithms
Undirected Graph Connectivity
Cut Points
Cut Edges
Biconnected Components
Directed Graph Connectivity
Strongly Connected Components
2-SAT
Minimum Vertex Cover
Directed Acyclic Graph
Topological Sorting
Relationship between Directed Acyclic Graph and Dynamic Programming
Bipartite Graph Matching Problems
General Graph Problems and Conversion Ideas to Bipartite Graph Problems
Maximum Matching
Minimum Path Cover for Directed Graphs
Minimum Cover for 0/1 Matrices
Perfect Matching
Optimal Matching
Stable Marriage
Network Flow Problems
Simple Characteristics of Network Flow Models and Their Relationship with Linear Programming
Max Flow Min Cut Theorem
Maximum Flow Problems
Maximum Flow Problems with Upper and Lower Bounds
Circulation Flow
Minimum Cost Maximum Flow / Maximum Cost Maximum Flow
Properties and Determination of Chordal Graphs
Combinatorial Mathematics
Common Ideas for Solving Combinatorial Mathematics Problems
Approximation
Recursion / Dynamic Programming
Probability Problems
Polya's Theorem
Computational Geometry / Analytical Geometry
Core of Computational Geometry: Cross Product / Area
Main Force of Analytical Geometry: Complex Numbers
Basic Shapes
Points
Lines, Line Segments
Polygons
Convex Polygons / Convex Hulls
Introduction of Convex Hull Algorithms, Wrapping Method
Graham's Scan
Introduction of Horizontal Sequences, Patch for Collinear Convex Hulls
Perfect Convex Hull Algorithm
Related Determination
Intersection of Two Lines
Intersection of Two Line Segments
Determination of a Point Inside Any Polygon
Determination of a Point Inside a Convex Polygon
Classic Problems
Minimum Enclosing Circle
Approximate O(n) Minimum Enclosing Circle Algorithm
Diameter of a Point Set
Rotating Calipers, Antipodal Points
Triangulation of Polygons
Mathematics / Number Theory
Greatest Common Divisor
Euclidean Algorithm
Extended Euclidean Algorithm
Congruence Equations / Binary Linear Indeterminate Equations
Systems of Congruence Equations
Linear Systems of Equations
Gaussian Elimination
Solving Linear Systems over mod 2 Fields
Exact Solutions for Integer Coefficient Systems
Matrices
Calculation of Determinants
Using Matrix Multiplication to Quickly Calculate Recursion Relations
Fractions
Fraction Trees
Continued Fraction Approximations
Number Theory Calculations
Finding the Number of Divisors of N
Finding phi(N)
Finding the Sum of Divisors
Fast Number Theoretic Transform
……
Prime Number Problems
Probabilistic Primality Testing Algorithms
Probabilistic Factorization
Data Structures
Organizational Structures
Binary Heap
Leftist Tree
Binomial Tree
Winner Tree
Skip List
Style Icon
Skew Heap
Reap
Statistical Structures
Fenwick Tree
Virtual Binary Tree
Segment Tree
Rectangle Area Union
Circle Area Union
Relational Structures
Hash Tables
Union-Find
Application of Path Compression Ideas
Data Structures in STL
Vector
Deque
Set / Map
Dynamic Programming / Memoization
Differences in Thinking Between Dynamic Programming and Memoization
Longest Subsequence Series Problems
Longest Non-decreasing Subsequence
Longest Common Subsequence
Longest Common Non-decreasing Subsequence
Dynamic Programming Solutions for a Class of NP Problems
Tree Dynamic Programming
Knapsack Problems
Optimization of Dynamic Programming
Quadratic Inequality
Convexity of Functions
State Design
Planning Direction
Linear Programming
Common Ideas
Binary
Minimum Representation
Strings
KMP
Trie Structure
Suffix Tree/Suffix Array
LCA/RMQ
Finite State Automaton Theory
Sorting
Selection/Bubble
Quick Sort
Heap Sort
Merge Sort
Radix Sort
Topological Sort
Sorting Networks
Proficient in Data Structures and Common Algorithm Aggregation
(1)
It is impossible to remember so many algorithms completely.
Common algorithms can be written out directly.
Uncommon ones can be understood by looking at the book for 10 minutes (because they were memorized before).
For algorithms that were never memorized before, it is hard to say; difficult ones may take several days to study.
That should be enough.
The commonly used algorithms that should be proficient include:
Various sorting algorithms (insertion sort, bubble sort, selection sort, quick sort, heap sort, merge sort)
Insertion and deletion of linear lists (general linear lists, stacks, queues)
Traversal of binary trees (pre-order, in-order, post-order)
Traversal of graphs (depth-first, breadth-first)
Binary search, sorted binary trees, hash searching (methods for handling conflicts).
(2)
When analyzing something, you can look at it from different perspectives. Many times, it’s like life; you feel that the way you viewed problems as a child was naive, and now you see problems more comprehensively, and the methods are different. Why? It’s just growth, and it’s the same with algorithms. For example, writing a program may seem very simple, but there can be interesting ways to express it, and how to do it more efficiently, etc.
(3)
In college, solidify the basic professional courses, such as: data structures, discrete mathematics, operating systems, etc. When encountering some basic data structures and algorithms, such as searching and sorting, you should be able to write the corresponding code immediately based on the principles; this is how I understand it. For deeper topics, it is also based on your proficiency.
(4)
"Analysis of Algorithm and Data Structure Test Questions" 2nd Edition, Mechanical Industry Press
If you want to practice, there are many questions here to practice, but in reality, very few can be used unless you are doing some high-end stuff. However, you can also combine it with your own projects.
(5)
Data structures may not be used in daily life, but they can cultivate your awareness of efficiency when programming. A person who has studied data structures may write programs that are more efficient than someone who has not studied them.
(6)
Master the algorithms needed for ACM.
It should be noted that ACM competitions are highly competitive, so you should connect with your actual applications.
What suits you is good; some people are not suited for algorithms and prefer system architecture, so don’t be envious of what others have.
Play to your strengths; that is what is important.
Phase One: Practice classic commonly used algorithms, type each of the following algorithms ten to twenty times, while simplifying your code,
because they are so commonly used that you should practice until you can write them without thinking, finishing in 10-15 minutes, or even being able to type them with the monitor turned off.
- Shortest Path (Floyd, Dijkstra, Bellman-Ford)
- Minimum Spanning Tree (first write Prim, Kruskal requires union-find, which is harder to write)
- Large Numbers (high precision) addition, subtraction, multiplication, division
- Binary Search (code can be within five lines)
- Cross Product, check line segment intersection, then write a convex hull.
- BFS, DFS, while also mastering hash tables (must be familiar, flexible, and code should be simple)
- Mathematical concepts: Euclidean algorithm (within two lines), line segment intersection points, polygon area formulas.
- Call the system's qsort, many techniques, gradually master.
- Conversion between arbitrary bases.
Phase Two: Practice slightly more complex but still commonly used algorithms.
For example:
- Bipartite Graph Matching (Hungarian), Minimum Path Cover
- Network Flow, Minimum Cost Flow.
- Segment Tree.
- Union-Find.
- Familiarize yourself with various typical dynamic programming problems: LCS, Longest Increasing Subsequence, Triangulation, Memoization DP.
- Game Theory algorithms. Game trees, binary methods, etc.
- Maximum Clique, Maximum Independent Set.
- Determine if a point is inside a polygon.
- Difference Constraint System.
- Bidirectional BFS, A* algorithm, Minimum Dissipation Priority.
Relevant Knowledge
Graph Theory
Path Problems
0/1 Edge Weight Shortest Path
BFS
Non-negative Edge Weight Shortest Path (Dijkstra)
Characteristics of problems solvable by Dijkstra
Negative Edge Weight Shortest Path
Bellman-Ford
Yen's Optimization of Bellman-Ford
Difference Constraint System
Floyd
General Path Problems
Transitive Closure
Minimax Distance / Maximin Distance
Euler Path / Tour
Cycle-Cycle Algorithm
Euler Path / Tour of Mixed Graphs
Hamilton Path / Tour
Construction of Hamilton Path / Tour for Special Graphs
Spanning Tree Problems
Minimum Spanning Tree
k-th Smallest Spanning Tree
Optimal Ratio Spanning Tree
0/1 Fractional Knapsack
Degree Constrained Spanning Tree
Connectivity Problems
Powerful DFS Algorithms
Undirected Graph Connectivity
Cut Points
Cut Edges
Biconnected Components
Directed Graph Connectivity
Strongly Connected Components
2-SAT
Minimum Vertex Cover
Directed Acyclic Graph
Topological Sorting
Relationship between Directed Acyclic Graph and Dynamic Programming
Bipartite Graph Matching Problems
General Graph Problems and Conversion Ideas to Bipartite Graph Problems
Maximum Matching
Minimum Path Cover for Directed Graphs
Minimum Cover for 0/1 Matrices
Perfect Matching
Optimal Matching
Stable Marriage
Network Flow Problems
Simple Characteristics of Network Flow Models and Their Relationship with Linear Programming
Max Flow Min Cut Theorem
Maximum Flow Problems
Maximum Flow Problems with Upper and Lower Bounds
Circulation Flow
Minimum Cost Maximum Flow / Maximum Cost Maximum Flow
Properties and Determination of Chordal Graphs
Combinatorial Mathematics
Common Ideas for Solving Combinatorial Mathematics Problems
Approximation
Recursion / Dynamic Programming
Probability Problems
Polya's Theorem
Computational Geometry / Analytical Geometry
Core of Computational Geometry: Cross Product / Area
Main Force of Analytical Geometry: Complex Numbers
Basic Shapes
Points
Lines, Line Segments
Polygons
Convex Polygons / Convex Hulls
Introduction of Convex Hull Algorithms, Wrapping Method
Graham's Scan
Introduction of Horizontal Sequences, Patch for Collinear Convex Hulls
Perfect Convex Hull Algorithm
Related Determination
Intersection of Two Lines
Intersection of Two Line Segments
Determination of a Point Inside Any Polygon
Determination of a Point Inside a Convex Polygon
Classic Problems
Minimum Enclosing Circle
Approximate O(n) Minimum Enclosing Circle Algorithm
Diameter of a Point Set
Rotating Calipers, Antipodal Points
Triangulation of Polygons
Mathematics / Number Theory
Greatest Common Divisor
Euclidean Algorithm
Extended Euclidean Algorithm
Congruence Equations / Binary Linear Indeterminate Equations
Systems of Congruence Equations
Linear Systems of Equations
Gaussian Elimination
Solving Linear Systems over mod 2 Fields
Exact Solutions for Integer Coefficient Systems
Matrices
Calculation of Determinants
Using Matrix Multiplication to Quickly Calculate Recursion Relations
Fractions
Fraction Trees
Continued Fraction Approximations
Number Theory Calculations
Finding the Number of Divisors of N
Finding phi(N)
Finding the Sum of Divisors
Fast Number Theoretic Transform
……
Prime Number Problems
Probabilistic Primality Testing Algorithms
Probabilistic Factorization
Data Structures
Organizational Structures
Binary Heap
Leftist Tree
Binomial Tree
Winner Tree
Skip List
Style Icon
Skew Heap
Reap
Statistical Structures
Fenwick Tree
Virtual Binary Tree
Segment Tree
Rectangle Area Union
Circle Area Union
Relational Structures
Hash Tables
Union-Find
Application of Path Compression Ideas
Data Structures in STL
Vector
Deque
Set / Map
Dynamic Programming / Memoization
Differences in Thinking Between Dynamic Programming and Memoization
Longest Subsequence Series Problems
Longest Non-decreasing Subsequence
Longest Common Subsequence
Longest Common Non-decreasing Subsequence
Dynamic Programming Solutions for a Class of NP Problems
Tree Dynamic Programming
Knapsack Problems
Optimization of Dynamic Programming
Quadratic Inequality
Convexity of Functions
State Design
Planning Direction
Linear Programming
Common Ideas
Binary
Minimum Representation
Strings
KMP
Trie Structure
Suffix Tree/Suffix Array
LCA/RMQ
Finite State Automaton Theory
Sorting
Selection/Bubble
Quick Sort
Heap Sort
Merge Sort
Radix Sort
Topological Sort
Sorting Networks
Proficient in Data Structures and Common Algorithm Aggregation
(1)
It is impossible to remember so many algorithms completely.
Common algorithms can be written out directly.
Uncommon ones can be understood by looking at the book for 10 minutes (because they were memorized before).
For algorithms that were never memorized before, it is hard to say; difficult ones may take several days to study.
That should be enough.
The commonly used algorithms that should be proficient include:
Various sorting algorithms (insertion sort, bubble sort, selection sort, quick sort, heap sort, merge sort)
Insertion and deletion of linear lists (general linear lists, stacks, queues)
Traversal of binary trees (pre-order, in-order, post-order)
Traversal of graphs (depth-first, breadth-first)
Binary search, sorted binary trees, hash searching (methods for handling conflicts).
(2)
When analyzing something, you can look at it from different perspectives. Many times, it’s like life; you feel that the way you viewed problems as a child was naive, and now you see problems more comprehensively, and the methods are different. Why? It’s just growth, and it’s the same with algorithms. For example, writing a program may seem very simple, but there can be interesting ways to express it, and how to do it more efficiently, etc.
(3)
In college, solidify the basic professional courses, such as: data structures, discrete mathematics, operating systems, etc. When encountering some basic data structures and algorithms, such as searching and sorting, you should be able to write the corresponding code immediately based on the principles; this is how I understand it. For deeper topics, it is also based on your proficiency.
(4)
"Analysis of Algorithm and Data Structure Test Questions" 2nd Edition, Mechanical Industry Press
If you want to practice, there are many questions here to practice, but in reality, very few can be used unless you are doing some high-end stuff. However, you can also combine it with your own projects.
(5)
Data structures may not be used in daily life, but they can cultivate your awareness of efficiency when programming. A person who has studied data structures may write programs that are more efficient than someone who has not studied them.
(6)
Master the algorithms needed for ACM.
It should be noted that ACM competitions are highly competitive, so you should connect with your actual applications.
What suits you is good; some people are not suited for algorithms and prefer system architecture, so don’t be envious of what others have.
Play to your strengths; that is what is important.
Phase One: Practice classic commonly used algorithms, type each of the following algorithms ten to twenty times, while simplifying your code,
because they are so commonly used that you should practice until you can write them without thinking, finishing in 10-15 minutes, or even being able to type them with the monitor turned off.
- Shortest Path (Floyd, Dijkstra, Bellman-Ford)
- Minimum Spanning Tree (first write Prim, Kruskal requires union-find, which is harder to write)
- Large Numbers (high precision) addition, subtraction, multiplication, division
- Binary Search (code can be within five lines)
- Cross Product, check line segment intersection, then write a convex hull.
- BFS, DFS, while also mastering hash tables (must be familiar, flexible, and code should be simple)
- Mathematical concepts: Euclidean algorithm (within two lines), line segment intersection points, polygon area formulas.
- Call the system's qsort, many techniques, gradually master.
- Conversion between arbitrary bases.
Phase Two: Practice slightly more complex but still commonly used algorithms.
For example:
- Bipartite Graph Matching (Hungarian), Minimum Path Cover
- Network Flow, Minimum Cost Flow.
- Segment Tree.
- Union-Find.
- Familiarize yourself with various typical dynamic programming problems: LCS, Longest Increasing Subsequence, Triangulation, Memoization DP.
- Game Theory algorithms. Game trees, binary methods, etc.
- Maximum Clique, Maximum Independent Set.
- Determine if a point is inside a polygon.
- Difference Constraint System.
- Bidirectional BFS, A* algorithm, Minimum Dissipation Priority.
Relevant Knowledge
Graph Theory
Path Problems
0/1 Edge Weight Shortest Path
BFS
Non-negative Edge Weight Shortest Path (Dijkstra)
Characteristics of problems solvable by Dijkstra
Negative Edge Weight Shortest Path
Bellman-Ford
Yen's Optimization of Bellman-Ford
Difference Constraint System
Floyd
General Path Problems
Transitive Closure
Minimax Distance / Maximin Distance
Euler Path / Tour
Cycle-Cycle Algorithm
Euler Path / Tour of Mixed Graphs
Hamilton Path / Tour
Construction of Hamilton Path / Tour for Special Graphs
Spanning Tree Problems
Minimum Spanning Tree
k-th Smallest Spanning Tree
Optimal Ratio Spanning Tree
0/1 Fractional Knapsack
Degree Constrained Spanning Tree
Connectivity Problems
Powerful DFS Algorithms
Undirected Graph Connectivity
Cut Points
Cut Edges
Biconnected Components
Directed Graph Connectivity
Strongly Connected Components
2-SAT
Minimum Vertex Cover
Directed Acyclic Graph
Topological Sorting
Relationship between Directed Acyclic Graph and Dynamic Programming
Bipartite Graph Matching Problems
General Graph Problems and Conversion Ideas to Bipartite Graph Problems
Maximum Matching
Minimum Path Cover for Directed Graphs
Minimum Cover for 0/1 Matrices
Perfect Matching
Optimal Matching
Stable Marriage
Network Flow Problems
Simple Characteristics of Network Flow Models and Their Relationship with Linear Programming
Max Flow Min Cut Theorem
Maximum Flow Problems
Maximum Flow Problems with Upper and Lower Bounds
Circulation Flow
Minimum Cost Maximum Flow / Maximum Cost Maximum Flow
Properties and Determination of Chordal Graphs
Combinatorial Mathematics
Common Ideas for Solving Combinatorial Mathematics Problems
Approximation
Recursion / Dynamic Programming
Probability Problems
Polya's Theorem
Computational Geometry / Analytical Geometry
Core of Computational Geometry: Cross Product / Area
Main Force of Analytical Geometry: Complex Numbers
Basic Shapes
Points
Lines, Line Segments
Polygons
Convex Polygons / Convex Hulls
Introduction of Convex Hull Algorithms, Wrapping Method
Graham's Scan
Introduction of Horizontal Sequences, Patch for Collinear Convex Hulls
Perfect Convex Hull Algorithm
Related Determination
Intersection of Two Lines
Intersection of Two Line Segments
Determination of a Point Inside Any Polygon
Determination of a Point Inside a Convex Polygon
Classic Problems
Minimum Enclosing Circle
Approximate O(n) Minimum Enclosing Circle Algorithm
Diameter of a Point Set
Rotating Calipers, Antipodal Points
Triangulation of Polygons
Mathematics / Number Theory
Greatest Common Divisor
Euclidean Algorithm
Extended Euclidean Algorithm
Congruence Equations / Binary Linear Indeterminate Equations
Systems of Congruence Equations
Linear Systems of Equations
Gaussian Elimination
Solving Linear Systems over mod 2 Fields
Exact Solutions for Integer Coefficient Systems
Matrices
Calculation of Determinants
Using Matrix Multiplication to Quickly Calculate Recursion Relations
Fractions
Fraction Trees
Continued Fraction Approximations
Number Theory Calculations
Finding the Number of Divisors of N
Finding phi(N)
Finding the Sum of Divisors
Fast Number Theoretic Transform
……
Prime Number Problems
Probabilistic Primality Testing Algorithms
Probabilistic Factorization
Data Structures
Organizational Structures
Binary Heap
Leftist Tree
Binomial Tree
Winner Tree
Skip List
Style Icon
Skew Heap
Reap
Statistical Structures
Fenwick Tree
Virtual Binary Tree
Segment Tree
Rectangle Area Union
Circle Area Union
Relational Structures
Hash Tables
Union-Find
Application of Path Compression Ideas
Data Structures in STL
Vector
Deque
Set / Map
Dynamic Programming / Memoization
Differences in Thinking Between Dynamic Programming and Memoization
Longest Subsequence Series Problems
Longest Non-decreasing Subsequence
Longest Common Subsequence
Longest Common Non-decreasing Subsequence
Dynamic Programming Solutions for a Class of NP Problems
Tree Dynamic Programming
Knapsack Problems
Optimization of Dynamic Programming
Quadratic Inequality
Convexity of Functions
State Design
Planning Direction
Linear Programming
Common Ideas
Binary
Minimum Representation
Strings
KMP
Trie Structure
Suffix Tree/Suffix Array
LCA/RMQ
Finite State Automaton Theory
Sorting
Selection/Bubble
Quick Sort
Heap Sort
Merge Sort
Radix Sort
Topological Sort
Sorting Networks
Proficient in Data Structures and Common Algorithm Aggregation
(1)
It is impossible to remember so many algorithms completely.
Common algorithms can be written out directly.
Uncommon ones can be understood by looking at the book for 10 minutes (because they were memorized before).
For algorithms that were never memorized before, it is hard to say; difficult ones may take several days to study.
That should be enough.
The commonly used algorithms that should be proficient include:
Various sorting algorithms (insertion sort, bubble sort, selection sort, quick sort, heap sort, merge sort)
Insertion and deletion of linear lists (general linear lists, stacks, queues)
Traversal of binary trees (pre-order, in-order, post-order)
Traversal of graphs (depth-first, breadth-first)
Binary search, sorted binary trees, hash searching (methods for handling conflicts).
(2)
When analyzing something, you can look at it from different perspectives. Many times, it’s like life; you feel that the way you viewed problems as a child was naive, and now you see problems more comprehensively, and the methods are different. Why? It’s just growth, and it’s the same with algorithms. For example, writing a program may seem very simple, but there can be interesting ways to express it, and how to do it more efficiently, etc.
(3)
In college, solidify the basic professional courses, such as: data structures, discrete mathematics, operating systems, etc. When encountering some basic data structures and algorithms, such as searching and sorting, you should be able to write the corresponding code immediately based on the principles; this is how I understand it. For deeper topics, it is also based on your proficiency.
(4)
"Analysis of Algorithm and Data Structure Test Questions" 2nd Edition, Mechanical Industry Press
If you want to practice, there are many questions here to practice, but in reality, very few can be used unless you are doing some high-end stuff. However, you can also combine it with your own projects.
(5)
Data structures may not be used in daily life, but they can cultivate your awareness of efficiency when programming. A person who has studied data structures may write programs that are more efficient than someone who has not studied them.
(6)
Master the algorithms needed for ACM.
It should be noted that ACM competitions are highly competitive, so you should connect with your actual applications.
What suits you is good; some people are not suited for algorithms and prefer system architecture, so don’t be envious of what others have.
Play to your strengths; that is what is important.
Phase One: Practice classic commonly used algorithms, type each of the following algorithms ten to twenty times, while simplifying your code,
because they are so commonly used that you should practice until you can write them without thinking, finishing in 10-15 minutes, or even being able to type them with the monitor turned off.
- Shortest Path (Floyd, Dijkstra, Bellman-Ford)
- Minimum Spanning Tree (first write Prim, Kruskal requires union-find, which is harder to write)
- Large Numbers (high precision) addition, subtraction, multiplication, division
- Binary Search (code can be within five lines)
- Cross Product, check line segment intersection, then write a convex hull.
- BFS, DFS, while also mastering hash tables (must be familiar, flexible, and code should be simple)
- Mathematical concepts: Euclidean algorithm (within two lines), line segment intersection points, polygon area formulas.
- Call the system's qsort, many techniques, gradually master.
- Conversion between arbitrary bases.
Phase Two: Practice slightly more complex but still commonly used algorithms.
For example:
- Bipartite Graph Matching (Hungarian), Minimum Path Cover
- Network Flow, Minimum Cost Flow.
- Segment Tree.
- Union-Find.
- Familiarize yourself with various typical dynamic programming problems: LCS, Longest Increasing Subsequence, Triangulation, Memoization DP.
- Game Theory algorithms. Game trees, binary methods, etc.
- Maximum Clique, Maximum Independent Set.
- Determine if a point is inside a polygon.
- Difference Constraint System.
- Bidirectional BFS, A* algorithm, Minimum Dissipation Priority.
Relevant Knowledge
Graph Theory
Path Problems
0/1 Edge Weight Shortest Path
BFS
Non-negative Edge Weight Shortest Path (Dijkstra)
Characteristics of problems solvable by Dijkstra
Negative Edge Weight Shortest Path
Bellman-Ford
Yen's Optimization of Bellman-Ford
Difference Constraint System
Floyd
General Path Problems
Transitive Closure
Minimax Distance / Maximin Distance
Euler Path / Tour
Cycle-Cycle Algorithm
Euler Path / Tour of Mixed Graphs
Hamilton Path / Tour
Construction of Hamilton Path / Tour for Special Graphs
Spanning Tree Problems
Minimum Spanning Tree
k-th Smallest Spanning Tree
Optimal Ratio Spanning Tree
0/1 Fractional Knapsack
Degree Constrained Spanning Tree
Connectivity Problems
Powerful DFS Algorithms
Undirected Graph Connectivity
Cut Points
Cut Edges
Biconnected Components
Directed Graph Connectivity
Strongly Connected Components
2-SAT
Minimum Vertex Cover
Directed Acyclic Graph
Topological Sorting
Relationship between Directed Acyclic Graph and Dynamic Programming
Bipartite Graph Matching Problems
General Graph Problems and Conversion Ideas to Bipartite Graph Problems
Maximum Matching
Minimum Path Cover for Directed Graphs
Minimum Cover for 0/1 Matrices
Perfect Matching
Optimal Matching
Stable Marriage
Network Flow Problems
Simple Characteristics of Network Flow Models and Their Relationship with Linear Programming
Max Flow Min Cut Theorem
Maximum Flow Problems
Maximum Flow Problems with Upper and Lower Bounds
Circulation Flow
Minimum Cost Maximum Flow / Maximum Cost Maximum Flow
Properties and Determination of Chordal Graphs
Combinatorial Mathematics
Common Ideas for Solving Combinatorial Mathematics Problems
Approximation
Recursion / Dynamic Programming
Probability Problems
Polya's Theorem
Computational Geometry / Analytical Geometry
Core of Computational Geometry: Cross Product / Area
Main Force of Analytical Geometry: Complex Numbers
Basic Shapes
Points
Lines, Line Segments
Polygons
Convex Polygons / Convex Hulls
Introduction of Convex Hull Algorithms, Wrapping Method
Graham's Scan
Introduction of Horizontal Sequences, Patch for Collinear Convex Hulls
Perfect Convex Hull Algorithm
Related Determination
Intersection of Two Lines
Intersection of Two Line Segments
Determination of a Point Inside Any Polygon
Determination of a Point Inside a Convex Polygon
Classic Problems
Minimum Enclosing Circle
Approximate O(n) Minimum Enclosing Circle Algorithm
Diameter of a Point Set
Rotating Calipers, Antipodal Points
Triangulation of Polygons
Mathematics / Number Theory
Greatest Common Divisor
Euclidean Algorithm
Extended Euclidean Algorithm
Congruence Equations / Binary Linear Indeterminate Equations
Systems of Congruence Equations
Linear Systems of Equations
Gaussian Elimination
Solving Linear Systems over mod 2 Fields
Exact Solutions for Integer Coefficient Systems
Matrices
Calculation of Determinants
Using Matrix Multiplication to Quickly Calculate Recursion Relations
Fractions
Fraction Trees
Continued Fraction Approximations
Number Theory Calculations
Finding the Number of Divisors of N
Finding phi(N)
Finding the Sum of Divisors
Fast Number Theoretic Transform
……
Prime Number Problems
Probabilistic Primality Testing Algorithms
Probabilistic Factorization
Data Structures
Organizational Structures
Binary Heap
Leftist Tree
Binomial Tree
Winner Tree
Skip List
Style Icon
Skew Heap
Reap
Statistical Structures
Fenwick Tree
Virtual Binary Tree
Segment Tree
Rectangle Area Union
Circle Area Union
Relational Structures
Hash Tables
Union-Find
Application of Path Compression Ideas
Data Structures in STL
Vector
Deque
Set / Map
Dynamic Programming / Memoization
Differences in Thinking Between Dynamic Programming and Memoization
Longest Subsequence Series Problems
Longest Non-decreasing Subsequence
Longest Common Subsequence
Longest Common Non-decreasing Subsequence
Dynamic Programming Solutions for a Class of NP Problems
Tree Dynamic Programming
Knapsack Problems
Optimization of Dynamic Programming
Quadratic Inequality
Convexity of Functions
State Design
Planning Direction
Linear Programming
Common Ideas
Binary
Minimum Representation
Strings
KMP
Trie Structure
Suffix Tree/Suffix Array
LCA/RMQ
Finite State Automaton Theory
Sorting
Selection/Bubble
Quick Sort
Heap Sort
Merge Sort
Radix Sort
Topological Sort
Sorting Networks
Proficient in Data Structures and Common Algorithm Aggregation
(1)
It is impossible to remember so many algorithms completely.
Common algorithms can be written out directly.
Uncommon ones can be understood by looking at the book for 10 minutes (because they were memorized before).
For algorithms that were never memorized before, it is hard to say; difficult ones may take several days to study.
That should be enough.
The commonly used algorithms that should be proficient include:
Various sorting algorithms (insertion sort, bubble sort, selection sort, quick sort, heap sort, merge sort)
Insertion and deletion of linear lists (general linear lists, stacks, queues)
Traversal of binary trees (pre-order, in-order, post-order)
Traversal of graphs (depth-first, breadth-first)
Binary search, sorted binary trees, hash searching (methods for handling conflicts).
(2)
When analyzing something, you can look at it from different perspectives. Many times, it’s like life; you feel that the way you viewed problems as a child was naive, and now you see problems more comprehensively, and the methods are different. Why? It’s just growth, and it’s the same with algorithms. For example, writing a program may seem very simple, but there can be interesting ways to express it, and how to do it more efficiently, etc.
(3)
In college, solidify the basic professional courses, such as: data structures, discrete mathematics, operating systems, etc. When encountering some basic data structures and algorithms, such as searching and sorting, you should be able to write the corresponding code immediately based on the principles; this is how I understand it. For deeper topics, it is also based on your proficiency.
(4)
"Analysis of Algorithm and Data Structure Test Questions" 2nd Edition, Mechanical Industry Press
If you want to practice, there are many questions here to practice, but in reality, very few can be used unless you are doing some high-end stuff. However, you can also combine it with your own projects.
(5)
Data structures may not be used in daily life, but they can cultivate your awareness of efficiency when programming. A person who has studied data structures may write programs that are more efficient than someone who has not studied them.
(6)
Master the algorithms needed for ACM.
It should be noted that ACM competitions are highly competitive, so you should connect with your actual applications.
What suits you is good; some people are not suited for algorithms and prefer system architecture, so don’t be envious of what others have.
Play to your strengths; that is what is important.
Phase One: Practice classic commonly used algorithms, type each of the following algorithms ten to twenty times, while simplifying your code,
because they are so commonly used that you should practice until you can write them without thinking, finishing in 10-15 minutes, or even being able to type them with the monitor turned off.
- Shortest Path (Floyd, Dijkstra, Bellman-Ford)
- Minimum Spanning Tree (first write Prim, Kruskal requires union-find, which is harder to write)
- Large Numbers (high precision) addition, subtraction, multiplication, division
- Binary Search (code can be within five lines)
- Cross Product, check line segment intersection, then write a convex hull.
- BFS, DFS, while also mastering hash tables (must be familiar, flexible, and code should be simple)
- Mathematical concepts: Euclidean algorithm (within two lines), line segment intersection points, polygon area formulas.
- Call the system's qsort, many techniques, gradually master.
- Conversion between arbitrary bases.
Phase Two: Practice slightly more complex but still commonly used algorithms.
For example:
- Bipartite Graph Matching (Hungarian), Minimum Path Cover
- Network Flow, Minimum Cost Flow.
- Segment Tree.
- Union-Find.
- Familiarize yourself with various typical dynamic programming problems: LCS, Longest Increasing Subsequence, Triangulation, Memoization DP.
- Game Theory algorithms. Game trees, binary methods, etc.
- Maximum Clique, Maximum Independent Set.
- Determine if a point is inside a polygon.
- Difference Constraint System.
- Bidirectional BFS, A* algorithm, Minimum Dissipation Priority.
Relevant Knowledge
Graph Theory
Path Problems
0/1 Edge Weight Shortest Path
BFS
Non-negative Edge Weight Shortest Path (Dijkstra)
Characteristics of problems solvable by Dijkstra
Negative Edge Weight Shortest Path
Bellman-Ford
Yen's Optimization of Bellman-Ford
Difference Constraint System
Floyd
General Path Problems
Transitive Closure
Minimax Distance / Maximin Distance
Euler Path / Tour
Cycle-Cycle Algorithm
Euler Path / Tour of Mixed Graphs
Hamilton Path / Tour
Construction of Hamilton Path / Tour for Special Graphs
Spanning Tree Problems
Minimum Spanning Tree
k-th Smallest Spanning Tree
Optimal Ratio Spanning Tree
0/1 Fractional Knapsack
Degree Constrained Spanning Tree
Connectivity Problems
Powerful DFS Algorithms
Undirected Graph Connectivity
Cut Points
Cut Edges
Biconnected Components
Directed Graph Connectivity
Strongly Connected Components
2-SAT
Minimum Vertex Cover
Directed Acyclic Graph
Topological Sorting
Relationship between Directed Acyclic Graph and Dynamic Programming
Bipartite Graph Matching Problems
General Graph Problems and Conversion Ideas to Bipartite Graph Problems
Maximum Matching
Minimum Path Cover for Directed Graphs
Minimum Cover for 0/1 Matrices
Perfect Matching
Optimal Matching
Stable Marriage
Network Flow Problems
Simple Characteristics of Network Flow Models and Their Relationship with Linear Programming
Max Flow Min Cut Theorem
Maximum Flow Problems
Maximum Flow Problems with Upper and Lower Bounds
Circulation Flow
Minimum Cost Maximum Flow / Maximum Cost Maximum Flow
Properties and Determination of Chordal Graphs
Combinatorial Mathematics
Common Ideas for Solving Combinatorial Mathematics Problems
Approximation
Recursion / Dynamic Programming
Probability Problems
Polya's Theorem
Computational Geometry / Analytical Geometry
Core of Computational Geometry: Cross Product / Area
Main Force of Analytical Geometry: Complex Numbers
Basic Shapes
Points
Lines, Line Segments
Polygons
Convex Polygons / Convex Hulls
Introduction of Convex Hull Algorithms, Wrapping Method
Graham's Scan
Introduction of Horizontal Sequences, Patch for Collinear Convex Hulls
Perfect Convex Hull Algorithm
Related Determination
Intersection of Two Lines
Intersection of Two Line Segments
Determination of a Point Inside Any Polygon
Determination of a Point Inside a Convex Polygon
Classic Problems
Minimum Enclosing Circle
Approximate O(n) Minimum Enclosing Circle Algorithm
Diameter of a Point Set
Rotating Calipers, Antipodal Points
Triangulation of Polygons
Mathematics / Number Theory
Greatest Common Divisor
Euclidean Algorithm
Extended Euclidean Algorithm
Congruence Equations / Binary Linear Indeterminate Equations
Systems of Congruence Equations
Linear Systems of Equations
Gaussian Elimination
Solving Linear Systems over mod 2 Fields
Exact Solutions for Integer Coefficient Systems
Matrices
Calculation of Determinants
Using Matrix Multiplication to Quickly Calculate Recursion Relations
Fractions
Fraction Trees
Continued Fraction Approximations
Number Theory Calculations
Finding the Number of Divisors of N
Finding phi(N)
Finding the Sum of Divisors
Fast Number Theoretic Transform
……
Prime Number Problems
Probabilistic Primality Testing Algorithms
Probabilistic Factorization
Data Structures
Organizational Structures
Binary Heap
Leftist Tree
Binomial Tree
Winner Tree
Skip List
Style Icon
Skew Heap
Reap
Statistical Structures
Fenwick Tree
Virtual Binary Tree
Segment Tree
Rectangle Area Union
Circle Area Union
Relational Structures
Hash Tables
Union-Find
Application of Path Compression Ideas
Data Structures in STL
Vector
Deque
Set / Map
Dynamic Programming / Memoization
Differences in Thinking Between Dynamic Programming and Memoization
Longest Subsequence Series Problems
Longest Non-decreasing Subsequence
Longest Common Subsequence
Longest Common Non-decreasing Subsequence
Dynamic Programming Solutions for a Class of NP Problems
Tree Dynamic Programming
Knapsack Problems
Optimization of Dynamic Programming
Quadratic Inequality
Convexity of Functions
State Design
Planning Direction
Linear Programming
Common Ideas
Binary
Minimum Representation
Strings
KMP
Trie Structure
Suffix Tree/Suffix Array
LCA/RMQ
Finite State Automaton Theory
Sorting
Selection/Bubble
Quick Sort
Heap Sort
Merge Sort
Radix Sort
Topological Sort
Sorting Networks
Proficient in Data Structures and Common Algorithm Aggregation
(1)
It is impossible to remember so many algorithms completely.
Common algorithms can be written out directly.
Uncommon ones can be understood by looking at the book for 10 minutes (because they were memorized before).
For algorithms that were never memorized before, it is hard to say; difficult ones may take several days to study.
That should be enough.
The commonly used algorithms that should be proficient include:
Various sorting algorithms (insertion sort, bubble sort, selection sort, quick sort, heap sort, merge sort)
Insertion and deletion of linear lists (general linear lists, stacks, queues)
Traversal of binary trees (pre-order, in-order, post-order)
Traversal of graphs (depth-first, breadth-first)
Binary search, sorted binary trees, hash searching (methods for handling conflicts).
(2)
When analyzing something, you can look at it from different perspectives. Many times, it’s like life; you feel that the way you viewed problems as a child was naive, and now you see problems more comprehensively, and the methods are different. Why? It’s just growth, and it’s the same with algorithms. For example, writing a program may seem very simple, but there can be interesting ways to express it, and how to do it more efficiently, etc.
(3)
In college, solidify the basic professional courses, such as: data structures, discrete mathematics, operating systems, etc. When encountering some basic data structures and algorithms, such as searching and sorting, you should be able to write the corresponding code immediately based on the principles; this is how I understand it. For deeper topics, it is also based on your proficiency.
(4)
"Analysis of Algorithm and Data Structure Test Questions" 2nd Edition, Mechanical Industry Press
If you want to practice, there are many questions here to practice, but in reality, very few can be used unless you are doing some high-end stuff. However, you can also combine it with your own projects.
(5)
Data structures may not be used in daily life, but they can cultivate your awareness of efficiency when programming. A person who has studied data structures may write programs that are more efficient than someone who has not studied them.
(6)
Master the algorithms needed for ACM.
It should be noted that ACM competitions are highly competitive, so you should connect with your actual applications.
What suits you is good; some people are not suited for algorithms and prefer system architecture, so don’t be envious of what others have.
Play to your strengths; that is what is important.
Phase One: Practice classic commonly used algorithms, type each of the following algorithms ten to twenty times, while simplifying your code,
because they are so commonly used that you should practice until you can write them without thinking, finishing in 10-15 minutes, or even being able to type them with the monitor turned off.
- Shortest Path (Floyd, Dijkstra, Bellman-Ford)
- Minimum Spanning Tree (first write Prim, Kruskal requires union-find, which is harder to write)
- Large Numbers (high precision) addition, subtraction, multiplication, division
- Binary Search (code can be within five lines)
- Cross Product, check line segment intersection, then write a convex hull.
- BFS, DFS, while also mastering hash tables (must be familiar, flexible, and code should be simple)
- Mathematical concepts: Euclidean algorithm (within two lines), line segment intersection points, polygon area formulas.
- Call the system's qsort, many techniques, gradually master.
- Conversion between arbitrary bases.
Phase Two: Practice slightly more complex but still commonly used algorithms.
For example:
- Bipartite Graph Matching (Hungarian), Minimum Path Cover
- Network Flow, Minimum Cost Flow.
- Segment Tree.
- Union-Find.
- Familiarize yourself with various typical dynamic programming problems: LCS, Longest Increasing Subsequence, Triangulation, Memoization DP.
- Game Theory algorithms. Game trees, binary methods, etc.
- Maximum Clique, Maximum Independent Set.
- Determine if a point is inside a polygon.
- Difference Constraint System.
- Bidirectional BFS, A* algorithm, Minimum Dissipation Priority.
Relevant Knowledge
Graph Theory
Path Problems
0/1 Edge Weight Shortest Path
BFS
Non-negative Edge Weight Shortest Path (Dijkstra)
Characteristics of problems solvable by Dijkstra
Negative Edge Weight Shortest Path
Bellman-Ford
Yen's Optimization of Bellman-Ford
Difference Constraint System
Floyd
General Path Problems
Transitive Closure
Minimax Distance / Maximin Distance
Euler Path / Tour
Cycle-Cycle Algorithm
Euler Path / Tour of Mixed Graphs
Hamilton Path / Tour
Construction of Hamilton Path / Tour for Special Graphs
Spanning Tree Problems
Minimum Spanning Tree
k-th Smallest Spanning Tree
Optimal Ratio Spanning Tree
0/1 Fractional Knapsack
Degree Constrained Spanning Tree
Connectivity Problems
Powerful DFS Algorithms
Undirected Graph Connectivity
Cut Points
Cut Edges
Biconnected Components
Directed Graph Connectivity
Strongly Connected Components
2-SAT
Minimum Vertex Cover
Directed Acyclic Graph
Topological Sorting
Relationship between Directed Acyclic Graph and Dynamic Programming
Bipartite Graph Matching Problems
General Graph Problems and Conversion Ideas to Bipartite Graph Problems
Maximum Matching
Minimum Path Cover for Directed Graphs
Minimum Cover for 0/1 Matrices
Perfect Matching
Optimal Matching
Stable Marriage
Network Flow Problems
Simple Characteristics of Network Flow Models and Their Relationship with Linear Programming
Max Flow Min Cut Theorem
Maximum Flow Problems
Maximum Flow Problems with Upper and Lower Bounds
Circulation Flow
Minimum Cost Maximum Flow / Maximum Cost Maximum Flow
Properties and Determination of Chordal Graphs
Combinatorial Mathematics
Common Ideas for Solving Combinatorial Mathematics Problems
Approximation
Recursion / Dynamic Programming
Probability Problems
Polya's Theorem
Computational Geometry / Analytical Geometry
Core of Computational Geometry: Cross Product / Area
Main Force of Analytical Geometry: Complex Numbers
Basic Shapes
Points
Lines, Line Segments
Polygons
Convex Polygons / Convex Hulls
Introduction of Convex Hull Algorithms, Wrapping Method
Graham's Scan
Introduction of Horizontal Sequences, Patch for Collinear Convex Hulls
Perfect Convex Hull Algorithm
Related Determination
Intersection of Two Lines
Intersection of Two Line Segments
Determination of a Point Inside Any Polygon
Determination of a Point Inside a Convex Polygon
Classic Problems
Minimum Enclosing Circle
Approximate O(n) Minimum Enclosing Circle Algorithm
Diameter of a Point Set
Rotating Calipers, Antipodal Points
Triangulation of Polygons
Mathematics / Number Theory
Greatest Common Divisor
Euclidean Algorithm
Extended Euclidean Algorithm
Congruence Equations / Binary Linear Indeterminate Equations
Systems of Congruence Equations
Linear Systems of Equations
Gaussian Elimination
Solving Linear Systems over mod 2 Fields
Exact Solutions for Integer Coefficient Systems
Matrices
Calculation of Determinants
Using Matrix Multiplication to Quickly Calculate Recursion Relations
Fractions
Fraction Trees
Continued Fraction Approximations
Number Theory Calculations
Finding the Number of Divisors of N
Finding phi(N)
Finding the Sum of Divisors
Fast Number Theoretic Transform
……
Prime Number Problems
Probabilistic Primality Testing Algorithms
Probabilistic Factorization
Data Structures
Organizational Structures
Binary Heap
Leftist Tree
Binomial Tree
Winner Tree
Skip List
Style Icon
Skew Heap
Reap
Statistical Structures
Fenwick Tree
Virtual Binary Tree
Segment Tree
Rectangle Area Union
Circle Area Union
Relational Structures
Hash Tables
Union-Find
Application of Path Compression Ideas
Data Structures in STL
Vector
Deque
Set / Map
Dynamic Programming / Memoization
Differences in Thinking Between Dynamic Programming and Memoization
Longest Subsequence Series Problems
Longest Non-decreasing Subsequence
Longest Common Subsequence
Longest Common Non-decreasing Subsequence
Dynamic Programming Solutions for a Class of NP Problems
Tree Dynamic Programming
Knapsack Problems
Optimization of Dynamic Programming
Quadratic Inequality
Convexity of Functions
State Design
Planning Direction
Linear Programming
Common Ideas
Binary
Minimum Representation
Strings
KMP
Trie Structure
Suffix Tree/Suffix Array
LCA/RMQ
Finite State Automaton Theory
Sorting
Selection/Bubble
Quick Sort
Heap Sort
Merge Sort
Radix Sort
Topological Sort
Sorting Networks
Proficient in Data Structures and Common Algorithm Aggregation
(1)
It is impossible to remember so many algorithms completely.
Common algorithms can be written out directly.
Uncommon ones can be understood by looking at the book for 10 minutes (because they were memorized before).
For algorithms that were never memorized before, it is hard to say; difficult ones may take several days to study.
That should be enough.
The commonly used algorithms that should be proficient include:
Various sorting algorithms (insertion sort, bubble sort, selection sort, quick sort, heap sort, merge sort)
Insertion and deletion of linear lists (general linear lists, stacks, queues)
Traversal of binary trees (pre-order, in-order, post-order)
Traversal of graphs (depth-first, breadth-first)
Binary search, sorted binary trees, hash searching (methods for handling conflicts).
(2)
When analyzing something, you can look at it from different perspectives. Many times, it’s like life; you feel that the way you viewed problems as a child was naive, and now you see problems more comprehensively, and the methods are different. Why? It’s just growth, and it’s the same with algorithms. For example, writing a program may seem very simple, but there can be interesting ways to express it, and how to do it more efficiently, etc.
(3)
In college, solidify the basic professional courses, such as: data structures, discrete mathematics, operating systems, etc. When encountering some basic data structures and algorithms, such as searching and sorting, you should be able to write the corresponding code immediately based on the principles; this is how I understand it. For deeper topics, it is also based on your proficiency.
(4)
"Analysis of Algorithm and Data Structure Test Questions" 2nd Edition, Mechanical Industry Press
If you want to practice, there are many questions here to practice, but in reality, very few can be used unless you are doing some high-end stuff. However, you can also combine it with your own projects.
(5)
Data structures may not be used in daily life, but they can cultivate your awareness of efficiency when programming. A person who has studied data structures may write programs that are more efficient than someone who has not studied them.
(6)
Master the algorithms needed for ACM.
It should be noted that ACM competitions are highly competitive, so you should connect with your actual applications.
What suits you is good; some people are not suited for algorithms and prefer system architecture, so don’t be envious of what others have.
Play to your strengths; that is what is important.
Phase One: Practice classic commonly used algorithms, type each of the following algorithms ten to twenty times, while simplifying your code,
because they are so commonly used that you should practice until you can write them without thinking, finishing in 10-15 minutes, or even being able to type them with the monitor turned off.
- Shortest Path (Floyd, Dijkstra, Bellman-Ford)
- Minimum Spanning Tree (first write Prim, Kruskal requires union-find, which is harder to write)
- Large Numbers (high precision) addition, subtraction, multiplication, division
- Binary Search (code can be within five lines)
- Cross Product, check line segment intersection, then write a convex hull.
- BFS, DFS, while also mastering hash tables (must be familiar, flexible, and code should be simple)
- Mathematical concepts: Euclidean algorithm (within two lines), line segment intersection points, polygon area formulas.
- Call the system's qsort, many techniques, gradually master.
- Conversion between arbitrary bases.
Phase Two: Practice slightly more complex but still commonly used algorithms.
For example:
- Bipartite Graph Matching (Hungarian), Minimum Path Cover
- Network Flow, Minimum Cost Flow.
- Segment Tree.
- Union-Find.
- Familiarize yourself with various typical dynamic programming problems: LCS, Longest Increasing Subsequence, Triangulation, Memoization DP.
- Game Theory algorithms. Game trees, binary methods, etc.
- Maximum Clique, Maximum Independent Set.
- Determine if a point is inside a polygon.
- Difference Constraint System.
- Bidirectional BFS, A* algorithm, Minimum Dissipation Priority.
Relevant Knowledge
Graph Theory
Path Problems
0/1 Edge Weight Shortest Path
BFS
Non-negative Edge Weight Shortest Path (Dijkstra)
Characteristics of problems solvable by Dijkstra
Negative Edge Weight Shortest Path
Bellman-Ford
Yen's Optimization of Bellman-Ford
Difference Constraint System
Floyd
General Path Problems
Transitive Closure
Minimax Distance / Maximin Distance
Euler Path / Tour
Cycle-Cycle Algorithm
Euler Path / Tour of Mixed Graphs
Hamilton Path / Tour
Construction of Hamilton Path / Tour for Special Graphs
Spanning Tree Problems
Minimum Spanning Tree