Algorithms Outline for Final Exam

4 sides of notes allowed.

Exam emphases

1. Individual topics that are new since the last quiz will be more emphasized than the topics you have been examined on before, probably meaning 30-35% of the exam will be on new topics.
2. Problems from later in the semester generally include skills needed from early in the semester implicitly, so most questions will not be straight from the early part of the course, though there may be some topics from earlier in the semester that did not get used much in the later part of the course.
3. The best characterization of the course is the course itself, but I have tried to give you homework on all topics, so reviewing homework is a good review. Looking at old exams or sample exams is a quick but not complete way to review the older material: You should have covered much more in all your work than there was space for in the midterm and quizzes. Obviously if you missed something on an exam, it would be good to make sure you know it now, but exams involve a number of arbitrary choices and omissions, and different choices are likely to be made on the final. Major topics are likely to reappear, but often be treated from a somewhat different angle than last time, or combined in different ways. A mostly different collection of secondary topics is likely to be on the final.
4. I repeat: the best review of what you need to be able to do is to go over homework. If you need further exercises on any subject, let me know.

Topics from previous topic guides plus:

• Seeing the graph and algorithm underneath a problem description.

• Floyd, Warshall, and Bellman-Ford algorithms and when to use them

• Dynamic Programming:

• Seeing recursive relationships and concise solutions
• Dynamic solution with memoizing
• Dynamic solution with reverse topological ordering
• Fancier solutions reconstructing the details of the optimal solution
• Calculating time and space requirements; minimizing their orders.

Unlike HW, where I often asked you to do all parts, I'm likely to ask you to just get a recursive solution or be given one version of a solution and modify it into another version.

• P-NP

• Decision problems

• Understand the famous problems associated with assorted standard names: CNF and 3-CNF satisfiability, Hamiltonian Cycle, Hamiltonian Path,
• Graph coloring, Knapsack, Subset Sum, Travelling Salesperson.
• Follow other problems in 13.3.2 if their statements are repeated.
• The class P
• Measuring input
• Polynomial time solutions
• The class NP: checking a correct solution in polynomial time
• Polynomial reducibility
• Reduction of a problem to a problem in P shows it is in P
• NP hardness, NP completeness
• Reduction of an NP complete problem to Q shows Q is NP hard
• Do very simple reductions
• Does P = NP? (just kidding)

Problems

1. Unlike the party problem, assume “knowing is not symmetric for this celebrity problem: Given n people, a celebrity is one who knows nobody else but everybody else knows the celebrity. To determine if there is a celebrity in a group of n people, you can ask questions only of the form, “Does A know B?” Suppose I say I can come up with an algorithm involving O(n) such questions to determine if and who is a celebrity within the group. Is it possible to do better than that?

2. In class we worked out a general Python solutions for Hw 5.3 8a, creating a tree from inorder and postorder traversals, and then a solution to part c, using that, to create a preorder traversal. Just solve part c, creating a preorder traversal from inorder and postorder, or return null or Python None if it is impossible, and do this with simple recursive code that does not create a tree as an intermediate step. Write code in Python, C#, C++ or Java. In all but Python it is easiest to assume all the traversals are given as strings of characters.

3. For a set of symbols x1, x2, x3, ... xn, you are given some equality constraints of the form xi= xj, and some inequality constraints, xi≠ xj. Is it possible to satisfy all of them with integer values? For instance, the constraints: x1= x2, x2= x3, x3= x4, x1≠ x4, cannot be satisfied. Suppose the number of constraints is m. Clearly explain and give pseudo-code for an O(n + m) algorithm to determine if such a set of constraints can be satisfied. Explain why your algorithm is O(n + m). Note: You are given only the symbols and relations. You are NOT given the values for the symbols. The question is about the ability to find consistent values for the symbols.

Hint: You cannot treat the = and ≠ relations in a similar way. Where is the better place to start?

follow

below

...

Solutions

1. If you ask fewer than n/2 questions, you get no information about at least one member. That person may or may not know any individual and may or may not be know by any individual, allowing for or disallowing anyone as celebrity. Hence there must be at least O(n) questions. You cannot have a better order than the one proposed.

You can make a finer argument for more than n/2, but the short argument above is sufficient to get O(n).

2. Instead of creating a tree/subtree, create a preorder traversal immediately.

This Python code allows either strings or lists. The only trickiness to allow both is the final return expression. It would be slightly cleaner if only one type was the target, for strings: root + left + right, and for lists: [root] + left + right.

```def thirdTraversal(inorder, postorder):
'''Given inorder and postorder traveral of a binary tree,
either both lists or both strings, return a corresponding sequence
containing the preorder traversal, or None if impossible.
>>> thirdTraversal('9310427685', '9140367582')
'2390148765'
>>> thirdTraversal([1, 2, 3], [1, 2, 3])
[3, 2, 1]
>>> thirdTraversal([1, 2, 3], [3, 1, 2]) # fails, returns None
>>>
'''
if len(postorder) == 0 and len(inorder) == 0:
return postorder
root = postorder[-1] # -1 is handy Python shorthand: index of the last element
if root not in inorder:
return None
i = inorder.index(root)
left = thirdTraversal(inorder[:i], postorder[:i])
if left is None:
return None
right = thirdTraversal(inorder[i+1:], postorder[i:-1])
if right is None:
return None
return postorder[-1:] + left + right
```

C# with strings:

```static string thirdTraversal(string inorder, string postorder)
{
if (postorder.Length == 0 && inorder.Length == 0)
return "";
int rootPostI = postOrder.Length - 1;
char root = postorder[rootPostI];
if (!inorder.Contains(root))
return null;
int i = inorder.IndexOf(root);
left = thirdTraversal(inorder.Substring(0,i), postorder.Substring(0,i));
if (left == null)
return null;
right = thirdTraversal(inorder.Substring(i+1),
postorder.Substring(i, rooPostI-i));
// Java 2nd param: postorder.substring(i, rooPostI)
if (right == null)
return null;
return root + left + right;
}
```
3. N distinct objects with relations in pairs - sure looks like a something to state as a graph. How to deal with equalities vs inequalities? The situation is not symmetric: Equalities give an equivalence relation; inequalities do not, so try just using the equalities initially. Because of the equivalence relation with equality, any two vertices connected by a path must be equal, so there cannot be an inequality between them. How to check all this efficiently? Run the component numbering variation of the DFS once. All variables in the same component must have the same value. Then check each inequality to make sure that the variables in the pair are not in the same component. Details in pseudo-code:

```Create empty lists neighbors[i] i = 1...n           #O(n)
for each equality constraint xi= xj:                #O(m), yielding no more than m edges
Add i to neighbors[j] and j to neighbors[i]
Run the component numbering algorithm, generating an array cc,
where cc[i] is the component number for xi.   #O(n+m)
for each inequality constraints, xi≠ xj:                      #O(m)
if cc[i] == cc[j]:
return False
return True   #The values in cc are a solution                #total time still O(n+m)
```