COMPUTER PROBLEM SOLVING

PROGRAMS AND ALGORITHMS

The vehicle for the computer solution to a problem is a set of explicit and unambiguous instructions
expressed in a programming language. This set of instructions is called a program. A Program may also be
thought of as an algorithm expressed in a programming language. An algorithm therefore corresponds to a
solution to a problem that is independent of any programming language.
To obtain the computer solution to a problem once we have the program we usually have to supply the
program with input or data. The Program then takes this input and manipulates it according to its instructions
and eventually produces an output which represents the computer solution to the problem. The realization of
the computer output is but the last step in a very long chain of events that have led up to the computer
solution to the problem.
Our goal in this work is to study in depth the process of algorithm design with particular emphasis on the
problem-solving aspects of the task,. There are many definitions of an algorithm. The following definition is
appropriate in computing science. An algorithm consists of a set of explicit and unambiguous finite steps
which, when carried out for a given set of initial conditions, produce the corresponding output and terminate
in a finite time.
REQUIREMENTS FOR SOLVING PROBLEMS BY COMPUTER
From time to time in our everyday activities, we employ algorithms to solve problems. For example, to look up
someone's telephone number in a telephone directory we need to employ an algorithm. Tasks such as this are
usually performed automatically without any thought to the complex underlying mechanism needed to
effectively conduct the search. It therefore comes as somewhat of a surprise to us when developing computer
algorithms that the solution must be specified with such logical precision and in such detail. After studying
even a small sample of computer problems it soon becomes obvious that the conscious depth of
understanding needed to design effective computer algorithms is far greater than we are likely to encounter in
almost any other problem-solving situation.

TOP-DOWN DESIGN
The primary goal in computer problem-solving is an algorithm which is capable of being implemented as
a correct and efficient computer program. In our discussion leading up to the consideration of algorithm
design we have been mostly concerned with the very broad aspects of problem-silving. We now need to
consider those aspects of problem-solving and algorithm design which are closer to the algorithm
implementation.
Once we have defined the problem to be solved and we have at least a vague idea of how to solve it, we
can begin to bring to bear powerful techniques for designing algorithms. The key to being able to successfully
design algorithms lies in being able to manage the inherent complexity of most problems that require
computer solution. People as problem-solvers are only able to focus on, and comprehend at one time, a very
limited span of logic or instructions. A technique for algorithm design that tries to accommodate this human
limitation is known as top-down design or stepwise refinement.
Top-down design is a strategy that we can apply to take the solution of a computer problem from a
vague outline to a precisely defined algorithm and program implementation. Top-down design provides us
with a way of handling the inherent logical complexity and detail frequently encountered in computer
algorithms. It allows us to build our solutions to a problem in a stepwise fashion In this way, specific and
complex details of the implementation are encountered only at the stage when we have done sufficient
groundwork on the overall structure and relationships among the various parts of the problem.
IMPLEMENTATION OF ALGORITHMS
The implementation of an algorithm that has been properly designed in a top-down fashion should be an
almost mechanical process. There are, however, a number of points that should be remembered.
If an algorithm has been properly designed the path of execution should flow in a straight line from top
to bottom. It it important that the program implementation adheres:: this top-to-bottom rule. Prohgrams (and
subprogrars implemented in this way are usually much easier understand and debug. They are also usually
much easier to modify should the need arise because the relationships between various parts of the program
are much more apparent.
THE EFFICIENCY OF ALGORITHMS
 Efficiency considerations for algorithms are inherent tied in with the design, implementation, and
analysis of algorithms. Every algorithm must use up some of a computer's resources to complete its task. The
resorces most relevant in relation to efficiency are central processing time (CPU time) and internal memory.
Because of the high cost of computing resources it is always desirable to algorithms that are economical in the
use of CPU : memory. This is an easy statement to make but one that is often difficult to follow either because
of bad design habits, or the inherent complexity of the problem, or both. As with most other aspects of
algorithm design, there is no recipe for designing efficient algorithms. Despite there being some generalities
each problem has its own characteristics which demand specific responses to solve the problem efficiently.
Within the framework of this last statement we will try to make a few suggestions that can sometimes be
useful in designing efficient algorithms.
EARLY DETECTION OF DESIRED OUTPUT CONDITIONS
The bubble sort also provides us with an example of another related type of inefficiency involving
termination. It sometimes happens, due to the nature of the input data, that the algorithm establishes the
desired output condition before the general conditions for termination have been met. For example, a bubble
sort might be used to sort a set of data that is already almost in sorted order. When this happens it is very
likely that the algorithm will have the data in sorted order long before the loop termination conditions are
met. It is therefore desirable to terminate the sort as soon as it is established that the data is already sorted.
To do this all we need to do is check whether there have been any exchanges in the current pass of the inner
loop. If there have been no exchanges in the current pass the data must be sorted and so early termination can
be applied (a check of algorithm 5.3 reveals how this is implemented for the bubble sort). In general, we must
include additional steps and tests to detect the conditions for early termination. However, if they can be kept
inexpensive (as in the bubble sort) then it is worth including them. That is, when early termination is possible,
we always have to trade tests and maybe even storage to bring about the early termination.
TRADING STORAGE FOR EFFICIENCY GAINS
A trade between storage and efficiency is often used to improve the performance of an algorithm. What
usually happens in this type of tradeoff is that we precompute or save some intermediate results and avoid
having to do a lot of unnecessary testing and computation later on.
One strategy that it sometimes used to try to speed up an algorithm is to implement it using the least
number of loops. While this is usually possible, inevitable it makes programs much harder to read and debug.
It is therefore usually better to stick to the rule of having one loop do one job just as we have one variable
doing one Job. When a more efficient solution to a problem is required it is far better to try to improve the
algorithm rather than resorting to "programming tricks" that tend to obscure what is being done. A clear
implementation of a better algorithm is to be preferred to a "tricky" implementation of an algorithm that is
not as good. We are now left with the task of trying to measure the efficiency of algorithms.
THE ANALYSIS OF ALGORITHMS
There are usually many ways to solve any given problem. In computing, as in most efforts of human endeavor,
we are generally concerned with "good" solutions to problems. This raises certain questions as to just what do
we mean by a "good" solution to a problem? In algorithm design "good" has both qualitative and quantitative
aspects. There are often certain esthetic and personal aspects to this but, on a more practical level, we are
usually interested in a solution that is economical in the use of computing and human resources. Among other
things, good algorithms usually possess the following qualities and capabilities :
1. They are simple but powerful and general solutions.
2. They can be easily understood by others, that is the implementation is clear and concise without being
"tricky".
3. They can be easily modified if necessary.
4. They are correct for clearly defined situations.
5. They are able to be understood on a number of levels.
6. They are economical in the use of computer time, computer storage and peripherals.
7. They are documented well enough to be used by others who do not have a detailed knowledge of
their inner workings.
8. They are not dependent on being run on a particular computer.
9. They are able to be used as a sub procedure for other problems.
10. The solution is pleasing and satisfying to its designer-a product that the designer feels proud to have
created
 These qualitative aspects of a good algorithm are very important but it is also necessary to try to provide
some quantitative measures to complete the evaluation of "goodness" of an algorithm. Quantitative measures
are valuable in that they can give us a way of directly predicting the performance of an algorithm and of
comparing the relative performance of two or more algorithms that are intended to solve the same problem.
This can be important because the use of an algorithm that is more efficient means a saving in computing
resources which translates into a saving in time and money.
EXCHANGING THE VALUES OF TWO VARIABLE
PROBLEM ~
Given two variables, a and b, exchange the values assigned to them.
ALGORITHM DEVELOPMENT
The problem of interchanging the values associated with two variables involves a very fundamental
mechanism that occurs in many sorting and data manipulation algorithms. To define the problem more clearly
we will examine a specific example.
Consider that the variables a and b are assigned values as outlined below. That is,
Starting configuration
a b
721 463
This means that memory cell or variable a contains the value 721, and memory cell or variable b contains the
value 463. Out task is to replace the contents of a with 463, and the contents of b with 721. In other words we
want to end up with the configuration below:
Target configuration
a b
463 721
To change the value of a variable we can use the assignment operator. Because we want a to assume the
value currently belonging to b, and b the value belonging to a we could perhaps make the exchange with the
following assignments:
a : = b ; (1)
b : = a ; (2)
where": =" is the assignment operator. In(1)": =" causes the value stored in memory cell b to be copied into
memory cell a.
Let us work through these two steps to make sure they have the desired effect. We started out with the
configuration
a b

721 463

then after execution of the assignment a : = b we have

a b
463 463
The assignment (1) has changed the value of a but has left the value of b untouched. Checking with our target
config uration we see that a has assumed the value 463 as required. So far so good! We must also check on b.
When the assignment step (2) i.e. b: = a is made after executing step (1) we end up with :
a b
463 463
In executing step (2) a is not changed while b takes on the value that currently belongs to a. The configuration
that we have ended up with does not represent the solution we are seeking. The problem, arises because in
making the assignment. :
a:=b
we have lost the value that originally belonged to a (i.e. 721 has beeen lost). It is this value that we want b to
finally assume. Our problem must therefore be started more carefully as:
new value of a : = old value of b;
new value of b : = old value of a What we have done with our present proposal is to make the assignment
 new value ofb: = new value of a
In other words when we execute step (2) we are not using the value a that will make thing work correctly-
because a has already changed.
To solve this exchange problem we need to find a way of not destroying "the old value of a" when we make
the assignment
a:=b
A way to do this is to introduce a temporary variable t and copy the original value of a into this variable before
executing step (1). The steps to do this are :
t : = a;
a:=b
After these two steps we have
a t b
463 721 463
We are better off than last time because now we still have the old value of a stored in t. It is this value that we
need for assignment to b. We can therefore make the assignment
b: = t
After execution of this step we have:
a t b
463 721 721

Rechecking with our target configuration we see that a and b have now been interchanged as required
The exchange procedure can now be outlined.
ALGORITHM DESCRIPTION
1. Save the original value of a in t.
2. Assign to a the original value of b.
3. Assign to b the original value of a that is stored in t
The exchange mechanism as a programming tool is most usefully implemented as a procedure that accepts
two variables and returns their exchanged values
APPLICATIONS
Sorting algorithms.

COUNTING
PROBLEM
Given a set of n student's examination marks (in I range 0 to 100) make a count of the number of stud€ that
passed the examination. A pass is awarded for all i of 50 and above.
ALGORITHM DEVELOPMENT
Counting mechanisms are very frequently used in computer algorithms.
Generally a count must be made of the number of items in a set which possess some particular
property or which satisfy some particular condition or conditions. This class of problems is typified by the
"examination marks" problem.
As a starting point for developing a computer algorithm for this problem we can consider how we
might solve a particular example by hand. Suppose that we are given the set of marks
55, 42,77 63, 29,57, 89
To make a count of the passes for this set we can start at the left, examine the first mark (i.e. 55), see if it is >
50, and remember that one student has passed so far.
The second mark is then examined and no adjustment is made to the count.
When we arrive at the third mark we see it is > 50 and so we add one to our previous count.
The process continues in a similar manner until all marks have been tested.
In more detail we have :
Marks Counting details for passes
55 previous count = 0
 current count = 1
Order in 42 previous count = 1
current count = 1
which 77 previous count = 1
current count = 2
marks 63 previous count = 2
current count = 3
are 29 previous count = 3
current count = 3
examined 57 previous count = 3
current count = 4
89 previous count = 4
current count = 5
.-. Number of students passed = 5
1
* After each mark has been processed the current count reflection the number of students that have passed
in the t marks list so far encountered.
We must not ask, now can the counting be achieved? From our example above we see that every time we
need to increase the count we build on the previous value. That is

current_count = previous_count + 1 ,
When, for example, we arrive at mark 57, we have
previous_count = 3
Current_count therefore becomes 4. Similarly when we get to the next mark (i.e. 80) the current_count
of 4 must assume the role of previous_count.
This means that whenever a new current_count is generated it must then assume the role of
previous_count before the next mark is considered.
The two steps in this process can be represented
by
current_count = previous_count + 1 (1)
previous_count = current_count (2)
These two steps can be repeatedly applied to obtain the count required. In conjunction with the
conditional test and input of the next mark we executed step (1), followed by step (2), followed by step (1),
followed by step (2) and so on.
Because of the way in which previous_count is employed in step (1) we can substitute the expression for
previous_current : in step (2) into step (1) to obtain the simpler expression
current_count: = current_count + 1

Tt
(new value) (old value)
The current_count on the RHS (right-hand side) of the expression assumes the role of previous_count. As this
statement involves an assignment rather than an equality (which would be impossible) it is a valid computer
statement. What is describes is the fact that the new value of current_ count is obtained by adding 1 to the old
value of current_ count.
Viewing the mechanism in this way makes it clear that the existence of the variable previous_count in its
own right is unnecessary. As a result we have a simpler counting mechanism.
The essential steps, in our pass-counting algorithm can therefore be summarized as : while less than n
marks have been examined do (a) read next mark, (b) if current mark satisfies pass requirement then add one
to count.
Before any marks have been examined the count must have the value zero. To complete the algorithm
the input of the marks and the output of the number of passes must be included. The detailed algorithm is
then as described below.
ALGORITHM DESCRIPTION
1. Prompt then read the number of marks to be processed.
2. Initialize count to zero.
 3. Which there are still marks to be processed repeatedly do

(a) read next mark.

(b) if it is a pass (i.e. > 50) then add one to count.
4. Write out total number of passes.

APPLICATIONS
All forms of counting.
SUMMATION OF A SET OF NUMBERS

PROBLEM
Given a set of n numbers design an agorithm that adds these numbers and returns the resultant sum. Assume
n is greater than or equal to zero.
ALGORITHM DEVELOPMENT
One of the most fundamental things that we are likely to do with a computer is to add a set of n
numbers. When confronted with this problem in the absence of a computer we simply write the numbers
down one under the other and start adding up the right-hand column. For example, consider the addition of
421, 583 and 714.
421
583
714
...8
In designing a computer algorithm to perform this task we must take a somewhat different approach. The
computer has a built-in device which accepts two numbers to be added, performs the addition, and returns
the sum of the two numbers (See Fig. 1). In designing an algorithm to add a set of numbers a primary concern
is the mechanism for the addition process. We will concentrate first on this aspect of the problem before
looking at the overall design.
The simplest way that we can instruct the computer's arithmetic unit to add a set of numbers is to write
down an expression that specifies the addition we wish to be performed. For our three numbers mentioned
previously we could write
S : = 421 + 583 + 714 (1)
The assignment operator causes the value resulting from the evaluation of the right-hand side of
statement (1) to be placed in the memory cell allocated to the variable s.
Expression (1) will add three specific numbers as required. Unfortunately it is capable of doing little else.
Suppose we wanted to sum three other numbers. For this task we would need a new program statement.
FIRST NUMBER
(A)

FIRST NUMBER SUM OF TWO

(A) NUMBERS
(A+B)

It would therefore seem reasonable that all constants in expression (1) could be replaced by variables.
SECOND
We would(B)
NUMBER then have
S : = a + b + c (2) Expression (2) adds any three numbers provided they have been previously assigned as
vlaues or contents of a, b, and c respectively. Expression (2) as the basic of a program for adding numbers is
more general and more useful than expression (1).
It still has a serious deficiency- it can only add sets of three numbers.
A fundamental goal in designing algorithms and implementing programs is to make the programs general
enough so that they will successfully handle a wide variety of input conditions.
That is, we want a program that will add any n numbers where n can take on a wide range of values.
 The approach we need to take to formulate an algorithm to add n numbers in a computer is different
from what we would do conventionally to solve the problem. Conventionally we could write the general
equation.
S = (a1 + a2 + a3 +……..+ an) (3)

n
Or equivalently S = ∑ ai (4)
i =l

(Reminder: ∑ is the mathema cal summa on operator)

We could also write a computer program statement somewhat like equation (3) to add our n numbers
but this is not very practical because we want to be able to change n (we may want to use the program to sum
a different sized set of numbers).
We must therefore look for a better mechanism more in keeping with the way a computer is naturally
designed to do things. Several facts about computers are relevant for our current problem.
Firstly, computers are well suited to do repetitive things. Secondly, the computer's adding device is
designed so that it can only add two numbers at a time.
We might therefore ask how we can formulate an algorithm for the addition of n numbers that makes
best use of these facts.
One way to do this that takes note of the fact that} the computer adds two numbers at a time it to start
by adding the first two numbers a., and a2. That is,
s = a., + a2 (1) We could then proceed by adding a3 to the s computed in step (1).
s = s + a3 (2)
(cf. counting statement in algorithm 2.2)
In a similar manner:
s:=s+a4
s:=s+a5
. . .
. . . (3,….,n-1)

