CSE1021-Introduction to Problem Solving and Programming

UNIT-1 Content
Introduction
 What is problem solving

Steps for Problem Solving

1.Analysis the problem
 Problem solving process using analysis method
2. Development an algorithm
 Examples
3. Codings
 Some of the coding languages
 C/C++, JAVA, PYTHON, JAVA SCRIPT, C#

4. Testing and debugging

 What is Problem solving

 Problem solving is the act of defining a problem; determining the

cause of the problem; identifying, prioritizing, and selecting
alternatives for a solution; and implementing a solution.
Steps for problem solving

1. Analysing the
problem

2.
5. Debugging
Developing
the problem
the algorithm

3. CODING 4.Testing
 1. Analysing the problem
 It is important to clearly understand a problem before we begin to find the
solution for it.
 If we are not clear as to what to be solved, we may end up developing a
program which may not solve our purposes.
 Thus, we need to read and analyse the problem statement carefully in order to
list the principal components of the problem and decide the core functionalities
that our solution should have.
 By analysing a problem , we would be able to figure out what are inputs that our
program should accept and the outputs that it should produce.
2. Developing An Algorithm

 It is essential to device a solution before writing a

program code for a given problem.
 The solution is represented in natural language and is
called an algorithm.
 We start with a tentative solution plan and keep on
refining the algorithm until the algorithm is able to
capture all the aspects of the desired solution.
 For a given problem , more than one algorithm is
possible we have to select the most suitable solution .
3. Coding

After finishing the algorithm , we need to

convert the algorithm into the format which can
be understood by the computer to generate
the desired solution. Different high level
languages can be used for writing a program.
It is equally important to record the details of the
coding procedures followed and document the
solution.
 Some of the coding languages

• JavaScript.
• Python. ...
• SQL. ...
• PHP. ...
• Ruby. ...
• C++ ...
• C Sharp. ...
• Visual Basic.
 4. Testing and Debugging
 The program should be created on various parameters. The
program should meet the requirements of the user. It must
respond within the expected time.it should generate correct
output for all possible inputs.
 In the presence of syntax erors , no output will be obtained.
 In case the output generated is incorrect, then the program
should be checked for logical errors.
 Software industry follows standardized testing methods:-
 Unit or component testing
 Integration testing
 System testing
 Acceptance testing while developing complex applications.
 UNIT-1 CONTENTS

Algorithm
Examples
Step for this examples are
Characteristics of a good algorithm
Difference between algorithm and
program
Algorithm

It is defined as sequence of instructions that describe a

method for solving problem. In other words it is a step –by
– step procedure for solving a problem.
 Problem

Algorithm

INPUT COMPUTER OUTPUT

In our day- to -day life we perform activities by following
certain sequence of steps.
For Examples:- An activity includes getting ready for
school, making breakfast, riding a bicycle, wearing a tie,
solving a puzzle and so on. To complete each activity, we
follow a sequence of steps. Suppose following are the
steps required for an activity‘riding a bicycle’.
Steps for this examples are:-

Stop on Remove the

reaching bicycle
the from the
destination. stand .

Use breaks Sit on the

whenever seat of the
needed bicycle

Start
peddling
Characteristics of a good algorithm

 Precision — the steps are precisely stated or defined.

 Uniqueness — results of each step are uniquely defined
and only depend on the input and the result of the
preceding steps.
 Finiteness — the algorithm always stops after a finite
number of steps.
 Input — the algorithm receives some input.
 Output — the algorithm produces some output.
Difference between algorithm and
program
S.N0 ALGORITHM PROGRAM

1. Algorithm is finite. Program need not to be

finite.

2. Algorithm is written using natural Programs are written using a

language or algorithmic specific programming
language. language.
CSE1021-Introduction to Problem Solving and Programming
 UNIT-1 CONTENTS (module 2)
 Algorithm
 Examples
 Step for this examples are
 Characteristics of a good algorithm
 Difference between algorithm and program
 Practice question
1. Write an algorithm to add two numbers.
2. Write an algorithm to find the square of a number.
3. Write an algorithm to find GCD of two numbers 45 and 54.
Building block of an algorithm
1. Sequence
2. Selection
Algorithm

It is defined as sequence of instructions that describe a

method for solving problem. In other words it is a step –by
– step procedure for solving a problem.
 Problem

Algorithm

INPUT COMPUTER OUTPUT

