Unit 1:Algorithm

CONCEPT OF PROBLEM
• A problem is any situation in which you have a starting point, a set of
directions, and the need to create a solution or answer.
• A problem is a question or situation that motivates you to search for a
solution. This implies first that you want or need to solve the problem and
second that you have to search for a way to find a solution. Whether a
question is a problem or an exercise depends on the prior knowledge of the
problem solver.
• Specifically, the task of defining the problem consists of identifying
what it is you know (input-given data), and what it is you want to
obtain (output-the result).
• Two aspects of problem:
[Link] detective for dealing with the crisis and the analytical parts of problem definition.
[Link] explorer for dealing with the context and the opportunity aspects of the problem.
Definition of Problem
• "A problem is an issue or obstacle which makes it
difficult to achieve a desired goal, objective or purpose".
OR
• "Problem refers to a situation, condition or issue that is
yet unresolved". OR
• A problem is "a question or situation raised for
consideration or solution".
Problem Solving
• Problem solving is the sequential process of analyzing
information related to a given situation and generating
appropriate response options.
• The ultimate goal of problem solving is to overcome obstacles
and find a solution that best resolves the issue.
• There are a number of different mental processes at work during
problem solving. These include:
[Link] recognizing a problem.
[Link] the problem in memory.
[Link] relevant information that applies to the current problem.
[Link] different aspects of the problem.
[Link] and describing the problem.
Definition
• Problem solving is "the process of working through
details of a problem to reach a solution".
OR
• Problem solving is a mental process that involves
discovering, analyzing and solving problems.
Problem Solving Steps
• Defining (identifying) the problem:
• In almost every problem solving methodology, the first step is defined or
identifies the problem. It is the most difficult and the most important of
all the steps. It involves diagnosing the situation so that the focus on the
real problem and not on its symptoms.

• Gather facts:
• You must understand what is involved in the problem before you can
continue toward the solution.
• Some means of gathering data are:
• Define key terms.
• Expressive assumptions.
• Discuss the problem with someone else.
• Get the viewpoint of others.
• Identify alternative ways to solve the problem:
• One way to identify possible solutions is to represent the problem
either internally or externally. By representing the problem, you will
select information that is related to the goal, the initial state, the
operators and restrictions. Operators are actions that change the
initial state of the problem into another. Then you may categorize it
as a type of problem, develop similar solutions, identify the criteria
for evaluating the solution and adjust and combine ideas.
• Some of the tools used to identify alternative ways:
• Systematic trial and error.
• Proximity searching.
• Means ends.
• Fractional method.
• Knowledge based.
• Implement and Evaluate
• Make a list of the different options that you have generated. Select
one or more solutions options from near the top of your list to try.
Measure the impact of the solution. The evaluation of your
implementation is not based on whether or not you followed the
steps, but on whether or not your goals are met.
• Observe the solution:
• Re-apply measurements to confirm that change has taken place.
• Check to ensure that the changes do not negatively impact another area.
• Provide sufficient information and training so that change can take place and
be sustained.
• Reflect on the problem solving process used. What would you have done
differently?
Problem Solving Techniques

Problem
Solving
Techniques

Trial and Divide and

