certainty

feasibility

Finiteness

There are 0 or more inputs

There is more than 1 output

correctness

simplicity

Optimality

time complexity

space complexity

An algorithm is a sequence of finite rules

Analytical Methods for Non-Recursive Algorithms

Analytical Methods for Recursive Algorithms

3 basic computing models

Computable problems (easy to solve problems)

Uncomputable problems (difficult problems)

P type questions

NP type problem

NPC issues

NP-hard problem

Recursion is a method that calls itself directly or indirectly in its definition

recursive exit

recursive body

You can look at the homework questions and understand what the code you wrote means.

Divide a large problem that is difficult to solve into smaller problems of the same type so that they can be solved individually and divided and conquered

Decomposition: Divide the original problem into a series of sub-problems

Solution: Solve each sub-problem recursively. If the subproblem is small enough, it can be solved directly

Merge: combine the results of subproblems into the solution of the original problem

The solutions to the sub-problems decomposed for the problem can be combined into the solution of the problem

Build and solve recursive equations

Read the summary of book P101

Make the subproblems roughly the same size

Decompose the problem into smaller sub-problems of the same nature

Optimal substructure properties

Overlapping sub-problem properties

Find the properties of the optimal solution and characterize its structural characteristics

Recursively define optimal values ​​(build dynamic transfer equations)

Calculate the optimal value in a bottom-up manner

Construct the optimal solution based on the information obtained when calculating the optimal value

Establish dynamic transfer equations and explain their meaning

Time complexity: analyze the number of nested loops and the number of loops

Space complexity: depends on the size of the table

Fibonacci Sequence

digital triangle problem

0-1 backpack problem

Matrix multiplication problem

longest common subsequence

longest non-increasing subsequence

Maximum sum of consecutive fields

Optimal substructure properties

greedy choice property

Determine the greedy selection strategy and describe the specific process

Do you need to sort?

The complexity of the process depends on the specific problem

Event arrangement issues

River crossing problem

Huffman coding

minimum spanning tree

Dynamically generate the solution space of the problem during the search process

solution vector

solution space tree

depth first search

pruning function

For the given problem, define the solution space of the problem

Identify easily searchable solution space problem structures

Search the solution space in a depth-first manner, and use pruning functions to avoid invalid searches during the search process

Given the solution space, determine whether it is a subset tree or a permutation tree, and design a pruning function

Depends on whether it is a subset tree or a permutation tree

0-1 backpack problem

Traveling Salesperson (TSP) Problem

symbolic triangle problem

P265 Summary

queued branch bounds

Priority queue branch bounding

The model is similar to the typical example. The same goes for the exam, there won’t be original questions, but the model may be the same.

Both time complexity and space complexity need to be analyzed

The main points should be grasped in the description of the idea. It can be explained step by step, and the process can be explained with examples. It should not be too simple.

Relevant variables and data structures are clearly described

Library functions can be called directly

Pseudocode generally appears in the form of functions, with necessary comments added.

Read the question requirements clearly and don’t miss any questions

Analysis requires a calculation process, not just results.