In our day- to -day life we perform activities by following
certain sequence of steps.
For Examples:- An activity includes getting ready for
school, making breakfast, riding a bicycle, wearing a tie,
solving a puzzle and so on. To complete each activity, we
follow a sequence of steps. Suppose following are the
steps required for an activity‘riding a bicycle’.
Steps for this examples are:-

Stop on Remove the

reaching bicycle
the from the
destination. stand .

Use breaks Sit on the

whenever seat of the
needed bicycle

Start
peddling
Characteristics of a good algorithm

 Precision — the steps are precisely stated or defined.

 Uniqueness — results of each step are uniquely defined
and only depend on the input and the result of the
preceding steps.
 Finiteness — the algorithm always stops after a finite
number of steps.
 Input — the algorithm receives some input.
 Output — the algorithm produces some output.
Difference between algorithm and
program
S.N0 ALGORITHM PROGRAM

1. Algorithm is finite. Program need not to be

finite.

2. Algorithm is written using natural Programs are written using a

language or algorithmic specific programming
language. language.
 Write an algorithm to add two numbers

STEP 1:- START

STEP2:- INPUT TWO NUMBERS NUM1 AND NUM 2
STEP 3:- ADD NUM1 & NUM2 AND STORE IN RESULTS
STEP 4:- PRINT RESULT
STEP 5:- STOP
Q1. Write an algorithm to find area of a square?

Q2. Write an algorithm to find perimeter of rectangle whose length is

4cm and breadth is 6cm?

Q3. Write an algorithm to find GCD (Greatest Common Division) of

two numbers 45 and 54?

Q4. Find the area of a square if the length of the diagonal is 12cm?

Q5. The length of each side of a square is 5cm and the cost of painting
it is Rs. 5 per sq. cm. Find the total cost to paint the square?
Q1. Write an algorithm to find area of a square?

SOLUTION 1:
Step 1- Start
Step 2- Input side
Step 3- Area of square
Step 4- Print area
Step 5- Stop
 Q3. Write an algorithm to find GCD (Greatest
Common Division) of two numbers 45 and 54?

Method 1:- Long Division

GCF of 45 and 54 is the divisor that we get when the
remainder becomes 0 after doing long division repeatedly.
• Step 1: Divide 54 (larger number) by 45 (smaller number).
• Step 2: Since the remainder ≠ 0, we will divide the divisor
of step 1 (45) by the remainder (9).
• Step 3: Repeat this process until the remainder = 0.
The corresponding divisor (9) is the GCF of 45 and 54.
2 Method of GCD:-
Only for positive
integers

 Step 1: Applying Euclid’s division lemma to a and b we get two

whole numbers q and r such that, a = bq+r ; 0 r < b.
 Step 2: If r = 0, then b is the HCF of a and b. If r ≠0, then
apply Euclid’s division lemma to b and r.
 Step 3: Continue the above process until the remainder is zero.
 Step 4: When the remainder is zero, the divisor at this stage is
the HCF of given numbers.
BUILDING BLOCKS OF ALGORITHM

 It has been proven that any algorithm can be constructed from just three
basic building blocks. These three building blocks are:-
 Sequence
 Selection
 Iteration.

BUILDING BLOCK COMMON NAME

SEQUENCE ACTION
SELECTION DECISION
ITERATION REPETITION OR LOOP
SEQUENCE

 A sequence is one the basic logic structures in computer programming. In a sequence

structure, an action, or event , leads to the next ordered action in a predetermined order.
The sequence can contain any number of actions, but no actions can be skipped in the
sequence. Once running, the program must perform each task without skipping.

 sequence


INSTRUCTION

INSTRUCTION


INSTRUCTION
SELECTION
 A selection ( also called a decision)is also one of the basic logic structures
in computer programming. In a selection structure, a question is asked, and
depending on the answer, the program takes one of two courses of action,
after which the program moves on to the next event.

selection

choice

instruction instruction
 ITERATION
An iteration is a single pass through a group/set of instructions. Most programs
often contain loops of instructions that are executed over and over again. The
computer repeatedly executes the loop, iterating through the loop.
LOOPING

CHOICE

INSTRUCTION
REPRESENTATION OF ALGORITHM

PSEUDO
FLOWCHART
CODE

ALGORITHM
FLOWCHART

 A flowchart is a visual representation of an algorithm. A flowchart is a

diagram made up of boxes, diamonds and other shapes, connected by
arrows. Each shape represents a step of the solution process and the arrow
represents the order or link among the steps.
 There are standardized symbols to draw flowcharts.
