CSE1021- Problem Solving

and Programming
[Link]
100256
Contents

1. Problem Solving Aspects

2. Top Down Design
3. Problem Solving Strategies
4. Programs and Algorithms
5. Algorithms
6. Flowcharts
7. Algorithms and Flowcharts – Samples
8. Analysis of Algorithms

2
Problems

A Task to be performed
• Best thought of inputs and matching outputs
Programs and Algorithms

The Vehicle for the computer Solution in 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.
Problem 1

A farmer wants to cross a river and take with him a wolf, a goat, and a cabbage.

There is a boat that can fit himself plus either the wolf, the goat, or the cabbage.

If the wolf and the goat are alone on one shore, the wolf will eat the goat.

If the goat and the cabbage are alone on the shore, the goat will eat the cabbage.

How can the farmer bring the wolf, the goat, and the cabbage across the river?

[Link]
Solution – 1
Step 1: Farmer takes Goat across the river (leaving Wolf and Cabbage behind)

Step 2: Farmer returns alone

Step 3: Farmer takes Wolf across the river

Step 4: Farmer returns with Goat

Step 5: Farmer takes Cabbage across the river

Step 6: Farmer returns alone

Step 7: Farmer takes Goat across the river

[Link]
Problem - 2
There are 4 men who want to cross a bridge. They all begin on the same side. You have 17 minutes
to get all of them across to the other side. It is night. There is one flashlight. A maximum of two
people can cross at one time.
Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must
be walked back and forth, it cannot be thrown etc.

Each man walks at a different speed. A pair must walk together at a rate of the slower man's pace.

Man 1: 1 minute to cross, Man 2: 2 minutes to cross., Man 3: 5 minutes to cross., Man 4: 10
minutes to cross.
For example, if Man 1 and Man 4 walk across first, 10 minutes have elapsed when they get to the
other side of the bridge. If Man 4 returns with the flashlight, a total of 20 minutes have passed, and
you have failed the mission.
[Link]
Solution - 2

Step 1: Men 1 and 2 travel over - Time Elapsed 15

Step 2: Man 2 brings back the flashlight – Time Elapsed 13

Step 3: Men 3 and 4 travel over and – Time Elapsed 3

Step 4: Man 1 brings back the flashlight – Time Elapsed 2

Step 5: Men 1 and 2 travel over – Time Elapsed 0

11
Algorithms
★Algorithm: a method or a process followed to solve a problem.

○ A recipe preparation.

★An algorithm takes the input to a problem (function) and transforms it to the
output.

○ A mapping of input to output.

★ A problem can have many algorithms.

12
Algorithm - Informally

An algorithm is any well-defined computational procedure

that takes some value, or set of values, as input and
produces some value, or set of values, as output.

An algorithm is the series of steps (not necessarily linear!)

that provide the solution to your problem.
Algorithm - Definition

An algorithm is a sequence of
unambiguous instructions for solving a
problem, i.e., for obtaining a required
output for any legitimate input in a
finite amount of time [Levitin].
World run on algorithms
• Without algorithms,
• Modern airplanes would not fly
• Cars could not be driven
• Rail and subway system would not work.
• FedEx and UPS would be crippled
• No Digital TV
• No Cable Systems
• No Telephone, etc.,
• No power etc…,
Anything software - driven
• Digital ecosystem
• Energy grid - Smart Grids (load balancing, fault detection, net
metering)
• Power plants (Decisions per second)
• Future Cars (collision avoidance, parking assistance, lane – departure
warnings, smart cruise control, inter car communication etc.,)
• Food Production. (Plant a seed to Harvest)
Characteristics

Finiteness

Definiteness

Generality

Effectiveness

Input / Output
Finiteness
An algorithm must terminate after finite number of steps.

18
Definiteness
The steps of the algorithm must be precisely defined

19
Generality
An algorithm must be generic enough to solve all problems of a
particular class

20
Effectiveness
The operations of the algorithm must be basic enough to be put down
on pencil and paper.

