Foundations of Algorithms
The following are analytical and programming problems to be completed by individual students (i.e., this is NOT
a collaborative assignment). Please follow the requirements provided under the link Programming Assignment
Requirements.
Problems for Grading
- [50 Points] Closest Pairs
In this form of algorithm development there are several practical applications, such as but not limited to moving
objects in a game, classification algorithms, computational biology, computational finance, genetic algorithms,
and N-body simulations.
In these implementations ensure you output your results to the command window for a two dimensional arrays
A ≤ 30 values, e.g. “double[][] A= new double[30][2];”. For a two dimensional array A > 30 please
create output files.
(a) [12.5 Points] Construct a brute-force algorithm (pseudocode) for finding the closest pair of points in a
set of n points in a two dimensional plane and show the worst-case big-O estimate for the number of
operations used by the algorithm. Hint: First determine the distance between every pair of points and
then find the points with the closest distance.
(b) [12.5 Points] Implement the brute-force algorithm from part (a).
(c) [12.5 Points] Given a set of n points (x1, y1), …,(xn, yn) in a two dimensional plan, where the distance between two points (xi
, yi) and (xj , yj ) is measured by using the Euclidian distance p
(xi − xj )
2 + (yi − yj )
2,
design an algorithm (pseudocode) to find the closest pair of points in a more efficient efficient way than
part a and the worst-case big-O estimate.
(d) [12.5 Points] Implement the the algorithm from part (c) with the following methods:
i. The distance of the closest pair of points.
ii. The n pair of closest points.
iii. The distance values for the n points. - [50 Points] Deterministic Turing Machine (DTM)
In 1900, mathematician David Hilbert enumerated 23 mathematical problems he considered challenges for the
coming century. The tenth problem is his list concerned algorithms: Given a polynomial, find an “algorithm”
for determining whether the polynomial has an integral root.In the way Hilbert phrased the above problem, he
explicitly asked that an algorithm be “devised”.As we now know, no algorithm exists for this task if the polynomial is de-fined on several variables. That is, the above problem is algorithmically unsolvable. However,
mathematicians of that period could not come to this conclusion with their intuitive notion of algorithm.
Although our intuitive notion of an algorithm is enough to “devise” solutions for certain problems (the ones
a computer can solve), it is useless for showing that no algorithm exists for a particular task, as our intuitive
notion is not a formal one.So, proving that an algorithm does not exist required having a clear definition of
algorithm.Such a definition was simultaneously given in 1936 by Alonzo Church and Alan Turing.Church used
a notational system called the lamda calculus to precisely define algorithms.Turing did it with his “machines”
1
This connection between the informal notion of algorithm and the precise definition is known as the the
Church-Turing thesis. More precisely, Turing proposed to adopt the Turing machine that halts on all inputs as
the precise formal notion corresponding to our intuitive notion of an “algorithm”. Note that the Church-Turing
thesis is not a theorem, but a “thesis”, as it asserts that a certain informal concept (algorithm) corresponds to
a certain mathematical object (Turing machine).
Since Turing machines can only deal with decision problems, you may find very strange the fact that a Turing
machine is a formal counterpart of our intuitive notion of an algorithm, as many computational problems are
not decision problems.Well, keep in mind that every computational problem is either equivalent to a decision
problem or is at least as “hard” as some decision problem. So, the restriction to decision problems is not a
problem.Besides helping us understand what we can or cannot do with computers, Turing machines can also
be used to formally define the complexity of an algorithm.
In this problem you will implement two variants of a DTM. The definition and example are provided below
followed by the two required implementations. A deterministic Turing machine consists of the following:
• A finite state control,
• A tape consisting of a two-way sequence of tape squares, and
• A read-write head.
A given DTM is manipulated through the execution of a program utilizing the following components:
• A finite set Γ of symbols,
• A finite set Q of states (q0 is designated as the start state and qY and qN are designated as halting
states), where {q0, qH} ∈ Q,
• The direction. s = (left, right, halt), where left = -1 and right = +1, in which to move the tape head s ∈ Q
• A transition function δ : (Q − {qY , qN }) × Γ → Q × {+1, 0, −1},
• Σ ⊂ Γ as a set of input symbols, and
• b ∈ (Γ − Σ) corresponds to the ”blank symbol” (#)
This allows a DTM to be represented as a finite set of program lines with the form of a 6-tuple TM M =
(Γ, Q, s, δ, Σ, b).
In other words, the DTM will scan the tape, and the transition function will read the symbol from Γ currently
written on the table and determine what character to write in its place as well as which direction s to move
the read-write head. Presumably, if the program indicates +1, the head moves to the right, if the program
indicates −1, the head moves to the left and if the program indicates 0, the head stays still.
To see how a DTM works, suppose we have Σ ⊂ Γ as a set of input symbols and b ∈ (Γ − Σ) a ”blank symbol”
(#). Next suppose we have an input string x ∈ Σ
∗ where we place the symbols of x in consecutive cells of the
tape in positions 1…|x|. All other cells on the tape are assumed to have b. The program will begin in state q0
with the read-write head scanning square 1 and proceed according to the transition function.
If the current state of the DTM is ever qY or qN , then the program terminates. On the other hand, if the current
state is in Q − {qY , qN }, then the program continues. When transitioning, the read-write head will first erase
the symbol in the square it is examining and then write the new symbol as specified by the transition function.
The read-write head then either moves one position to the right or one position to the left, and the Finite State
Control updates the state to some successor q
0
.
Because we have limited the set of halting (or terminal) states to qY , qN , we note that a DTM is only able
to solve problems that return a Boolean result. In particular, we say that a DMT is used to solve decision
problems where qY indicates the DMT has decided yes and qN indicates the DTM has decided no.
The set of states is defined to be Q = q0, q1, q2, q3, qY , qN , and the transition function δ is defined by the
following table:
2
start q0 q1 q2
q3
qY
qN
0, 1, [R]
b, [L]
0, !b, [L]
1, !b, [L]
b, [L]
0, !b, [L]
1, !b, [L]
b, [L]
0, 1, b, [L]
Figure 1: DTM State Diagram
Table 1: DTM model illustrated in Figure 1.
Q − {qY , qN } 0 1 b
q0 (q0, 0, +1) (q0, 1, +1) (q1, b, −1)
q1 (q2, b, −1) (q3, b, −1) (qN , b, −1)
q2 (qY , b, −1) (qN , b, −1) (qN , b, −1)
q3 (qN , b, −1) (qN , b, −1) (qN , b, −1)
To reiterate how the DTM works, Table 1 represents the states q = Q − {qY , qN }, symbols in x, and the
direction the read-write head moves (s). Starting with the initial state represented with q0 the finite controller
reads the initial symbol represented by x. At each step the controller reads the symbol x on the tape at state
q, enters the state q
0 = Q = q0, q1, q2, q3, qY , qN , writes the symbol x
0
in the current cell, erasing x, and moves
in the direction identified by s. This is represented as the five-tuple (q, x, q0
, x0
, s) TM. For Table 1 the DTM is
represented by the following finite-state machine in Figure 1. The edges in Figure 1 are labeled with the symbol(s) on the tape, a symbol that overwrites the current symbol (if any), and the direction of tape movement.
For example, (1, !b, [R]) on the edge between q1 and q3 denotes when the read/write head is over a symbol 1
while in state q1 overwrite the 1 with b and move the tape to the right.
Please note that you can define other symbols in Γ and you should. Consider representing two unary numbers
on the tape and performing the operations in your assignment. If you include S,E in your set Γ you could use
those symbols to recognize the start of data on the tape (S) and the end of data on the tape (E) making those
symbols available to you in your state modeling. Remember that each state must fully define the operation of
the DTM in that state for each symbol in Γ.
(a) [25 Points] Implement the DTM example provided in the Course Content under Module 3. Ensure that
your components as listed above are clearly identified in your variable list. The finite-state machine
with the individual states, state table and five-tuple TM are shown in the above example. You should
implement the following methods:
i. States method, this method should have all of the operations of your TM.
ii. Program line that executes the operations for each identified state, this should follow the n-tuple TM
as described above for M.
iii. Print method that outputs the change in tape (x ≤ 30) after each transition function is executed.
iv. Write method, for tape larger than x > 30 write the outputs to a file
(b) [25 Points] Expand the implementation of the DTM in part (a) to perform additional binary operations
(addition, subtraction, multiplication) at each state. You should implement the following methods that will
allow for other operations:
3
i. Addition – The tape will need to handle variable length binary inputs, e.g., tape values of 01100101
add 101 or add 101101101.
Table 2: Binary Addition Rules
Operation
x + x
0
Sum Carry
0 + 0 0 0
0 + 1 1 0
1 + 0 1 0
1 + 1 0 1
ii. Subtraction – The tape will need to handle variable length binary inputs, e.g., tape values of 01100101
subtract 101 or subtract 101101101.
Table 3: Binary Subtraction Rules
Operation
x − x
0
Sum Carry
0 − 0 0 0
0 − 1 0 1
1 − 0 1 0
1 − 1 0 0
iii. Multiplication – The tape will need to handle variable length binary inputs, e.g., tape values of
01100101 multiply 101 or multiply 101101101.
Table 4: Binary Multiplication Rules
Operation
x × x
0
Multiplication
0 × 0 0
0 × 1 0
1 × 0 0
1 × 1 1
4
The post Foundations of Algorithms appeared first on homework handlers.
