DATA STRUCTURE
AND ALGORITHMS
Dr. Muhammad Awais Sattar
Assistant Professor RSCI
1
ALGORITHM
“A Finite Sequence Of Instructions, Each Of Which
Has A Clear Meaning And Can Be Performed With
A Finite Amount Of Effort In A Finite Length Of
Time”
Given an algorithm to solve a particular problem, we are naturally led
to ask:
What is it supposed to do? (Specification)
Does it really do what it is supposed to do? (Verification)
How efficiently does it do it? (Performance Analysis)
ALGORITHMS- A DEEP DIVE
ALGORITHMS- A DEEP DIVE
• Algorithms are not answers but well-defined steps for getting to
answers.
• Algorithms use DATA STRUCTURES.
• Learning about algorithms and data structures will help you become
better problem-solvers!
• Understanding the problem
• Ascertaining the capabilities of a computational device
• Choosing between exact and approximate problem solving
• Deciding on appropriate data structures
• Algorithms + Data Structures = Programs
EXAMPLE 1: (LETS BAKE A CAKE)
Baking a Cake:
1. Start
2. Preheat the oven
3. Gather the ingredients
4. Measure out the ingredients
5. Mix the ingredients to make the batter
6. Grease a pan
7. Pour the batter into the pan
8. Put the pan in the oven
9. Set a timer
10. When the timer goes off, take the pan out of
the oven
EXAMPLE 2 : (FINDING THE
LARGEST NUMBER)
Step 1: Start
Step 2: Declare variables a,b and c.
Else
If b > c
Step 3: Read variables a,b and c.
Display b is
Step 4: If a > b
the largest number.
If a > c
Else
Display a is the largest
number.
Display c is
the greatest number.
Else
Step 5: Stop
Display c is the largest
number.
ALGORITHMS- EXAMPLES
• Algorithm examples:
• Finding the fastest route in a GPS navigation
system
• Navigating an airplane or a car (cruise control)
• Finding what users search for (search engine)
• Sorting, for example sorting movies by rating
DATA STRUCTURES
“Data Structures is about how data can be stored in
different structures”
We structure data in different ways depending on what
data we have, and what we want to do with it.
Let's consider an example without computers in mind,
just to get the idea.
DATA STRUCTURES (EXAMPLE)
If we need to organize
information about relatives, a
family tree is an ideal data
structure
We opt for a family tree because
it allows us to represent not only
individuals but also their
relationships, providing a clear
overview that makes it easy to
trace a particular family
member across multiple
DATA STRUCTURES (EXAMPLE)
With a family tree data structure
displayed visually, it becomes
simple to identify, for instance, that
my mother's mother is 'Emma,' as
the structure clearly shows the
connections between generations.
However, without the links from
child to parent that the family tree
provides, understanding the
relationships between individuals
would be much more challenging.
DATA STRUCTURES
Data structures enable us to efficiently handle vast
amounts of data, which is crucial for applications like
large databases and internet indexing services.
They are fundamental components in building fast and
powerful algorithms. By organizing and managing data
effectively, data structures reduce complexity and
enhance overall performance.
DATA STRUCTURES
In Computer Science, data structures are
categorized into two main types.
Primitive Data Structures: are the basic
structures offered by programming languages to
store single values, such as integers, floating-
point numbers, characters, and booleans.
Abstract Data Structures: on the other hand,
are more advanced structures built using
primitive types, designed to perform complex
and specialized tasks. Common examples of
abstract data structures include arrays, linked
lists, stacks, queues, trees, and graphs.
DATA STRUCTURES TOGETHER WITH
ALGORITHMS
Data structures and algorithms (DSA)
work closely together.
A data structure isn’t very useful if you
can’t search through it or change it
quickly with an algorithm, and an
algorithm needs a data structure to
work on.
DSA is about finding smart ways to
store and find data, perform tasks on
data, and solve problems.
DATA STRUCTURES TOGETHER
WITH ALGORITHMS
By learning DSA, you can:
• Pick the best data structure or algorithm for any situation.
• Write programs that run faster and use less memory.
• Solve tricky problems in a clear and organized way.
WHERE IS DATA STRUCTURES AND
ALGORITHMS NEEDED?
For handling large amounts of data, like in
social networks or search engines.
For scheduling tasks, helping a computer
decide which task to do first.
For planning routes, such as finding the
shortest path in a GPS system from A to B.
For optimizing processes, like organizing tasks
to finish them as quickly as possible.
For solving complex problems: from finding the
best way to load a truck to teaching a
computer to learn from data.
WHERE IS DATA STRUCTURES AND
ALGORITHMS NEEDED?
DSA is fundamental in nearly
every part of the software world:
• Operating Systems
• Database Systems
• Web Applications
• Machine Learning
• Video Games
• Cryptographic Systems
• Data Analysis
• Search Engines
THEORY AND TERMINOLOGY
These new terms and ideas will be introduced and explained
clearly when necessary, but here’s a list of some key terms to
give you a quick overview of what's ahead.
Algorithm: A set of step-by-step instructions to solve a
specific problem.
Data Structure: A way of organizing data so it can be used
efficiently. Common data structures include arrays, linked lists,
and binary trees.
Time Complexity: A measure of the amount of time an
algorithm takes to run, depending on the amount of data the
algorithm is working on.
THEORY AND TERMINOLOGY
Space Complexity: A measure of the amount of
memory an algorithm uses, depending on the amount of
data the algorithm is working on.
Big O Notation: A mathematical notation that
describes the limiting behavior of a function when the
argument tends towards a particular value or infinity.
Used in this tutorial to describe the time complexity of
an algorithm.
Recursion: A programming technique where a function
calls itself.
THEORY AND TERMINOLOGY
Divide and Conquer: A method of solving complex
problems by breaking them into smaller, more
manageable sub-problems, solving the sub-problems,
and combining the solutions. Recursion is often used
when using this method in an algorithm.
Brute Force: A simple and straight forward way an
algorithm can work by simply trying all possible solutions
and then choosing the best one.
A SIMPLE ALGORITHM: FIBONACCI
NUMBERS
Fibonacci Numbers
The two first Fibonacci numbers are 0
and 1, and the next Fibonacci number
is always the sum of the two previous
numbers, so we get 0, 1, 1, 2, 3, 5, 8,
13, 21
To generate a Fibonacci number, all we
need to do is to add the two previous
Fibonacci numbers.
The algorithm to create the 20 first
Fibonacci numbers
A SIMPLE ALGORITHM: FIBONACCI
NUMBERS
How it works:
Start with the two first Fibonacci
numbers 0 and 1.
• Add the two previous numbers together to
create a new Fibonacci number.
• Update the value of the two previous
numbers.
Do point a and b above 18 times.
A SIMPLE ALGORITHM: FIBONACCI
NUMBERS
Implementation Using a For Loop:
It can be a good idea to list what the code must contain
or do before programming it:
• Two variables to hold the previous two Fibonacci numbers
• A for loop that runs 18 times
• Create new Fibonacci numbers by adding the two previous ones
• Print the new Fibonacci number
• Update the variables that hold the previous two fibonacci
numbers
A SIMPLE ALGORITHM: FIBONACCI
NUMBERS
prev2 = 0
prev1 = 1
print(prev2)
print(prev1)
for fibo in range(18):
newFibo = prev1 + prev2
print(newFibo)
prev2 = prev1
prev1 = newFibo
A SIMPLE ALGORITHM: FIBONACCI
NUMBERS
Recursion is when a function calls itself.
To implement the Fibonacci algorithm we need most of
the same things as in the code example above, but we
need to replace the for loop with recursion.
To replace the for loop with recursion, we need to
encapsulate much of the code in a function.
We need the function to call itself to create a new
Fibonacci number as long as the produced number of
Fibonacci numbers is below, or equal to, 19.
A SIMPLE ALGORITHM: FIBONACCI
NUMBERS
print(0) prev1 = newFibo
print(1) count += 1
count = 2 fibonacci(prev1,
def fibonacci(prev1, prev2)
prev2): else:
global count return
if count <= 19: fibonacci(1,0)
newFibo = prev1 +
prev2
A SIMPLE ALGORITHM: FIBONACCI
NUMBERS
Finding The nth Fibonacci Number Using Recursion
To find the nth Fibonacci number we can write code based
on the mathematic formula for Fibonacci number n:
This just means that for example the 10th Fibonacci
number is the sum of the 9th and 8th Fibonacci numbers.
When using this concept with recursion, we can let the
function call itself as long as n is less than, or equal to, 1.
If n≤1 it means that the code execution has reached one
of the first two Fibonacci numbers 1 or 0.
A SIMPLE ALGORITHM: FIBONACCI
NUMBERS
This formula uses a 0-based index. This means that to
generate the 20th Fibonacci number, we must write F(19).
def F(n):
if n <= 1:
return n
else:
return F(n - 1) + F(n - 2)
print(F(19))
A SIMPLE ALGORITHM: FIBONACCI
NUMBERS
Notice that this recursive method calls itself two times,
not just one.
This makes a huge difference in how the program will
actually run on our computer.
The number of calculations will explode when we
increase the number of the Fibonacci number we want.
To be more precise, the number of function calls will
double every time we increase the Fibonacci number we
want by one.
CONCLUSION
An algorithm can be implemented in different ways and
in different programming languages.
Recursion and loops are two different programming
techniques that can be used to implement algorithms.