21
Input - Output
The algorithm must have certain initial and precise inputs, and outputs
that may be generated at its intermediate and final steps.

22
23
• Problem Solving is a creative process that needs systemization and
mechanization
• Most people during their schooling, acquire atleast a modest set of
problem solving skills which they are or are not aware of
• Anyone who is not naturally skilled in problem solving, number of
steps can be taken to raise the level of one’s performance
• There is no universal method. Different strategies work for different
people
Problem Solving Aspect

Working General
Problem Getting Use of Similarities
backwards Problem
Definition Started on Specific among
from the Solving
Phase a Problem Examples Problems
solution Strategies

25
Problem Definition Phase

26
Problem Definition Phase
• Success in solving any problem – understand the problem at hand
• Progress will be there if the problem what we try to solve is clearly
understood
Problem Definition Phase

28
Problem Definition Phase
Success in solving any problem comes from how to understand the
problem in a better way

What must be done rather than how to do it

Try to extract from the problem statement

A set of precisely defined tasks

From the definitions, we are led in a natural way to algorithm designs

29
Problem Definition Phase – General

What are you asked to find or show?

Can you restate the problem in your own words?

Can you think of a picture or a diagram that might help you understand the
problem?

Is there enough information to enable you to find a solution?

Do you understand all the words used in stating the problem?

Do you need to ask a question to get the answer?

30
Problem Definition Phase – Programming

Can I restate the problem in my own words?

What are the inputs that go into the problem?

What are the outputs that should come from the solution to the
problem?
Can the outputs be determined from the inputs? In other words, do I
have enough information to solve the problem?
How should I label the important pieces of data that are a part of the
problem? 31
An Example - Write a function which takes
two numbers and returns their sum.
Can I restate the problem in my own words? Maybe something like "Write a function that adds two
numbers," or "Implement addition."

What are the inputs that go into the problem? Two numbers.

This might seem like an open and shut case, but even here it's worth thinking about the structure
of the inputs.

For instance, are the numbers integers, or are floats allowed too? Should the inputs even be
numbers at all, or strings representing numbers? If the latter, the problem suddenly becomes much
harder, because you can represent arbitrarily large numbers with strings. 32
An Example - Write a function which takes
two numbers and returns their sum.
What are the outputs that should come from the solution to the problem? One number,
representing the sum of the inputs. Here too, it's worth thinking about type: should the output
be a number, a string, or something else?

Can the outputs be determined from the inputs? It seems that way, though the answer depends a
bit on the answer to 2. For instance, if it's possible that there could be fewer than two inputs, it's
not necessarily clear what the output should be if the user doesn't pass in any arguments at all.
(Note how we're already finding examples of edge cases, before we've started writing any code!)

How should I label the important pieces of data that are a part of the problem? This is a matter of
personal preference, but it seems like there are four things that could use labels: the function,
the two inputs, and the output. Names like add, num1, num2, and sum seem suitably
descriptive.
33
34
Getting Started on a problem

35
Getting Started on a problem
• Many ways to solve most problems
• Many solutions to most problems
• A block often occurs at this point because people become concerned
with details of the implementation before they have completely
understood or worked out an implementation – independent solution
• The best advice here is not to be too concerned about detail.
• The sooner you start coding your program the longer it is going to
take

36
The use of Specific Examples

37
The use of Specific Examples
• A Useful strategy when we are stuck is to use some props or
heuristics (i.e., rules of thumb) to try to get a start with the problem
• E.g. if you want to find the maximum / minimum in a set of numbers, Choose
a particular set of numbers and work out the mechanism for finding the
maximum / minimum in this set.

38
The use of Specific Examples
• It is usually much easier to work out the details of a solution to a
specific problems is more clearly defined.
• A specific problem often forces us to focus on details that are not so
apparent when the problem is considered abstractly.
• Geometrical or schematic diagrams representing certain aspects of
the problem can be usefully employed in many instances
• It is very easy to fall into the trap of thinking that the solution to a
specific problem or a specific class of problems is also a solution to
the general problem.

