1. Simple Polygons
Let P be a non-convex simple polygon. This means that the convex hull of P has an edge ab that is not an edge of P. Consider the area that is enclosed by the edge ab and the polygon P. Let us call this area a pocket of P. This pocket is itself a polygon. Now the trick here is to observe that an ear of a pocket of P is a mouth of P! and since by the two-ear theorem we know that this pocket must have at least one ear, then this means that P has at least one mouth.
Q.E.D.
A more detailed proof can be found here.
2. Collapsing Compass
- Draw a circle C1 centered at A with radius AB.
- Draw a circle C2 centered at B with radius BA. C1 and C2 intersect at point D, E.
- Draw a circle C3 centered at D with radius DC.
- Draw a circle C4 centered at E with radius EC. The other intersect point of C3 and C4 is the required point
proof:
The key point it to prove the line DE is both perpendicular bisector
of AB and CX. There are several ways to achieve this goal; here
is one example:
DC = DX. So D is on the perpendicular bisector of CX.
EC = EX. So E is on the perpendicular bisector of CX.
Following the same proof, DE is also the perpendicular bisector
of AB.
So AX is the mirror of BC with the perpendicular bisector of AB
3. Algorithms for Turing Machines
Idea: Scan the tape from left to right
and then right to left; cross off one leftmost mark and two right
most marks during each round of the scan. Finally, there is only
one mark (the (n+1)-st one) left, and the computation comes to
end.
The following is the instruction units, in which 1 denotes the
start state and 0 denotes the stop state.
Current State (a) |
Current Symbol (A) |
Action (B) |
Next State (b) |
1 |
X |
- |
1 |
1 |
- |
R |
2 |
2 |
X |
R |
2 |
2 |
- |
L |
3 |
3 |
X |
- |
3 |
3 |
- |
L |
4 |
4 |
X |
- |
4 |
4 |
- |
L |
5 |
5 |
X |
L |
6 |
6 |
X |
L |
7 |
6 |
- |
- |
0 |
7 |
X |
L |
7 |
7 |
- |
R |
1 |
4. Big "O" Notation
The answer to both sections of this question can be found in Chapter 3 of the textbook by Udi Manber. Part (a) is a proof straight from the book, while part (b), where you only needed to give a counterexample, is a solved exercise in the books (problem 3.15); you can find the solution in the back.