CS 250

Data Structures & Algorithms

(Week 2, Lecture 3)
Dr. Muhammad Kamran Khan
Assistant Professor

Department of Electrical Engineering

Military College of Signals
National University of Sciences and Technology (NUST)

1
Last Lecture Summary
 What is Data?
 Computer Program
 What are Data Structures?
 Basic Data Structures
 Selection of Data Structures
 Data Structure Operations
 Abstract Data Type (ADT)
 Types of Data Structures

2
Today’s Lecture
 What is Problem Solving?
 Introduction to Algorithms
 What is an Algorithm?
 Computer Algorithm and Program
 Favorite vs. Efficient Algorithm
 Measuring Efficiency
 Running Time of an Algorithm
 Analyzing an Algorithm with Simple Example
 Algorithm History and Applications

3
Computer Program
• To exactly know, what is data structure? We must know:
- What is a computer program?
Computer Program Solution
Problem

Input Process Output

(DS) (Algorithm) (DS)

Data Structures + Algorithms = Programs

4
 Data Structures & Algorithms
 Data Structures is about how data can be stored in
different structures
 Algorithms is about how to solve different
problems, often by searching and manipulating
data structures

5
Data Structures & Algorithms

6
What is Problem Solving?
 Some examples of problems:
- A farmer trying to get his fields cropped before the storm
comes.
- A student trying to improve his gpa to improve his grades.
- A man trying to push his car in the middle or road with no
petrol.
- Parents trying to make budget with increase in tuition fees
- A covid patient trying to wait for this test/medications.
- ……etc.,

7
What is Problem Solving?
 A dictionary defines a problem as a question raised
for inquiry, consideration, or solution.
 In mathematics, a problem is usually a situation to resolve
with well-defined mathematical principles.
 Solving is defined as finding a solution for something such
as a problem.
 Problem Solving is “the act of finding a solution to a
perplexing, distressing, vexing and unsettled question”.
 We will focus on problem solving using computers also
called computational problem solving

8
Problem Solving using computers?
 A computer can do nothing without being explicitly told
what to do. Computers are dummy devices…
 It cannot specify or analyze the problem and come up with
a solution.
 Steps for problem solving with computers include:
1. The entity (the client) with the problem must specify
(outline) the problem to be solved.
2. A human(the programmer) must analyze the problem
develop the instructions (the program) for solving the
problem and have the computer carry out the instructions.

9
Introduction to Algorithms
 Algorithms are fundamental

Operating Systems Machine learning Cryptography

scheduling algorithms & fast geometric algorithms fast number theoretic &
efficient data structures & similarity search algebraic algorithms

Compilers Networking Computational Biology

scheduling algorithms & uses shortest- algorithms that operate on strings -
efficient data structures path algorithms often employs the DP paradigm

10
What is an Algorithm?
 Algorithm in simple words is a set of step-by-step
instructions to complete a task. For example
Task: To make a cup of tea.
 Algorithm:

Step 1: Add water and milk to the kettle,

Step 2: Boil it till it bubbles,
Step 3: Add tea leaves (as required),
Step 4: Add sugar,
Step 5: Serve it in cup.

11
Several definitions of algorithm
 An algorithm is a definite procedure for solving a problem in
finite number of steps

 Algorithm is a well defined computational procedure that takes

some value(s) as input, and produces some value(s) as output

 Algorithm is finite number of computational statements that

transform input into the output

 Algorithm Definition : A finite set of statements that

guarantees an optimal solution in finite interval of time

12
What is a Computer algorithm?
 A computer algorithm is an orderly step-by-step procedure
(instructions) to the computer to solve a specific problem.
 The main features of computer algorithm are:

1. It accepts one / more inputs.

2. It returns at least one output.

3. Each instruction must be simple, clear and unambiguous.

4. It must terminates after finite steps.

5. It is language independent.

13
Algorithm Specification
 Algorithms are often specified either in Natural Language or
Pseudo Code Specification
1. Natural Language Specification (NLS)
 In this form of specification, English language words, phrases and
terminology are used to describe the algorithm important steps.
 NLS highlight the algorithm design features.

Example; Algorithm for inorder traversal of a binary tree

 Step #1: Visit Left Node
 Step #2: Visit Root Node
 Step #3: Visit Right Node
 In NLS there are no formalities in phrases and words.
 Freedom in choice of words and style variation.

14
Algorithm Specification – Cont…
2. Pseudo Code Specification (PCS)
• In this form of specification symbol and phrases of some high level
programming (a combination of English words and mathematical
symbols) are used to describe the working of an algorithm.
• It is more useful for analysis purpose.
• There is no standardized notation used for the pseudo code.
− However, the following notation is normally followed.
 Procedures: Name followed by input parameters enclosed in
