This second assignment will give you practice in performing problem reductions. This is an important skill to develop for this course. It is also handy if you plan to write any sort of software. Algorithm re-use is everywhere.
The problems in this assignment are relatively straightforward so as not to not burden you too much. Given that, please resist the temptation to look up the answers online. Work through the problems yourself and if you cannot solve them, describe your challenges - where you get stuck - in your submission. Also, please reach out to me with any questions.
It is critical and required that you document your thought process for each question in detail. I will grade your submission primarily on the detailed articulation of your thought process and approach. You will not get full marks if you merely get the answer right, but did not provide a description of how you got there. Also, please demonstrate in your submission that you understand the two problems referenced in each question, and explain in detail, preferably with an example, how you can use (the Oracle for) one, to solve the other.
It may be beneficial to work each problem out by hand. As such, you have two options to submit your assignment:
Submit your legible handwritten solutions to the assignment box outside my office.
Submit a PDF of your solutions to me by email.
Whichever route you choose, they are both due by the deadline set out on the Course Schedule page.
A palindrome is a word which is spelled the same backwards and forwards. For example civic and level are palindromes.
Reduce the problem of checking if a string is a palindrome (F) to the problem of string reversal (G).
In other words, find some way to solve F using a form of G.
Reduce the problem of counting the number of occurrences of a character in a string (F) to the problem of checking if two characters are equal (G).
A linked list is a data structure comprised of an ordered set of elements, where each element has a pointer to the next element.
Reduce the problem of finding the length of a linked list (F) to the problem of checking if a linked list is empty (G).
The process of factorization is used to identify integers which, when multiplied, equal the number being factorized. For example, two factors of the number 21 are 7 and 3.
A prime number is a number which only has the factors of 1 and itself. For example, 23 has no factors beyond 1 and 23.
Reduce the problem of determining if a number is prime (F) to the problem of integer factorization (G).
A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set. In other words, there are no edges between vertices within the same set.
The two-colouring problem asks whether it is possible to assign one of two colours to each vertex of a graph such that no two adjacent vertices have the same colour.
Reduce the problem of determining if a graph is bipartite (F) to the problem of two-colouring a graph (G).
A subsequence of a string is a string generated from the original string by deleting 0 or more characters without changing the order of the remaining characters. Subsequences of “FUN” are “”, “F”, “U”, “N”, “FU”, “UN”, “FN” and “FUN”.
A string's edit distance, is a way to assess the degree of difference between two strings. In determining edit distance, the goal is to find the minimal number that any of the following actions can be taken to turn the first string (A) into the second string (B):
Insert: Insert any character before or after any index of string A.
Delete: Remove a character of string A.
Replace: Replace a character at any index of string A with some other character.
For example, the edit distance between snow and sun is 3: snow > sno > suno > sun.
Reduce the problem of finding the longest common subsequence of two strings (F) to the problem of computing the edit distance between two strings (G).
String rotation refers to shifting all characters in a string by a certain number of positions, with those that go beyond the string length bound being added to the other end of the string. For example, rotating "this assignment is fun" by 2 positions gives "un this assignment is f".
String concatenation is the process of joining two strings end-to-end. For instance, concatenating "computability" and "is weird sometimes" results in "computabilityis weird sometimes".
Reduce the problem of string rotation (determining whether one string is a rotation of another) (F) to string concatenation (G).
A Hamiltonian Cycle in a graph is a cycle that visits every vertex exactly once and returns to the starting vertex. The Traveling Salesman Problem requires the finding of an optimal route in a graph of locations and distances between them, which visits every location once, and which returns to the starting location.
Reduce the problem of determining if a graph has a Hamiltonian cycle (F) to the Traveling Salesman Problem (G).
The String Rewriting Problem is a computational problem that involves transforming one string into another using a set of rewriting rules. For example, we might have the following rules:
ab -> ba
ca -> D
ra -> c
b -> ε (where ε represents the empty string)
We can now apply these rules, in any order we choose, to a string such as "abracadabra":
apply rule 1: baracadabra
apply rule 2: baraDdabra
apply rule 3: bacDdabra
apply rule 3: bacDdabc
apply rule 1: bacDdbac
apply rule 4: acDdbac
apply rule 4: acDdac
At this point no more string reductions are possible. Note that a different sequence of applying the rules may give different results.
Recall from the book that the Post Correspondence Problem is a mathematical puzzle where you're given a set of "dominoes," each with a string on the top and a different string on the bottom.
The goal of the problem is to find a sequence of these dominoes where the string formed by reading the top strings in order is exactly the same as the string formed by reading the bottom strings in the same order.
Essentially, you're trying to "match" the top and bottom strings by choosing dominoes in a specific sequence, with repetition allowed.
Reduce the Post Correspondence Problem (F) to the String Rewriting Problem (G).