There are zero or more external quantities as inputs to the algorithm

The algorithm produces at least one quantity as output

Each instruction that makes up the algorithm is clear and unambiguous

Each instruction in the algorithm has a limited number of executions, and the time to execute each instruction is also limited.

· Closer to algorithmic language, easy to learn and master

· Provides a structured programming environment and tools, making the program more readable, maintainable and reliable.

· Does not depend on machine language, has little to do with hardware, has good portability and high reuse rate

· High degree of automation and short development cycle

· Separate the top-level design of the algorithm from the underlying implementation, without having to consider the underlying implementation

· Algorithm design is separated from data structure design, and algorithm efficiency is optimized.

· Is the meaning of each sentence or word in the question clear?

· What information has been given

· What results do you want to find?

· Whether the information given has redundant parts

· Is there any hidden information?

· Whether certain assumptions have been made

...

· What is the mathematical model that best fits this problem?

· Are there any other problems similar to this that have been solved?

...

· Provide proofs for each step, especially the conditions and lemmas that exist before and after the execution of this step

· Provide evidence that the algorithm will terminate

· The memory space and running time required by the algorithm need to be estimated or bounded

· Ability to use quantitative criteria to compare the efficiency of different algorithms for the same problem

(1) 4 aspects of experimental testing

(2) Data analysis

Content includes: 1. Problem description and analysis 2. Modeling and Solving 3. Algorithm design and correctness proof process 4. Algorithm complexity analysis 5. Test result records and analysis reports 6. Input/output requirements and format description, etc.

Let T(N, I) represent the time complexity of algorithm A on an abstract computer. in: · N: the size of the problem to be solved DN: The set of all possible inputs of size N · P(DN): Probability distribution of DN · I: input to the algorithm

· Worst case scenario:

· Best case scenario:

· Average situation:

(1) Question

(2) answer

An algorithm that calls itself directly or indirectly is called a recursive algorithm. A function defined in terms of itself is called a recursive function.

(1) Factorial n!

(2) Fibonacci sequence

(3) Ackerman function

(1) Arrangement problem

(2) Integer division problem

(3) Hanoi Tower Problem

(1) Divide large problems that are difficult to solve directly into several sub-problems

(2) Solve each sub-problem separately

(3) Then merge the solutions to the sub-problems to get the solution to the big problem

1. Common pattern code

2. Description

(1) Premise

(2) Recursion relationship

(3) Solve

(4) Supplement