Some are given in table:-
Shapes or symbols to draw flow charts

SYMBOL FUNCTION DESCRIPTION

START/END Also called “Terminator” symbol. It indicates where the
flow starts and ends.

PROCESS Also called “Action Symbol,” it represents a process,

action, or a single step
DECISION A decision or branching point, usually a yes/no or true/
false question is asked, and based on the answer, the
path gets split into two branches.
INPUT/ OUTPUT Also called data symbol, this parallelogram shape is used
to input or output data.
END Connector to show order of flow between shapes.
Q1. draw the flowchart to add 10 and
20. print the sum
 A=10
START
 B=20
 C=A+B
A=10
 PRINT (C)
B=20

C=A+B

PRINT(C)

END
Q2. DRAW THE FLOWCHART TO FIND
SIMPLE INTEREST
START  Input p ,r , t
 Si= p*r*t/100

Input p ,r , t  Print (Si)

Si= p*r*t/100

Print(Si)

STOP
Q. DRAW THE FLOWCHART by using raptor
tool TO FIND AREA OF TRIANGLE WITH
ALGORITHM
FLOW CHART
IF…. Else

How to use decision box

Decision
q. Draw the flow chart to print the smallest
number of two numbers
 Input A, B
 If A<B
 Print(A)
 Else
 Print(B)
 START

Input A,B

If
A<B YES Print A
?

Else
N
O

Print B

STOP
Q1. DRAW THE FLOW CHART TO FIND EVEN
OR ODD NUMBER

Q2.DRAW THE FLOWCHART TO FIND

POSITIVE OR NEGATIVE NUMBER
FLOW CHART BASED ON DO-WHILE
CONDITION
do
{
statement;
}
while(condition);
FLOW CHART BASED ON DO-WHILE
CONDITION
do
{
statement;
}
while(condition);
Pseudo code

 A pseudocode is another way of representing an algorithm. It is considered

as a non-formal language that helps programmers to write algorithm.
 It is a detailed description of instructions that a computer must follow in a
particular order.
 It is intended for human reading and cannot be executed directly by the
computer. No specific standard for writing a pseudocode exists.
 The word “pseudo” means “not real,” so “pseudocode” means “not real
code”. Following are some of the frequently used keywords while writing
pseudocode:
• INPUT
• COMPUTE
• PRINT
• INCREMENT
• DECREMENT
• IF/ELSE
• WHILE
• TRUE/FALSE
Q1.Write an algorithm to display the sum of two
numbers entered by user using both
pseudocode and flowchart.

Pseudocode steps:-
 Step 1:- input num 1
 Step 2:- input num 2
 Step 3:- compute result = num 1+ num 2
 Step 4:- print result
 START

INPUT num1, num2

Result= num1+num2

Print Result

Stop
 Difference between algorithm and
pseudo code
Algorithm Pseudo code

1.Systematic logic approach to solve any 1.It is simple version of programming code
program. that does not require any strict programming
It is written in natural language. language syntax.

2. It has specific syntax of the programming 2. It does not have specific syntax like any of
language and can be executed on the programming language and thus
computer. cannot be executed on computer.
Q. Write an algorithm to calculate area and perimeter of a
rectangle, using both pseudocode and flowchart. Pseudocode for
calculating area and perimeter of a rectangle?
 Q. Write an algorithm to calculate area and perimeter of a rectangle,
using both pseudocode and flowchart. Pseudocode for calculating
area and perimeter of a rectangle?

 input length
 input breadth
 compute Area = length * breadth
 print Area
 compute Perimeter = 2 * (length + breadth)
 Print perimeter
 Programming language

 A programming language is a computer language that is used by programmers (developers) to

communicate with computers. It is a set of instructions written in any specific language ( C, C++, Java,
Python) to perform a specific task.
 A programming language is mainly used to develop desktop applications, websites, and mobile
applications.
Types of programming language
 Low level language

 Low-level language is machine-dependent (0 s and 1s) programming language.

 The processor runs low- level programs directly without the need of a compiler or
interpreter, so the programs written in low-level language can be run very fast.
Low-level language is further divided into two
parts :-

•Machine
1.
language
•Assembly
2.
language
 Machine language

 Machine language is a type of low-level programming language.

 It is also called as machine code or object code.
 Machine language is easier to read because it is normally displayed in binary or hexadecimal form (base
16) form.
 It does not require a translator to convert the programs because computers directly understand the
