Algorithmic Problem

Solving

Dr. Mritunjay Shall Peelam

Assistant Professor, UPES

Problem Solving 1
Course Introduction and Objectives

Problem Solving 2
Course Outcomes

Problem Solving 3
Syllabus
Unit I Introduction to problem solving, and set theory Lecture 7

Introduction to algorithmic problem solving, review of set theory, invariants, chocolate

bars, empty boxes, the tumbler problem, crossing a river: brute force, nervous couples,
the bridge problem and conditional statements

Unit II Games Lecture 7

Games: matchstick games, winning strategies: assumptions, labelling positions, winning

strategies: formulating requirements, subtraction-set games, sums of games: a simple
sum game, sums of games: maintain symmetry, more simple sums, sums of games:
evaluating positions, using the Mex function.

Problem Solving 4
Syllabus
Unit III Knights and Knaves Lecture 7

Knights and knaves: logic puzzles, calculation logic: propositions, knight and knaves,
calculation logics: Boolean equality, hidden treasures, calculation logics, equals for
equals, equivalence and continues equalities, negation: contraposition, negation:
handshake problem, inequivalence.

Problem Solving 5
Syllabus

Unit IV Induction, Fake coin detection and Tower of Hanoi Lecture 9

Induction: example problems, cutting the plane, induction: Triominoes, looking for
patterns induction: the need for proof, from verification to construction, fake-coin
detection: problem formulation, fake-coin detection: problem solution, the tower of
Hanoi: specification and solution, the tower of Hanoi: inductive solution, the
iterative solution, the language of mathematics: variables, expressions and laws, the
language of mathematics: functions, algebraic properties, Boolean operators, and
binary relations.

Problem Solving 6
Text / Reference Books

Problem Solving 7
 Unit I Introduction
to problem solving,
and set theory

Dr. Mritunjay Shall Peelam

Assistant Professor, UPES

Problem Solving 8
Introduction to problem solving and
review of set theory
An algorithm is a well-defined procedure, consisting of a number of instructions
that are executed in turn.

Algorithms, building blocks of algorithms (statements, state, control flow,

functions), notation (pseudo code, flow chart, programming language),
algorithmic problem solving, simple strategies for developing algorithms
(iteration, recursion).

Illustrative problems: find minimum in a list, insert a card in a list of sorted cards,
Guess an integer number in a range, Towers of Hanoi.

Problem Solving 9
Definition of problem solving

Problem solving is the systematic approach to define the problem and

creating number of solutions.

The problem solving process starts with the problem specifications

and ends with a Correct program.

Problem Solving 10
Techniques of problem solving

Problem solving technique is a set of techniques that helps in

providing logic for solving a problem.

Problem solving can be expressed in the form of

• Algorithms
• Flowcharts
• Pseudo codes

Problem Solving 11
Algorithm

Algorithm is an ordered sequence of finite, well defined, unambiguous instructions

for completing a task.

It is an English-like representation of the logic which is used to solve the problem.

It is a step- by-step procedure for solving a task or a problem.

It is also defined as “any problem whose solution can be expressed in a list of

executable instruction”.

It is defined as a sequence of instructions that describe a method for solving a

problem.

In other words it is a step by step procedure for solving a problem.

Problem Solving 12
 Algorithm

Algorithm to find the area of the circle

1. Start
2. Read the value of radius r
3. Calculate - Area=3.14*r*r
4. Print the Area of the circle
5. Stop

Problem Solving 13
Characteristics of algorithm

Should be written in simple English.

Each and every instruction should be precise and unambiguous.
Instructions in an algorithm should not be repeated infinitely.
Algorithm should conclude after a finite number of steps.
Should have an end point
Derived results should be obtained only after the algorithm
terminates.

Problem Solving 14
 Qualities of a good algorithm
The following are the primary factors that are often used to judge the
quality of the algorithms.

Time – To execute a program, the computer system takes some amount of

time. The lesser is the time required, the better is the algorithm.

Memory – To execute a program, computer system takes some amount of

memory space. The lesser is the memory required, the better is the
algorithm.

Accuracy – Multiple algorithms may provide suitable or correct solutions to

a given problem, some of these may provide more accurate results than
others, and such algorithms may be suitable.
Problem Solving 15
 Qualities of a good algorithm

Time - Lesser time required.

Memory - Less memory required.

Accuracy - Suitable or correct solution obtained.

Sequence - Must be sequence and some instruction may be repeated in

number of times or until particular condition is met.

Generability - Used to solve single problem and more often algorithms are
designed to handle a range of input data.

Problem Solving 16
 Algorithmic Problem Solving

Algorithmic problem solving is solving problem that require the

formulation of an algorithm for the solution.

Understanding the Problem:

• It is the process of finding the input of the problem that the
algorithm solves.
• It is very important to specify exactly the set of inputs the
algorithm needs to handle.
• A correct algorithm is not one that works most of the time, but
one that works correctly for all legitimate inputs.

Problem Solving 17
 Algorithmic Problem Solving

Ascertaining the Capabilities of the Computational Device:

• If the instructions are executed one after another, it is called sequential algorithm.

• If the instructions are executed concurrently, it is called parallel algorithm.

Problem Solving 18
 Algorithmic Problem Solving

Choosing between Exact and Approximate Problem Solving :

• The next principal decision is to choose between solving the problem exactly or
solving it approximately.

• Based on this, the algorithms are classified as exact algorithm and approximation
• algorithm.

• Data structure plays a vital role in designing and analysis the algorithms.

• Some of the algorithm design techniques also depend on the structuring data
specifying a problem’s instance.

