22-24 Flashcards
Why is a recursive solution to the knapsack problem bad? How can we improve?
Recursive knapsack is an expensive algorithm because it recomputes the same values over and over. If we store these values when they’re computed and then retrieve them when necessary we can make the algorithm more efficient. This technique is known as memoisation (not misspelt).
What is dynamic programming?
Dynamic programming is used for optimisation problems, where we want to find the ‘best’ way to do things. It is recursive and involves breaking down large problems into small ones. This requires subproblem optimality (a simple way to combine the optimum solution for smaller problems). Dynamic programming avoids the inefficiency that subproblem overlap causes for straightforward recursion. This is done by memo-ising. Dynamic programming computes the table bottom-up as opposed to top down.
What are some example ways to compare strings?
Consider two strings, we can come up with notions of how close they are, including the ordering of the letters. Several possibilities are: The longest substring common to both strings, the number of changes to convert one string into another (the edit distance) or the longest string, such that the characters in it are in both S1 and S2 in the same order but not necessarily consecutively.
How can we make a longest common string?
Let Xm be the position in a string X and Yn the position in a string Y. Let Z be a substring of X and Y. If xm and Yn match then Zk = Xm = Yn and Z(k-1) is an LCS of X(m-1) and Y(n-1). If this is not the case then either Z is an LCS of X(m-1) and Y or Z is and LCS of Xm and T(n-1).
What is a Hamilton cycle?
A Hamilton cycle in a graph is a sequence of adjacent vertices and distinct edges in which every vertex of the graph appears exactly once. The simplest algorithm for solving these is a brute force algorithm, this lists every permutation of the n vertices in G. For each we check whether G has edges connecting the neighbouring vertices. There are n! permutations, which means n! complexity, the checking part of the algorithm has O(n) complexity.
What are P and NP problems?
P is the class of all problems solvable by algorithms that are O(n^2). NP (non-deterministic polynomial) is the class of problems for which a proposed solution can be checked in polynomial time. P is either a subset or equal to NP, the Hamilton cycle problem is NP.
Is the Hamilton cycle problem NP-complete? What does this mean?
The HCP has been shown to be NP-complete, this means that if an efficient solution is found it can be easily converted for every other problem in NP.
What is the travelling salesman problem and what are some common solutions and complexities?
The travelling salesman problem is to visit every city/location only once and return to the starting city. This must be done at the lowest cost. Brute force is the simplest solution, but dynamic programming can be used to do much better (see slides). A naïve recursive solution is n! where n is the number of vertices. With memoisation we can do better. Coming to 2^V(still pretty bad).
