# 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.