Introduction & Programming with

Computational Problem Solving

ESP8266

P. Rajakumar
Assistant Professor
Department of CSE
Parul Institute of Technology
Content

1. Program Development Cycle……………………………

2. Pseudocode…………………………………………………….
3. Flowchart………………………………………………………..
4. Representation of data as bits…………………………
5. Binary Systems………………………………………………..
6. Storing Integers……………………………………………….
7. Storing fractions………………………………………………

INDEX
Program Development Cycle
The program development life cycle is a set of steps or phases which
are used to develop a program in any programming language.

Phases of Program Development.

➢ Problem Definition.
➢ Problem Analysis.
➢ Algorithm Development.
➢ Coding and Documentation.
➢ Testing and Debugging.
➢ Maintenance.
Six phases of program development cycle
Problem Definition.
In this phase, we need to understand what is the problem statement,
what is our requirement and what is the output of the problem.

Problem Analysis.
Here, we determine the requirements like variables, functions, etc. to
solve the problem. It means that we gather the required resources to
solve the problem, which are defined in the problem definition phase.

Algorithm Development.
Here, we develop a step-by-step procedure that is used to solve the
problem by using the specification given in the previous phase. It is very
important phase for the program development. We write the solution in
step-by-step statements.
Coding and Documentation.
Here, we use a programming language to write or implement the actual
programs for the steps defined in the previous phase.
We write the program to solve the given problem by using any
programming languages like C, C++, Java, etc.

Testing and Debugging.

In this phase, we check whether the written code in the previous step is
solving the specified problem or not. This means, whether it is solving
the problem for various input data values or not. We also test if it is
providing the desired output or not.
Maintenance.
Even after the software is completed, it needs to be maintained and
evaluated regularly. In software maintenance, the programming team
fixes program errors and updates the software.

Pseudocode
▪ A Pseudocode is defined as a step-by-step process of an algorithm.
▪ Pseudocode does not use any programming language for its
representation.
▪ It uses the simple English text for human understanding.
▪ Pseudocode is the intermediate state between an idea and
implementation code.
Steps to write Pseudocode.
• Understand the problem.
✓ Identify inputs and outputs.
• Define the purpose.
✓ State the goal of program
• List the inputs and outputs.
✓ Specify the input and output clearly.
• Break the problem into steps.
✓ Divide the problem into step by step and arrange in order.
• Use simple, structured statements.
✓ Use keywords like
• START / END
• INPUT /OUTPUT
• IF…THEN … ELSE …
• WHILE, FOR LOOPS
• CALCULATE, DISPLAY, etc
• Write in plain language.
✓ Avoid using syntax of any programming language.
• Check logic and flow.
✓ Make sure every input gives the desired output.
• Refine and optimize.
✓ Remove unnecessary steps to clarity and efficiency.

Write a pseudocode for addition of two number

START
INPUT number1
INPUT number2
CALCULATE sum =Number1 + Number2
DISPLAY sum
END
Write a pseudocode to calculate the area of a circle
START
INPUT radius
CALCULATE area = 3.14 * radius * radius
DISPLAY area
END

Write a pseudocode for finding the sum of digits of a given number.

START
INPUT number
SET sum = 0
WHILE number > 0 DO
Digit = number MOD 10
sum = sum + digit
Number = number DIV 10
END WHILE
DISPLAY sum
END
Write a pseudocode for reverse of a given number
START
INPUT number
SET reverse = 0
WHILE number > 0 DO
digit = number MOD 10
reverse = reverse * 10 + digit
number = number DIV 10
END WHILE
DISPLAY reverse
END
Write a pseudocode for factorial of a given number
START
INPUT number
SET factorial = 1
FOR i=1 TO number DO
Factorial=Factorial * i
END FOR
DISPLAY Factorial
END

Write a pseudocode for Fibonacci series of a given number

Write a pseudocode for Fibonacci series of a given number

