INTRODUCTION TO

PROGRAMMING

DIGITAL NOTES

I B.TECH – I SEMESTER
A.Y. 2023-24

Nadimpalli Satyanarayana Raju

Institute of Technology
(Autonomous)
Permanently Affiliated to JNTUK, Kakinada, Accredited by NAAC with “A” Grade Recognized by
UGC 2(f) and 12(b) under UGC act, 1956
Sontyam, Sontyam – Anandapuram Road, Visakhapatnam – 531 173
Andhra Pradesh
Introduction to Programming (R23) Unit -1

UNIT – 1
Introduction to Programming and Problem Solving
Program: Program is the set of instructions which is run by the computer to perform specific task.
The task of developing program is called programming. To obtain a computer solution to a problem,
which provides input to the program which is manipulated according to instructions and produces
output.
ALGORITHM
Algorithm is the set of rules that define how particular problem can be solved in finite number of
steps. Any good algorithm must have following characteristics
1. Input: Algorithm must have 0 or more inputs
2. Output: Algorithm must produce atleast one output.
3. Definiteness: each step of the algorithm must be clear and unambiguous.
4. Effectiveness: Every instruction must be very basic.
5. Finiteness: Algorithm must include finite number of steps
Advantages of Algorithms:
1. It is the way to solve a problem step-wise so it is easy to understand.
2. It uses definite procedure.
3. It is not dependent with any programming language.
4. Each step has its own meaning so it is easy to debug
Disadvantage of Algorithms:
1. It is time consuming
2. Difficult to show branching and looping statement
3. Large problems are difficult to implement
Problem Solving: Problem solving is the process of identifying a problem, developing possible
solution paths, and finally implementing the algorithm to develop a computer program. Problem
solving is the process of solving a problem in a computer system by following a sequence of steps
which include
i) Developing an algorithm: An algorithm is a sequence of steps for solving a problem.
Example: Algorithm for Simple Interest
Step 1: Start
Step 2: Read p,n,r
Step 3: Calculate si= p * n * r /100
Step 4: Print si
Step 5: Stop

ii) Drawing a flowchart: A flowchart is a pictorial representation of a process which describe the
sequence and flow of control and information within the process. It is the one of the most
important technique to depict an algorithm.
Advantage of Flowchart:
1. Easier to understand
2. Helps to understand logic of problem
3. Easy to draw flowchart in any software like MS-Word
4. Complex problem can be represent using less symbols
5. It is the way to documenting any problem
6. Helps in debugging process

NS Raju Institute of Technology (Autonomous) Page 2

Introduction to Programming (R23) Unit -1
Disadvantage of Flowchart:
1. For any change, Flowchart have to redrawn
2. Showing many looping and branching become complex
3. Modification of flowchart is time consuming

Figure: Flowchart Symbols

Flowchart for computing SI

iii) Writing a Pseudo code: A Pseudo code is similar to algorithms but uses generic syntax for
describing the steps that are to be performed for solving a problem.
Example:
SumOfTwoNumbers()
Begin
Set sum =0;

NS Raju Institute of Technology (Autonomous) Page 3

Introduction to Programming (R23) Unit -1
Read: a, b;
Set sum = a + b;
Print sum;
End

REQUIREMENTS FOR PROBLEM SOLVING BY COMPUTER

Algorithms are employed to solve problems. The requirements for problem solving by computer
include:
1. Clear Understanding of the Problem: Precise articulation of the problem is essential. Define the
problem in a way that a computer can understand and process it. This includes identifying inputs,
desired outputs, constraints, and the problem's scope.
2. Input Data: Determine what data is required to solve the problem. Collect, acquire, or generate
the necessary input data. Ensure the data is accurate and reliable.
3. Algorithms and Methods: Formulate a step-by-step procedure or algorithm to solve the problem.
Algorithms provide a clear set of instructions for the computer to follow, breaking down the
solution into smaller, manageable steps. Choose appropriate algorithms, methods, and
techniques that are relevant to the problem.
4. Data Structures: Use suitable data structures to represent and manipulate data efficiently.
Common data structures include arrays, lists, trees, graphs, queues, and stacks.
5. Logical Precision: While developing computer algorithms the solution must be specified with
logical precision in much detail.

PHASES OF PROBLEM SOLVING

The following are the some basic steps to solve the problems by computer.
Step 1: Identify and Define Problem
Explain you problem clearly.
Step 2: Generate Possible Solutions
 List out all the solution that you find.
 Generate the maximum number of solution.

Step 3: Evaluate Alternatives

After generating the maximum solutions, remove the undesired solutions.
Step 4: Decide a Solution
After filtering all the solution, you have the best solution only. Then choose one of the best solution
and make a decision to make it as a perfect solution.
Step 5: Implement a Solution:
After getting the best solution, implement that solution to solve a problem.
Step 6: Evaluate the result
After implementing a best solution, Evaluate how much you solution solve the problem. If your
solution will not solve the problem then you can again start with Step 2.

PROBLEM SOLVING STRATEGIES

A problem-solving strategy is a plan used to find a solution to a problem. Each problem-solving
strategy includes multiple steps on how to resolve a problem.
1. Divide and Conquer Approach
2. Greedy Technique
3. Dynamic Programming
4. Backtracking Algorithm
NS Raju Institute of Technology (Autonomous) Page 4
Introduction to Programming (R23) Unit -1
TOP-DOWN DESIGN
Top-down design is a problem-solving method that breaks down a bigger problem into smaller,
less complex sub-problems and solving each sub-problem individually. Then break the sub-
problem into tasks until they are directly solvable. Top-Down approach is also termed as breaking a
bigger problem into smaller problems and solving them individually in recursive manner. It is also
known as “stepwise refinement”. Top-Down Model is followed by structural programming languages
like C, Fortran, etc.
Working of Top-Down Approach
1. Start with an overview of the problem.
2. Divide the problem into smaller sub-problems.
3. Solve each sub-problem.
4. Combine the subproblems.
Advantages
 Breaking problems into parts helps identify what needs to be done.
 At each step of refinement, new sub-problem become less complex and easier to solve.
 Parts of the solution may be reusable.
 Breaking problems into parts allows more than one person to solve the problem.