divide-and-conquer(P) { if ( | P | <= n0) adhoc(P); //Solve small-scale problems //!1: DIVIDE: Decompose the problem divide P into smaller subinstances P1,P2,...,Pk; //!2: CONQUER: Solve each sub-problem recursively for (i=1,i<=k,i) yi = divide-and-conquer(Pi); //!3: MERGE: Merge the solutions of each sub-problem into the solution of the original problem return merge(y1,...,yk); }

The binary search algorithm is a typical example of using the divide-and-conquer strategy. This method makes good use of the condition that n elements have been sorted, reducing the time complexity from O(n) for sequential search to O(logn)

· Non-recursive

· recursion

Usually, when analyzing algorithm complexity, addition and multiplication operations are treated as basic operations. However, in some cases, we have to deal with very large integers, which cannot be represented directly in the computer, so we need to use software methods to implement the calculation of large integers. Assume that X and Y are both n-bit binary large integers, and now calculate their product. For simplicity, n is a power of 2.

· Divide n-bit binary integers X and Y into 2 segments, each segment is n/2 bits long, as shown in the figure:

· From this, we can get:

· Write the product of X and Y in the following form:

· Therefore, each calculation only needs to do 3 multiplications of n/2-digit integers, 6 additions and subtractions, and 2 shifts.

In the process of calculating matrix multiplication, we remember two n-order matrices as A and B, and the product is C. Then calculating each element C[i][j] of C requires n multiplication operations and n - 1 addition operations. Therefore, the calculation time required to calculate n2 elements of C is O(n3), which obviously needs improvement. To simplify the problem, let us write n as a power of 2.

· Divide each matrix in matrices A, B and C into 4 sub-matrices of equal size, as shown in the figure:

· In order to reduce the multiplication calculation, we first perform the following 7 calculations:

· Then, we express Cij as follows:

In a chessboard consisting of 2k·2k squares, there is exactly one square that is different from the other squares. This square is called a special square, and the chessboard is a special chessboard. We are required to use 4 different shapes of L-shaped dominoes to cover the non-special squares on the given special chessboard, and the coverage is not allowed to be repeated.

· Divide the 2k·2k chessboard into four 2k-1·2k-1 sub-boards, so the special square must be located on one of the sub-boards, leaving three sub-boards without special squares:

· We use an L-shaped domino to cover the intersection of the three sub-boards, as shown in the picture:

· Repeat until it is reduced to a 1·1 chessboard

public void chessBoard(int tr, int tc, int dr, int dc, int size) //tr:row, tc:column { if (size == 1) return; int t = tile, // L-shaped tile number s = size/2; // Split the chessboard if (dr < tr s && dc < tc s) // if-else statement processes the upper left corner chessboard chessBoard(tr, tc, dr, dc, s); // The special square is on this chessboard else {//There are no special squares on this board board[tr s - 1][tc s - 1] = t; // Cover the lower right corner with L-shaped dominoes numbered t chessBoard(tr, tc, tr s-1, tc s-1, s); // Cover the remaining squares } if (dr < tr s && dc >= tc s) // if-else statement processes the upper right corner chessboard chessBoard(tr, tc s, dr, dc, s); // The special square is on this chessboard else {//There are no special squares on this board board[tr s - 1][tc s] = t; // Cover the lower left corner with L-shaped dominoes numbered t chessBoard(tr, tc s, tr s-1, tc s, s); // Cover the remaining squares } if (dr >= tr s && dc < tc s) // if-else statement processes the lower left corner chessboard chessBoard(tr s, tc, dr, dc, s); // The special square is on this chessboard else {//There are no special squares on this board board[tr s][tc s - 1] = t; // Cover the upper right corner with L-shaped dominoes of size t chessBoard(tr s, tc, tr s, tc s-1, s); // Cover the remaining squares } if (dr >= tr s && dc >= tc s) // if-else statement processes the lower right corner chessboard chessBoard(tr s, tc s, dr, dc, s); // The special square is on this chessboard else { // There are no special squares on this board board[tr s][tc s] = t; // Cover the upper left corner with L-shaped dominoes of size t chessBoard(tr s, tc s, tr s, tc s, s); // Cover the remaining squares } }

Divide the elements to be sorted into two sub-sets of roughly the same size, sort the sub-sets respectively, and finally merge the sorted sub-sets into the required set

public static void mergeSort(Comparable a[], int left, int right) { if (left<right) {//At least 2 elements int i=(left right)/2; //Get the midpoint mergeSort(a, left, i); mergeSort(a, i 1, right); merge(a, b, left, i, right); //Merge into array b copy(a, b, left, right); //Copy back to array a } }

(1) Decomposition

(2) Recursive solution

(3) Merge

(1) Worst case scenario

(2) Best case scenario

(1) Worst case scenario

(2) Best case scenario

(3) Average situation

private static int partition (int p, int r) { int i = p, j = r 1; Comparable x = a[p]; //Fixed selection of the first element as pivot // Swap the elements of <x to the left area // Swap the elements >x to the right area while (true) { while (a[ i].compareTo(x) < 0 && i<r); while (a[--j].compareTo(x) > 0); if (i >= j) break; MyMath.swap(a, i, j); } a[p] = a[j]; a[j] = x; return j; } private static int randomizedPartition (int p, int r) { int i = random(p,r); MyMath.swap(a, i, p); return partition (p, r); }

Given an array from smallest to largest: a[1] a[2] ... a[k] ... a[n] It is required to find the kth smallest element. k (1<=k<=n)

· Randomly select a pivot

· Move forward if it is smaller than pivot, and move backward if it is larger than pivot.

· After one round, divide the array according to pivot, and know the pivot number j. If you want to select the kth smallest number, there are three situations:

· Worst time complexity

· Average time complexity

(1 Introduction

(2) Steps

(3) Analysis

(4) Complexity

private static Comparable randomizedSelect(int p,int r,int k) { if (p==r) return a[p]; int i = randomizedpartition(p,r), j = i-p 1; if (k<=j) return randomizedSelect(p,i,k); else return randomizedSelect(i 1,r,k-j); } private static Comparable select (int p, int r, int k) { if (r-p<5) { //Use a simple sorting algorithm to sort the array a[p:r]; bubbleSort(p,r); return a[p k-1]; } //Find the median of each group //Exchange the third smallest element from a[p 5*i] to a[p 5*i 4] with a[p i]; r-p-4 is the n-5 mentioned above for ( int i = 0; i<=(r-p-4)/5; i ) { int s=p 5*i, t=s 4; for (int j=0;j<3;j ) bubble(s,t-j); //bubble is a round of bubbles in bubbleSort MyMath.swap(a, p i, s 2); } //Find the median of the median, Comparable x = select(p, p (r-p-4)/5, (r-p 6)/10); int i=partition(p,r,x), j=i-p 1; if (k<=j) return select(p,i,k); else return select(i 1,r,k-j); }

Design a round-robin competition schedule that meets the following requirements: (1) Each player must compete once with other n − 1 players. (2) Each player can only compete once a day (3) The round robin lasts for n − 1 days in total

Divide all the players in half, and the game schedule for n (take 2k) players can be determined by designing the game schedule for n/2 players. By recursively dividing the players until only 2 players are left, the game schedule becomes simple. At this time, just let these two players compete.

When multiple matrices are multiplied, the order of the products will affect the number of calculations. As shown in the picture

Given n matrices {A1, A2,⋯ , An}, where Ai and Ai 1 are multiplicable, i = 1, 2,..., n − 1. Gives the sequence of matrices with the least number of multiplications

(1) Algorithm idea

(2) Algorithm process

(3) Recursion formula

(4) Solve

(1) Premise

(2) Structural characteristics of the optimal solution

(3) Establish a recursive relationship

(4) Overlapping sub-problems

(5) Algorithm description

(6) Complexity analysis

(1) Optimal substructure characteristics

(2) Overlapping sub-problem characteristics

(1) How to analyze the optimal substructure properties of the problem? proof by contradiction

(2) How to utilize optimal substructure properties? Construct a recurrence relation

Given 2 sequences: X = {x1, x2,..., xm} Y = {y1, y2,..., yn} Find the longest common subsequence of X and Y (Longest Common Sequence)

· Plagiarism code detection system

·Web page keyword search

·DNA sequence matching

·Audio recognition system

(1) Premise

(2) Symbol convention

(3) Situation analysis

(4) Recursion formula

(5) Algorithm description

(6) Complexity analysis

Convex polygon: P = {v0, v1, ..., vn-1} · n edges vivi 1 (v0 = vn) · Line segment vivj (vi and vj are not adjacent) chord · A chord divides the polygon into 2 polygons: {vi, vi 1, ..., vj}, {vj, vj 1, ...,vi}

(1) Concept

(2) Nature

The weight function w(·) of a triangle can be defined in various ways, for example

All possible triangulations of a convex polygon are denoted as a set F, and the triangulation with the smallest weight among them is found.

If the convex polygon T is the optimal triangulation and is divided into two parts T1 and T2, then T1 and T2 must be the optimal triangulation of the sub-polygon and satisfy:

(1) j = i

(2)j>i

(1) Time complexity

(2) Space complexity

(1 Introduction

(2) Rules

(3) Question

(4) Example

(1) Optimal substructure properties

(2) Recursive structure of solution

· Divide n pixels into m continuous segments {Si}m

·

·

Determine the optimal segment S' of the pixel sequence <p1, p2, ..., pn>, which requires the least storage space

(1) Optimal substructure properties

(2) Recursive formula

(3) Complexity analysis

(1) Description

(2) Proof

(1) The complexity of this algorithm

(2) Improve algorithm

There is a set of n activities E = {1, 2, ..., n}, activity i occupies resources within the duration, and different activities will have time conflicts and are incompatible. Find the largest sub-set of consistent activities from the set of activities.

(1) Steps

(2) Part of the code

1. Excluding sorting time, the algorithm complexity is O(n)

2. Including the sorting time, the algorithm complexity is O(nlogn)

(1) Common points

(2) Differences

A batch of containers is to be loaded onto a ship with a carrying capacity of c. in The weight of container i is wi. not exceeding the carrying capacity of the ship Load as many containers as possible onto the ship.

(1) Description

(2) Proof

(1) Description

(2) Proof

public static float loading(float c, float [] w, int [] x) { int n=w.length; Element [] d = new Element [n]; for (int i = 0; i < n; i ) d[i] = new Element(w[i],i); MergeSort.mergeSort(d); float opt=0; for (int i = 0; i < n; i ) x[i] = 0; for (int i = 0; i < n && d[i].w <= c; i ) { x[d[i].i] = 1; opt =d[i].w; c -= d[i].w; } return opt; }

The main time load of loading is sorting, ~ O(nlogn)

According to the frequency of characters appearing in the file, establish an optimal representation method using a string of 0 and 1 to represent each character.

Characters that appear frequently have shorter codes, and characters that appear less frequently have longer codes.

(1) Prefix code

(2) Coding tree

(3) Average code length

(4) Optimal prefix code

Construct a binary tree T representing the optimal prefix code from the bottom up

(1) The nature of greedy selection

(2) Optimal substructure

(1) State space

(2) Constraint definition

(3) Completeness characteristics

(1) Solution vector

(2) Solution space

(1) Slipknot

(2) Extension node

(3) Dead node

The backtracking method dynamically generates the solution space of the problem during the search process, and only saves the path from the root node to the current expansion node, with a space complexity of O(h(n))

(1) Subset tree (combination problem)

(2) Arrangement tree (arrangement problem)

subset tree

private static void backtrack (int i) {//Search for the i-th layer node if (i > n) { // Reach the leaf node Update the optimal solution bestx, bestw; return; } r -= w[i]; //try to load i if (cw w[i] <= c){ //Loading i cannot be overweight - constraints. Thinking: Why is there no limit function here? ? ? ? ? ? // Search left subtree (load i) x[i] = 1; cw = w[i]; backtrack(i 1); cw -= w[i]; //Undo the loading of i and prepare data for analysis without loading i!!!!!!!!!! } else{ //Prune, do nothing here } //Try not to load i if (cw r > bestw){ //The total weight w[i 1..n] after i must be heavy enough——limiting conditions x[i] = 0; // Search the right subtree (without i) backtrack(i 1); } else{ //Prune, do nothing here } r = w[i]; }

O(2n)

public class FlowShop{ static int n; //Number of jobs static int f1; // Machine 1 completes processing time static int f; //sum of completion time static int bestf; // current best value static int [][] m; // The processing time required for each job static int [] x; // Current job schedule static int [] bestx; // Current optimal job scheduling static int [] f2; // Machine 2 completes processing time private static void backtrack(int i) { //Main program framework: Recursive algorithm to generate n full arrangements if (i > n) { for (int j = 1; j <= n; j ) // Save the current best minx[j] = x[j]; bestf = f; } else for (int j = i; j <= n; j ) { //Detect x[i]...x[n] in sequence f1 = m[x[j]][1]; // f2[i] = ((f2[i-1]>f1) ? f2[i-1] : f1) m[x[j]][2]; f = f2[i]; if (f < minf) { // Boundary conditions MyMath.swap(x,i,j); backtrack(i 1); MyMath.swap(x,i,j); } f1 -= m[x[j]][1]; f -= f2[i]; } } }

There are n symbols in the first row. Count how many different symbol triangles there are.

//Search for the i-th subtree in the solution space private static void backtrack (int t) { if ((count>half)||(t*(t-1)/2-count>half)) // or - the number exceeds half, prune return; if (t>n) sum ; // It is a feasible symbolic triangle, and the number of feasible solutions (sum) is accumulated else for (int i=0;i<2;i) { //The added symbol on the right side of the first line is 0 ("-") or 1 (" ") p[1][t]=i; count =i; // number of " " for (int j=2;j<=t;j ) { // p[j][t-j 1]=p[j-1][t-j 1]^p[j-1][t-j 2]; // Same or count =p[j][t-j 1]; } backtrack(t 1); for (int j=2;j<=t;j) //restore to t count-=p[j][t-j 1]; count-=i; } }

On a chessboard with n × n squares Place n that are immune to each other queens, that is, any 2 Queens are not placed in the same row or in the same row in a column or on the same slash

subtopic

priority

data structure

public static void shortest(int v, float [] dist, int [] p) { //Detailed code omitted... //The code of the core part is as follows while(true) { // Search the solution space of the problem for (int j=1;j<=n;j ) // There is an edge between vertices i and j, and the path length is smaller than the original path length from source point s to j if (a[enode.i][j] < Float.MAX_VALUE && enode.length a[enode.i][j] < dist[j]) { // Vertex i is reachable from vertex j and satisfies control constraints dist[j]=enode.length a[enode.i][j]; p[j]=enode.i; HeapNode node = new HeapNode(j,dist[j]); heap.put(node); // Join the live node priority queue //A node in the graph may be added multiple times } if (heap.isEmpty()) break; else enode = (HeapNode) heap.removeMin(); } }

· Queued branch limits

· Priority queue branch bounding

· Pruning function

· Algorithm Description

·Construct optimal solution

private static double bound(int i) { //Use fractional backpack to estimate the upper bound for items after i double cleft = c - cw; //remaining capacity double b = cp; //value upper bound while (i <= n && w[i] <= cleft) {//n represents the total number of items, cleft is the remaining space cleft -= w[i]; //w[i] represents the space occupied by i b = p[i]; //p[i] represents the value of i i; } if (i <= n) b = p[i] / w[i] * cleft; // Fill the remaining capacity to fill the backpack return b; // b is the upper bound function }

private static double BBKnapsack() {//Priority queue type branch limit, return the maximum value, bestx returns the optimal solution //Variable definition (omitted)... while (i != n 1) {// non-leaf node //Check the left child node: add the i-th item double wt = cw w[i]; if (wt <= c) {//Constraints //The left son node is a feasible node if (cp p[i] > bestp) bestp = cp p[i]; addLiveNode(up,cp p[i],cw w[i],i 1, enode, true); //Join the live node priority queue } up = bound(i 1); //Check the right child node: do not add the i-th item if (up >= bestp) //upper bound condition addLiveNode(up,cp, cw, i 1, enode, false); //Join the live node priority queue // Remove the next extension node HeapNode node=(HeapNode) heap.removeMax(); cw = node.weight; cp = node.profit; up = node.upperProfit; i =node.level; } //Construct the current optimal solution (omitted)... }