START
INPUT n
SET first=0
SET second=1
PRINT first , second
FOR i=2 TO n DO
CALCULATE next=first + second
PRINT next
SET first=second
SET second=next
END FOR
END
Flowchart
Flowchart is a graphical representation of the logical steps of a
program. Flowcharts use simple geometric shapes to depict processes
and arrows to show relationships and data flow.
Here is the some of symbols used in flowchart.
Draw the flowchart to calculate the average of two numbers.
Draw the flowchart for factorial of number.
Draw the flowchart for sum of digit of number.
Draw the flowchart for reverse of number.
Draw the flowchart for Fibonacci series of number.
Representing Information as bits.
Representing information as bits involves converting data into
sequences of binary digits (0s and 1s), bit is the smallest unit of data. It
can have two possible values:
0 – Off/Low voltage.
1 – On/High Voltage.
Computers are digital systems. They only understand two states (0 and
1). By combining bits, computers represent numbers, characters,
images, audio, and video.

Information are represented as Bits

Number
Binary number system is used.
Decimal 5--- Binary 101
Decimal 8--- Binary 1000
Character
Characters are encoded as numbers using standards like ASCII code or
Unicode.
Example
'A' → ASCII code 65 → Binary 01000001
'a' → ASCII code 97 → Binary 01100001

Images
An image is broken into pixels.
Each pixel is represented by bits for color values (RGB).
Example
A pixel with Red=255, Green=0, Blue=0 → Binary: 11111111
00000000 00000000
Audio
Sound waves are sampled at regular intervals.
Each sample is stored as a binary number.
Example: A sample value of 3000 → Binary 101110111000

Video
Video = sequence of images (frames) + audio, all stored as bits.

Example
Word "Hai":
'H' = ASCII 72 = Binary 01001000
‘a' = ASCII 97 = Binary 01100001
'i' = ASCII 105 = Binary 01101001

Hai= 01001000 01100001 01101001

Binary System
➢ A binary system is a numerical system with base-2, it has two digits 0
and 1, to represent values.
➢ It is the foundation of all digital computers, processing and storing
data, text, and images as sequences of digits.
➢ Each binary digit is called a bit, and combinations of bits form more
complex data.

Applications of Binay system

• Digital Computers
• Data Storage
• Programming
Storing Integers
➢ Integers are stored in computer memory using a fixed number of bits,
by converting integer value in binary format.
➢ computers can only understand binary (0s and 1s), decimal integers
must be converted into bits for storage.
Process of storing integers
Binary conversion:
The decimal integer is first converted to its binary equivalent. For
example, the decimal number 13 is represented as the binary
number 1101.
Fixed-size storage:
A variable declared as an integer is assigned a fixed amount of memory,
such as 8, 16, 32, or 64 bits. The binary number is then padded with
leading zeros to fill this fixed storage space. For example, if a 32-bit
integer 13 would be stored as 00000000 00000000 00000000 00001101.
Encoding negative numbers:
For signed integers, which can be either positive or negative, a special
method is used to represent the sign. The most common method in
modern computing is two's complement.
• The sign bit:
In two's complement, the leftmost bit (the most significant bit) acts as
the sign bit. 0 indicates a positive number, while a 1 indicates a
negative number.
• Range:
This technique results in an uneven range of positive and negative
numbers. For example, a 32-bit signed integer can hold values from
-2,147,483,648 to 2,147,483,647.
• Two's complement calculation:
To find the two's complement representation of a negative number
Storing Fractions.
Fractions numbers with a decimal point, like 3.14 or –0.125 are stored in
computers differently than integers. There are different ways.

1. Fixed-Point Representation
2. Floating-Point Representation
3. Rational Representation

Fixed-Point Representation
• The binary point is fixed at a certain position.
• If 8 bits are used, we might allocate 4 bits for the integer part and 4
bits for the fractional part.
Example:
0101.1100 (binary) → 5.75 (decimal)
Floating-Point Representation
There are a series of floating-point representations for various ranges of
the value. For simplicity, we will look primarily at the IEEE 754 32-bit
floating-point standard.

Find normalized scientific notation of binary-

This means that the number should have a single, non-zero leading digit
to the left of the decimal point.
Example-1
8.125110 the binary values is 1000.0012
The normalized scientific notation can be written as 1.00000 x 23
Example-2
0.12510 the binary values is 0.0012
That is 0.125 * 2 = 0.25 -> 0
0.25 * 2 = 0.5 -> 0
0.5 *2 = 1 -> 1 The binary value is 0.0012
The normalized scientific notation can be written as 1.0 x 2-3
Biased exponent
-The bias for the IEEE 754 32-bit floating- point standard is 12710
Example
Find binary representation of Floating point number -7.75
1. Determine the sign bit: 1(since negative)
2. Convert to binary -7.75 = -0111.112
3. Normalized scientific notation = 1.1111 x 22
4. Compute biased exponent= 210 + 12710 = 12910
5. Convert biased exponent into binary 129= 100000012
Finally Write Components in binary:
Sign Exponent Mantissa
1 10000001 11110000000000000000000