39
Similarities among Problems

40
Similarities among Problems
• Try to do with as much past experience as possible to bear o the
current problem
• If there are any similarities between the current problem and other
problems that we have solved or we have been solved.
• Make an effort to be aware of the similarities among problems.
• The more experience one has the more tools and techniques one can
bring to bear in talking a given problem.
• A classis case of experience blocking progress was Einstein’s discovery
of relativity.
• Newton’s theory was correct and that was all there was to it.

41
Similarities among Problems
• In trying to get a better solution to a problem, sometimes too much
study of the existing solution or a similar problem forces us down the
same reasoning path (which may not be the best) and to the same
dead end.
• In trying to get a better solution to a problem, it is usually wise, in the
first instance at least, to try to independently solve the problem.
• A skill that it is important to try to develop in problem solving is the
ability to view problem from a variety of angles
• One must be able to metaphorically turn a problem upside down,
inside out, sideways, backwards, forwards and so on.
• Once one has developed this skill it should be possible to get started
on any problem.
42
Working backwards from the solution

43
Working backwards from the solution
• We do not know where to start on a problem
• We already have the solution to the problem an then try to work
backwards to the starting conditions.
• Even a guess at the solution to the problem may be enough to give us
a foothold to start on the problem.
• Another practice that helps us develop our problem solving skills is,
once we have solved a problem, to consciously reflect back on the
way we went about discovering the solution.
• This can help us significantly – “We learn most when we have to
invent”
44
General problem – solving strategies

45
General problem – solving strategies
Divide – and – Decrease and Transform and
Brute Force
Conquer Conquer Conquer

Dynamic Greedy Branch and

Backtracking
Programming Programming Bound

Space and
Exhaustive Approximation
Time Trade –
Search algorithms
Offs.
46
 1. Brute-Force
• Simple, Straight Forward
• Example: Padlock with 4 Digits, Exhaustive Search of Lost Articles in
Home.

47
 2. Divide and Conquer
• Problem divided into sub problems, sub problems are solved
independently and merge the solutions of sub problem for final
solution of the problem.
• Example: Counting the coins by grouping them into denomination.

48
 3. Greedy Algorithm
• Decisions are taken based on Local Optimal Solution at every stage.
• Travelling from Kanyakumari to Kashmir by visiting all the states
capital.

49
 4. Dynamic Programming
• Mathematical Optimization Problem
• Breaks the problem into sub problems, solve the sub problems over
time as sequence to reach the final solution.
• Uses Recursion
• Example: Arranging the cards for rummy game.

50
5. Branch and Bound – Combinatorial
Optimization

51
 6. Randomized Algorithm
• Random Numbers for Decision Making & Optimization.
• Accidently Good
• Feedback Assessments, Surprise Checks, etc.

52
 7. Back Tracking
• Incremental Approach
• Uses the previous stage solution to next stage solution
• Examples: Crossword

53
Top – Down Design
Breaking the problem into Sub
problems

Choice of Suitable Data Structure

Construction of the loops

Establishing Initial Conditions for the

loops

Finding the Iterative Construct

Termination of the loops

54
Breaking the problem into Sub problems

Split the bunch

of sticks in to
individuals and
break them one
by one

55
Lion Vs Cows

[Link]
Lion Vs Cows
Once upon a time, there lived four cows in the forest. Every day, they used to graze together in a
particular place.
One day a lion passed that way and saw the four cows. The lion went near the cows.

When the cows saw the lion coming near to them, all of them fought together against the lion.

The Lion ran away.

After some days, the cows quarreled with each other and began to graze in different directions and
all alone.
This was noticed by the lion. The lion thought that its turn had come and came there.

The lion killed all the four cows one by one.

Moral : Break the group of problems and Deal with them individually.
Choice of Suitable Data Structure

[Link]