Brainstormin
Error Conquer
g Technique
Technique Technique
Trial and Error Method (Technique)
• Trial and error, or trial by error, is a general method of
problem solving.
• A trial and error approach to problem solving involves
trying a number of different solutions and ruling out
those that do not work.
• This approach can be a good option, if you have a very
limited number of options available.
• This method is often used by people who have little
knowledge in the problem area.
• Features of Trial and Error Method
• Solution-oriented: Trial and error makes no attempt to discover why a
solution works, merely that it is a solution.
• Problem-specific: Trial and error makes no attempt to generalize a solution
to other problems.
• Non-optimal: Trial and error is an attempt to find a solution, not all solutions,
and not the best solution.
• Needs little knowledge: Trial and error can proceed where there is little or
no knowledge of the subject.
• Advantages:
• Easy to implement.
• This method is best in situations where you have more test subjects.
• Disadvantages:
• Time consuming because of need to run each and every test.
Brainstorming Method (Technique)
• Brainstorming is a group creativity technique designed to
generate a large number of ideas for the solution to a problem.
• Brainstorming process involves a group working together and
stating ideas, arguing the merits of those ideas, supplementing
those ideas or rejecting those ideas.
• Brainstorming combines a relaxed, informal approach to
problem solving with lateral thinking.
• Basic Rules of Brainstorming:
• Combine and Improve Ideas: This approach is assumed to lead to
better and more complete ideas than merely generating new ideas
alone. It is believed to stimulate the building of ideas by a process of
association.
• No Criticism: This is often emphasized that in group brainstorming,
criticism should be put on hold. Instead of immediately stating what might
be wrong with an idea, the participants focus on extending or adding to it.
It reserves criticism for a later critical stage of the process. By suspending
judgment, one creates a supportive atmosphere where participants feel
free to generate unusual ideas.
• Focus on Quantity Rule: This rule is a means of enhancing different
production, aiming to facilitate problem solving through the maximum
quantity breeds quality. The assumption is that the greater the number of
ideas generated, the greater the chance of producing a radical and
effective solution.
• Unusual Ideas are Welcome: To get a good and long list of ideas,
unusual ideas are welcome. They may open new ways of thinking and
provide better solutions than regular ideas. They can be generated by
looking from another perspective or suspended assumptions.
• Variations of Brainstorming Techniques:
• Nominal Group Technique: The Nominal Group Technique is
a type of brainstorming that encourages all participants to
have an equal say in the process. It is also used to generate a
ranked list of ideas. Participants are asked to write down their
ideas anonymously. Then the moderator collects the ideas and
each is voted on by the group.
• Group Passing Technique: Each person in a circular group
writes down one idea, and then passes the piece of paper to
the next person in a clockwise direction, who adds some
thoughts. This technique is repeated until everybody gets
their original piece of paper back. By this time, it is likely that
the group will have extensively elaborated each idea.
• Team Idea Mapping Method: Team Idea Mapping method of
brainstorming works by the method of association. It may
improve collaboration and increase the quantity of ideas, and
is designed so that all attendees participate and no ideas are
rejected.
• Electronic Brainstorming: Electronic Brainstorming is a
computerized version of the manual brain storming technique.
It can be done via e-mail. Electronic brainstorming also
enables much larger groups to brainstorm on a topic than
would normally be productive in a traditional brainstorming
session. Electronic brainstorming eliminates many of the
problems of standard brainstorming, such as production
blocking and evaluation apprehension.
• Directed Brainstorming: Directed Brainstorming is a
variation on electronic brainstorming described above. It can
be done manually or with computer technology. This works
when the solution space is known prior to the session. If
known, that criteria can be used to intentionally constrain the
ideation, process. In directed brainstorming, each participant
is given one sheet of paper and told the brainstorming
question.
• Individual Brainstorming: Individual Brainstorming is the
use of brainstorming on a solitary basis. Individual
brainstorming typically includes such techniques as free
writing, free speaking, word association, and the spider web,
which is a visual note taking technique in which a people
diagram their thoughts.
• Advantages:
• Easy to understand i.e. it is not a complicated technique.
• It is inexpensive.
• If controlled properly, it is a quick way of generating ideas.
• Encourages creative thinking and thinking "out of the box".
• Generates ideas and solutions that can be used elsewhere.
• Provides an opportunity for widespread participation and involvement
• Disadvantages:
• As this is a group activity, participants have to listen patiently and have
to spend more time in sharing their ideas till they are noticed by others.
• More discrete and introvert participants might find it difficult to express
their crazy or unorthodox ideas.
Divide and Conquer Method
(Technique):
• The name Divide and Conquer is because the problem is conquered by dividing it
into several smaller problems.
• Divide and Conquer is an approach to solve a problem that is a special case of
means-ends analysis.
• In Divide and Conquer, one solves a problem by first defining a sub-goal that
involves solving a smaller version of the same kind of problem.
• In other words, divide and conquer is the explicit use of recursion to solve a
problem.
• A Divide and conquer algorithm is closely tied to a type of recurrence relation
between functions of the data in question; data is divided into smaller portions and
then result is calculated.
• Divide and Conquer technique is the basis of efficient algorithms for all kinds of
problems, such as sorting (quick sort, merge sort) and the discrete Fast Fourier
Transforms (FFTs). Its application to numerical algorithms is commonly known as
binary splitting.
• Working
• It works by recursively breaking down a problem into two or
more sub-problems of the same (or related) type, until these
become simple enough to be solved directly.
• The solutions to the sub-problems are then combined to give a
solution to the original problem
• Advantages of Divide and Conquer Technique:
• Solving difficult problems: Divide and Conquer is a
powerful tool for solving conceptually difficult problems, all it
requires is a way of breaking the problem into sub-problems,
of solving the trivial cases and of combining sub-problems to
the original problem.
• Disadvantages of Divide and Conquer Technique:
• Slow Recursion: The overhead of the repeated subroutine
calls, along with that of storing the call stack, can outweigh
any advantages of the approach. This, however, depends
upon the implementation style: with large enough recursive
base cases, the overhead of recursion can become negligible
for many problems.
• Complicated for simple problems: Another problem of a
divide and conquer approach is that, for simple problems, it
may be more complicated than an iterative approach,
especially if large base cases are to be implemented for
performance reasons.
• Algorithm Efficiency: The Divide and Conquer paradigm
often helps in the discovery of efficient algorithms.
• Parallelism: Divide and Conquer algorithms are naturally
adapted for execution in multi-processor machines, especially
shared-memory systems where the communication of data
between processors does not need to be planned in advance,
because distinct sub-problems can be executed on different
processors.
• Memory Access: Divide and Conquer algorithms naturally
tend to make efficient use of memory caches. The reason is
that once a sub-problem is small enough, it and all its sub-
problems can, in principle, be solved within the cache, without
accessing the slower main memory.
PROGRAM DEVELOPMENT CYCLE
• Program development cycle is a set of phases and steps
that are followed by problem solver to define, develop
and maintain a program.
• Planning your program using a sequence of steps,
referred to as the program development cycle.
 Define a
