Turing first described the Turing machine in an article published in 1936, 'On Computable Numbers, with an Application to the Entscheidungsproblem'.

A Turing machine

The read/write head is programmable. It is be helpful to think of the operation of programming as consisting of altering the head's internal wiring by means of a plugboard arrangement. To compute with the device, you program it, inscribe the input on the tape (in binary or decimal code, say), place the head over the square containing the leftmost input symbol, and set the machine in motion. Once the computation is completed, the machine will come to a halt with the head positioned over the square containing the leftmost symbol of the output (or elsewhere if so programmed).

The head and the tape

A Turing machine is an idealised computing device consisting of a read/write head (or 'scanner') with a paper tape passing through it. The tape is divided into squares, each square bearing a single symbol--'0' or '1', for example. This tape is the machine's general purpose storage medium, serving both as the vehicle for input and output and as a working memory for storing the results of intermediate steps of the computation.

States

The head contains a subdevice that I call the indicator. This is a second form of working memory. The indicator can be set to any one of a number of 'positions'. In Turing machine jargon, the position of the indicator at any time is called the state of the machine at that time. To give a simple example of the indicator's function, it may be used to keep track of whether the symbol last encountered was '0' or '1'. If '0', the indicator is set to its first position, and if '1', to its second position.

Atomic operations

There are just six types of fundamental operation that a Turing machine performs in the course of a computation. It can:

• read (i.e. identify) the symbol currently under the head
• write a symbol on the square currently under the head (after first deleting the symbol already written there, if any)
• move the tape left one square
• move the tape right one square
• change state
• halt.

The instruction table

A program or 'instruction table' for a Turing machine is a finite collection of instructions, each calling for certain atomic operations to be performed if certain conditions are met. Every instruction is of the form:

If the current state is n and the symbol currently under the head is x, then write y on the square currently under the head [y may be identical to x], go into state m [m may be n], and - - - .

In place of - - - may be written either 'move left one square' or 'move right one square' or 'halt'.

An example

The machine in this example starts work with a blank tape. The tape is endless. The problem is to set up the machine so that if the scanner is positioned over any square and the machine is set in motion, it will print alternating binary digits on its tape, 0 1 0 1 0 1..., working to the right from its starting place, and leaving a blank square in between each digit.

In order to do its work the machine makes use of four states, labelled 'a', 'b', 'c' and 'd'. The machine is in state a when it starts work.

The table of instructions for this machine is as follows.The top line of the table reads: if you are in state a and the square you are scanning is blank then print 0 on the scanned square, move right one square, and go into state b.

state	scanned symbol	print	move	next state
a	blank	0	R	b
b	blank		R	c
c	blank	1	R	d
d	blank		R	a

A machine acting in accordance with this table of instructions toils endlessly on, printing the desired sequence of digits and leaving alternate squares blank.

Turing first described the Turing machine in an article published in 1936, 'On Computable Numbers, with an Application to the Entscheidungsproblem'.

A Turing machine

The read/write head is programmable. It is be helpful to think of the operation of programming as consisting of altering the head's internal wiring by means of a plugboard arrangement. To compute with the device, you program it, inscribe the input on the tape (in binary or decimal code, say), place the head over the square containing the leftmost input symbol, and set the machine in motion. Once the computation is completed, the machine will come to a halt with the head positioned over the square containing the leftmost symbol of the output (or elsewhere if so programmed).

The head and the tape

A Turing machine is an idealised computing device consisting of a read/write head (or 'scanner') with a paper tape passing through it. The tape is divided into squares, each square bearing a single symbol--'0' or '1', for example. This tape is the machine's general purpose storage medium, serving both as the vehicle for input and output and as a working memory for storing the results of intermediate steps of the computation.

States

The head contains a subdevice that I call the indicator. This is a second form of working memory. The indicator can be set to any one of a number of 'positions'. In Turing machine jargon, the position of the indicator at any time is called the state of the machine at that time. To give a simple example of the indicator's function, it may be used to keep track of whether the symbol last encountered was '0' or '1'. If '0', the indicator is set to its first position, and if '1', to its second position.

Atomic operations

There are just six types of fundamental operation that a Turing machine performs in the course of a computation. It can:

• read (i.e. identify) the symbol currently under the head
• write a symbol on the square currently under the head (after first deleting the symbol already written there, if any)
• move the tape left one square
• move the tape right one square
• change state
• halt.

The instruction table

A program or 'instruction table' for a Turing machine is a finite collection of instructions, each calling for certain atomic operations to be performed if certain conditions are met. Every instruction is of the form:

If the current state is n and the symbol currently under the head is x, then write y on the square currently under the head [y may be identical to x], go into state m [m may be n], and - - - .

In place of - - - may be written either 'move left one square' or 'move right one square' or 'halt'.

An example

The machine in this example starts work with a blank tape. The tape is endless. The problem is to set up the machine so that if the scanner is positioned over any square and the machine is set in motion, it will print alternating binary digits on its tape, 0 1 0 1 0 1..., working to the right from its starting place, and leaving a blank square in between each digit.

In order to do its work the machine makes use of four states, labelled 'a', 'b', 'c' and 'd'. The machine is in state a when it starts work.

The table of instructions for this machine is as follows.The top line of the table reads: if you are in state a and the square you are scanning is blank then print 0 on the scanned square, move right one square, and go into state b.

state	scanned symbol	print	move	next state
a	blank	0	R	b
b	blank		R	c
c	blank	1	R	d
d	blank		R	a

A machine acting in accordance with this table of instructions toils endlessly on, printing the desired sequence of digits and leaving alternate squares blank.

Use Principle of Mathematical induction to show that the polynomial P(X) = X3 - X, is divisible by 6, where X is a non-negative integer





