Problem solving techniques

Unit I

Introduction

1.1 HISTORY OF COMPUTER

Until the development of the first generation computers based on vacuum tubes,
there had been several developments in the computing technology related to the mechanical
computing devices.
Calculating Machines
ABACUS was the first mechanical calculating device for counting of large numbers. The
word ABACUS means calculating board. It consists of bars in horizontal positions on which
sets of beads are inserted. The horizontal bars have 10 beads each, representing units, tens,
hundreds, etc.
Napier’s Bones
was a mechanical device built for the purpose of multiplication in 1617ad. by an English
mathematician John Napier.
Slide Rule
was developed by an English mathematician Edmund Gunter in the 16 th century. Using
the slide rule, one could perform operations like addition, subtraction,multiplication and
division. It was used extensively till late 1970s
Pascal’s Adding and Subtraction Machine
was developed by Blaise Pascal. It could add and subtract. The machine consisted of
wheels, gears and cylinders.
Leibniz’s Multiplication and Dividing Machine
was a mechanical device that could both multiply and divide. The German philosopher
and mathematician Gottfried Leibniz built it around 1673.
Punch Card System
was developed by Jacquard to control the power loom in 1801. He invented the punched
card readerthat could recognize the presence of hole in the punched card as binary one and
the absence of the hole as binary zero. The 0s and 1s are the basis of the modern digital
computer.
Babbage’s Analytical Engine
 An English man Charles Babbage built a mechanical machine to do complex mathematical
calculations, in the year 1823. The machine was called as difference engine. Later, Charles
Babbage and Lady Ada Lovelace developed a general-purpose calculating machine, the
analytical engine. Charles Babbage is also called the father of computer.
Hollerith’s Punched Card Tabulating Machine
was invented by Herman Hollerith. The machine could read the information from a punched
card and process it electronically.

1.2 Characteristics and limitation of computer

Speed, accuracy, diligence, storage capability and versatility are some of the key
characteristics o f a computer. A brief overview of these characteristics are

Speed

The computer can process data very fast, at the rate of millions of instructions per
second. Some calculations that would have taken hours and days to complete otherwise, can
be completed in a few seconds using the computer. For example, calculation and generation
of salary slips of thousands of employees of an organization, weather forecasting that requires
analysis of a large amount of data related to temperature, pressure and humidity of various
places, etc.

Accuracy

Computer provides a high degree of accuracy. For example, the computer can accurately
give the result of division of any two numbers up to 10 decimal places.

Diligence

When used for a longer period of time, the computer does not get tired or fatigued. It can
perform long and complex calculations with the same speed and accuracy from the start till
the end.

Storage Capability

Large volumes of data and information can be stored in the computer and also retrieved
whenever required. A limited amount of data can be stored, temporarily, in the primary
memory. Secondary' storage devices like floppy disk and compact disk can store a large
amount of data permanently.

Versatility

Computer is versatile in nature. It can perform different types of tasks with the same
ease. At one moment you can use the computer to prepare a letter document and in the next
moment you may play music or print a document.

Limitation or Drawback of Computer

1. No I.Q. : Computer is not a magical device. It performs only those works which man
can does but the main difference is that computer can work those operations with very
high speed and reliable accuracy. It has no any intelligence quality or thinking power
2. No Feeling: Because computer is only a machine, it has no feeling like human being.
It has no brain for thinking as man can does. Man had successes to make computer
memory be different inventions of technology but he couldn’t make heart.
3. Data Machine Readable: Computer data is read by machine, meaning data obtained
from the computer can be read by the computer itself.
4. It required power to operate.
5. Problem may occur due to system breakdown

1.3 Hardware/ anatomy of computer

CPU
The CPU is the brain of the system. It executes all the program code from the operating
system and the applications the user runs and processing of data. It sends CPU commands to
direct the actions of all the other components in the computer.

Memory

RAM, which stands for Random Access Memory, is the short term memory that the computer
uses to keep track of what it's doing. If the computer loses power, anything stored in RAM is
lost.

Secondary Storage Device

Computer storage device is any type of hardware that stores data. The most common type of
storage device, which nearly all computers have, is a hard drive.

INPUT AND OUTPUT DEVICES

Input Devices

Input device is a hardware device that sends information to the computer.

Mouse

Mouse is a pointer device. The mouse allows an individual to control a pointer in a graphical
user interface (GUI). Utilizing a mouse a user has the ability to perform various functions
such as opening a program or file and does not require the user to memorize commands.

Digital camera

A type of camera that stores the pictures or video it takes in electronic format instead of to
film.

Web Cam

A camera connected to a computer that allows anyone connected to the Internet to view still
pictures or motion video of a user.

Joystick

A computer joystick allows an individual to easily navigate an object in a game such as

navigating a plane in a flight simulator.

