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
Problems for Grading

  1. [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 )
    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.
  2. [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”
    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
    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:
    start q0 q1 q2
    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
    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:
    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
    x + x
    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
    x − x
    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
    x × x
    0 × 0 0
    0 × 1 0
    1 × 0 0
    1 × 1 1

The post Foundations of Algorithms appeared first on homework handlers.

"Looking for a Similar Assignment? Get Expert Help at an Amazing Discount!"