Design and Analysis of Algorithms

Lecture 1: Introduction
BS Course Semester-4

Dr. Muhammad Ilyas Fakhir

Computer Science Department

GC University Lahore

February 13, 2023

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 1 / 45
 Outlines

1 Introduction
Course Outlines and Objectives
A Gist from History
Algorithms in Real World
Why Algorithms?
Properties of Algorithms
Pseudo Code
Analysis of Algorithms

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 2 / 45
 Course Outlines

C OURSE O UTLINES
The Role of algorithms in computing. Model of Computation, Designing
Techniques and Growth of functions, Asymptotic Notations. Analysis of
Algorithms. Recurrences; The Recursion-Tree method for solving
Recurrences, The Master Method for Solving Recurrences and The
Substitution Method for Solving Recurrences. Heaps, Maintaining Heap
Property, Building Heap, The Heap-Sort Algorithms and Priority Queues.
Insertion Sort, Merge Sort, Quick-Sort, Description of Quick-Sort,
Performance of Quick-Sort, A randomized Version of Quick-Sort, Analysis of
Quick-Sort and Linear-Time Sorts, Counting Sort, Radix Sort and Bucket Sort.
Data Structures, Binary Search Trees, Red Black Trees, Balancing of RB Trees
and Rotations. Dynamic Programming and Greedy Algorithms. Graphs,
Techniques to Traverse the Graphs (DFS, BFS), Topological Sort, Connected
Components, Minimum Spanning Tree.

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 3 / 45
 Objectives of the course

O BJECTIVES OF THE COURSE

The objective of the course is to develop following skills in the students of
computer science:
getting to the mathematical core of problems
improving mathematical and algorithmic writing
enhancing programming skills
performing a literature review for a problem
identifying appropriate algorithms and data structures
analysis of algorithms for time and space complexity,
understanding of algorithm design methodologies
identification of difficult questions and finding strategies to cope with
them

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 4 / 45
 Reference Books

R EFERENCE B OOKS
Introduction to Algorithms, T. H. Cormen, C. E. Leiserson, and R. L.
Rivest, MIT Press, McGraw-Hill, 3rd Edition, New York, NY, 2010.
Algorithms, Robert Sedgewick and Kevin Wayne, 4th Edition, 2011,
Algorithms; S. Dasgupta, C. Papadimitriou, and U. Vazirani;
McGraw-Hill Higher Education, 2006
The Art Of Computer Programming (3 volumes) Knuth, Donald
Ervin, Addison-Wesley, 1977.

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 5 / 45
 The Name Algorithm

The Name Algorithm

The etymology of the word Algorithm dates back to the 8th Century AD. The
word Algorithm is derived from the name of the
Persian author “Abu Jafar Mohammad ibn Musa al Khowarizmi”

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 9 / 45
Figure: Muhammad al-Khowarizmi, from a 1983 USSR commemorative stamp
scanned by Donald Knuth Reference: ACM Trans - Algorithms
 Abu Jafar Mohammad ibn Musa al Khowarizmi

Abu Jafar Mohammad ibn Musa al Khowarizmi

Abu Jafar Mohammad ibn Musa al Khowarizmi - was a great mathematician
who was born around 780 AD in Baghdad. He worked on, algebra, geometry,
and astronomy. His treatise on algebra, Hisab al-jabr w’al-muqabala, was the
most famous and important of all of alKhwarizmi’s works. It is the title of this
text that gives us the word "algebra"

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 11 / 45
 Algorithmic Problems in the Real World

Figure: Shortest Paths

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 12 / 45
 Shortest Paths - Paris to Berlin

Figure: Shortest Paths - Paris to Berlin

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 13 / 45
 Digital Information: Compression and Coding

Digital Information: Compression and Coding

Compression: reduce size for storage and transmission
Coding: add redundancy to protect against errors in storage and
transmission
Efficient algorithms for compression/coding and decompressing/decoding
part of most modern gadgets (computers, phones, music/video players ...)

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 14 / 45
 Search and Indexing: String Matching and Link Analysis

Search and Indexing: String Matching and Link Analysis

Web search: Google, Yahoo!, Microsoft, Ask, ...
Text search: Text editors (Emacs, Word, Browsers, ...)
Regular expression search: grep, egrep, emacs, Perl, Awk, compilers

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 15 / 45
 Public-Key Cryptography

Public-Key Cryptography
Foundation of Electronic Commerce
RSA Crypto-system: generate key n = pq where p; q are primes
Primality: Given a number N, check if N is a prime or composite.
Factoring: Given a composite number N, find a non-trivial factor

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 16 / 45
 Optimization