58
Librarian Vs Books
• There is one library which contains many book racks.
• Librarian need to find individual racks to keep the books in classified
manner
• Stories, Mathematics, Bio-Science, Engineering, Medical etc.
• Books need to be numbered and racks must have name
• It helps to viewers to find the appropriate book (data) easily with less
searching time.
• Librarian can easily maintain issue and return records (push and pop)

Moral : Keep the data in efficient format and structure to deal with it.
Construction of Loops

60
6 Circuit Labyrinth
• One Entry point
• Six iterations
• Know the strategies to find exit
• If it not works you may fail
• You may be trapped inside loop
Have you seen any movies regarding this ?
Or any stories on Labyrinth ?
Its function is to hold the Minotaur, the monster eventually killed by the hero Theseus.
Daedalus had so cunningly made the Labyrinth that he could barely escape it after he
built it.

Moral : How to enter and exit using predefined logics

Establishing Initial Conditions for the Loops

62
Finding the Iterative Constructs

63
Termination of the Loops

[Link] [Link]
Implementation of Algorithms

Flowcharts Pseudo Code

Programming
Language (Python)

65
 Implementation of Algorithms

Problem solving
phase

Implementation
phase

[Link] 66
Pseudo Code
• In Pseudo code it looks like this:

67
Pseudo Code
• For example, for making a cup of tea: • Or as a program:
Organize everything together;

Plug in kettle;

Put teabag in cup;

Put water into kettle;

Wait for kettle to boil;

Add water to cup;

Remove teabag with spoon/fork;

Add milk and/or sugar;

Serve; 68
Pseudo Code
• SELECTION
• So, we could state this as
• What if we want to make a
choice, for example, do we want
to add sugar or not to the tea?
• We call this SELECTION.

69
Pseudo Code
• SELECTION • Loop

70
Pseudo Code: Example
• Write an algorithm to determine a student’s final grade and indicate
whether it is passing or failing. The final grade is calculated as the
average of four marks.

 Detailed Algorithm
 Step 1: Input M1,M2,M3,M4
Step 2: GRADE  (M1+M2+M3+M4)/4
Step 3: if (GRADE < 50) then
Print “FAIL”
else
Print “PASS”
endif

71
The Flowchart
• (Dictionary) A schematic representation of
a sequence of operations, as in a
manufacturing process or computer
program.
• (Technical) A graphical representation of
the sequence of operations in an
information system or program.
• Information system flowcharts show how data
flows from source documents through the
computer to final distribution to users.
• Program flowcharts show the sequence of
instructions in a single program or subroutine.
Different symbols are used to draw each type
of flowchart.
72
The Flowchart
• Flowchart Symbols
Name Symbol Use in Flowchart

Oval Denotes the beginning or end of the program

Flowchart
Parallelogram Denotes an input operation

shows logic of an
algorithm
Rectangle Denotes a process to be carried out
e.g. addition, subtraction, division etc.

emphasizes
Diamond Denotes a decision (or branch) to be made. individual steps
The program should continue along one of and their
two routes. (e.g. IF/THEN/ELSE)
interconnections

Hybrid Denotes an output operation

e.g. control flow
from one action to
the next
Flow line Denotes the direction of logic flow in the program 73
The Flowchart: Example
START

Input
M1,M2,M3,M4
• Step 1: Input M1,M2,M3,M4
• Step 2: GRADE 
GRADE(M1+M2+M3+M4)/4
(M1+M2+M3+M4)/4
• Step 3: if (GRADE <50) then
• Print “FAIL” N IS Y
• else GRADE<5
• Print “PASS” 0

• endif PRINT
“FAIL”

STOP

74
 The Flowchart: Example
START
• Write an algorithm and draw a
flowchart that will read the two sides
Input
of a rectangle and calculate its area. W, L

Pseudo code ALxW

• Input the width (W) and Length (L) of a
rectangle
Print
• Calculate the area (A) by multiplying L A
with W
• Print A
STOP

75
The Flowchart