Keyboard
One of the main input devices used on a computer, a computer keyboard looks very similar
to the keyboards of electric typewriters, with some additional keys.

Microphone

Sometimes abbreviated as mic, a microphone is a hardware peripheral that allows computer

users to input audio into their computers.

Scanner

Input device that allows a user to take an image and/or text and convert it into a digital file,
allowing the computer to read and/or display the scanned object.

Output Device

Any peripheral that receives and/or displays output from a computer. Below are some
examples of different types of output devices commonly found on a computer.

Monitor

A monitor is a video display screen. Monitor is also called as Visual Display Unit (VDU) or
Video Display Terminal (VDT).

CRT (Cathode Ray Tube)

Monitors are built very similarly to older (tube) television sets. They are heavy, bulky, take
up a lot of desk space, and emit radiation.

LCD (Liquid Crystal Display)

Monitors are thin and flat. They are light, compact, take up very little desk space emit no
known radiation.

Printer

A printer is an output device responsible for taking computer data and generating a hard
copy of that data.

1.4 Types of computer

Computer can be classified in two ways based on their different type and sizes and their
data-handling capabilities.
PC(personal computer)

A personal computer also known as a multi-purpose microcomputer.

Its price, capacity and size make it feasible for individual use.

Personal computer can be operated directly by the user without the need for experts or
technicians

It consists of a microprocessor as a CPU, memory, input unit and output unit.

Example

Laptops and desktop computers.

Desktop computer

A pc is designed to be in one location and fits on or under a desk.

Laptop computer

A laptop computer is a battery-powered portable pc that is small enough to rest in the

users lap and can be carried from one place to another.

Characteristics of personal computer

 It is relatively cheaper than other computer

 It is designed for personal or individual use
 Time-sharing features like mini and mainframe computer are not available in these
types of computer
 Suitable for personal work such as making an assignment ,watching a movie ,or at
the office for office work,etc.
 Easy to use
 It uses a limited number of software
 It is the smallest size

Workstation

A workstation is a special-purpose computer system designed for technical or scientific

applications

It consists of a fast microprocessor, with a large amount of RAM and a high –speed
graphic adapter.
 They are usually connected to local area networks and run multi-user operating systems

It is generally used to perform a specific task with great accuracy

Characteristics of workstation

 It is expensive compared to personal-computer

 They are exclusively designed for complex tasks
 It provides large storage capacity better graphics and a more powerful CPU
when compared to a PC
 Some workstations are designed or certified for use only with a specific
application such as AutoCAD, avid Express studio HD, or 3D studio Max.

Minicomputers
Minicomputers are digital computers, generally used in multi-user systems. They have
high processing speed and high storage capacity than the microcomputers. Minicomputers
can support 4–200 users simultaneously. The users can access the minicomputer through their
PCs or terminal. They are used for real-time applications in industries, research centres, etc.
PDP 11, IBM (8000 series) are some of the widely used minicomputers.
Characteristics of a minicomputer
 Its weight is low
 Because of its low weight, it is easy to carry anywhere
 Less expensive than a mainframe computer
 Faster than workstation
Mainframe Computers
Mainframe computers are multi-user, multi-programming and high performance
computers. They operate at a very high speed, have very large storage capacity and can
handle the workload of many users. Mainframe computers are large and powerful systems
generally used in centralized databases. The user accesses the mainframe computer via a
terminal that may be a dumb terminal, an intelligent terminal or a PC. A dumb terminal
cannot store data or do processing of its own. It has the input and output device only. An
intelligent terminal has the input and output device, can do processing, but, cannot store data
of its own. The dumb and the intelligent terminal use the processing power and the storage
facility of the mainframe computer. Mainframe computers are used in organizations like
banks or companies, where many people require frequent access to the same data. Some
examples of mainframes are CDC 6600 and IBM ES000 series.
Characteristics of mainframe computer
 It is also expensive computer
 It has a high storage capacity and great performance
 It can process a he amount of data very quickly
 It runs smoothly for a long period of time
 Its lifespan is also long
Super computer
They are biggest and fastest computers
They are designed to handle large amounts of data such as processing trillions of
instructions in one second.
A supercomputer consists of thousands of interconnected that help execute user
instruction very quickly
The first supercomputer was build by Roger Cray in 1976
Characteristics of supercomputer
 Data processing speed is very fast
 These are very expensive
 It can perform up to ten trillion distinct calculations each second
 Supercomputer used in large organisation to manage a huge amount of data such
as the stock market
 It is used in various scientific research and development to analyse data
obtained from the exploration of solar systems satellites etc.

1.5Software

Computer software, or simply software, is a collection of data or computer instructions

that tell the computer how to work.

The computer hardware cannot perform any task on its own. It needs to be instructed
about the tasks to be performed. Software is a set of programs that instructs the computer
about the tasks to be performed.