Example of a Top-Down approach to draw a figure.

Digital clock representation of Top-Down diagram

ALGORITHM DESIGNING
Algorithm design is a mathematical process for solving problems. It involves creating a step-by-step
plan to solve a problem.
The following is a list of several popular design approaches:
1. Divide and Conquer Approach: It is a top-down approach. The algorithms which follow the
divide & conquer techniques involve three steps:
 Divide the original problem into a set of subproblems.

NS Raju Institute of Technology (Autonomous) Page 5

Introduction to Programming (R23) Unit -1
 Solve every sub-problem individually, recursively.
 Combine the solution of the subproblems (top level) into a solution of the whole original
problem.
2. Greedy Technique: Greedy method is used to solve the optimization problem. An optimization
problem is one in which we are given a set of input values, which are required either to be
maximized or minimized (known as objective), i.e. some constraints or conditions.
 Greedy Algorithm always makes the choice (greedy criteria) looks best at the moment, to
optimize a given objective.
 The greedy algorithm doesn't always guarantee the optimal solution however it generally
produces a solution that is very close in value to the optimal.
3. Dynamic Programming: Dynamic Programming is a bottom-up approach we solve all possible
small problems and then combine them to obtain solutions for bigger problems. Dynamic
Programming is frequently related to Optimization Problems.
4. Backtracking Algorithm: Backtracking Algorithm tries each possibility until they find the right
one. It is a depth-first search of the set of possible solution. During the search, if an alternative
doesn't work, then backtrack to the choice point, the place which presented different alternatives,
and tries the next alternative.

PROGRAM VERIFICATION
Program verification is the process of applying formal methods directly to verification of code.
Program verification is the process of using mathematical proof techniques to establish that the results
obtained by the execution of a program with arbitrary inputs are in accord with formally defined
output specifications. Usually, Top down approach is followed for program verification. We start by
proving the correctness of the basic structure of the algorithm and the process is repeated until we get
down to the program steps.
The main goal of the program verification is to understand what happens when a program is executed
when input is given.
i) Input and Output assertion: Input assertion verifies the values assigned to the variables. For e.g.,
in the expression (a/b), the value of the variable b must be always >= 1.
Output assertion must specify the results that the program is expected to produce for the given
input assertion. For e.g., x/y, q is the quotient and r is the remainder. The output assertion can be
written as (x = q *y + r ) ∧ (q > r) .
ii) Verification of program segments with branches: A program may have several condition
checking paths but for any given input only one of these paths will be executed. Should make sure
all logical paths are executed.

iii) Verification of program segments with loops: Verify the execution of the loop and the number
of iterations.
As an example, consider the following program to compute the factorial of n.
i=1, f=1;

NS Raju Institute of Technology (Autonomous) Page 6

Introduction to Programming (R23) Unit -1
while(i<=n)
{
f=f*i;
i++;
}
iv) Proof of termination: To prove that a program terminates, it is necessary to show that the
expected output is attained in a finite number of steps. This implies that every loop in the program
terminates in a finite number of steps.

IMPROVING EFFICIENCY
The efficiency of an algorithm is defined as the number of computational resources used by the
algorithm. An algorithm must be analyzed to determine its resource usage and the efficiency of an
algorithm can be measured based on the usage of different resources. For maximum efficiency of
algorithm resource usage must be minimized.
Measures of resource usage: Measures are normally expressed as a function of the size of the
input n. The two most common measures are:
 Time: The amount of time required to execute an algorithm.
 Space: The amount of memory needed by the algorithm to execute. The amount of memory
needed by the code and the amount of memory needed for the data on which the code operates.
To improve the efficiency of the algorithms the following are the suggestions:
 Redundant computations
 Referencing array elements
 Inefficiency due to late termination
 Early detection of desired output conditions
 Trading storage for efficiency gains

ALGORITHM ANALYSIS AND NOTATIONS

Analysis of algorithms is the determination of the amount of time and space resources required to
execute it.
 Big O notation: Describes the worst-case running time of a program.
f(n) = O(g(n)), read as f of n is big oh of g of n, iff (if and only if) positive constants c and n0 exist
such that f(n) <= cg(n) for all n, n >= n0.
 Omega notation: Represents the minimum running time of an algorithm, or the best-case
complexity
f(n) = omega(g(n)), read as f of n is omega of g of n, iff (if and only if) positive constants c and
n0 exist such that f(n) >= cg(n) for all n, n >= n0.
 Theta notation: Represents the upper and lower bound of the running time of an algorithm, or the
average-case complexity.
f(n) = Theta(g(n)), read as f of n is theta of g of n, iff (if and only if) positive constants c1, c2, and
n0 exist such that c1g(n) <=f(n) <= c2g(n) for all n, n >= n0.

QUESTIONS FROM UNIT – I

1. Define an algorithm and explain the characteristics of an algorithm?
2. Discuss various problem solving strategies?
3. Write short note on program verification.
4. Explain algorithm analysis and notations?
5. Explain the steps involved in top-down approach.

NS Raju Institute of Technology (Autonomous) Page 7