Optimization
Find the cheapest of most profitable way to do things
Airline schedules - AA, Delta, ...
Vehicle routing - trucking and transportation (UPS, FedEx, Union
Pacific, ...)
Network Design - AT&T, Sprint, Level3 ...
Linear and Integer programming problems

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 17 / 45
 Main Questions for Algorithms’ Study

Questions
What are algorithms?
Why is the study of algorithms worthwhile?
What is the role of algorithms relative to other technologies used in
computers?

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 18 / 45
 Informally: An Algorithm

Informally: An Algorithm
Informally, an algorithm is any well-defined computational procedure
that takes
1 INPUT: some value, or set of values, as and
2 OUTPUT: some value, or set of values
An algorithm as a tool for solving well-specified computational
problem.
Input sequence is called an INSTANCE of the sorting problem.

Example
Sorting Problem
INPUT: A sequence of n numbers ha1 , a2 , ..., an i
OUTPUT: A permutation ha´1 , a´2 , a´3 , ..., a´n i such that a´1 ≤ a´2 ≤ a´3 ... ≤ a´n

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 19 / 45
 Why Algorithms?

Why Algorithms?
Why study algorithms and performance?
Algorithms helps us to understand scalability.
Performance often draws the line between what is feasible and what is
impossible.
Algorithmic mathematics provides a language for talking about program
behavior
Performance is the currency of computing.
The lessons of program performance generalize to other computing
resources.

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 20 / 45
 A Correct Algorithm

A Correct Algorithm
An algorithm is said to be CORRECT, if for every input instance, it
halts with the correct output.
Correct algorithm solves the given computational problem.
Incorrect? Contrary to what one might expect.
An algorithm can be specified in English language, as a computer
Language or a hardware design.
Requirement? specification must provide a precise description of the
computational procedure to be followed.

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 21 / 45
 What kind of problems are solved by algorithms? I

Human Genome Project

In Human Genome Project: to identify 100,000 genes in human DNA,
determining the sequences of the 3 billion chemical base pairs that make
up human DNA.
Storing these information in database and developing tools for data
analysis.
Each of these steps requires sophisticated algorithms.

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 22 / 45
 What kind of problems are solved by algorithms? II

Internet Accessibility & E-Commerce

Internet: clever algorithms are employed to manage and manipulate
large volume of data.
Finding good routes
Search engine to quickly find desired pages.
Electronic Commerce: goods and services to be negotiated and
exchange electronically.
to keep information such as credit card numbers, passwords, and bank
statements.
Public-key cryptography and digital signatures are among the core
technologies based on numerical computation and number theory.

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 23 / 45
 contd..

Manufacturing and other commercial enterprises

In manufacturing and commercial settings: Linear programming.
to find shortest route between adjacent interactions in the market.
Matrices operations.
Points to figure .

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 24 / 45
 Data structures

Definition (Data structures)

A data structure is a way to store and organize data in order to facilitate
access and modifications. No single data structure works well for all purposes,
and so it is important to know the strengths and limitations of several of them.

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 25 / 45
 Properties of Algorithms

Properties of Algorithms
Finite set of instructions to accomplish a task. The algorithm should be
correct
The properties of an algorithm are as follows:

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 26 / 45
 Properties of Algorithms

Definition
An Algorithm is defined as “Finite set of instructions to accomplish a task”.

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 27 / 45
 Properties of Algorithms

five properties
An Algorithm has five properties as follows:
1 Finiteness: An algorithm should end in a finite number of steps.
2 Definiteness: Every step of an algorithm should be clear and
unambiguously defined.
3 Input: The input of an algorithm can either be given interactively by the
user or generated internally.
4 Output: An algorithm should have at least one output.
5 Effectiveness: Every step in the algorithm should be easy to understand
and prove using paper and pencil.

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 28 / 45
 Pseudo Code

Pseudo Code
An algorithm is independent of any language or machine whereas a
program is dependent on a language and machine
To fill the gap between these two, we need pseudo codes

Definition
Psuedo-codeis a way to represent the step by step methods in finding the
solution to the given problem.

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 29 / 45
 Pseudo Code

Figure: Pseudo Code for making Tea

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 30 / 45
 Pseudo Code

Pseudo Code
Pseudocode (“fake” code) is similar to some programming languages
that you’re familiar with, but does not have any particular syntax rules.
Instead, it is a higher-level description of a process.
You may use familiar control structures such as loops and conditionals,
but you can also utilize natural language descriptions of operations.

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 31 / 45
 Pseudo Code

Pseudo Code
There are no established rules for pseudocode, but in general, good
pseudocode:
Clearly labels the algorithm
Identifies the input and output at the top of the algorithm
Does not involve any language or framework-specific syntax-no
semicolons, declaration of variables or their types, etc.
Makes liberal use of mathematical notation and natural language for
clarity

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 32 / 45
 Pseudo Code