Software tells the computer how the tasks are to be performed; hardware carries out
these tasks. Different sets of software can be loaded on the same hardware to perform
different kinds of tasks.
Types of Software:

Software can be broadly classified in two categories:

1. System Software, and

2. Application Software.

System software provides the basic functions that are performed by the computer. It is
necessary for the functioning of a computer.

Application software is used by the users to perform specific tasks. The user may choose the
appropriate application software, for performing a specific task, which provides the desired
functionality.

The system software interacts with hardware at one end and with application software at the
other end. The application software interacts with the system software and the users of the
computer. Figure below shows the hierarchy of software, hardware and users.

System Software

System software is a type of computer program that is designed to run a computer's hardware
and application programs. If we think of the computer system as a layered model, the system
software is the interface between the hardware and user applications.

For example, when you buy a computer, the system software would also include different
device drivers. When you request for using any of the devices, the corresponding device
driver software interacts with the hardware device to perform the specified request. If the
appropriate device driver for any device, say a particular model of a printer, is installed on the
computer, the user does not need to know about the device driver, while printing on this
printer.

The purposes of the system software are:

❖ To provide basic functionality to computer,

❖ To control computer hardware, and

❖ To act as an interface between user, application software and computer hardware

System software for the management and functionality of computer relates to the functioning
of different components of the computer like processor, input and output devices etc.

System software for the development of application software provides services required for
the development and execution of application software. System software provides the
software tools required for the development of application software.

Loader: A loader is the part of an operating system that is responsible for loading programs
and libraries. It is one of the essential stages in the process of starting a program, as it places
programs into memory and prepares them for execution.

Linker: A linker is a computer program that takes one or more object files generated by a
compiler and combines them into one, executable program.

Application software

Application Software The software that a user uses for accomplishing a specific task is the
application software. Application software may be a single program or a set of programs. A
set of programs that are written for a specific purpose and provide the required functionality
is called software package. Application software is written for different kinds of applications
—graphics, word processors, media players, database applications, telecommunication,
accounting purposes etc.

Some examples of application software packages are as follows:

• Word Processing Software: For writing letter, reports, documents etc. (e.g. MS-WORD).

• Image Processing Software: For assisting in drawing and manipulating graphics (e.g. Adobe
Photoshop).

• Accounting Software: For assisting in accounting information, salary, tax returns (Tally
software).

• Spreadsheet Software: Used for creating budget, tables etc. (e.g. MS-Excel).

• Presentation Software: To make presentations, slide shows (e.g. MS-PowerPoint)

• Suite of Software having Word Processor, Spreadsheet and Presentation Software: Some
examples are MS-Office, Google Docs, Sun Open office, Apple iWork.

• CAD/CAM Software: To assist in architectural design. (e.g. AutoCAD, Autodesk)

• Geographic Information Systems: It captures, stores, analyzes, manages, and presents data,
images and maps that are linked to different locations. (e.g. ArcGIS)

• Web Browser Software: To access the World Wide Web to search documents, sounds,
images etc. (e.g. Internet Explorer, Chrome).
1.6 programming languages
• A language is the main medium of communicating between the Computer systems and
the most common are the programming languages.
• As we know a Computer only understands binary numbers that is 0 and 1 to perform
various operations but the languages are developed for different types of work on a
Computer.
• A language consists of all the instructions to make a request to the system for
processing a task.
• From the first generation and now fourth generation of the Computers there were
several programming languages used to communicate with the Computer.
• Here we will go in the detail of the Computer language and its types.
Types of programming language
Machine language
Assembly language
High level language
4 GL and 5 GL
Machine Language
• The first generation language developed for communicating with a Computer.
• It is written in machine code which represents 0 and 1 binary digits inside the
Computer string which makes it easy to understand and perform the operations.
• As we know a Computer system can recognize electric signals so here 0 stands for
turning off electric pulse and 1 stands for turning on electric pulse.

• It is very easy to understand by the Computer and also increases the processing speed.

Advantage :
No need of a translator or interpreter to translate the code, as the Computer can directly
can understand.
Disadvantage :
Remember the operation codes, memory address every time you write a program and also
hard to find errors in a written program.
Assembly Language
• The second generation programming language that has almost similar structure and set
of commands as Machine language.
• Here we use words or names in English forms and also symbols.
• The programs that have been written using words, names and symbols in assembly
language are converted to machine language using an Assembler.
• Because a Computer only understands machine code languages that’s why we need an
Assembler that can convert the Assembly level language to Machine language so the
Computer gets the instruction and responds quickly.
Disadvantage :
it is written only for a single type of CPU and does not run on any other CPU.
• But its speed makes it the most used low level language till today which is used by
many programmers.

High Level Languages