parentheses. For example, FINDMAX (A, n).
 Assignments to variables: left arrows (←) e.g., j← k ← p
 Variables comparison: symbols x ≤ y, x ≥ y, x ≠ y, x = y, x > y, x < y
 Logical expressions: connectives exp1 AND exp2 , exp1 OR exp2,
NOT exp.
 Computations: arithmetic symbols +, -, *, /

15
Algorithm Specification – Cont…
 Exchanges (Swapping): symbol ↔ e.g., A[i] ↔ A[k]
 Loops and iterations: Words for, do, repeat, while, until are used to
describe loops, such as: for ----, do ----, while ----, do ---- while, do ----
- until etc.
 Conditionals: Words if and then are used to specify conditional
statements, such as: if ---- then-----else----
 Block structure: Using indentation i.e., a block with in another block.
For example a block is illustrated as below.
for --- (start of outer most block)
for --- (start of next / inner block)
if --- else ---- ( start of a new block)
 Array: Name followed by size in brackets, e.g., A[1..n]

16
Algorithm Specification – Cont…
 Pseudo Code for displaying even and odd numbers

for i ← 1 to n
if i%2 = 0
print “even number”
else
print “odd number”

17
Computer Program – Steps
 Steps involved in writing a computer program:

1. Problem formulation & specification

2. Design of solution

3. Implementation

4. Testing

5. Documentation

6. Evaluation of the solution

18
Favorite Algorithm
 Favorite algorithm

- Takes less memory (Space Efficient).

- Smaller execution time.

- Smaller programming time.

- Time complexity (most important).

19
Efficient Algorithm
 Consumes lesser amount of resources while solving a
problem of size n
 Memory

 Time

20
Measuring Efficiency
 The efficiency of an algorithm is a measure of the amount of
resources (time and memory) consumed in solving a problem of size
n.

 It would seem that the most obvious way to measure the efficiency

of an algorithm is to run it and measure how much processor time is

needed.

21
Running Time of an Algorithm
 Factors affecting running time:
- Nature of input
- Number of input
- Number of steps / primitive operations

 Running time is measured in terms of number of steps/ primitive (+,

*,<, =, A[i]) operations.
 Generally, time grows with size of input,
 so running time of an algorithm is usually measured as function of input size.

 Independent from machine, OS

22
Analyzing an Algorithm
Calculating Running time of an Algorithm
 Running time is measured by number of steps / primitive operations

performed

 Steps means elementary operation

- For example: +, *,<, =, A[i] etc

 Measure the number of steps taken in term of size of input

23
Simple Example
// Input: int A[N], array of N integers
// Output: Sum of all numbers in array A

int Sum(int A[], int N) {

int s=0;
for (int i=0; i< N; i++)
s = s + A[i];
return s;
}

How should we analyse this?

24
Simple Example – Cont…

1,2,8: Once
3: N+1 iteration
4,5,6,7: Once per each iteration
of FOR loop, i.e., N iteration
Total: 1+1+1+(N+1)+N+N+N+N = 5N + 4
The complexity function of the
algorithm is : f(N) = 5N +4

25
Growth of 5N+4
 Estimated running time for different values of N:
 N = 10 => 54 steps
 N = 100 => 504 steps
 N = 1,000 => 5004 steps
 N = 1,000,000 => 5,000,004 steps

 As N grows, the number of steps grow in linear proportion to N for

this function “Sum”.

26
Algorithm History
 The word algorithm is derived from the title “Khwarizmi”

 The name of a Muslim mathematician Abu Abdullah Muhammad

Ibn Musa Al-Khwarizmi.

 A Persian mathematician, astronomer, geographer and a scholar

of the 9th century in Baghdad.

 Considered as one of the fathers of algebra.

27
Algorithm Applications
 To solve variety of problems in the field of

 computer science, mathematics including

 other disciplines like medical, health, education, business etc.

depend on the use of algorithms.

 The main categories of applications types are:

 Searching Algorithms

 Sorting Algorithms

 Strings Processing

28
Algorithm Applications
 Optimization Algorithms (Shortest routes, minimum cost).

 Image Processing

 Data Mining and Big data Algorithms (Clustering, Classification,

Rules mining)

 Mathematical Algorithms (Random number generator, matrix

operations, etc.)

 Algorithm for Hard or Intractable Problems

29
Summary
 Introduction to Algorithms
 What is an Algorithm?
 Computer Algorithm and Program
 Favorite and Efficient Algorithm
 Measuring Efficiency
 Running Time of an Algorithm
 Analyzing an Algorithm with Simple Example
 Algorithm History
 Algorithm Applications

30
THANK YOU

31