Algorithm+ Data structure=programs

Problem Solving 19
 Review of Set Theory

Definition
A set is a collection of objects.
An object in the collection is called an element or member of the set.
The term class is also used to denote a set.
A set may contain finite number of elements or infinite number of
elements.
A set is called an empty set or a null set if it contains no element.
An empty set is denoted by the letter ϕ.

Problem Solving 20
Review of Set Theory
• Collection of unordered and distinct elements is called a set.
• ObjectiveUnordered means that it has no fixed position.
• Distinct means that there is no repetition.
Examples:
(i) 𝐴={2,4,9,8}
(ii) A={2,4,9,8}
(iii)𝐴={1,3,5,7,9}
(iv)A={1,3,5,7,9}
(v) 𝐵={8,9,7,6}
(vi)B={8,9,7,6}
(vii)𝐴={𝑥∣𝑥 is an odd number and 1≤𝑥≤9}
(viii)A={x∣x is an odd number and 1≤x≤9}

Problem Solving 21
 Review of Set Theory

Examples:

The set of letters forming the word 'PASCAL', is a finite set, whose elements are the five
distinct letters of the word.

The set of all telephone numbers in the directory. This is also a finite, though a large, set.

The set of persons in a moving queue. This is also a finite set, but difficult to list, due to the
constant flux (At any instant of time, people are entering as well as leaving the queue).

The set of whole (natural) numbers greater than 10.

This is an infinite set, but the elements in the set can be listed, i.e. 11, 12, 13, ...

Problem Solving 22
 Review of Set Theory

Notations:
• A set is generally denoted by capital letters A, B, C, ......, X, Y, Z.
• Elements of the set are denoted by small letters a, b, c, ......, x, y, z.
• If x is an element of the set A, we express this fact by writing
'x ∈ A' (∈ means 'belongs to')
• If x is not an element of A, we write
'x ∉ A’

Problem Solving 23
 Review of Set Theory

There are various ways of describing a set:

Listing Method:
In this method, the elements are listed within braces.
e.g.
(i) A = {pencil, byte, 5}
(ii) B = {2, 4, 6, 8, .....}

Problem Solving 24
 Review of Set Theory

Statement Form:

A statement describing the set, especially where the elements share

a common characteristic.e.g.

(i) The set of all equilateral triangles.

(ii) The set of all Prime Ministers of India.

Problem Solving 25
 Review of Set Theory
Set-Builder Notation:
• It is not always possible or convenient to describe a set by the Listing
method or the Statement form.
• A more concise or compact way of describing the set is to specify the
property shared by all the elements of the set.
• This property is denoted by P(x), where P is a statement concerning an
element x of the set.
•
The set is then simply written as:
{x | P(x)}
where the braces { } denote the clause "the set of", and the slash or stroke | denotes "such
that" (read as "A is the set of all x such that x is greater than 10").

Problem Solving 26
 Review of Set Theory
Set-Builder Notation:
• It is not always possible or convenient to describe a set by the Listing
method or the Statement form.
• A more concise or compact way of describing the set is to specify the
property shared by all the elements of the set.
• This property is denoted by P(x), where P is a statement concerning an
element x of the set.
•
The set is then simply written as:
{x | P(x)}
where the braces { } denote the clause "the set of", and the slash or stroke | denotes "such
that" (read as "A is the set of all x such that x is greater than 10").

Problem Solving 27
 Review of Set Theory
Some Special Sets (Number Sets):
Symbol Description
N the set of all natural numbers {1, 2, 3, ...... }.
Z the set of all integers {...... –2, –1, 0, 1, 2, ........ }.
Z⁺ the set of all positive integers {0, 1, 2, ...... }.
Q the set of rational numbers.
Q⁺ the set of non-negative rational numbers.
R the set of real numbers.
ℂ the set of complex numbers.

Problem Solving 28
 Review of Set Theory
Some Consequences:

The following consequences of the definition of a subset of a set are of

basic importance:

• Every set is a subset of itself.

• Two sets A and B are equal if and only if A ⊆ B and B ⊆ A.
• The null set Φ is a subset of every set A.
• For any sets A, B, and C, if A ⊆ B and B ⊆ C, then A ⊆ C.
• For any sets A, B, C, if A = B and B = C, then A = C.

Problem Solving 29
Review of Set Theory

Problem Solving 30
Review of Set Theory

Problem Solving 31
Review of Set Theory

Problem Solving 32
Review of Set Theory

Problem Solving 33
Review of Set Theory

Problem Solving 34
Review of Set Theory

Problem Solving 35
Review of Set Theory

Problem Solving 36
Review of Set Theory

Problem Solving 37
Review of Set Theory

Problem Solving 38
Review of Set Theory

Problem Solving 39
Review of Set Theory

Problem Solving 40
Review of Set Theory

Problem Solving 41
Review of Set Theory

Problem Solving 42
Review of Set Theory

Problem Solving 43
Review of Set Theory

Problem Solving 44
Review of Set Theory

Problem Solving 45
Review of Set Theory

Problem Solving 46
Review of Set Theory

Problem Solving 47
Review of Set Theory

Problem Solving 48
Review of Set Theory

Problem Solving 49
Review of Set Theory

Problem Solving 50
Review of Set Theory

Problem Solving 51
Review of Set Theory

Problem Solving 52
Review of Set Theory

Problem Solving 53
Review of Set Theory

Problem Solving 54
Review of Set Theory

Problem Solving 55
Review of Set Theory

Problem Solving 56
Review of Set Theory

Problem Solving 57
Thank You

Problem Solving 58