Subject Name Logical Thinking & Problem Solving
Subject Code 25CSH-107
Semester 1
LESSON OBJECTIVES
• To understand the importance of algorithms in programming
• To learn how to write algorithms
• To differentiate different algorithms for same task
STRUCTURE OF THE LESSON
• Introduction to Algorithms
• How to design an algorithm
• Analysing the performance of algorithm
• Summary
• FAQs
• References
Introduction to Algorithms
How to make a computer do what you want, elegantly and efficiently
Figure 1 Computer
An algorithm is a step-by-step process to achieve some outcome. When algorithms involve a
large amount of input data, complex manipulation, or both, we need to construct clever
algorithms that a computer can work through quickly.
Before starting with this tutorial, kindly watch this video by BBC about the working of
algorithms in real practice.
The best algorithms also run fast, are sparing in their use of memory and other computer
resources, and are easy to understand and modify. As a result, the study of algorithms is very
closely tied to computers, computer science, and programming.
Algorithms are important to computer science, but they aren't exclusively part of computer
science. You’d need to think about algorithms if you went out of town and needed to get a
pet sitter for your beloved hamsters.
Figure 2 Hamster example
Imagine your pet sitter is very good at following directions, but they’re not very good at using
their own judgment, so you need to give very detailed feeding instructions.
1. Check the hamster’s food bowl.
2. If the food bowl is empty, put five pellets in the bowl.
3. Otherwise, if the food bowl does have some leftover food pellets in it,
put three pellets in the bowl.
There are four pellets in the bowl after your sitter runs this algorithm and before the hamsters
have a chance to nibble on anything. What can you conclude?
Answer: When the pet sitter is done, the number of pellets in the bowl can be expressed as
the sum of two numbers:
• The number of pellets in the bowl when the pet sitter arrived and
• The number of pellets added due to the instructions.
You can use the letter n
n to represent the number of pellets in the bowl when the pet sitter arrives. If n
n is zero, there will be exactly 5 pellets in the bowl after food is added. Otherwise, if n
n is positive, there will be 3 + n
3+n pellets.
The only way for there to be exactly four pellets in the bowl is if n = 1
n=1. This means the hamsters left 1 pellet in the bowl from the night before, so 3 more were
added.
Algorithms in computer science are almost never just sequences of commands. Algorithms
can also include conditional instructions. For example:
Figure 3 Hamster Algorithm
The line starting with if describes the conditional instruction's test: hamster is hiding.
The algorithm above uses a conditional instruction, a pattern you'll see constantly in
computer science, algorithms, and programming:
• describe a test;
• list some instructions to run if the test succeeds;
• list other instructions to run if the test fails.
If you want to make your pseudocode look more like written English, you could
write otherwise: instead of else:. Nearly every programming language uses the
words if and else for describing the pattern of describing a test, commands for if the test
succeeds, and alternative commands for if the test fails.
How to Design an Algorithm?
In order to write an algorithm, following things are needed as a pre-requisite:
1. The problem that is to be solved by this algorithm.
2. The constraints of the problem that must be considered while solving the problem.
3. The input to be taken to solve the problem.
4. The output to be expected when the problem is solved.
5. The solution to this problem, in the given constraints.
For example, let’s write an algorithm to add 3 numbers and print their sum:
1. START
2. Declare 3 integer variables num1, num2 and num3.
3. Take the three numbers, to be added, as inputs in variables num1, num2, and num3
respectively.
4. Declare an integer variable sum to store the resultant sum of the 3 numbers.
5. Add the 3 numbers and store the result in the variable sum.
6. Print the value of variable sum
7. END
Analyzing the performance of an algorithm
We design an algorithm to get a solution of a given problem. A problem can be solved in more
than one ways.
Figure 4 Analysing performance of algorithm
Hence, many solution algorithms can be derived for a given problem. The next step is to
analyze those proposed solution algorithms and implement the best suitable solution.
Generally, the performance of an algorithm depends on the following elements...
1. Whether that algorithm is providing the exact solution for the problem?
2. Whether it is easy to understand?
3. Whether it is easy to implement?
4. How much space (memory) it requires to solve the problem?
5. How much time it takes to solve the problem? Etc.,
When we want to analyze an algorithm, we consider only the space and time required by that
particular algorithm and we ignore all the remaining elements. Performance analysis of an
algorithm is performed by using the following measures...
1. Space required to complete the task of that algorithm (Space Complexity). It includes
program space and data space
2. Time required to complete the task of that algorithm (Time Complexity)
SUMMARY
• An algorithm is a step-by-step process to achieve some outcome. When algorithms
involve a large amount of input data, complex manipulation, or both, we need to
construct clever algorithms that a computer can work through quickly.
• The best algorithms also run fast, are sparing in their use of memory and other
computer resources, and are easy to understand and modify.
• Algorithms in computer science are almost never just sequences of commands.
Algorithms can also include conditional or looping instructions.
• When we want to analyse an algorithm, we consider only the space and time required
by that particular algorithm and we ignore all the remaining elements.
FREQUENTLY ASKED QUESTIONS
Q1 Where are algorithms used in real life?
Answer: In real life these algorithms are used in mp3 players, video players, making
dictionaries and there are much examples for searching and sorting.
Searching Algorithms is used in Quantum computing also. In Operating system scheduling of
tasks is done through various algorithms such as FIFO, Round robin, etc. Google when
showing search results uses page ranking techniques. Facebook when showing news feed
uses a similar ranking algorithm to make it more relevant to you. All these use a modification
of Link Analysis, an interesting branch in Data Mining.
So, whenever you press a key on your keyboard, make a call, perform a calculation, start an
application or press a remote button, always an algorithms is triggered. So, there are
countless examples of many algorithms in our daily life and making our life easier.
Q2 What are the various types of algorithms?
Answer: There are numerous types of algorithms designed to a particular purpose.
• Recursive algorithms.
• Dynamic programming algorithm.
• Backtracking algorithm.
• Divide and conquer algorithm.
• Greedy algorithm.
• Brute Force algorithm.
• Randomized algorithm.
• Facial recognition algorithms
• Shortest Path Finding Algorithm
Q3 Write an algorithm and draw a flowchart to find maximum of three numbers.
Answer:
Algorithm:
Step 1 : Start
Start 2 : Input a, b, c
Start 3 : if a > b goto step 4, otherwise goto step 5
Start 4 : if a > c goto step 6, otherwise goto step 8
Start 5 : if b > c goto step 7, otherwise goto step 8
Start 6 : Output "a is the largest", goto step 9
Start 7 : Output "b is the largest", goto step 9
Start 8 : Output " c is the largest", goto step 9
Start 9 : Stop
Flowchart:
Figure 5 Flowchart- Maximum of three numbers
REFERENCES:
Books:
• Introduction to Algorithms by Ronald L. Rivest
• The Art of Computer Programming by computer scientist Donald Knuth.
Websites:
• https://en.wikipedia.org/wiki/Algorithm
• https://fiftyexamples.readthedocs.io/en/latest/algorithms.html
• https://study.com/academy/lesson/what-is-an-algorithm-definition-examples.html
YouTube Links:
• What is an algorithm and why should you care? https://youtu.be/CvSOaYi89B4
• What is an algorithm? https://youtu.be/6hfOvs8pY1k
• Characteristics of algorithm. https://youtu.be/FbYzBWdhMb0