Pseudo Code
Algorithms are developed during the design phase of software
engineering.
During the design phase, we first look at the problem, try to write the
“psuedo-code” and move towards the programming (implementation)
phase.
It is a high level description of the algorithm
It is less detailed than the program
Will not reveal the design issues of the program
Uses English like language

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 33 / 45
 Algorithm 1 Text Summarization Algorithm
1: procedure S UMMARY C ONSTRUCTION
Input: Text Document.
Output: Summary sentences.
2: Creating information table from a text document.
3: Generate matrices.
4: Call Pocedure: Reduct Construction [Algorithm 2]
5: Return: Summary sentences

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 34 / 45
 Another Pseudo Code

z←1
for i = 1 → n do for loop
z ← z + 1i

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 35 / 45
 Pseudo Code

Figure: Computing the Mean

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 36 / 45
 Algorithm 2 My algorithm
1: procedure M Y P ROCEDURE
2: stringlen ← length of string
3: i ← patlen
4: top:
5: if i > stringlen then return false
6: j ← patlen
7: loop:
8: if string(i) = path(j) then
9: j ← j − 1.
10: i ← i − 1.
11: goto loop.
12: close;
13: i ← i + max(delta1 (string(i)), delta2 (j)).
14: goto top.

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 37 / 45
 Observe

Observe
1 The input does not have a specific type (such as int or double), it uses set
notation which also indicates how large the collection is.
2 There is no language-specific syntax such as semicolons, variable
declarations, etc.
3 The loop construct doesn’t specify the details of incrementing a variable,
instead using a “foreach” statement with some set notation
4 Code blocks are not denoted by curly brackets, but are clearly delineated
by using indentation and vertical lines
5 Assignment and compound assignment operators do not use the usual
syntax from C-style languages, instead using a left-oriented arrow to
indicate a value is assigned

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 38 / 45
 Life Cycle of an Algorithm

Life Cycle of an Algorithm

Design the Algorithm
Write (Implementation of the Algorithm)
Test the Algorithm
Analyze the Algorithm

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 39 / 45
 life cycle of an algorithm

life cycle of an algorithm

The life cycle of an algorithm consists of the four phases: Design, Write, Test
and Analyze.
1 Design: The design techniques help in devising the algorithms. Some
techniques are Divide & Conquer, Greedy Technique, Dynamic
Programming etc.
2 Write (implementation):Implementing the algorithm in pseudo code
which will be later represented in an appropriate programming language.
3 Test:Testing the algorithm for its correctness.
4 Analyze:Estimating the amount of time/space (which are considered to
be prime resources) required while executing the algorithm

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 40 / 45
 Analysis of Algorithms

Analysis of Algorithms
An algorithm when implemented, uses the computer’s primary memory
and Central Processing Unit
Analyzing the amount of resources needed for a particular solution of the
problem
The Analysis is done at two stages:
1 Priori Analysis: Analysis done before implementation
2 Posteriori Analysis: Analysis done after implementation

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 41 / 45
 Priori Analysis:

Priori Analysis:
This is the theoretical estimation of resources required. Here the efficiency of
the algorithm is checked. If possible the logic of the algorithm can be
improved for efficiency. This is done before the implementation of the
algorithm on a machine and so it is done independent of any
machine/software.

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 42 / 45
 Posteriori Analysis:

Posteriori Analysis:
This Analysis is done after implementing the algorithm on a target machine.
It is aimed at determination of actual statistics about algorithm’s consumption
of time and space requirements (primary memory) in the computer when it is
being executed as a program.

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 43 / 45
 Example

Example
Algorithm to check whether a number is prime or not.
1 Algo1: Divide the number n from 2 to (n-1) and check the reminder
2 Algo2: Divide the number n from 2 to n/2 and check the reminder
3 Algo3: Divide the number n from 2 to sqrt(n) and check the reminder
Before implementing the algorithm (Priori Analysis) in a programming
language, the best of the three algorithms will be selected(Algo3 will suit if n
is large).
After implementing the algorithm (Posteriori Analysis) in a programming
language, the performance is checked with the help of a profiler.

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 44 / 45
 References I

Introduction to Algorithms, T. H. Cormen, C. E. Leiserson, and R. L. Rivest, MIT Press, McGraw-Hill, 3rd Edition, New York, NY,
2010.
Slides from Infosys Technologies Ltd 2004
Analysis of Algorithms: An Active Learning Approach; Jeffrey J. McConnell Jones and Bartlett Publishers International Barb House,
Barb Mews London, UK 2001

Dr. Muhammad Ilyas Fakhir (CS Department) Design and Analysis of Algorithms February 13, 2023 45 / 45