Digital computers have enhanced human capability in major walks of life and are still penetrating to diverse areas of human endeavor. Their pervasiveness is due to their ability to solve problems with ease and precision, which otherwise would take considerable amount of time for humans alone. One of its main characteristics is programmability (i.e. ability to instruct what to do), have made the wonders we see at present. The programs that run on them routes our communications world-wide, defeated Gary Kasparov (Russian Chess Master), guides our space shuttles into deep space, implement sophisticated medical procedures …etc.
The computing power available for us today is so enormous, that we don’t utilize it to its full extend, other than for frequent mail checks, play games, browse YouTube videos, Documentation etc. There is a wide gap in the technology available to us and its utilization. Computer Scientists and Technologists World-wide are ambitiously designing computing systems to be handled with ease for different background of people. We’ll focus onto see, what are the core skills needed by anyone to create the next Facebook, YouTube … And be part of this digital revolution.
These are the basics…
Firstly, one needs to develop Algorithm for the problem.
Secondly, Translate the Algorithm to executable codes using a suitable language.
Computers at a conceptual level basically do the following;
- Fetch data and instructions from memory (Input data for processing from keyboard, sensors…),
- Compare or check the data to a value (if, if-else…).
- Loop through a set of operations(for, while loops)
- Place the modified/unmodified data back to memory (Output data for display, actuation…).
As computers execute instructions sequentially, one needs to develop step by step procedure (Algorithm) for the problem at hand. An e.g. hypothetical Algorithm for Air-conditioning system would be
- STEP1: Input the desired Room Temperature (t) from the user.
- STEP2: Measure the room temperature (T)
- STEP3: if (T > t), then lower the actuation.
- STEP4: else if (T < t), then increase the actuation.
- STEP5: else, maintain the actuation.
- STEP6: Repeat STEP2.
The above hypothetical algorithm, typically describes series of steps a computer controlling an AC to follow. From the above one can deduce that the Algorithm,
- Gives provision to input data from the user.
- Senses the present Temperature.
- Checks the present Temperature to the input value and does the required actuation and
- Repeats (Loops) through the process.
Thus, when developing Algorithm, one has to break down the problem, into a series of steps containing the 4 constructs.
- Conditionals like if, if-else.
- Loops like while(), for()
Once you have broken down and described your problem using the above 4 constructs, then such problems are solvable by computers and you would need just to translate them to computer executable using a suitable language. Computer languages are being designed to be simple, such than once you have developed your Algorithm using the 4 constructs, it’s a direct job to code your Algorithm. Computer languages are designed in such a way that the programmer need to worry of every detail of the system (Like how should the data move from memory to processor or vice versa) and need only concentrate on developing and implementing Algorithms.
Understanding Computer Algorithms
For the case of simplicity, one can classify most of the Algorithms being executed by computers as Forward and Inverse. Forward Algorithms are similar to Hypothetical AC system. They have an input, a set of operations and an output. Examples of similar algorithms are billing system seen in supermarkets, ticketing systems seen in Transportations, Device driver codes, Encryption and Decryption algorithms … Forward Algorithms have a direct input-output relation.
Inverse Algorithms, unlike Forward Algorithms, there is no direct input – output relation. These Algorithms make computers play chess, checkers, gives the best possible route between two places considering Traffic, weather…etc. They assist in Cryptanalysis (breaking Ciphers). These Algorithms are used for industrial and medical tomography, locating oil, natural gas and other resources interior of the earth, reconstructing Astronomical images from telescope data …etc. They are often categorized under the realm of ‘Artificial Intelligence ‘.
We shall see a simple implementation of both kinds of Algorithms using a Mind game known as ‘MASTERMIND‘.
Python files for the game are available for download here.
Mastermind (Bulls and Cows numerical version) is an old code breaking mind game. It’s a two-player game, played with pencil and paper. Here one player assumes a unique 4 digit number and the opponent tries to guess it, with a limited number of chances (usually 8). The first player replies the matching digits in terms of number of bulls and cows.
If the matching digits are in the correct position, then it is a “bulls”, if in a different position it is a “Cow”.
- Secret number : 1953
- Opponent’s try : 1235
Player1 replies: 1 bull and 2 cows. (The bull is “1”, the cows are “5” and “3”)
Then again the second player is given a second chance to guess the correct number based on present information and the game continues.
Mastermind is a typical example of both Forward and Inverse Algorithms for Computers.
In Forward Problem, Algorithm is to be developed such that computer assumes a secret 4 digit number, and a human tries to guess it back. Each time user guesses a 4 digit number, inputs it, computer calculates the matches in terms of number of bulls and cows and gives the response back to the user. User is given a limited number of chances to guess the number.
In Inverse Problem, Algorithm is to be developed such that computer tries to guess the 4-digit number assumed by a human. User assumes a unique 4 digit, computer tries a guess and human inputs the matches (number of bulls and Cows) from user. Computer is given a limited number of chances to guess the number.
Mastermind – Forward Problem
You are free to try the Algorithm, here the challenge is to develop an algorithm that selects a unique four digit number, inputs the user guess and computer computes the matches (Bulls and cows) and outputs the matches to the user. The Algorithm could be described as:
- STEP1: Assume a 4 digit unique number and store in a variable named NUM.
- STEP2: Set bulls and cows = 0
- STEP3: inputs the user guess and store it in a variable named userGuess.
- STEP4: Take each digit of userGuess and compare it with each digits of NUM,
if They are equal and in the same position
then increment bulls by one
else if they are equal and in different position
then increment cows by one
- STEP5: Respond to the user with the Bulls and cows.
- STEP6: while chances are there OR (Bulls not equal to 4),
A python implementation of the Algorithm is provided along.
Mastermind – Reverse Problem
(Here computer tries to guess the number assumed by a Human.)
Humans have an intuitive approach in solving such problems and it’s quite difficult to capture such intuition into Algorithms. Computers only obey instructions and here we need to develop an algorithm that can make computers behave like an intuitive being.
Computers are competent in generating a long list of numbers, traversing through the list, comparing two or three lists. Humans are error prone in such approaches and very slow. This competency of computer is what we will use here to develop an Algorithm that can guess the unique number.
Looking the problem, one can see that there are 4536 combination of unique four digit numbers possible for the game. Initially computer chooses a number from the possible lists as first guess and outputs it to the user. User Inputs the matches (Number of Bulls and Cows) for the guess. Now computer can use the first guessed number and traverse through the list to see which all numbers give the same matches (as given by the user) and generate a new list. This list will be shorter than previous lists and computer can choose a number from the new list as second guess. And the process continues. This could briefly be described as:
STEP1: Generate all the 4536 unique numbers and store them in a list.
STEP2: Check if user is ready with the number. If ‘yes’ continue else ‘wait’
STEP3: Respond the first number in the list(Response) to user as the guess.
STEP4: Get the user feedback (number of bulls and cows).
STEP5: Compare the Response through each number in the list and generate the matches (Bulls and Cows).
STEP6: If the matches generated is same as the user matches,
store them in a new list,
else discard the number from the list.
STEP7: Update the list and continue STEP3, until Bulls = 4.
The Algorithm, when tested guesses the number with 5 – 6 moves.
A python implementation of the Algorithm is provided along.
Algorithms drive computers into placing our satellites in orbits, route our communications world-wide, they brought to life Facebook, YouTube, Google and innumerable other computer applications. They still drive the need to invent the Next computing systems.
Developing and implementing algorithms is a key skill required by anyone to be part of this digital revolution. As computer scientists and Technologists world-wide are thriving to make computers as simple as possible for anyone to program and implement their ideas,
What will you make?