Flowcharts is a graph used to depict or show a step by step

solution using symbols which represent a task.

The symbols used consist of geometrical shapes that are

connected by flow lines.

It is an alternative to pseudocoding; whereas a pseudocode

description is verbal, a flowchart is graphical in nature

76
The Flowchart Rules
• sequence control structure • selection control structure

Statement 1
No Yes
Condition

Statement 2

else- then-
Statement 3
statement(s) statement(s)

77
The Flowchart Rules
• repetition control structure

yes Loop
Condition
Statement(s)

no

78
Programming Languages

79
Programming Languages
• What is a Programming Languages

programming language allows

people to create programs that tell
machines (computers) what to do.
A programming language is a tool
for developing executable models
for a class of problem domains.
80
Levels of Programming Languages

81
Levels of Programming Languages

82
Types of Programming

Batch Programming (BASIC, FORTRAN,

COBOL)

Structured Programming (PASCAL, C)

Object-Oriented Programming (C++, Java,

C#, PYTHON)

Logic/Declarative Programming (Prolog)

Functional/Applicative Programming (Lisp)

Top Programming Languages
High-level Languages
C

C++

• Developed by Bell Laboratories in the

JAVA
early 1970s.
PYTHON
• Provides control and efficiency of
assembly language while having third
generation language features.
R

• Often used for system programs.

HTML • UNIX is written in C.

XML
High-level Languages
C

C++

JAVA
• It is C language with additional features.
• Widely used for developing system and
PYTHON application software.
• Graphical user interfaces can be
R
developed easily with visual
programming tools.
HTML

XML
High-level Languages
C

C++

• An object-oriented language similar to C++

JAVA
that eliminates lots of C++’s problematic
features
PYTHON
• Allows a web page developer to create
programs for applications.
R
• Objective of JAVA developers is that it be
machine, platform and operating system
HTML independent.

XML
High-level Languages
C

C++

• Extensible Markup Language.

JAVA

• A language for defining other

PYTHON
languages

HTML

XML
High-level Languages
C

C++

• HyperText Markup Language.

JAVA

• Used on the Internet and the

PYTHON
World Wide Web (WWW).
• Web page developer puts brief
R
codes called tags in the page to
indicate how the page should be
HTML
formatted.

XML
Difference between a high and
low-level programming language

• Low level languages work more closely with

Hardware and do not require a compiler to be
Executed.
• High level languages are more Understandable
for the programmer in terms of The words in the
code.
Program Verification
Verification and Validation
The program being developed must be checked to ensure that it
meets its specification and delivers the functionality expected by
the people paying for the software.

Verification
• Are you building the product right?
• Software must conform to its specification

Validation
• Are you building the right product?
• Software should do what the user really requires
 Verification and Validation Goals

• Establish confidence that the software system is ‘fit for its

intended purpose’.
• Level of required confidence depends upon
System purpose
User expectations
Marketing environment
• deciding how much effort should be spent on the V & V process.
Efficiency of Algorithms
• Every algorithm must use up some computer resources to complete its
tasks.
• The resources most relevant in relation to efficiency are central processor
time and internal memory.
• The efficiency or running time 2of4 2an
5 2 algorithm is stated as a function
relating the input length to the number of steps, known as time
complexity, or volume of memory, known as space complexity.
• A good algorithm is correct, but a great algorithm is both correct
and efficient.
• The most efficient algorithm is one that takes the least amount of
execution time and memory usage possible while still yielding a correct
answer.

94
Efficiency of Algorithms - Problem
• Consider an algorithm for drawing a house. Since the problems is a
little vague, there are many potential solutions. Here is one of them:
• Algorithm1: DrawSimpleHouse
1. draw a square frame 24252

2. draw a triangular roof

3. draw a door

95
Efficiency of Algorithms - Solution
1. draw a square frame
2. draw a triangular roof
3. draw a door
4. draw windows
5. draw chimney
6. draw smoke
7. draw land
8. draw path to door

96
Efficiency of Algorithms

Algorithm The space

The runtime
efficiency is used to complexity of an
complexity (a.k.a.
describe properties algorithm is the
running time) of an
of an algorithm amount of storage
algorithm is the
relating to how space that it
amount of time that
much of various requires while
it takes to complete
types of resources it running from start
once it has begun.
consumes. to completion.
Algorithm for setting a table
• AlgorithmY1: SetTableFor4
1. walk to kitchen
2. repeat 4 times {
3. getGlass()
4. place glass on table
5. getPlate()
6. place plate on table
7. getUtensils()
8. place knife and fork on table }
9. go back onto couch
Algorithm for setting a table
• AlgorithmY2: EfficientSetTableFor4
1. walk to kitchen
2. getGlasses()
3. place glasses on table
4. getPlates()
5. place plates on table
6. getUtensils()
7. place knives and forks on table
8. go back onto couch
• We can actually generalize the algorithm to set the table for as many
guests as we want by supplying some additional information in our
functions.
• A parameter is a piece of data provided as input to a function or
procedure.
• We can supply an arbitrary number in our algorithm to specify how
many place settings to set as follows:
Algorithm for setting a table
• AlgorithmY3: EfficientSetTableFor8
1. walk to kitchen
2. getGlasses(8)
3. place glasses on table
4. getPlates(8)
5. place plates on table
6. getUtensils(8)
7. place knives and forks on table
8. go back onto couch
• For example, consider these two algorithms for setting the table for n
people:

Algorithm A: Algorithm B:
1. walk to kitchen 1. walk to kitchen
2. repeat n times { 2. getGlasses(n)
3. getGlass() 3. place glasses on table
4. place glass on table 4. getPlates(n)
5. getPlate() 5. place plates on table
6. place plate on table 6. getUtensils(n)
7. getUtensils() 7. place knives and forks on table
8. place knife and fork on table 8. go back onto couch
}
9. go back onto couch
Analysis of Algorithms
• 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 saving computing resources which translates into a
saving in time and memory.
• We can have three cases to analyze an algorithm:
1. Worst Case
2. Average Case
3. Best Case
• Counting the operations for searching an element
PROCEDURE searchList(numbers, targetNumber) {
index ← 1
REPEAT UNTIL (index > LENGTH(numbers)) {
IF (numbers[index] = targetNumber) {
RETURN index
}
index ← index + 1
}
RETURN -1
}
searchList([3, 37, 45, 57, 93, 120], 45)
• Now let's count the number of operations that the linear search algorithm
needed to find that value, by counting how often each type of operation
was called.
operation # of times
Initialize index to 1 1
Check if index is greater than LENGTH(numbers) 3
Check if numbers[index] equals targetNumber 3
Return index 1
Increment index by 1 2
• That's a total of 10 operations to find the targetNumber at the index of 3.
Notice the connection to the number 3? The loop repeated 3 times, and
each time, it executed 3 operations.
• There's a pattern to how many operations it takes to find a number, based on where that number
is in the list. It always takes one operation to initialize index, and then as many loop iterations as
the item's position (3rd item = 3 iterations), with 3 operations per iteration.
• So, for an item located at position L, linear search takes 1 + 3L operations to find it.

Location in list # of operations

1st item in list (1 + 3*1) = 4
2nd item in list (1 + 3*2) = 7
3rd item in list (1 + 3*3) = 10
4th item in list (1 + 3*4) = 13
5th item in list (1 + 3*5) = 16
6th item in list (1 + 3*6) = 19
• The best case for an algorithm is the situation which requires the
least number of operations. According to that table, the best case for
linear search is when targetNumber is the very first item in the list.
• What about the worst case? According to that table, the worst case is
when targetNumber is the very last item in the list, since that requires
repeating the 3 loop operations for every item in the list.
• The average case is when targetNumber is in the middle of the list.
That's the example we started with, and that required 3 repetitions of
the loop for the list of 6 items.