(1) Longest Increasing Subsequence
Pseudocode: DP, Time complexity .
(2) Polynomal Time
An algorithm runs in polynomial time if its runtime is some polynomial in , which can be written as .
(3) Cobham-Edmonds Thesis
A language can be decided efficiently if and only if it can be decided in time for some .
can be decided efficiently but,
can not be decided efficiently.
(4) Complexity Class P
The complexity class is a class that contains all the problems that can be solved in polynomial time,
Where stands for Turing Machine.
Common P problems are,
(5) Non-deterministic Turing machine
A nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. For example, BST is an NTM because its time complexity is the height of the tree.
(6) NTM to TM Theorem
For any NTM with time complexity , there is a TM with time complexity .
(7) Complexity Class NP
The complexity class NP (nondeterministic polynomial time) contains all problems that can be solved in polynomial time by an NTM.
Common NP problems are,
From the definition, we can easily know that,
But it is still the most important question in theorical computer science that if
It can be explained simply as if a solution to a problem can be checked efficiently, can that problem be solved efficiently?
Backtracking is a general algorithm for finding the solutions to some computational problems. It abandons a candidate (called backtrack) as soon as it determinates the candidate can not possibily be completed to a valid solution. Backtracking is commonly used to solve some NP-complete questions.
(3) Crosswords I
Find a specific word in a matrix.
(4) Crosswords II
Clean a room by robot.
(5) N-Queens I
Trick 1: how to get the diagonal/anti-diagonal index for a cell in an matrix.
For an matrix, there will be diagonals or anti-diagonals. So the index of a diagonal can be calculated by,
And the index of an anti-diagonal can be calculated by,
Trick 2: Before we put a queen, we have to check three sets.
We don't need to check the rows because we will only put one queen in each row.
(6) N-Queens II
This is just a similar question without requirement for printing the board.
(6) Valid Sudoku
Before we see how to solve a Sudoku, let's first see how we can validate one. This is not a backtracking problem.
(7) Solve Sudoku
Next, let's solve a Sudoku.
Combination and permutation problems can also be solved by backtracking.
(9) Combination Sum I
Find all the combinations that sums up to a target value.
Get the list of all the subsets of a set. Note backtrack doesn't help with this problem because it has to traverse all the cases.
(11) Subset II
Everything is similar but this time the set contains duplicated values. So in this question, the backtracking will work for us.
Give all the permutations of a list.
(12) Permutations II
Give all the permutations of a list with duplicate values.
(13) Letter Combinations