Term
|
Definition
| the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one word into another |
|
|
Term
| See http://www.let.rug.nl/kleiweg/lev/ |
|
Definition
| Find the Levenshtein distance between horse and ros |
|
|
Term
| TRUE. VERTEX-COVER is known to be NP-Complete, and we specifically reduced 3-SAT to this in class. |
|
Definition
| [TRUE/FALSE/UNKNOWN] If VERTEX-COVER has a polynomial time algorithm then 3-SAT has a polynomial time algorithm. |
|
|
Term
| UNKNOWN. INDEPENDENT SET is NP-Complete and there is no known polynomial time for any problem in this class. |
|
Definition
| [TRUE/FALSE/UNKNOWN] There is a polynomial time algorithm to solve the INDEPENDENT SET PROBLEM. |
|
|
Term
| TRUE. A naive algorithm runs in O(n196), which is a polynomial. |
|
Definition
| [TRUE/FALSE/UNKNOWN] Given a graph G with n vertices, deciding if there is a clique of size 195 is solvable in polynomial time. |
|
|
Term
| TRUE. INDEPENDENT SET is NP-Complete, which means that all problems in NP can be reducted to it in polynomial time. |
|
Definition
| [TRUE/FALSE/UNKNOWN] All problems in the class NP can be reduced to INDEPENDENT-SET. |
|
|
Term
| See practice exam answers |
|
Definition
Palindrome substring. Given a string, find the longest palindrome substring. Here is an example string. Let us identify all the palindromic substrings here.
Input String: ACECCBBA
One letter palindromic substring A, B, C, E Two letter palindromic substring CC Three letter palindrome sequence CEC
Give a dynamic program to compute the length of the longest palindromic substring. |
|
|
Term
| See practice exam answers |
|
Definition
| Profs for Dinner: You want to invite some Profs from the CSE Department for dinner (wonder why?!). As is well known, Profs are jealous of each other and end up not even on speaking terms. A grad student in the local sociology department created a database which is a two dimensional n x n matrix H (where n is the total number of CS Profs) with H[i, j] = 1 if Prof i is on speaking terms with Prof j and 0 otherwise (there are many 0s but at least lets assume H[i, i] = 1 for all i!) To make a good party, you want to invite at least k Profs, but so that all are willing to talk to each other. First, show that the problem of deciding if there is such a group of Profs is in the class NP. Second show that this problem is NP-complete by reducing INDEPENDENT SET to this problem. |
|
|
Term
| See practice exam answers |
|
Definition
| Suppose that someone gives you an oracle (a magic algorithm whose running time you can consider to be constant) to answer the CLIQUE decision problem: Does graph G have a clique of size k? Show how to use this to solve for the actual elements of the largest clique in Graph G. If there are multiple different cliques of size k, you can return any of them. Give the run-time of your algorithm (assuming the oracle runs in constant time), and argue that your algorithm is correct. |
|
|
Term
| See practice exam answers |
|
Definition
For a graph G(V, E), an "ALMOST INDEPENDENT SET" (AIS) is a set of nodes V' where there is at most one edge connecting nodes in V'. The decision problem for "ALMOST INDEPENDENT SET" is: "Does graph G have an ALMOST INDEPENDENT SET of size k?". Prove that "ALMOST INDEPENDENT SET" is NP-Complete.
(a) Prove ALMOST INDEPENDENT SET is in the set NP.
(b) Describe how to reduce from regular INDEPENDENT SET to an ALMOST INDEPENDENT SET problem.
(c) Argue that the solution to the regular INDEPENDENT SET problem on the original input is always the same as the solution to the ALMOST INDEPENDENT problem you create.
(d) Argue that your translation to create the ALMOST INDEPENDENT problem is polynomial time. |
|
|