Example
Find binary representation of Floating point number -0.125
1. Determine the sign bit of -0.125 is: 1(since negative)
2. Convert to binary -0.125= -0.0012
3. Normalized scientific notation= 1.0 x 2-3
4. Compute biased exponent = -310 + 12710=12410
5. Convert biased exponent into binary 12410=011111002
6. Write the components in binary
Sign Exponent Mantissa
1 01111100 0000000000000000000000
Rational Representation
Fraction is stored as two integers: numerator and denominator.

Example
3/5 is represented as Numerator=3 and denominator=5

Computational Problems

➢ A computational problem is a problem that can be solved step-by-

step with a computer.
➢ These problems usually have a well-defined input, constraints, and
conditions that the output must satisfied.
Types or (Examples) of Computational Problems.
1. Decision problem
2. Search problem
3. Counting problem
4. Optimization problem

Decision problem
• A decision problem is one where the answer is yes or no.
• For instance, "given a number n, is n prime?“.
Search problem
• A search problem is one where the solution consists of one or more
values that satisfies a given condition.
• For instance, we may want to compute a path from one geographical
location to another on a map.
Counting problem
A counting problem is one where the answer is the number of solutions
to a search problem.

Optimization problem
• An optimization problem is one where the solution is the "best"
possible solution, where the "best" can be defined in a different way.
• For instance, we may want to compute the fastest route from one
location to another.

Iterative and Recursive Approaches to Solve Computational

Problems.
Iteration and recursion are two fundamental approaches to solving
computational problems that involve repeating a set of instructions.
An iterative approach uses loops to repeat steps, while a recursive
approach calls a function from within itself until a base condition is
met
Iterative approach
Iteration solves a problem by executing a block of code repeatedly using
a loop structure, like a for or while loop, until a controlling condition is
no longer true.
Example
#include <stdio.h>
void main() {
int n, i;
int fact = 1;
printf("Enter a positive integer: ");
scanf("%d", &n);
if (n > 0)
{
for (i = 1; i <= n; i++)
{
fact *= i;
} printf("Factorial of %d = %d\n", n, fact);
}
else if(n==0)
{
printf(“%d\n”,fact);
} else
{
printf(“Factorial is not possible for negative numbers”);
}
}
Recursive approach
Recursion solves a problem by breaking it down into smaller, self-
similar subproblems.
A recursive function has two parts: a base case that provides - stopping
condition and a recursive case that calls the function itself.
Example
#include <stdio.h>
int factorial(int n)
{
if (n == 0 || n == 1) // base case
return 1;
else
return n * factorial(n - 1); // recursive call
}
int main() {
int num;
printf("Enter a positive integer: ");
scanf("%d", &num);
if (num >=0)
{
printf("Factorial of %d = %d\n", num, factorial(num));
}
else
{
printf("Factorial is not defined for negative numbers.\n");
}

return 0;
}
Easy and Hard Computational Problems
Easy Computational Problems
➢ Problems that can be solved in a reasonable amount of time
(polynomial time).
➢ These problem belong to the class P (Polynomial time).
➢ These algorithms that run efficiently (time grows slowly as input
grows).
➢ Solvable with step-by-step deterministic methods.
Examples
• Sorting numbers (like Bubble Sort, Quick Sort).
• Searching in a list (Binary Search).
• Finding the greatest common divisor (Euclidean algorithm).
• Checking if a number is prime (modern algorithms do this fast).
Hard Computational Problems
➢ Hard Problems for which no efficient algorithm is known. They
might take exponential time to solve.
➢ Many fall into NP (Nondeterministic Polynomial time), NP-hard,
or NP-complete categories.
➢ Time required grows very fast with input size.

Examples
• Travelling Salesman Problem (TSP) → Find the shortest route
visiting all cities.
• Sudoku solving.
• Graph Coloring problem.
• Knapsack problem.