. . .
s:=s+an

From step (2) onwards we are actually repeating the same process over and over- the only difference is
that values of a and s change with each step.
th
For general i step we have
s : = s + ai+1 (i)
This general step can be placed in a loop to iteratively generate the sum of n numbers.
The algorithm we want to develop for summing n numbers should perform correctly for all values of n
greater than or equl to 0 (i.e. n > 0). It must therefore work correctly forthesumofzero(n = 0)and the sum of 1
(n = 1) numbers. This means the step (1) we have used is not appropriate. However, if we replace i + 1 in the
general step (i, by i and substitute i = 1 we get:
s : = s + a1 {r)
The step (1') will be correct provided s : = 0 before this step is executed. It follows that all sums for n > 1
can be generated iteratively. The instance where n = 0 is a special case which cannot be generated iteratively.
The sum of zero numbers is zero and so we can generate the first sum directly by the assignment.
s:=0
The core of the algorithm for summing n numbers therefore involves a special step followed by a set of n
iterative steps. That is,
1. Computer first sum (s = 0) as special case.
2. Build each of the n remaining sums from its predecessor by an iterative process.
3. Write out the sum of n numbers.
The only other considerations involve the input of n, the numbers to be summed, and the input of successive
numbers with each iterative step. Our complete algorithm can now be outlined.
ALGORITHM DESCRIPTION
 Given a number n, compute n factorial (written as n!) where n > 0.
ALGORITHM DEVELOPMENT
1. Prompt and read in the number of numbers to be summed.
2. Initialize sum for zero numbers.
3. While less than n numbers have been summed repeatedly do

(a) read in next number,

(b) compute current sum by adding the number read to the most recent sum.
4. Write out sum of n numbers

PROBLEM
We can start the development of this algorithm by examining the definition of n ! We are given that
n! = 1 x 2 x 3 x ........... x (n - 1) x n for n > 1
and by definition 0! = 1
In formulating our design for this problem we need to keep in mind that the computer's arithmetic unit
can only multiply two numbers at a time.
Applying the factorial definition we get
0! = 1; 1! = 1 x 1 ; ' 2! = 1 x 2;
3! = 1 x 2 x 3; 4! = 1 x 2 X 3 X 4
We see that 4! contains a//the factors of 3!. The only difference is the inclusion of the number 4. We can
generalize this by observing that n! can always be obtained from (n-1)! by simply multiplying it by n (for n > 1).
That is,
. n! = nx (n- 1)! for n > 1
Using this definition we can write the first few factorials as:
11 = 1 x 0!; 2! = 2 x 1!; 3! = 3 x 2!; 4! = 4 * 3!

If we start with p = 0! = 1 we can rewrite the first few steps in computing n! as :

p:=p (1) =0!

p:=p*1 =1!

p:=p*2 (2…n+1) =2!

p:=p*3 =3!

p:=p*4 =4!

From step (2) onward we are actually repeating the same process over and over. For the general (i + 1
)th step we have.
p: = p*1 (i+1)
This general step can be placed in a loop to interatively generate n!. This allows us to take advantage of
the fact that the computer's arithmetic unit can only multiply two numbers at a time.
In many ways this problem is very much like the problem of summing a set of n numbers (algorithm
2.3).
In the summation problem we performed a set of additions, whereas in this problem we need to
th
generate a set of products. It follows from the general (i + 1 ) step that all factorials for n > 1 can be
generated iteratively. The instance where n = 0 is a special case which must be accounted for directly by the
assignment
p:=1 (by definitions of 0!)
The central part of the algorithm for computing n! therefore involves a special initial step followed by n
iterative steps.
1. Treat 0! as a special case ( p : = 1)
 2. Build each of the n remaining products p from its predecessor by an iterative process.
3. Write out the value o n factorial.
ALGORITHM DESCRIPTION
1. Establish n, the factorial required where n > 0.
2. Set product p for 0! (special case). Also set product count to zero.
3. While less than n products have been calculated repeatedly do

(a) increment product count,

th
(b) compute the i product p by multiplying i by the most recent product.
4. Return the result nl.
This algorithm is most usefully implemented as a function that accepts as input a number n and returns as
output the value of n!. In the Pascal implementation p has been replaced by the variable factor.
APPLICATIONS
Probability, statistical and mathematical computations.

REVERSING THE DIGITS OF AN INTEGER

PROBLEM
Design an algorithm that accepts a positive integer and reverses the order of its digits.
ALGORITHM DEVELOPMENT
Digit reversal is a technique that is sometimes used in computing to remove bias from a set of numbers.
It is important in some fast information-retrieval algorithms. A specific example clearly defines the relationship
of the input to the desired output. For example.
Input: 27953
Output: 35972
Although we might not know at this stage exactly how we are going to make this reversal one thing is
clear-we are going to need to access individual digits of the input number. As a starting point we will
concentrate on this aspect of the procedure.
The number 27953 is actually
4 3 2
2 x 10 + 7 x 10 + 9 x 10 + 5 X 10 + 3
To access the individual digits it is probably going to be easiest to start at one end of the number and
work through to the other end.
The question is at which end should be start ? Because other than visually it is not easy to tell how many
digits there are in the input number it will be best to try to establish the identity of the least significant digit
(i.e. the rightmost digit).
To do this we need to effectively "chop off' the least significant digit in the number. In other words we
want to end up with 2795 with the 3 removed and identified.
We can get the number 2795 by integer division of the original number by 10
i.e. 27953 div 10 ^2795
This chops off the 3 but does not allow us to save it. However, 3 is the remainder that results from
dividing 27953 by 10. To get this remainder we can use the mod function. That is,
27953 mod 10 -> 3
Therefore if we apply the following two steps
r: = nmod 10 (1) =» (r = 3)
n : = ndiv 10 (2) => ( n = 2795)
we get the digit 3, and the new number 2795. Applying the same two steps to the new value of n we can
obtain the 5 digit. We now have a mechanism for iteratively accessing the individual digits of the input
number.
 Our next major concern is to carry out the digit reversal, when we apply our digit extraction procedure to
the first two digits we acquire first the 3 and then 5. In the final output they appear as :
3 followed by 5 (or 35)
If the original number was 53 then we could obtain its reverse by first extracting the 3, multiplying it by
10, and then adding 5 to give 35. That is,
3 x 10 + 5 -> 35
The last three digits of the input number are 953. They appear in the "reversed" number as 359.
Therefore at the stage when we have the 35 and then extract the 9 we can obtain the sequence 359 by
multiplying 35 by 10 and adding 9. That is,
35 x 10 + 9 ->359
Similarly
359 x 10 + 7 ->3597
and
3597 x 10 + 2 -> 35972

The last number obtained from the multiplication and addition process is the "digit-reversed" integer we
have been seeking. On closely examining the digit extraction, and the reversal process, it is evident that they
both involve a set of steps that can be performed iteratively.
We must now find a mechanism for building up the "reversed" integer digit by digit.
Let us assume that the variable dreverse is to be used to build the reversed integer. At each stage in
building the reversed integer its previous value is used in conjunction with the most recently extracted digit
Rewriting the multiplication and addition process we have just described in terms of the variable
dreverse we get
iteration Value of dreverse
[1] dreverse : = dreverse * 10 + 3 3
[2] dreverse : = dreverse * 10 + 5 35
[3] dreverse : = dreverse * 10 + 9 359
. .
. .
. .

Therefore to build the reversed integer we can use the construct:

dreverse: = (previous value of dreverse) * 10
+ (most recently extracted righmost digit) The variable dreverse can be used on both sides
of this expression. For the value of dreverse to be correct (i.e. dreverse = 3) after the first iteration it must
initially be zero. This initialization step for dreverse is also needed to ensure that the algorithm function
correctly when the input number to be reversed is zero.
What we have not established yet is under what conditions should the iterative process terminate.
The termination condition must in some way be related to the number of digits in the input integer. In fact
as soon as all digits have been extracted and processed termination should apply. With each iteration the
number of digits in the number being reversed is reduced by one, yielding the sequence shown in Table.
Accumulative integer division of the "number being reversed" by 10 produces the sequences 27953, 2795,
279,
In our example, when the integer division process is applied for a 5th time a zero results since 2 is less
than 10. Since at this point in the ( computation the "reversed" number has been fully constructed we can
use the zero result to terminate the interative process
Number being Reversed number
Step
reversed being constructed
27953 3 [1]
2795 35 [2]
279 359 [3]
27 3597 [4]
2 35972 [5]
The central steps in our digit reversal algorithm are:
1. While there are still digits in the number being reversed do
(a) extract the rightmost digit from the number being reversed and append this digit to the right hand
end of the current reversed number representation;
(b) Remove the rightmost digit from the number being reversed.
When we include input and output considerations and details on initialization and termination we arrive at the
following algorithm description.

ALGORITHM DESCRIPTION
Establish n, the positive integer to be reversed. Set the initial condition for the reversed integer dreverse.
While the integer being reversed is greater than zero do
Use the remainder function to extract the rightmost digit of the number being reversed,
Increase the previous reversed integer representation dreverse by a factor of 10 and add to it the
most recently extracted digit to give the current dreverse value;
(c)
Use integer division by 10 to remove the rightmost digit from the number being reversed.
This algorithm is most suitably implemented as a function which accepts as input the integer to be reversed
and returns as output the integer with its digits reversed.
APPLICATIONS
Hashing and information retrieval, data base applications.

BASIC CONCEPTS OF 'C LANGUAGE

• Identifiers and Keywords
• Constants • Data types
• Operators • Statements
• I/O Functions
• Control Structures
In this chapter we will discuss the elementry part of C Language like operators, statements, Input &
Output statements and Control structures etc.
IDENTIFIERS AND KEYWORDS
Identifiers can be defined as the name of the variables and some other program elements using the
combination of the following characters.
Alphabets : a .. z , A .. Z
Numerals : 0 .. 9
Underscores: _
Special Characters: All the characters other than listed as alphabets, numerals and underscore, are listed
as special characters. For example [ ],Blank Space,() etc.
In C Language, upper case and lower case letters are distinct and hence there are 52 letters in all. A
variable should not begin with a digit. Examples of valid identifiers are as under:
My_Name
i
I
h_hello
Here above the second and third variables are separate identifiers. Example of invalid identifiers are as
under:
3pq
a()rr
in tax
 In the first the identifier is starting with a digit which is not allowed. In second the special characters are
not allowed. In the third the space between the identifiers is not allowed.
Keywords ; The keywords are also identifiers but not defined by the user. They are the reserved words in
use. We should not choose them as variables or identifiers. There are only 32 keywords available in C
language. The list of keywords are as follows :
auto double if static
break else int struct
case enum long switch
char extern near typedef
const float register union
continue far return unsigned
default for short void
do goto signed while
CONSTANTS
There are three types of constants:
 String Constants
 Numeric Constants
 Character Constants

String Constants :
A String constant is a stream of characters enclosed within the quotation marks whose maximum length
is 255 characters. Following are the valid string constants :
□ 1 "the total value ="
□ 2 "$2000"
□ 3 "Welcome to the world of computers" .
Following is the list of invalid string constants:
□ 1 "hello pintu □ 2 'welcome home'
In the first the closing double quotation marks are not putted whereas in second the characters are not
enclosed in double quotation marks.
Numeric Constants :
Numeric constants are positive or negative numbers. There are two types of numeric constants -Integer
Constants and Real Constants. An integer constant is a sequence of digits. There are three types of integers
namely decimal, octal and hexadecimal. Example of valid decimal numeric constant" are as under:

- 120 0
213 23 + 128
The octal integer constants can be the combination of digits from the set 0 through 7 with a leading 0.
Examples of valid octal numeric constants are as under:
033
0
0441
Tho sequence of digits preceded by OX is considered as hexadecimal numeric constants. The
combination of digits from 0 to 9 and A to F will make a hexadecimal integer. Examples of valid hexadecimal
numeric constants are as under:
0X2
OXbaf
OX
| The general usage of octal and hexadecimal integers is not done in the programming. The second type of
numeric constant is real constant. These type of constants are used to represent the physical quantities like
pressure, temprature etc which vary continuously. These quantities are represented by numbers containing
fractional parts like 15.234. Such type of numbers are called real constants. Examples of real constants are as
under:
0.122
- 4.32
+ 23.33

Character constants :

A character within single quotation marks will represent a character constant. Examples of character
constants are as under:
'X'
'x'
' ?'
V
There are some backslash character constants used in the interactive C language programming. The
backslash (/') is used to denote the non printing cha^cters and other special characters for a specific
[Link] following is the list of backslash character constants.
•\a Alert a bell character
'
'\t' Horizontal Tab
'\n' New Line
'\b' Backspace
'\f Form Feed
V Carriage Return
'\v' Vertical Tab
'\" Single quote
'\0' Null character
'\?' Question Mark
'\000' Octal Value '\Xhhh' Hexadecimal Value
DATA TYPES
The types of data structures provided by C can be classified under the categories :
• Fundamental data types
• Derived data types

Fundamental data types :

The fundamental data types include the data types at the lowest level, i.e. those which are used for
actual data representation in the memory. All other data types are'based on the fundamental data types.
The fundamental data types are :
char - For characters and strings.
int - For integers.
float - For numbers with decimals.
Since the above data types are fundamental, i.e. at machine level, the storage requirement is hardware
dependent. The following table will show the storage requirement of the above data types.
Data type No. of bytes on a computer
char 1 bytes
Int 2 bytes
Float 4 bytes

Derived data types :

Derived data types are based on the fundamental data types, i.e. a derived data type is represented in
the memory as a fundamental data. Some of the derived data types with their storage requirements are
illustrated in the table.
 Data type No. of bytes on a computer
short int 2 bytes 4
long int bytes 8
double float bytes

The following table will summarize the data types

Data type Meaning of data type

char Character
int Integer
long int Long integer
short int Short integer
unsigned char Unsigned character
unsigned int Unsigned integer
unsigned short int Unsigned short integer
unsigned long int Unsigned long integer
float Floating point number
double Double precision floating point
number

DEFINING DATA
Definition of memory for any data, both fundamental and derived data types, is done in the following format.
[data type] [variable name],...;
All data are normally defined in the beginning of a function.
The definition
char ans;
The above statement defines a memory location of size one byte, of character type referred to as ans. The
following table illustrates the definition of various data types.
Data Data Memory Size Value
Definition Type Defined (Byte) Assigned
char a,c; char a and c 1
char a='Z'; char A 1 Z
int count; int count 2 —
int c = 10; int c 2 10
float ff; float ff 4
float f=10.1; float f 4 10.1

TEST : Write the appropriate definition for defining the variables

1 abc to store integers
2 chr to store a character value and assign a character to it.
3 f to store the value 90.89.
4 i, j to store integers and assign the value 1 to j
DEFINING STRINGS
The definition, char ans;
defines a memory location ans which is one byte in size and can store only one character. To define a memory
location with contiguous bytes, addressable by one variable name, the following definition would be used.
char str[10];
The above definition defines a memory location referred to as str containing 10 bytes for storing up to 9 valid
characters.
The following definition defines a string abc as a group of 7 contiguous bytes to store up to 6 valid characters.
Char abc[7];
In the above definitions, one extra byte is used internally by C language.
TEST : Write a appropriate definition for defining a string.
1 name to store 25 valid characters.
2 addr to store 30 valid characters.

OPERATORS IN 'C LANGUAGE

There is a rich list of operators available in C language. The different types of C operators and their usage
are explained in the following sections.
In C, there are some unusual operators used to perform the task of logical decision making, unlike the
other higher level language.
Following is the operators category in C language

1 Arithmetic operators
2 Assignment operators
3 Comparison and Logical operators
4 Bitwise operators
5 Unary operators
6 Ternary cperators

Arithmetic Operators :
These are the basic operators used in any programming language. Normally, these operators are
considered as basic operators and known as binary operators as they require two variables to be evaluated.
The following table shows the basic arithmetic operators.
Operator Operators Meaning
+ For Addition
— For Subtraction
* For Multiplication
/ For Division
% For Remainder (Modulo)
The / operator is used for division purpose. When we are dividing the value 40 by 8 then the answer will
be 5 but when we are dividing the 11 by 2 then the answer will be stored as 5. In this case one of the operands
should be a floating point value and the result will also be of floating point type. Identically, this also applies to
addition, subtraction and multiplication. For Is fer operations the value of the result is not seriously affected by
the type of operands.
For Example
5 + 3 = 8 (integer form),
0 + 3.0 = 8.0 (Floating point form)
The following notations will show that what will be the result of every expression.
Integer/Integer = Integer
Integer/Float = Float
Float/Integer = Float
Float/Float = Float
11/2 = 5 => 11.0/2.0 = 5.5
v
The result of / operator will give the quotient but when we want \ \e remainder then we should use the
operator %. 11 % 2 will give the remainder as 1.

Assignment operators :
The symbol = is use as a assignment operator. Fo example we want to store the value 10 to the integer
variable i then we will use the assignment operator = .
 in» j = 10; z = x + y;
where x and y are added and the result of this expression is assigned in the variable z.

[ Fundamentals of 'C Language Comparison and Logical operators

The comparison and logical operators are the operators very much required in the programs. The
following table will show the list of comparison and logical operators used in C language.
Operator Operators Meaning
< Less Than
> Greater Than
< Less than or equal to
> Greater than or equal to
= Equal to
Not equal to
&& Logical and operator
II Logical or operator
! Not operator

Bitwise operators :
There are certain situations wherein bitwise operations are to be performed, and this is possible in C
language. Following are the bitwise operators in the C language.
Operator Operators Meaning
& Bitwise AND
A Bitwise exclusive OR
I Bitwise inclusive OR
» Bitwise right shift
« Bitwise left shift
Bitwise compliment
Unary Operators :
The unary operators require only a single expression to produce a line. Unary operators usually precede their
single operands. Sometimes some unary operators may be followed by the operands such as incrementer and
decrementer. The most common unary operation is unary minus, where a minus sign precedes a numerical
constant, a variable or an expression. The following table shows the unary operators in C language.

Operator Operator Meaning

* Contents of the storage field to
which a pointer is pointing
& Address of a variable
++ Incrementer
-- Decrementer

Ternary operators :
C includes a very special operator called the ternary or conditional operator. It is called ternary because
it uses three expression. The ternary operators act like a shorthand version of the if else construct. The
general format of the ternary operator is : expM ? expr2 : expr3 which result either in expr2 or expr3 being
evaluated. If exprl is true, then expr2 is evaluated otherwise expr3 is evaluated.
For example,
result = (tot % 2 == 0) ? true : False;
In the above statement if tot % 2 returns 0 then the result will be true otherwise the result will be false.
STATEMENTS
A statement in a computer program carries out some action. There are three types of statements used in
C language; they are expression statement, compound statement and control statement.

Expression Statement:
 An expression statement consists of any valid C expression followed by a semicolon. The expression
statement is used to evaluate a group of expressions.
For example,
x=y; /*The value of y is assigned to variable x7 sum=x+y; /*
The value of x is added with the value of y and assigned to the variable sum*/

Compound Statement:
A group of valid C language expression statements placed within a { and } statement is called a
compound statement. The individual statement may be an expression statement, a compound statement or
even a control statement.
Note that the compound statement is not completed with a semicolon.
For example,
{
a=b+c;
x=x*x;
y=a+x;
Control Statement:
The control statement is used for the program flow and to check the conditions of the given expression
or a variable or a constant. The keywords of the control statements are normally predefined or reserved
words and the programmer may not use them as ordinary variables.
For example,
if (a>b) {
statement;
statement;
statement;
}
while (condition) {
statement;
statement;
statement;
}
The condition within brackets defined should be true then only the C compiler will execute the body of
the loop.

Input Output Functions & Control Structures

Standard Standard
Input device Output Device

C Language
The C Language environment assumes that the standard input device (Keyboard), the output device
(Monitor) and the standard output device (Monitor) are always linked to the environment. For standard input
output operations, the C environment uses stdin, stdout, stderr as references for accessing the devices.
C language as such does not provide for any input output operations as part of the language. They exists
as functions written in C language and are available in the standard C library along with other functions. These
input and output functions may be used by an.
programmer.
Any input or output operation takes place as a stream of characters. The standard input-output
functions may be dealt under character based input output functions and under string based(stream of
characters) input output functions.
The standard input output functions are buffered i.e. each device has an associated buffer through which
any input or output operation takes place. After an input operation from the standard input device, care must
be taken to clear the standard input buffer lest the previous contents of the buffer interfere with subsequent
input operations. After output operations, the buffer need not be cleared since subsequent output data will
overwrite the previous buffer contents.
Character input Output Functions :
The following small program will accept a single character from the keyboard and will displays it on the
standard output device monitor.
# include <stdio.h>
main()
{
/*program for accept & display a character*/
char chr;
chr = getc(stdin);
fflush(stdin);
putc([Link]);
}
The function main first defines a memory location, chr of char data type and then invokes the functions
getc & putc.
/* ------ */ this is the comment entry. We can put the comment entries in every program for programmers
convenience.
The funtion getc accepts the input device-reference (stdin) to read one character from the standard input
device. The character react is returned in the variable chr of type character. The function putc accepts two
parameters one as the variable in which the read value is stored and another is the reference stdout for
standard output device to output one character. The funtion fflush() clears the buffer associated with a
specified input output device. It is a good programming practice to clear the buffer even if there are no
subsequent input operation in a function.

The #include includes the specified file as part of a function at the time of compilation. Hence contents of
the included file are compiled along with the function being compiled.
The statement #include <stdio.h> includes, at the time of compilation, the contents of the standard
input output file , stdio.h which contains definitions of stdin, stdout and stderr. Whenever the references
stdin, stdout and stderr are used in a function, the statement #include <stdio.h> has to be used.
TEST : Write a program to accept a character and display it 3 times.
getchar() & putchar() are the another character handling funtions which can be used instead of getc() and
putc() functions. The above written program can be write by using the getchar and putchar functions.
# include <stdio.h>
main()
{
/*program for accept & display a character*/
char chr;
chr = getchar();
fflush(stdin);
putchar(chr);
TEST : Write a program to accept a character and display it 3 times unsing getcharQ and putcharQ functions.

String based Input Output Functions :

The functions getc(), putc(), getcharQ and putchar() performs character based input outputs. The C
language provides the functions gets() and puts() for string based input and output.
The following small program will accept a string of 10 characters from the keyboard and display it on the
standard output device monitor.
# include <stdio.h>
 main()
{
/*program for accept & display a string*/
char chr[21];
gets(chr);
fflush(stdin);
puts(chr);
}
The funtion puts() acceps, as parameter, a string variable or a string constant (enclosed in double quotes) for
the display on the standard output device monitor. The functions gets() accepts a stream of characters and
stores it in the variable specified. The string will be terminated by the NULL character '\0'.
The puts() function causes the cursor to jump to the next line after printing the string.
TEST :
1) Write a program to accept a string and display it 2 times.
2) Write a program to accept your name and diaplay it in the following format
My Name is : Dinesh Tiwari

Formatted Input Output Functions :

C language provides standard funtions for performing formatted input and output. These functions
accept as parameters a format specification string and a list of variables. The format specification string
consists of a spcification for each of the variables in terms of its data type, called conversion character and
width of input.

Formatted Output:
The function printf() is used for formatted output to standard output based on a format specification.
The format specification alongwith the data to be output, are the parameters to the printf() function.
The syntax of the printf() function is as follows:
printf("Format specification",Datal, Data2,..);
For example, printf("%d\n",num);
The following are the format specification available in C language
%d - The data value will be of type integer.
%c - The data value will be of type character.
%S - The data value will be of type string (stream of characters).
%f - The data value will be of type float or double.
Other symbols permitted in the format specification string are :
\n For new line. \t For tab.
The format specification string may also have text.
For example:
Printf(“The total value is %d Rs.",val);
If the value of val is 100 then the output of the above said statement will be the total value is 100 Rs.
TEST :
1) What will be the output of the following program
#include <stdio.h>
main()
{
 char c,str[10];
int i=10;
float f= 10.10;
printf("Enter the string\n");
gets(str);
fflush(stdin);
printf("i=%d\tf=%f\nc=%c\tstr=%s \n",i,f,c,str);
getch();
}
Between the character, % and the conversion character, there may be :
• a minus sign denoting left adjustment of the data.
• a digit specifying the minimum width in which the data is to be output. If the data has the larger number
of characters than the specified width, the width occupied by the output is larger. If the data consists of fewer
characters than the specified width, it is padded to the right (if minus sign is specified) o*to the left (if no
minus sign is specified) with blanks. If the digit is prefixed with a zero, the padding is done with zeros instead
of blanks.
• a period separates the width from the next digit.
• a digit specifying the precision (number of decimal places for numeric data) or the maximum number of
characters to be output.
letter l(ell) to indicate that the data item is a long integer and not an int.

Following table shows the resulting output of data, according to the format specification string :
Format specifi- Data Output
cation string
l% 2dl 9 | 9|
l% 2dl 123 |123|
l% 03d! 9 |009|
I%- 2dl 7 |7 |
l% 5.3dl 2 |002|
l% 3.1 dl 15 | 15|
l% 3.5dl 15 |00015|
i% 5sl "output string" loutput stringl
l%15J "output string" I output string I
l%15.5sl "output string" I output string I
l%fl 83.88 I 88.880000 I
l%4.1fl 88.88 I 88.8 I

The following example shows that the data can be output as another datatype based on the conversion
character.

#include <sdtio.h>
main()
{ int num = 65;
printf(“The value of num is %d\n",num);
printf("Character equivalent of %d is %c\n",num,num);
}
The output of the above program is:
The value of num is 65 Character equivalent of 65 is A
TEST :
1) Write a program to display the appropriate character value of number 71.
2) What will be the output of the following program.
#include <stdio.h>
main()
{
printf("%c",65);
}
Formatted Input:
The function scanf() is used for formatted input from standard input and provides many of the
conversion facilities of the function printf().
The syntax of the scanf() is as follows :
scanf("format specification",datal, data2,...);
The scanf function reads and converts characters from the standard input and according to the format
specification string and store the input in memory locations represented by the other arguments.
The following example will show you how scanf will be used.
scanf ("%d",&i);
where i is an integer type of variable. The & sign is 'jsed with the integer, char & float type of data values
not with the string type of format specification e.g. scanf ("%s",name);
This will accept a stream of characters & terminated on space. The difference in gets() & scanf() function
is that the gets() funtion accepts the string up to enter key pressed means that string is terminated by NULL
('\0') character whereas the scanf terminates the string on space.
#include <stdio.h>
main()
{
char str1[25],str2[25];
printf("Enter first string\n");
scanf("%s",str1);
fflush(stdin);
printf(“Enter second string\n");
gets(str2);
fflush(stdin);
printf(“The first string is %s\n",str1);
printf(“The second string is %s",str2);
getch();
}
TEST :
1) Write a program to accept a name and age of a student and print it with the help of scanf & printf
statements.
CONTROL STATEMENTS
The control statement is used for the program flow and to check the conditions of the given expression
or a variable or a constant. The keywords of the control statements are normally predefined or reserved words
and the programmer may not use them as ordinary variables. Control statements or control structures are
mainly used to have the control over the programs. When programmer wants to use the conditions in his
programs or wants to do some repetitive tasks then he has to use the control statements. There are many
control structure which are available in C language. They are : if……else, switch..case, while, do..while and for.
If construct:
 The first control statement of C language is construct. It works on the condition, if the condition i true
then it will execute the true part of the construct and if the condition is false then it will execute the el or false
part of the construct. For example
if (a>b)
printf(“a is greater\n");
else
printf(“b is greater\n");
In the above example if the condition is true then "a is greater will be printed on to the screen else it will
display the message "b is greater". Here there is only one statement in if and else part so, we don't have to
write the statements in opening and closing curly braces.
TEST :
1) Write a program to accept two numbers and find greater of two numbers. We can also do the nesting
of if statement means that if within a if statement. The following structure will display the nested if
if (cond)
if(cond)
{ statement;
statement;
}
else
{ statement;
statement;
}
else if(cond)
{ statement;
statement;
}
else
{ statement;
statement;
}
TEST :
1) Write a program to accept a number between 1 to 7 & display the appropriate day assume Monday is
first day. e.g.
Input Number: 3
Output : Wednesday

Switch. Case Construct:

Switch case construct is used for executing the instructions according to the specified value.
Here the statements will be executed according to the value inputted by the user. The different cases
will be defined and can be exited by each case by using the break statement.
So, the break statement is used to come out from the loop. The structure of the switch case is as
follows.
Switch(Val) {
case 1 : statement;
break;
case 2 : statement;
break;
 case 3 : statement;
break;
case 4 : statement;
break;
default : statement;
}
Here val may any integer type data or it may be a character data.
TEST :
1) Write a program to accept a number between 1 to 7 & display the appropriate day using switch case
statement assume Monday is first day. e.g.
Input Number: 3
Output : Wednesday

LOOPS

First, what does mean by a loop ?

When we want to execute some statements again and again for specific conditions then we should have
to keep those statements in loops. So, loop is nothing but the iterative statements performing up to a given
condition i.e. if the condition is true then the body of loop will be executed and as soon as condition becomes
false then the body of loop will not be executed. In C language there are three loops available. Tney are as
follows.
- do..while loop.
- while loop.
- for loop.
Each loop will be executed for the true condition. The syntax of do while is
do {
statement; statement; statement;
} while(cond);
In this the body of loop will be executed first then the condition will be checked out. The statements
will be executed for one time although the condition '3 false in first time.
For example
int i = 1;
do
{
printf("%d\n",i);
i = i + 1; or i++;
} while(i<=10);
In the above example the value of i will be printed on screen from 1 to 10. But if we put the value of i as
11 initially then only first time it will perform the body of loop because the condition becomes checked after
performing the body of loop and it is false in first time.
The next loop (while) is little bit different from the first one. In this loop the condition is first checked out
and if the condition is true then and only then the body of loop will be executed. The syntax of the while ioop
is as follows.
while(cond) {
statement;
statement;
statement;
}
For example
 int i = 1;
while(i<=10)
{
printf("%d\t",i);

}
In the above example the values from 1 to 10 will be printed on the screen. But it will not print anything
if the value of i is 11 initially. So, this is the difference between the while and do..while loop that in case of
while loop the condition is checked first whereas in the do...while loop the body of loop will be executed first
then the condition, will be checked.
The last but least loop is for loop. Generally this loop is used by the programmers. The function of this loop is
same as while loop but the initialization, condition and incr/decr will be defined in one statement. The syntax
of for loop is
for(initialisation; condition; incr./decr.)
{ statement;
statement;
statement;
}
For example
int i;
for(i=0; i<=10; i++)
{
“
printf( %d”,i);
}
Again, the result will be same as in the previous example. But the syntax is changed.
TEST :
1) Write a program to print the even numbers from 1 to 50 with while, do..while and for loop.

SOLVED PROGRAMS
Write a program to interchange the values of two variables.
#include<stdio.h>
main()
{ int a,b,c;
clrscr();
printf(“enter the value of a,b ");
scanf("%d%d",&a,&b);
c = a;
a = b;
b = c;
printf("%d %d",a,b);
getch();
}
Write a program to interchange the values of two variables without using third variable.
#include<stdio.h>
main()
{ int a,b;
clrscr();
printf("enter the value of a,b ");
scanf("%d%d",&a,&b);
 a = a + b;
b = a - b;
a = a - b;

printf("%d %d",a,b);
getch();
L
Write a program to generate a series
2 2 2 2
2 , 3 , 4 ......... n .
#include <stdio.h>
#include <conio.h>
main()
{
int i=0,n=0;
clrscr();
printf("Enter the value of n\n");
scanf("%d",&n);
fflush(stdin);
/*Series Starts*/
for(i=2;i<=n;i++)
{
printf("%d",i*i);
}
getch();
}
2 3 4 n
Write a program to generate a series 2 ,3 ,4 ,..n .
#include <stdio.h>
#include <conio.h>
#include <math.h>
main() {
int i=0,n=0;
clrscr();
printf(“Enter the value of n\n");
scanf("%d",&n);
fflush(stdin);
/*Series Starts*/
for(i=2;i<=n;i++)
{
printf("%d",pow(i,i));
}
getch();
}
Write a program to print the fibonnaci series

#include<stdio.h>
main()
 { long int c,i,n,a = 0,b = 1;
clrscr();
printf("How many numbers of ths series do you want ");
scanf("%ld",&n);
printf("%6ld\n%6ld\n", a,b);
for(i=3; ;i++)
{ c = a + b;
a = b;
b = c;
if(c<=n)
printf("%6ld\n", c);
else break;
}
getch();
}
Write a program to reverse a digit..
/*Reversing a digit*/
#include <stdio.h>
#include <conio.h>
void main()
{ int n=0,i=0,rn=0,r=0,q=0;
clrscr();
printf("Enter the Number for reversing\n");
scanf("%d",&n);
fflush(stdin);
printf("The reversed number is ");
while ( n > 0 )
{ r = n%10;
rn = rn * 10 + r;
q = n / 10;
n = q;
}
printf("%d",rn); getch();
}
Write a program to check the prime number.
#include<stdio.h>
#include<conio.h>
enum check { PRIME, NOTPRIME } flag;
main()
{ int i=1 ,n;
clrscr();
printf("Enter the number: ");
scanf("%d",&n);
flag = PRIME;
for(i=2;k=n/2;i++)
{ if(n%i==0)
{flag = NOTPRIME;
 break;
}
}
if(flag == PRIME)
printf("\n%d is a prime number",n);
if(flag == NOTPRIME)
printf("%d is not a prime number",n);
printf("\nPress any key to continue....");
getch();
}
Write a program to print the arm strong numbers between 1 to 500.
#include<stdio.h>
main()
{ int i,a,b,temp,n,x,sum=0; clrscr();
for(i=1;i<=500;i++) { n=i;
sum=0;
while(n > 0)
{ a = n%10;
b = n/10;
n = b;
x=a*a*a;
sum=sum+x;
}
if(sum==i)
{ printf("\n%d°,sum);
printf("ars no."); •
}
}
getch();
}
Write a program to check the arm strong number.
#include<stdio.h>
main()
{ int i,a,b,n,x,sum=0;
clrscr();
printf("Enter the number\n");
scanf("%d",&n);
fflush(stdin);
i=n;
sum=0;
while(n > 0)
{ a = n%10;
b = n/ 10;
n = b;
x=a*a*a;
sum=sum+x;
}
if(sum==i) {
printf("ars no.\n");
 }
else {
printf(“Not an ars no.\n");
}
}
getch();
}
Write a program to print the factorial of a given number.
/*Factorial*/
#include <stdio.h>
#include <conio.h>
void main()
{
int n = 0,f = 1,i=0;
clrscr();
printf("Enter the number for finding factorial\n");
scanf("%d",&n);
for(i = 1; i<=n; i++)
{
f = f*i ;
}
printf("The Factorial is : %d",f);
getchQ;

Print the pyramid-1

#include<stdio.h>
main()
{ int i,j,k,n; clrscr();
printf("how many lines
scanf("%d",&n);
for(i=1 ;i<=n;i++)
{ for(j=1;j<=40-i;j++)
printf("");
for(k=1;k<2*i;k++)
printf ("*");
printf("\n");
}
getch();
)
Print the pyramid-2
#include<stdio.h>
main()
{ int i,j,k,l,h;
clrscr();
printf("Enter the hight of pyramid");
scanf("%d",&h);
gotoxy(0,20);
 for(i=1 ;i<=h;i++)
{ for(j=1;j<=10-i;j++)
printf(" ");
for(k=1;k<2*i;k++)
{ printf("%d",k);
printf(" ");
}
printf("\n\n");
}
printf("===== “);
getch();
}
Print the pyramid -3
#include<stdio.h>
main()
{ int i,j,k,n;
clrscr();
printf("how many lines ");
scanf("%d",&n);
for(i=1 ;i<=n;i++)
{ for(j=1;j<=40-i;j++)
printf("");
for(k=1;k<2*i;k++)
printf("*");
printf("\n");
}
for(i=n;i>=1 ;i--)
{ for(j=40-i;j>=1;j--)
printf("");
for(k=2*i;k>1;k--)
printf ("*");
printf ("\n");
}
getch();
}
Print the Floyds
#include<stdio.h>
#include<conio.h>
main()
{ int i=0 , num=0;
int j , n;
clrscr();
printf("How many rows do you want: ");
scanf("%d",&n);
while(++i<=n)
{ for(j = 1 ;j<=i;j++)
 printf("%4d",++num);
printf("\n");
}
getch();
}
Draw two triangles
#include<stdio.h>
#include<conio.h>
main()
{
int i=0,j=0,n=20,num;
int col = 39,row = 13;
clrscr();
printf("How many rows of the figure U want...");
scanf("%d",&n);
clrscr();
num = n;
row = row - n/2;
while(i++<n)
{ j = j+(M)*3;
while(num)
{ if(col-j>0 && row >0 && row < 25) {
gotoxy(col-j,row);
printf("%2d",num);
}
if(col+j<77 && row > 0 && row< 25) {
gotoxy(col+j,row);
printf("%2d",num);
}
j += 3;
num--;
}
num = n - i;
j = 0;
row++;
}
getch();

ADVANCED CONCEPTS OF C LANGUAGE

• Arrays • Pointers
• Functions • Structures
Here, we will discuss only the concepts of functions, arrays, pointers and structures and their programs.
Our main objective is to learn how to implement and design the programs based on different topics."
ARRAYS
 An Array is a contiguous area in the memory referred to by a common name. So, when we are declaring
the arrays then they are statically allocates the memory means that a fixed number of bytes will be reserved
for storing the values. They are static in nature. They are of two types : one dimensional and
multidimensional arrays. In one-D array the subscript will be only one whereas in multi-D arrays the subscripts
are defined on the basis of their dimensions.

Defining Arrays
In general, defining an array of any type, whether of fundamental data type or of derived data type is
done in the following format:
<data type> <name of array> [number of elements]
char str[10];
is for defining a character array, str to store 10 characters where str[0] to str[9] is for storing valid characters
and str[10] for storing the string terminator
'\0\
When a string is input using any of the string based functions, namely scanf() and gets(), the null character is
automatically appended to the string in memory as the string terminator. In same manner we can define the
integer and float type arrays.
int a[10];
float b[ 15];

Initialising the arrays

Arrays are groups of contiguous memory locations, the size'of which is specified at the time of definition
of the array in a function. Hence initialisation of an array involves moving element by element, or one data at a
time into the array. Thus initialisation of an array is not achievable by a single instruction. The exception to this
is when the array is defined outside a function. The following function illustrates this.
Char str[15]="this is a pen";
main()
{
printf("%s",str);
gets(str);
fflush(stdin);
printf("%s",str);
}
An array may also be initialized by specifying each element separated by commas, as in the following
function. The size of the array, in this case, may or may not be specified; it is defined by the number of
elements in the list. A character array needs a string terminator, '\0' character, as the last character, whereas
numerical arrays (int and float) may not have a terminator. A terminator in case of numeric arrays, would be
useful in the form of a low or high data value as the last element, if the number of elements in the array are
not known at-the time of processing. The following function illustrates initialization of arrays.
char str[ ] = {'M';O','N','D','A','Y','\0'};
float amt[ ] = [22.22,235.23,456.90};
main()
{
Statement;
Statement;
Statement;
.
.
.
}
Array elements can be initialised individually or with the help of control statements. If we have to
initialise the elements individually "then we have to define the subscript value e.g.
a[0]=0;
 a[1]=0;
When we are using the control statement with the array then the complete array will be initialised e.g.
for(i=0;i<10;i++)
a[i]=0;

Array Manipulation
There is more than one way for handling arrays in terms of performing operations on arrays namely,
through the use of subscript and through the use of pointers which Will be discussed later. In this section ,
arrays will be manipulated through the use of subscripts. Following programs on arrays will show that how the
arrays can be manipulated.
- Average of n numbers
#include <stdio.h>
#include <conio.h>
main()
{ int n[5],sum,i;
float avg; .'
clrscr();
printf(“Enter the numbers\n");
sum=0;
for(i=0;i<5;i++)
{ scanf("%d",&n[i]);
sum=sum+n[i];
}
avg =(sum / i);
printf("%f",avg);
getch();
}
Maximum number from n number of elements
#include<stdio.h>
main()
{ int a[9],i,x,n;
clrscr();
printff How many numbers do you want\n");
scanf("%d",&n);
if(n>9)
exit(0);
else {
printf(“Enter the value of a[0]\n”);

scanf("%d",&a[0]);

x = a[0];

printf(“Enter the numbers\n");

for(i=1 ;i<n;i++)

{ scanf("%d",&a[i]);

if(a[i] > x)
 x = a[i];

}
Printf(“Maximum number is ......... ");
printf("%d",x);
}
getch();
}
Reverse a String
#include <stdio.h>
main()
{ char a[10];
int i;
clrscr();
printf("enter the string”);
gets(a);
for(i=0;a[i]!='\0';i++);
for(;i!=-1;i--)
printf("%c",a[i]);
getch();

TEST
1) Write a program to print the the number of possible combinations of the number 1,2 and 3. This is
about the one dimensional arrays. There is another kind o x array which is called es multi dimensional array.
When there are two or more than two dimensions then it is ^aiied as multidimensional array. The declaration
of this type of array is as under.
char a[5][5];
int a[4][4];
float a[3]T2];
Where a is the array name and there are two subscript values representing the row and columns. The
number of elements in these arrays will be the multiplication of the [Link] example if we have an array
of 2 by 3 order then the number of elements of this array will be six. Mainly we are using the 2-D arrays which
is used for soiving the problems related with matrices. Here are some programs on the 2-D arrays.
Addition of two matrix
#include <stdio.h>
#include <conio.h>
main()
{ int a[2}[2],b[2][2],c[2][2],i=0,j=0;
clrscr();
printf(“Generate first matrix\n");
for(i=0;i<2;i++)
{
for(j=0;j<2;j++) {
scanf ("%d",&a[i][j]);
fflush(stdin);
}
 }
printf(“Generate second matrix\n");
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{ scanf(“%d”,&b[i][j]);
fflush(stdin);
}
}
/'Matrix Addition*/
c[0][0]=0;
for(i=0;i<2;i++) {
for(j=0;j<2;j++)
{
c[i][j]=a[i][j]+b[i][j];
}
}
/'Printing the resultant matrix*/
Printf(“The Resultant matrix is \n");
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
printf f%d\t",c[i]0]);
}
printf f\n");
}
getch();
}
Multiplication of matrix
#include <stdio.h>
#include <conio.h>
main()
{
int a[2][2],b[2][2],c[2][2],i=0,j=0,k=0;
clrscr();
printf ("Generate first matrix\n”);
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
scanf("%d",&a[i][j]);
fflush(stdin);
 }
}
printf("Generate second matrix\n");
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
scanf("%d",&b[i][j]);
fflush{stdin);
}
}
/'Matrix Multiplication*/
for(i=0;i<2;i++)
{
for(j=0;j<2;j++) {
c[i][j]=0;
for(k=0;k<2;k++) {
c[i][j]=c[i][j]+a[i][k]*b[k][j];
}
}
}
/'Printing the resultant matrix*/
Printf(“The Resultant matrix is :\n");
for(i=0;i<2;i++) {
for(j=0;j<2;j++) {
printf ("%d\t",c[i][j]);
}
printf("\n");
}
getch();
}
Transpose of a matrix
#include <stdio.h>
#include <conio.h>

main()
{ int a[2] [2],b[2] [2],!=0>0;
clrscr();
printf(“Generate the matrix\n");
for(i=0;i<2;i++)
{
for(j=0;j<2;j++) {
scanf("%d",&a[i][j]);
fflush(stdin);
}
}
 /*Transpose of Matrix */
for(i=0;i<2;i++)
{
for(j=0;j<2;j++)
{
b[i][j]=afj][i];
}
}
/*Printing the resultant matrix*/
printf(“The Resultant matrix is :\n");
for(i=0;i<2;i++) {
for(j=0;j<2;j++) {
printf("%d\t",b[i][j]);
}
printf("\n");
}
getch();
}
TEST :
1) Write a program to store and print the sales of 4 salesmen for products p1 ,p2, p3 and p4 also give the
total sales.

POINTERS
Consider the following declaration : int i=10;
The above statement implies that space in memory is reserved for the variable i.
This variable has the value 10 and is supposed to stce at memory location (or address) 1001. The
following picture will show you an idea about how space is occupied by the variable i.
i
10
1001

Now there is another variable ptr which holds the address 1001 then this ptr is nothing but the pointer.
So, pointers are the variables which holds the address of another variable. See the following instructions for
defining the pointers.
int i = 10;
int *ptr; /'Declaration of the pointer*/
ptr = &i; /"Initialisation of the pointer*/
Here ptr is the pointer which holds the address of the variable i. We had assigned the address of i to the
pointer ptr. This is done with the help of the symbol &. & means the address. Whereas, pointers can be
defined by the symbol *. The * makes the difference and the implication is : ptr is a pointer to an integer
variable. At the time of pointer manipulation we are using two symbols & and *. The * represents the value at
the address. The & represents the address.
So, if we print the value of *ptr from the above instructions then it will print the value 10 because ptr
pointing to the address 1001 and whatever will be the value at that address that will be printed.
TEST :
1) What will be the output of the following program.
 main()
{
int i = 5,*ptr; ptr=&i;

printf("%d\t%d",i,*ptr);

}
If we want to define the character pointer then use that data type. We can also increase or decrease the
position of the pointers by ptr++ or ptr--. String handling is much more comfortable after by using the pointers.
Following programs can explain the pointers in more detail.

Program for displaying the pointer values

#include<stdio.h>
include<conio.h>

main()
{
int i,*j,**k;
clrscr();
i = 10;
j = &i;
k = &j;
printf("\n%5d %5u",i,&i);
printf("\n%5u %5u %5d",j,&j,*j);
printf("\n%5u %5u %5u %5d\n ",k,&k,*k,**k);
(**k)++;
printf("\n%5d %5u",i,&i);
printf("\n%5u %5u %5d",j,&j,*j);
printf("\n%5u %5u %5u %5d\n ",k,&k,*k,**k);
(*k)++;
printf("\n%5d %5u",i,&i);
printf("\n%5u %5u %5d",j,&j,*j);
printf("\n%5u %5u %5u %5d\n ",k,&k,*k,**k);
getch();
}
String copy
#include<conio.h>
#include<stdio.h>
main()
{
char *sourse="gfdgfdgfg";
char *des="fhdhfd";
int i;
clrscr();
printf("Enter the string: ");
gets(sourse);
for(i=0;sourse[i]!='\0';i++)
 des[i] = sourse[i];
des[i] = '\0';
printf(“The string is: %s",des);
printf("\nPress any key to continue: ");
getch();
}
Length of a string (Method 1)
#include<conio.h>
#include<stdio.h>
main() {
char *str="gfdgfdgfg"; int i;
unsigned count=0; printf("Enter the string: "); gets(str);
for(i=0;str[i]!='\0';i++) count++;
printffThe length of the string is: %d",count); printf("\nPress any key to continue: "); getch();
L
Length of a string (Method 2)
#include<conio.h>
#include<stdio.h>
main()
{
char *str="gfdgfdgfg";
int i = 0;
unsigned count=0;
clrscr();
printf(“Enter the string: ");
do
{
fflush(stdin);
str[i] = getche();
if(str[i] == V)
break;
i++;
}
while(1);
str[i]= '\0';
for(i=0;str[i]!='\0';i++)
count++;
printf("\nThe length of the string is: %d",count);
printf("\nPress any key to continue: ");
getch();
}
TEST :
1) Write a program to reverse a string using pointer.
FUNCTIONS
Functions are used when we want to break a complete program into sub modules. These are nothing but
the subroutines of a main program. They are called from the main program and after manipulating the
instructions a value will be returned. As explained earlier, functions are the building blocks of C. All programs
definitely consist of one function - main() -and inevitably refer to, or, in programming terminology call or
invoke standard functions of C such as printf(), scanf() etc. as well as user-defined functions

Advantages of functions
Besides the obvious advantages of :
- reusability
- structuring of programs
functions also provide programmers a convenient way of designing programs in which complex
computations can be built into the functions. The programmer has to simply ensure that the required
parameters are passed to the function.
Generally, the standard functions require parameters like printf(), scanf() etc.
Similarly, user-defined functions may or may not have parameters. Consider following example:
main()
{
func();
}
func()
{
printf(“Hello World");
}
main() {

c=add(a,b);
printf("%d",c);
}
int add(int x,int x)
{
int z;
z = x + y;
return(z);
}

In the above example there are two types of parameters.

Actual parameters
Formal parameters
The actual parameters are defined in the function from where it is called and the formal parameters are
declared in the function body itself. Here the actual parameters are a and b whereas the formal parameters
are x and y.
Here the function returns a value. This is done using the return statement. If a function returns a value
other than int, then the function must be declared and defined as that type.
The next part deals with user-defined functions in detail.

Invoking Functions
In C programs, functions that have parameters, are invoked in two ways.
1) call by value
2 ) call by reference
In call by value method the values of the actual parameters are passed to the formal parameters.
Following example illustrates the call by value method.
 main() {
int a,b; a=10,b=20;
interchange(a,b);
}
interchange(int a, int b)
{
int c;
c=a;
a=b;
b=s.
printf("%d\t%d",a,b);
}
Here the values of a and b 10 and 20 will be passed to the formal parameters of the function interchage.
Call by reference means that the called function should be able jto refer to the variables of the caller
function directly, and not create its own copy of the values in different variables. This would be possible only if
the addresses of the variables are passed as parameters to the function. Consider the same program written
using call by reference :
main() {
int a=10,b=20;
interchage(&a,&b);
printf("%d\t%d",a,b);
}
interchage(int *x,int *y)
{
int *z;
*z=*a;
*a=*b;
*b=*z;
}
Here in this program the address of a and b will be hold by the pointers x and y.
TEST :
1 ) Write a program using function 'o calculate the area of a circle.
Programs on Functions
Convert into given base equivalent
#include<stdio.h>
#include<conio.h>
int convert(int num,int base);
main()
{
int n,b;
clrscr();
printf("Enter the decimal number:");
scanf("%d",&n);
printf(“Enter the base in which U want to convert the number: ");
scanf("%d",&b);
 printf(“The equivalent is: ");
convert(n.b);
printf(“\nPress any key to continue....");
getch();
}
int convert(int num,int base)
{
int i;
if(num==0)
return 0;
i = num%base;
num = num/base;
convert(num,base);
if(i==10)
printf("A");
if(i==11)
printf ("B");
if(i==12)
printf ("C");
if(i==13)
printf("D");
if(i==14)
printf("E");
if(i==15)
printf("F");
if(i>=0 && i<=9)
printf("%d",i);
}
Length of a string (Method 3)
#include<conio.h>
#include<stdio.h>
int len(char *ptr);
main()
{
char *str="gfdgfdgfg";
int count;
clrscr();
printf("Enter the string: ");
gets(str);
count = len(str);
printf("The length of the string is: %d",count);
printf(“\nPress any key to continue: ");
getch();
 }
int len(char *ptr)
{
int i,count=0;
for(i=0;ptr[i]!='\0';i++)
count++;
return count;
}
Number to Word Conversion
#include<stdio.h>
#include<conio.h>
{
char a[10];
int i=0,len,fiag=1;
clrscr();
printf("Enter any number\n");
gets(a);
for(i=:0;a[i]!=’\0';i++)
{ if(a[i]>='0'&&a[i]<='9');
else
flag = 0;
}
. if(flag==0)
{ printf("\n not a valid number");
getch();
exit(0);
}
i=0;
len = strlen(a);
if(len==7)
{ number(a[i],a[i+1]);
i++;
if(a[i]>’0’&&a[i-1]>’1’)
write_digit(a[i++]);
else
i++;
print(“lakh”);
len-=2;
}
if(len==6)
{ write_digit(a[i++]);
printf("lakh ");
len--;
}
if(len==5)
{ number(a[i],a[i+1]);
i++;
if(a[i]>'0' && a[i-1]>’1’)
write_digit(a[i++]);
else i++;
printf("thousand");
len-=2;
}
if(len==4)
{ write_digit(a[i++]);
printf("thousand");
len--;
}
if(len==3)
{ if(a[i]==’0’)
i++;
else
{ write_digit(a[i++]);
printf("hundred");
}
len—;
}
if(len==2)
{
if(a[i]=='0')
{
write_digit(a[i]);
}
else
{
number(a[i],a[i+1]);
i++;

if(a[i]>'0' && a[i-1]>'1')

write_digit(a[i++]);
else i++;
}
len-=2;
}
if(len==1)
write_digit(a[i]);
printf("\nPress any key to continue");
getch();
}
write_digit(char x) {
switch(x)
{ case'1': printf ("one ");
break;
case '2': printf(“two");
break;
case '3': printf("three");
break;
case '4': printf("four");
break;
case '5': printf("five");
break;
case '6': printf("six");
break;
case '7': printf(“seven");
break;
case '8': printf ("eight");
break;
case '9': printf("nine ");
break;
}
return;
}
number(char x, char y)
{ char a[4];
int i;
a[0] = x;
a[1] = y;
a[2] = '\0';
i = atoi(a);
if(i>=20&&i<30) printf(“twenty”);
if(i>=30&&i<40) printf(“thirty”);
if(i>=40&&i<50) printf(“forty”);
if(i>=50&&i<60) printf(“fifty”);
if(i>=60&&i<70) printf(“sixty”);
if(i>=70&&i<80) printf(“seventy”);
if(i>=80&&i<90) printf(“eighty”);
if(i>=90) printf(“ninty”);
if(i==10) printf(“ten”);
if(i==11) printf(“eleven”);
if(i==12) printf(“twelve”);
if(i==13) printf(“thirteen”);
if(i==14) printf(“fourteen”);
if(i==15) printf(“fifteen”);
 if(i==16) printf(“sixteen”);
if(i==17) printf(“sventeen”);
if(i==18) printf(“eighteen”);
if(i==19) printf(“nineteen”);
return;
}

STRUCTURES
When we want to define the records then we have to use the structures. The structure is nothing but the
user defined data type. It is a collection of different types of data values. The structures are defined by the
keyword struct. A sample declaration of structure is given below.
struct emp {
int eno;
char enm[20];
float sal;
};
So, emp is a structure consist of eno, enm and sal having different data types. The structure name is used
along with the variable name when referring to any member of the structure.
For example :
[Link] refers to the variable employee number
[Link] refers to the variable employee name
[Link] refers to the variable employee salary.
Following program will tell you that how to input the values and print the values from a structure.
main()
{ struct emp
{
int eno;
char enm[20];
float sal;
};
struct emp e1
printf("Enter the employee number\n");
scanf("%d",&[Link]);
printf("Enter the employee name\n");
gets([Link]);
printf("Enter the employee salary\n");
scanf("%f",&[Link]);
printf(“The values stored are\n");
printf("%d\t%s\t%f",e1 .[Link] .enm, e1 .sal);
getch();
}
You can define the structure before the function main(). Here e1 is the variable of type struct emp and
we are referring all the different variables with the help of e1.
This is how we can store a record with e: variable but the problem is when we want to store the records of
10 employees then it is not possible to store it in one variable for that we have to define 10 different structure
type variable again it is logically incorrect. So, how can we solve this type of problem?
 This can be solved by defining the array of structures if we know the number of employees and if we
don't know the number of employees then we have to use the pointer to a structure.
Here we are discussing only array of structures. The following program will store the information of 10
employees.
#include <stdio.h>
#include <conio.h>
struct emp
{
int eno;
char enm[20];
float sal;
};
main()
{
struct emp e[10]; int i=0;
printf ("Enter the information of 10 employees\n");
for(i=0;i<10;i++)
{
scanf("%d",&e[i].eno);
gets(e[i].enm);
scanf("%f",&e[i].sal);
}
printf("Display the information of 10 employees\n");
for(i=0;i<10;i++)
printf("%d\t%s\t%f\n",e[i].eno,e[i] .enm, e[i].sal);
getch();
}
The structures are importantly used for solving data structure problems. See some structure declarations
and see the output after compilation.
#include<stdio.h>
#include<conio.h>
void main(void)
{
struct student {
char name[20];
struct date {
int d;
int m;
int y;
} dob;
}
s1 = {"Gajanan",21,9,74};
clrscr();
printf("%s\n%d/0%d/19%d", s1 .name, [Link].d, [Link], [Link].y);
getch(); .
}
#include<stdio.h>
 #include<conio.h>
void main(void)
{
struct st1
{
char name[10]; char*ptr1;
};
struct st2
{
char *ptr2; struct st1 a;
};
struct st2 b = {"amit", "atul", "anup"}; clrscr();
printf("%s\n%s\n",b.ptr2,b.a.ptr1);
printf("%s\n%s\n",b.ptr2++,b.a.ptr1++);
printf("%s\n%s\n",b.ptr2++,b.a.ptr1++);
getch();
}
TEST :
1) Write a program to store the records of 50 students and count the number of girls and boys using
structure.

Data Representation & Arithmetic

1. Decimal Representation in Computers.
The binary number system is most natural for computer because of the two stable states of its
components. But this is not a natural system for us as we work with decimal number system.
To represent decimal digits into binary form we require 10 combinations so we need to have a 4 digit
code because 4 bit can represent 24 = 16 combinations one of the popularly known representation is BCD.
e.g. Binary Coded Decimals (BCD)
Decimal Binary coded Decimal
0 000
1 0001
2 0010
9 1001
10 1010
15 0001 0101
20 0010 0000

2. Alphanumeric Representation
A set containing alphabets (in both cases), the decimal digits and special characters consist of at least 70-
80 elements. One such code generated for this set popularly used is ASCII (American National Standard code
for Information Interchange). This code uses 7 digits to represent 128 characters.
Ex. Partial listing of 7 bit ASCII code.
character 7 bit ASCII Hexa

A 100 0001 41
... … … …
… … … …
… … … …
Z 101 1010 5A
0 001 0000 31
... … … …
… … … …
… … … …
9 011 1001 39
= 011 1101 3D
> 011 1110 3E
? 011 1111 3F

3. Computational Data Representation

The Computational Data representation in digital computer should have :

• Provisions for sign representation

• Provisions for decimal position.
One bit can be used to represent sign and by default it should be the left most bit.
An 8 bit number
8 7 6 5 4 3 2 1

1 bit 7 bit
sign magnitude

The decimal position can be represented by a position between the flip-flops (Storage cells in computer)
To determine this decimal position, two methods are :
(i) Fixed point representation where the decimal position is assumed either at the beginning or at the
end of a number.
(ii) Floating point representation where a second register is used to determine the position of the
decimal in a number.

4. Complement of a Number :

There are two types of complements for a number of base r. These are called r's complement
and (r - 1)'s complement

-Ex. For decimal numbers (base 10) complements will be

(i) 10s complement
(ii) 9 s complement
Sol. For binary numbers (base 2) complements will be
(i) 2's complement
(ii) 1's complement.

(A) 9's Complement :

The 9'th complement is obtained by subtracting each digit of a number from 9 (the highest
digit value).
Ex. 1. 9's complement of 329
= 9 9 9
- 3 2 9
= 6 7 0

(B) 1's Complement :

The1’s complement is obtained by subtracting each bit of a binary number from 1or by
replacing 1->0 and 0->1 or by complementing each bit .
Ex. 2. 1's complement of 10010
= 1 1 1 1 1
- 1 0 0 1 0
= 0 1 1 0 1
Ex. 3. 1's complement of 101011
= 010100 {By complementing each bit}

(C) 10's Complement :

The 10's complement is obtained by adding 1 to the 9's complement

Ex. 4. 10's Complement of 329
= 670 + 1
= 671

(D) 2's Complement :

The 2’s complement is obtained by adding 1 is the 1's complement.

Ex. 5. 2's complement of 10010
= 01101
+1 (1 + 1 in binary = 10)
= 01110

5. Fixed Point Representation:

When an integer binary number is positive, the sign is represented by 0 and the magnitude by
a positive binary number. When the number is negative the sign is represented by 1 but rest of the
number may be represented in one of the three possible ways :
1. Signed - magnitude representation
2. Signed - 1's complement representation
3. Signed - 2's complement representation
(Assumption size of register = 7 bit, 8th bit is used for error checking and correction or other
purposes).
Ex. Representation of +8 and - 8 in these three ways.
Signed magnitude representation :
+8 -8
0 001000 1 00 1000

Signed 1's complement :

+ 8 - 8
0 001000 1 110111
(Complement all the bits including sign bit of the positive number to obtain its complement
negative number)

Signed 2's complement :

+8 -8
0 001000 1 111000
(2's complement of the positive number including sign bit)

6. Arithmetic Addition :
 The addition of two numbers follows the rules of ordinary arithmetics in signed magnitude
representation and require comparison and subtraction. The implementation of such a scheme in digital
hardware will require a long sequence of control decisions and circuits.
By contrast, the rule for adding numbers in the signed 1's or 2's complement system does not require
comparison or subtraction (only addition and complementation are required).
Ex. Add + 30 and + 15 in binary using 7 bit register in
Signed 1's complement
Signed 2's complement
Sol. Signed 1's complement :
Signed 1's complement have a rule. Add the two numbers including the sign bit. If carry of the most
significant bit or sign bit is one, then increment the result by 1 and discard the carry over. (The negative
numbers should be stored in the signed 1's complement form in the registers.). Here
+30 0 011 110
+15 0 001 111

-30 1 100 001

-15 1 110 000

Now,
+30 0 011 110
+15 0 001 111
+45 0 101 101

+30 0 011 110

-15 1 110 000
+15 1 0 001 110

carry out is 1 so add 1 to the sum and discard the carry over
.-. Sum = 0 001 111 which is + 15.

-30 1 100 001

+15 0 001 111
-15 1 110 000

-30 1 100 001

-15 1 110 000
-45 1 10 010 001

carry out is 1, so add 1 to sum and discard the carry

1 010 001
1
1 010 010

+45 is 0 101 101

1’s complement of -45 is 1 010 010

Signed 2's Complement :

This procedure requires only one control decision and only one circuit adding the two numbers.
But negative numbers should be stored in signed 2's complement form in the registers.
Signed 2's complement have a rule. Add the two numbers including the sign bit.
If carry of the most significant bit or sign bit is one then discard the carry over
In signed 2's complement notation
+30 0 011 110
+15 0 001 111

-30 1 100 001

-15 1 110 001

+30 0 011 110

+15 0 001 111
+45 0 101 101

+30 0 011 110

-15 1 110 000
+15 1 0 001 111
discard the carry out of the sign bit

-30 1 100 010

+15 0 001 111
-15 1 110 001

-30 1 100 010

-15 1 110 001
-45 1 10 010 011

discard the carry out of the sign bit.

+ 45 is 0 101 101
- 45 in 2's Complement 1 010 011

7. Representation of Zero :

Signed magnitude
+0 -0
0 000 000 1 000 000
Signed 1's complement
+0 -0
0 000 000 1 111 111
Signed 2's complement
+0 -0
0 000 000 0 000 000

1 111 111
+ 1
1 0 000 000
= 0 000 000
discard the carry

So in signed 2's complement notation there is just one zero and there is no positive or negative zero.
Because of this reason signed 2's complement is preferred for binary arithmetic.

8. Arithmetic Substraction :
 The subtraction can be easily done using the 2's complement by taking the 2's complement of the
subtractend (inclusive of sign bit) and then adding the two numbers.
Ex. Solve (20) - (12) in binary using 7 bit register.
Sol. Representation for
for 20 : 0 010 100
for 12 : 0 001 100
2's complement of subtractend is
1 110 100
Adding the two numbers
0 010 100
1 110 100
1 0 001 000
discard the carry out

=> result is 0 001 000 i.e. + 8.

9. Overflow :

An overflow is said to have occurred when the sum of two n digit numbers occupies n + 1 digits. An
overflow is a problem in digital computers because the width of registers is finite. A result that contains n + 1
bits cannot be accommodated in a register with a standard length of n bits.
An overflow condition can be detected by observing the carry into the sign bit position and the carry out
of the sign bit position. If these two carries are not equal, an over flow condition is produced. This is indicates
in the examples. If the two carries are applied to an exclusive OR gate, an overflow will be detected when the
output of the gate is equal to 1.
Ex. Add the following numbers in 8 bit register in signed 2's complement notation.
i) Carries: 0 1

+65 0 1000001
+70 0 1000110
+135 1 0000111

This is a negative number - 131 which is obviously a wrong result. This has occurred because of overflow.
ii) Carries: 1 1

-25 1 100 111

-30 1 100 010
-55 1 1 001 001
Two carries are equal. No overflow

10. Decimal Fixed Point Representation :

By representing numbers in decimal (or BCD) we are wasting a considerable amount of storage space
since the number of bits needed to store a decimal number in a binary code is greater than the number of bits
needed for its equivalent binary representation.
Ex. 24 in BCD will be represented as 0010 0100
Sol. It needs 8 bit register with 8 flip-flops 24 in binary will be represented as 11 000. It needs 5 flip-flops.
However there are some advantages in the use of decimal representation because computer input and
output data are generated by people who use the decimal system. It can be used at places where the amount
of computer arithmetic is less than the amount of input/output of data. Examples : Calculators, business data
processing.
The arithmetic in decimal can also be performed in signed 9's complement and 10's complement
representation.

11. Floating Point Representation :

The floating point representation of a number consists of two parts :
(1) The first part represents a signed, fixed point number called the "mantissa (m)";
(2) The second pant designates the position of the decimal (or binary) point and is called the "exponent
(e)"
Floating-point is always interpreted to represent a number in the following form :
m x re .
The mantissa m and the exponent e are physically represented in the register (including their signs).
The radix r and the radix-point position of the mantissa are always assumed.
Ex. An eight bit exponent and 16 bit mantissa will be represented in floating point representation as
24……………………10 9 8……………………..3 2 1

15 bit mantissa 7 bit exponent

Sign bit sign bit

24 bit floating point representation

Ex. A decimal +14.32 in a typical floating point notation:
2 -2
14.32=0.14332*10 or 1433+ 10
Sign Sign
0 1432 0 02
Mantissa fraction Exponent

0 1432 0 02
Mantissa integer Exponent

Normalization

A floating-point numbers said to be normalized if the most significant digit of the mantissa is non zero.
for example, the decimal number 320 is normalized but 0032 is not.
Regardless of the assumed position of radix point in the mantissa, the number is normalized only if its
leftmost digit is non zero.
for example, the 8-bit binary number 00100100 is not normalized because of the two leading 0's

The number can be normalized by shifting two positions to the left to obtain 10010000. The two shifts multiply
the number by 21 = 4.
To keep the same value for the floating point number, the exponent must be subtracted by 2.
Ex: A floating point binary number -1001.101 in a 16 bit register can be represented in normalised form
(assuming 10 bits for mantissa and 6 bits for exponent).
Sol:

1 100100000 0 00101

Mantissa(fraction) Exponent

A zero cannot be normalized as all the digits in mantissa and exponent have to be zero.
Arithmetic operations with floating-point numbers are more complex and take longer time.
Objective Questions
1. The binary code for the word BOY in ASCII-7 (Haxa) is
(a) 42 4F 59
(b) 4B 50 59
(c) 24 F4 95
(d) 4A 4F 59
2. In an eight bit register - 14 can be represented as (signed magnitude representation).
(a) 0 0001110
(b) 1 1110000
(c) 1 0001110
(d) 1 1101001
3. In an 7 bit signed 2's complement representation + 25 will be represented
as
(a) 0 011001
(b) 1 011001
(c) 0 110010
(d) 1 110010
4. Find 1's and 2's complement of 000000
(a) 111111, 100000
(b) 000000, 000000
(c) 111111, 000000
(d) 011111, 111111
5. 2's complement of 11001100 is
(a) 01010100
(b) 00110011
(c) 01000100
(d) 00110100
6. 9's complement of 629 is
(a) 370
(b) 371
(c) 361
(d) 325
7. Addition of + 50 and - 55 in 8 bit register using 2's complement will be
(a) 0 0000101
(b) 1 1111011
(c) 1 1111010
(d) None of the above
8. Addition of + 25 and - 12 in 6 bit register using 1's complement will be
(a) 0 01101
(b) 1 100010
(c) 1 01101
(d) None of the above
9. Result of 20 - 11 in binary using 7 bit register will be
(a) 0 001001
 (b) 1 001001
(c) 1 110110
(d) 0 001101
10. Complement representation preferred to signed magnitude representation because
(a) Representation of zero is easy
(b) Less number of control decisions and circuits
(c) Both (a) & (b)
(d)None of the above
11. If carry into the sign bit position and carry out of the sign bit position are not equal then
(a) Result is negative
(b) Overflow condition
(c) Both a < b
(d) None of the above
-15
12. Minimum number of bits required to represent exponent of 101 x 2 will be
(a) 5 bit (b) 4 bit
(c) 8 bit (d) 7 bit
30
13. Minimum number of bits required to represent exponent of 11 x 2 will be
(a) 5 bit (b) 6 bit
(c) 7 bit (d) 8 bit

SOLUTIONS
Ans. 1. (a) In ASCII-7
B = 100 0010 = (42)16
O = 100 1111 = (4F)16
Y = 101 1001 = (59)16
Ans. 2. (b) (14)10 = (1110)2 in eight bit, first is for sign bit and 7 bit for magnitude
(- 14)10 = 1 0001110
Ans. 3. (a) (25)10 = (11001)2
+ sign => sign bit = 0
(+ 25)10 = 0 011001
Ans. 4. (c)
1's complement of 000000 = 111111
2's complement = 111 111
+ 1
1 000 000
discard the carry out = 000 000
Ans. 5. (d) 2's complement of 11001100
= 0011 0011
+ 1
0 0110100
Ans. 6. (a) 9's complement of 629 is
9 9 9
- 6 2 9
 3 7 0
Ans. 7. (b) (+ 50) + (- 55) = - 05
(5)10 = (101)2
in 8 bit = 0 0000101
- 5 = 1 1111010
+ 1
= 1 1111011
Ans. 8. (a) (+ 25) + (- 12) = + 13
(13)10 = (1101)2
in 6 bit register = 0 01101
Ans. 9. (a) (20) - (11) = + 9
(9)10 = (1001)2
in 7 bit register = 0 001001
Ans. 12. (a) (15)10 = (1111)2
So 4 bit required by adding one bit for sign. 5 bit required to represent (- 15).
Ans. 13. (b) (30)10 = (11110)2
5 bit + 1 bit sign = 6 bit.