685.621-Programming Assignment 1 Solved

Problem 1 - Data Analysis
The Iris Plants Database contains 3 classes of 50 instances each, where each class refers to a type of Iris plant. Five attributes/features were collected for each plant instance. It can be downloaded from iris.arff on the Sample Weka Data Sets webpage (https://storm.cis.fordham.edu/ gweiss/datamining/datasets.html).

1.   Implement an algorithm to read in the Iris dataset.

2.   Implement an algorithm to visually see two sets of features and the class they belong to.

3.   Implement your sorting algorithm from Homework 1 Problem 5.


Problem 2 - Deterministic Turing Machine
In this problem you will implement two variants of a DTM. The definition and example are provided below followed by two 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 (left, right, hault) 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” (#)

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)
Q−{qY ,qN}
0
1
b
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 q0.

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.

Table 1: 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

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 q0 = Q = q0,q1,q2,q3,qY ,qN, writes the symbol x0 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). For Table 1 the DTM is represented by the following finite-state machine in Figure 1.

0,1

 

Figure 1: DTM State Diagram

Implement the DTM example provided in the course content under Module 3 (and above). 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:

1.   States method, this method should have all of the operations of your TM.

2.   Program line that executes the operations for each identified state, this should follow the n-tuple TM as described above for M.

3.   Print method that outputs the change in tape (x ≤ 30) after each transition function is executed.

4.   Write method, for tape larger than x 30 write the outputs to a file