Problem

Test and Design a

debug Problem

Execute
Code the
the
program
program

Compile
and link
the
program
• Step 1: Define the Problem:
• It is very important that you understand the problem you are trying to solve. Make
sure you read the problem specifications carefully.
• Know what data is to be input into the program and what form that data should be in.
Also, know what processing has to be done to that data.
• Finally, determine what the expected output is supposed to be and what form the
output must take.
• Step 2: Design the Program:
• There are several ways of describing program design. Two common methods are by
flowcharts and pseudocode.
• A flowchart is a graphic description of a program design that uses combinations of
various standard flowchart symbols.
• We shall use flowcharts to represent only the basic program control structures.
• Pseudocode (literally, "false code") describes program design using English.
Pseudocode avoids the syntax of a programming language and, instead, emphasizes
the design of the problem solution.
• Step 3: Code the Program
• To code a program means to translate the design from step 2 into a
computer programming language.
• Code the program by entering it into your IDE's text editor, or any text
editor on your computer system. Make sure that you save the program to
disk before proceeding to the next step.
• In the next step of the program development cycle, you will submit the
program code, called the source program or the source code, to the
computer for compilation.
• Step 4: Compile and Link the Program
• The only language a given computer understands is its own machine
language. A machine language instruction is a binary-coded instruction
(consisting of zeros and ones) that commands the computer to do one
specific task, such as add 1 to a register.
• Each computer has its own machine language. The machine
language for a Sun workstation is different from the machine
language of a Macintosh, which is different from the machine
language of an IBM PC, and so on. Because machine language
is in binary, it is difficult to write and find errors in machine
language programs.
• A compiler has two main functions.
• Checking fatal syntax errors.
• Translate the code into machine specific language.
• First it checks the source program for syntax errors. Syntax
errors are errors in the grammar of the programming
language. If there are any fatal syntax errors (that is, errors so
severe that the compiler does not understand the statement
and cannot translate the statement into machine language),
the compiler will stop and notify you of the errors it found.
• If the compiler finds no fatal errors, it translates each high-
level language instruction into one or more machine language
instructions. This machine language version of the source
program is the object program.
• Step 5: Execute the Program:
• Once you have compiled and linked the program, you are ready to
execute the program.
• Executing the program is usually quite simple. In some IDEs, all you
need to do is select the execute option from a menu or click an icon.
• Step 6: Test and Debug the Program
• Even if a program executes, it does not mean that the program is
correct.
• Even if a program gives correct results using some data, it does not
mean that the program will give correct results using another set of
data.
• Thus, program should be tested for various possible sets of data and
should be debugged whenever required.
CONCEPT OF ALGORITHM
• An Algorithm is a finite set of precise instructions for performing a computation or for
solving a problem.
• Algorithm is a sequence of activities to be processed for getting desired output (solution)
from a given input (problem).
• An algorithm can be thought of as the detailed instructions for carrying out some operation. A
computer program follows a sequence of exact instructions to accomplish this. This sequence
of instructions is called an Algorithm.
• Uses of Algorithm:
1. Using the algorithm's basic layout, the program can be developed in any desired language.
2. An algorithm is a representation in simple English language so it is very easy to understand. So problem
can be easily and simply solved.
3. Algorithm facilitates easy coding.
• Definition:
• We can define algorithm as "a set of instructions for solving a problem". OR
• A step-by-step procedure for solving a particular problem is an Algorithm. OR
• An algorithm can be defined as "a process that performs some sequence of operations in order to solve a
given problem". OR
• An algorithm is "a step-by-step solution to a problem".
Approaches for Designing an
Algorithm
[Link]-down Approach: A top-down design approach starts
by identifying the major components of the system or
program decomposing them into their lower level
components and iterating until the desired level of module
complexity is achieved. In this approach, we start with the
topmost module and incrementally add modules that it calls.
(For example: 'C' language).
[Link]-up Approach: A bottom-up design approach
starts with designing the most basic or primitive
components and proceeds to higher level components.
Starting from the very bottom, the operations that provide a
layer of abstraction is implemented.
Algorithmic Strategies
• Recursive Algorithm:
• A Recursive algorithm is an algorithm which calls itself with
smaller (or simpler) input values, and which obtains the result
for the current input by applying the same operations for the
smaller (or simpler) input.
• More generally if a problem can be solved utilizing solutions to
smaller versions of the same problem, and the smaller
versions reduce to easily solvable cases, then one can use a
recursive algorithm to solve the problem.
• Iterative Algorithm:
• In these algorithms, the process is carried out repetitively on
the inputs in order to achieve the desired output.
Characteristics
• Every algorithm must satisfy the following
characteristics:

• Input : An algorithm must have zero or more input.

• Output : Must produce at least one output.
• Definiteness : Each instruction must be clear and distinct.
• Finiteness : The algorithm must terminate after a finite
number of steps.
• Effectiveness : Each operation must be definite also it
should be feasible i.e. practically it should be possible.
Types of
Algorithms
• The various types of
algorithms are Brute force,
Divide and Conquer,
Greedy algorithm and
Backtracking.

This Photo by Unknown Author is licensed under CC BY-NC-ND

Brute force algorithm
• A brute force algorithm is a simple, comprehensive search strategy that
systematically explores every option until a problem's answer is discovered. It's
a generic approach to problem-solving that's employed when the issue is small
enough to make an in-depth investigation possible. However, because of their
high temporal complexity, brute force techniques are inefficient for large-scale
issues.
• These are algorithms that use obvious non-sophisticated approaches to solve
the problems in hand.
• Typically, they are useful for small domains, due to large overheads in
sophisticated approaches.
• Examples are:
• Bubble sort.
• Computing the sum of N numbers by direct addition
• Standard matrix multiplication.
• Linear (sequential) search.
Divide and Conquer algorithm
• Divide and Conquer is based on partitioning the
problem into two or more smaller subprograms, solving
them (using recursion or if they are simple enough,
directly) and combining the subproblem solutions into a
solution for the original problem.
• Example of Divide and Conquer algorithms includes:
• Merge Sort and Quick sort.
• The Fast Fourier Transform.
• Strassen's Matrix Multiplication.
Greedy algorithms
• Greedy algorithms always make the choice that seems
best at the moment. This locally optimal choice is made
with the hope that it leads to a globally optimal solution.
• Some greedy algorithms may not be guaranteed to
always produce an optimal solution. Greedy algorithms
are often applied to combinational optimization problems.
• Example of Greedy algorithms includes:
• Kruskal's and Prim's minimal spanning tree algorithms.
• Dijkstra's single source shortest path algorithm.
• Huffman Coding.
Backtracking algorithm
• A backtracking algorithm is a problem-solving method where you build a
solution step by step, and if you reach a point where the solution is not possible,
you go back (backtrack) and try a different path.
• It’s like exploring all possible choices, but instead of blindly checking everything
(like brute force), it prunes the wrong paths early to save time.
• Example:
• Depth First Search.
• 8 Queens Problem.
• Traveling salesperson problem.
• Analogy:
• Think of solving a maze:
• You start at the entrance and try one path.
• If you hit a dead end, you go back to the last decision point and try a different path.
• Repeat until you reach the exit.
• That’s backtracking!
Advantages
• An algorithm gives a language independent layout of
the program.
• It is step-by-step procedure of a solution to a given
problem, which is very easy and simple to understand.
• It uses a definite procedure.
• It is easy for programmer to convert it into an actual
program because the given problem is break down into
smaller steps.
• It is easy to debug as every step is got its own logical
sequence.
Disadvantages
• It is time consuming.
• It is difficult to show branching and looping if the
problem is big.