machine language programs.
 The advantage of machine language is that it helps the programmer to execute the programs faster than
the high-level programming language.
Assembly language

 Assembly language (ASM) is also a type of low-level programming language that is

designed for specific processors.
 It represents the set of instructions in a symbolic and human-understandable form.
 It uses an assembler to convert the assembly language to machine language.
 The advantage of assembly language is that it requires less memory and less execution
time to execute a program.
High level language

 High-level languages allow us to write computer code using

instructions resembling everyday spoken language (for example:
print, if, while) which are then translated into machine language to
be executed.
 Programs written in a high-level language need to be translated
into machine language before they can be executed.
 Some programming languages use a compiler to perform this
translation and others use an interpreter.
Examples of High-level Language

 ADA
 C
 C++
 JAVA
 BASIC
 COBOL
 PASCAL
 PHYTON
Basic

 Short for Beginner's All-purpose Symbolic Instruction Code.

 Developed in the 1950s for teaching University students to program and
provided with every self respecting personal computer in the 1980s.
 BASIC has been the first programming language for many programmers.
 It is also the foundation for Visual Basic.
Example of basic :-

 PRINT "Hello world!"

Visual Basic

 A programming language and environment developed by Microsoft.

 Based on the BASIC language, Visual Basic was one of the first products to
provide a graphical programming environment and a paint metaphor for
developing user interfaces.
Examples of visual basic

 MsgBox "Hello, World!“

c

 Developed by Dennis Ritchie at Bell Labs in the mid 1970s.

• C is much closer to assembly language than are most other high-level
languages.
• The first major program written in C was the UNIX operating system.
• The low-level nature of C, however, can make the language difficult to use
for some types of applications.
Example of c:-

#include<stdio.h>
int main(void)
{
printf("hello, world\n");
return 0;
}
C++

 A high-level programming language developed by Bjarne Stroustrup at Bell

Labs.
• C++ adds object-oriented features to its predecessor, C.
• C++ is one of the most popular programming language for graphical
applications, such as those that run in Windows and Macintosh environments.
Example of c++:-

#include<iostream.h>
Int main
{
cout<<“hello world”<<endl;
return 0;
}
Pascal

 A high-level programming language developed by Niklaus Wirth in the late

1960s.
• The language is named after Blaise Pascal, a seventeenth-century French
mathematician who constructed one of the first mechanical adding
machines.
• It is a popular teaching language.
Example of pascal :-