Download this from Google Drive as PDF!

Use Principle of Mathematical induction to show that the polynomial P(X) = X3 - X, is divisible by 6, where X is a non-negative integer





Download this from Google Drive as PDF!

Discuss some real world problems, to which the techniques given below are applicable
(i) Divide & Conquer
(ii) Dynamic Programming
(iii) Greedy Approach

Interval scheduling is a class of problems in computer science, particularly in the area of algorithm design. The problems consider a set of tasks. Each task is represented by an interval describing the time in which it needs to be executed. For instance, task A might run from 2:00 to 5:00, task B might run from 4:00 to 10:00 and task C might run from 9:00 to 11:00. A subset of intervals is compatible if no two intervals overlap. For example, the subset {A,C} is compatible, as is the subset {B}; but neither {A,B} nor {B,C} are compatible subsets, because the corresponding intervals within each subset overlap.

The interval scheduling maximization problem (ISMP) is to find a largest compatible set - a set of non-overlapping intervals of maximum size. The goal here is to execute as many tasks as possible.

Reference : https://en.wikipedia.org/wiki/Interval_scheduling

Discuss some real world problems, to which the techniques given below are applicable
(i) Divide & Conquer
(ii) Dynamic Programming
(iii) Greedy Approach

Interval scheduling is a class of problems in computer science, particularly in the area of algorithm design. The problems consider a set of tasks. Each task is represented by an interval describing the time in which it needs to be executed. For instance, task A might run from 2:00 to 5:00, task B might run from 4:00 to 10:00 and task C might run from 9:00 to 11:00. A subset of intervals is compatible if no two intervals overlap. For example, the subset {A,C} is compatible, as is the subset {B}; but neither {A,B} nor {B,C} are compatible subsets, because the corresponding intervals within each subset overlap.

The interval scheduling maximization problem (ISMP) is to find a largest compatible set - a set of non-overlapping intervals of maximum size. The goal here is to execute as many tasks as possible.

Reference : https://en.wikipedia.org/wiki/Interval_scheduling

Discuss some real world problems, to which the techniques given below are applicable
(i) Divide & Conquer
(ii) Dynamic Programming
(iii) Greedy Approach

Dynamic programming used to avoid repetitive work. That can be achieve by remembering partial results.

Real World Problem : Min-Num-Coins

(Gives the minimum number of coins for Given Amount)

In Automated shop, someone purchased goods of Rs. 389, After billing Machine start showing few combination of change to achieve the Amount 389. Customer will select a combination and give the money. Similar If customer paid 500 to pay 389 then Shopkeeper will also calculate the change with minimum coins.

Aircraft stand assignment to minimize walking

Gate scheduling is concerned with assigning flights to terminal or ramp positions, called gates. It is a key activity in airport operations. With the increase of civil air-traffic and the corresponding growth of airports in the past decades, the complexity of the task has increased significantly. At large international airports, several hundreds of flights must be handled per day.

Discuss some real world problems, to which the techniques given below are applicable
(i) Divide & Conquer
(ii) Dynamic Programming
(iii) Greedy Approach

Dynamic programming used to avoid repetitive work. That can be achieve by remembering partial results.

Real World Problem : Min-Num-Coins

(Gives the minimum number of coins for Given Amount)

In Automated shop, someone purchased goods of Rs. 389, After billing Machine start showing few combination of change to achieve the Amount 389. Customer will select a combination and give the money. Similar If customer paid 500 to pay 389 then Shopkeeper will also calculate the change with minimum coins.

Aircraft stand assignment to minimize walking

Gate scheduling is concerned with assigning flights to terminal or ramp positions, called gates. It is a key activity in airport operations. With the increase of civil air-traffic and the corresponding growth of airports in the past decades, the complexity of the task has increased significantly. At large international airports, several hundreds of flights must be handled per day.

Discuss some real world problems, to which the techniques given below are applicable
(i) Divide & Conquer
(ii) Dynamic Programming
(iii) Greedy Approach

I am going to explain using real world systems around us

Government and Company: 

In real world, Government follows the divide and conquer approach to get all problem listed and resolve. Using State Leaders, District Leaders, Block Leader, Village Leader etc. 

Similar for the company, suppose someone purchased a Product from Patanjali, and He received an outdated product from store. For this problem He can't complain directly to CEO of Patanjali. 

CEO > Managers of different fields > Territorial Manager > Area Manager > Local Distributor > Then Local Shop

By this chain they can easily find the problem and solved in mannered way. 

Simple word, We can solve a big problem in small pieces and solve it, after solving each merge them together. 

So basically, divide any big problem into smaller problems (to make our life easy), solve individual problems and combine the solution of small problems to get the solution to big problem. Note that sometimes, there is no need for combining solutions of small problems.

Discuss some real world problems, to which the techniques given below are applicable
(i) Divide & Conquer
(ii) Dynamic Programming
(iii) Greedy Approach

I am going to explain using real world systems around us

Government and Company: 

In real world, Government follows the divide and conquer approach to get all problem listed and resolve. Using State Leaders, District Leaders, Block Leader, Village Leader etc. 

Similar for the company, suppose someone purchased a Product from Patanjali, and He received an outdated product from store. For this problem He can't complain directly to CEO of Patanjali. 

CEO > Managers of different fields > Territorial Manager > Area Manager > Local Distributor > Then Local Shop

By this chain they can easily find the problem and solved in mannered way. 

Simple word, We can solve a big problem in small pieces and solve it, after solving each merge them together. 

So basically, divide any big problem into smaller problems (to make our life easy), solve individual problems and combine the solution of small problems to get the solution to big problem. Note that sometimes, there is no need for combining solutions of small problems.