• The assembly language was easier to use compared with machine language as it
relieved the programmer from a burden of remembering the operation – codes and
addresses of memory location.
• Even though the assembly languages proved to be great help to the programmer, a
search was continued for still better languages nearer to the conventional English
language.
 • The languages developed which were nearer to the English language, for the use of
writing the programmer in 1960 were known as High Level languages.
• The different high level languages which can be used by the common user are
FORTRAN, COBOL, BASIC, PASCAL, PL-1 and many others.
• Each high level language was developed to fulfil some basic requirements for particular
type of problems.
• But further developments are made in each language to widen its utility for different
purposes.
Fourth Generation Languages(4GLs)
• The 3GLs are procedural in nature i.e., HOW of the problem get coded i.e., the
procedures require the knowledge of how the problem will be solved.
• Contrary to them, 4GLs are non procedural.
• That is only WHAT of the problem is coded i.e., only ‘What is required’ is to be
specified and rest gets done on its own.
• Thus a big program of a 3GLs may get replaced by a single statement of a 4GLs.
• The main aim of 4GLs is to be cut down on developed and maintenance time and
making it easier for users.

Fifth Generation Language :

The fifth-generation languages are also called 5GL. It is based on the concept of artificial
intelligence. It uses the concept that rather than solving a problem algorithmically, an
application can be built to solve it based on some constraints, i.e., we make computers learn
to solve any problem. Parallel Processing & superconductors are used for this type of
language to make real artificial intelligence.

Examples: PROLOG, LISP, etc.

Advantages :
1. Machines can make decisions.

2. Programmer effort reduces to solve a problem.

3. Easier than 3GL or 4GL to learn and use.

Disadvantages :
1. Complex and long code.

2. More resources are required & they are expensive too.

 1.7 Features of good programming language

 Simplicity: the language must offer clear and simple concepts that are easy to
understand, facilitating learning and application. But simplicity can be a difficult
balance to strike without compromising the overall capability of the language.
 Capability: apart from being easy to use, the language must be well-equipped with a
robust set of features to perform a wide range of tasks. If a programming language
was designed to be used in a specific area, it must provide the necessary means
(operators, structures, and syntax) to achieve ideal results.
 Abstraction: it is the language’s ability to define and use complicated structures or
operations while ignoring certain low level details.
 Efficiency: programming languages that can be translated and executed efficiently
help avoid the excessive consumption of memory and time.
 Structuring: the language allows programmers to write their code according to
structured programming concepts to avoid creating errors.
 Compactness: a language with this characteristic can express operations concisely
without having to write too many details.
 Principle of Locality: also known as the locality of reference, this phenomenon
describes a computer program’s preference for continually accessing the same areas
of memory over a short span of time. By enabling the usage of loops and subroutines,
a programming language can exploit the principle of locality for optimising the
overall performance of an application.
1.7 Translators
Any program written in a high-level language is known as source code. However, computers
cannot understand source code. Before it can be run, source code must first be translated into
a form which a computer understands.

A translator is a program that converts source code into machine code. Generally, there are
three types of translator:

 compilers

 interpreters

 assemblers
 Compilers

A compiler takes the source code as a whole and translates it into machine code all in one go.
Once converted, the object code can be run unassisted at any time. This process is
called compilation.

Compilers have several advantages:

 Compiled programs run quickly, since they have already been translated.

 A compiled program can be supplied as an executable file. An executable file is a file that
is ready to run. Since an executable file cannot be easily modified, programmers prefer to
supply executables rather than source code.

 Compilers optimise code. Optimised code can run quicker and take up less memory space.

Compilers also have disadvantages:

 The source code must be re-compiled every time the programmer changes the program.

 Source code compiled on one platform will not run on another - the machine code is
specific to the processor's architecture.

Interpreters

An interpreter translates source code into machine code one instruction at a time. It is similar
to a human translator translating what a person says into another language, sentence by
sentence, as they speak. The resulting machine code is then executed immediately. The
process is called interpretation.

Interpreters have several advantages:

 Instructions are executed as soon as they are translated.

 Errors can be quickly spotted - once an error is found, the program stops running and the
user is notified at which part of the program the interpretation has failed. This makes
interpreters extremely useful when developing programs.

Interpreters also have several disadvantages:

 Interpreted programs run slowly as the processor has to wait for each instruction to be
translated before it can be executed.
 Additionally, the program has to be translated every time it is run.

 Interpreters do not produce an executable file that can be distributed. As a result, the
source code program has to be supplied, and this could be modified without permission.

 Interpreters do not optimise code - the translated code is executed as it is.

Assemblers

Assemblers are a third type of translator. The purpose of an assembler is to translate assembly
language into machine code.

Whereas compilers and interpreters generate many machine code instructions for each high-
level instruction, assemblers create one machine code instruction for each assembly
instruction.