Program HelloWorld(output);
begin
writeLn('Hello, World!’)
end.
Java

 A high-level programming language developed by Sun Microsystems.

• Java was originally called OAK, and was designed for handheld devices
and set-top boxes.
• Oak was unsuccessful so in 1995 Sun changed the name to Java and
modified the language to take advantage of the burgeoning World Wide
Web.
• Java is a general purpose programming language with a number of features
that make the language well suited for use on the World Wide Web.
Example of java language:-

/** Outputs "Hello, World!" and then exits */

public class HelloWorld
{
public static void main(String[] args)
{
System.out.println("Hello, World!");
}
}
Python

 Python is a computer programming language often used to build websites and

software, automate tasks, and conduct data analysis.
 Python is a general purpose language, meaning it can be used to create a variety of
different programs and isn’t specialized for any specific problems.
 This versatility, along with its beginner-friendliness, has made it one of the most-used
programming languages today.
Why python is so popular?
 Python is popular for a number of reasons. Here’s a deeper look at what makes it so versatile and easy to use
for coders.
• It has a simple syntax that mimics natural language, so it’s easier to read and understand. This makes it
quicker to build projects, and faster to improve on them.
• It’s versatile. Python can be used for many different tasks, from web development to machine learning.
• It’s beginner friendly, making it popular for entry-level coders.
• It’s open source, which means it’s free to use and distribute, even for commercial purposes.
• Python’s archive of modules and libraries—bundles of code that third-party users have created to expand
Python’s capabilities—is vast and growing.
• Python has a large and active community that contributes to Python’s pool of modules and libraries, and
acts as a helpful resource for other programmers. The vast support community means that if coders run into a
stumbling block, finding a solution is relatively easy; somebody is bound to have run into the same problem
before.
 Example of python programming:-

#This program prints Hello, world! print('Hello, world!')

Hello, world!
 Comparison between machine language,
assembly language and high level
language
Machine language Assembly language High level language
Time to Since it is the basic language of the A program called an A program called a
execute computer, it does not require any ‘assembler’ is required to compiler or interpreter is
translation, and hence ensures convert the program into required to convert the
better machine efficiency. This machine language. Thus, it program into machine
means the programs run faster. takes longer to execute than language. Thus, it takes
a machine language more time for a computer
program. to execute.
Time to Needs a lot of skill, as instructions are Simpler to use than machine Easiest to use. Takes less
develop very lengthy and complex. Thus, it language, though instruction time to develop programs
takes more time to program. codes must be memorized. It and, hence, ensures better
takes less time to develop program efficiency.
programs as compared to
machine language.
Language translator
compiler

 Compile is to transform a program written in a high level

programming language from source code into object
code.
 This can be done by using a tool called compiler.
 A compiler reads the whole source code and translates
it into a complete machine code program to perform
the required tasks which is output as a new file.
interpreter

Interpreter is a program that executes

instructions written in a high-level
language.
 An interpreter reads the source code one
instruction or line at a time, converts this
line into machine code and executes it.
assembler

 An assembler translates a program written in assembly language into machine

language and is effectively a compiler for the assembly language, but can also
be used interactively like an interpreter.
 Assembly language is a low-level programming language.
 Low-level programming languages are less like human language in that they
are more difficult to understand at a glance; you have to study assembly code
carefully in order to follow the intent of execution and in most cases, assembly
code has many more lines of code to represent the same functions being
executed as a higher-level language.
 An assembler converts assembly language code into machine code (also
known as object code), an even lower-level language that the processor can
directly understand.
EFFICIENCY OF ALGORITHM
Time complexity

 Time complexity is the amount of time taken by an algorithm to run, as a

function of the length of the input. It measures the time taken to execute
each statement of code in an algorithm.
 This gives a clear indication of what exactly Time complexity tells us.
 It is not going to examine the total execution time of an algorithm. Rather,
it is going to give information about the variation (increase or decrease)
in execution time when the number of operations (increase or decrease)
in an algorithm.
 Yes, as the definition says, the amount of time taken is a function of the
length of input only.
Constant time complexity

An algorithm is said to have

constant time with order O (1) when
it is not dependent on the input size
n.
 Irrespective of the input size n, the
runtime will always be the same.
Linear time complexity

An algorithm is said to have a linear time

complexity when the running time
increases linearly with the length of the
input.
 When the function involves checking all
the values in an input data, such function
has Time complexity with this order O(n).
 Logarithmic time

 An algorithm is said to have a logarithmic time complexity when it reduces the size of
the input data in each step.
 This indicates that the number of operations is not the same as the input size. The
number of operations gets reduced as the input size increases.
 Algorithms with Logarithmic time complexity are found in binary trees or binary search
functions.
 This involves the search of a given value in an array by splitting the array into two and
starting searching in one split. This ensures the operation is not done on every
element of the data.
Quadratic time complexity

An algorithm is said to have a non – linear

time complexity where the running time
increases non-linearly (n^2) with the length of
the input.
Generally, nested loops come under this time
complexity order where for one loop takes O(n)
and if the function involves loop within a loop,
then it goes for O(n)*O(n) = O(n^2) order.
HOW TO CALCULATE TIME COMPLEXITY

1. For( i=0; i<n; i++) i=o, n=1

{
statement;
}
time complexity =o(n)
 2. for(i=n; i>0; i--) n=1
{
statement;
}
time complexity=o(n)
3. for(i=1; i<n; i=i+2) i=1 n=10
{
Statement;
}
time complexity=o(n)/2
Nested loop condition

For( i=0; i<n; i++)

{
for(j=0;j<i;j++)
{
Statement;
}
} time complexity =0(n^2)
Time complexity for searching and
sorting techniques are:-

Best Averag
case e case

Worst
case
Space complexity

The space complexity of an algorithm or a

computer program is the amount of memory
space required to solve an instance of the
computational problem as a function of
characteristics of the input.
It is the memory required by an algorithm until
it executes completely.
Asymptotic notations

Big-oh
Big omega
theta
Example of big oh

f(n)=o(g(n) if constant is +ve and no.

Such that f(n)<= c*g(n) n>no.

Example:-f(n)= 2n+3<=10 *n
N=1
F(n)= 2*1+3<=10*1
5<=10 f(n)=o(n)
UNIT -1 END