Fundamentals of Algorithms

spring-2025
Lecture-01
Introduction

Department of CS&IT
• Course Title : Fundamentals of Algorithms
• Credit Hours : 03
• Program : BSCS
• Instructor : Mariya bibi
• Email : mariya.bibi@cs.uol.edu.pk
• Contact no : 000-0000000
• Office : 218 2st Flour
• Office Hour: on appointment

• TA :
 Objectives
•We will study fundamental algorithms for solving a
variety of problems, including sorting, searching and
graph algorithms. More importantly, we will focus on
general design techniques that underlie these
algorithms.
 Grading
(Tentative)
• Midterm(s) 30%
• Quizes 10%
• Assignments 10%
• Final Exam 50%

• If you miss 6 or more classes you will get NA

grade!

*Pop Quiz: an unscheduled or unannounced quiz.

 Grading Policies
• Missed exams:
o you will get zero for each missed quiz!
o no make-up exam for Midterm/final for any excuse!

• Lateness:
o Late assignments are penalized up to 25% per day.

• Ethics:
o All assignments/projects are to be your own work.

• Participation:
o You are supposed to be active in the class by involving and
participating disscusions via asking questions, proposing solutions,
explaning your ideas, etc.
Introduction
What is Algorithm?
►Is a complete list of the steps (finite sequence of instructions)
necessary to perform a task/computation or for solving a problem.

►The steps maybe a general descriptions (not very detail) or may be

totally precise description (very detail).

►Often used in Mathematics, computing, linguistics, and related

subjects for calculation and data processing.

►The term is a corruption of the name al-Khowarizmi (9th century

mathematician) – Algorism.

►Algorism was used for the rules for performing arithmetic using
decimal notation.

►Algorism evolved into the word algorithm by 18th century.

 What is Algorithm?
• Sequence of steps that can be taken to solve a
problem
• An algorithm is a sequence of unambiguous instructions for
solving a problem in a finite amount of time.
• An Algorithm is well defined computational procedure that
takes some value, or set of values, as input and produces some
value, or set of values as output.
• More generally, an Algorithm is any well defined computational
procedure that takes collection of elements as input and
produces a collection of elements as output.

Input output
Algorithm
 Cont……

Algorithms are the ideas behind computer programs.

•An algorithm is the thing which stays the same whether the program is in
C++ running on a PC in New York or is in Android running on a
Smartphone in Lahore
 Example: What is an Algorithm?
I.I What is an Algorithm?

Problem: Input is a sequence of integers stored in an array.

Output the minimum.
INPUT Algorithm

OUTPUT
instance
m:= a[1];
25, 90, 53, 23, 11, 34 for I:=2 to size of input 11
if m > a[I] then
m:=a[I];
return s

m
Data-Structure
Example of Simple Algorithm

We often used algorithm in our life , but when and

how?

→ Your cooking recipe

→ Your daily routine as a student
→ When you buy something
→ When you go outing
→ My class routine
Describe an algorithm by Natural Languages

EXAMPLE 1: A recipe for baking a cake

A) general - without subroutines

1. MIX MARGERINE AND SUGAR

2. ADD EGG TO THE MIXTURE
3. BEAT THE MIXTURE
4. ADD THE FLOUR TO THE MIXTURE
5. POUR MIXTURE INTO PAN
6. BAKE IN OVEN FOR 40 MINUTES AT
350°F
 Properties of Algorithms

It must be correct.
It must be composed of a series of concrete steps.
The execution sequence of instructions should
not be ambiguous.
It must have finite number of instructions and
steps.
It must terminate.

13
 Syntax & Semantics
An algo. is “correct” if its: WARNINGS:
– Semantics are correct
– Syntax is correct 1. An algo. can be
syntactically correct,
yet semantically
Semantics: incorrect – very
The concept embedded in an dangerous situation!
algorithm (the soul!)
2. Syntactic
Syntax: correctness is easier to
The actual representation of check as compared
an algorithm (the body!) with semantic
 Solving Problems (1)
When faced with a problem:
1. We first clearly define the problem

2. Think of possible solutions

3. Select the one that we think is the best under the

prevailing circumstances

4. And then apply that solution

5. If the solution woks as desired, fine; else we go

back to step 2
 Solving Problems(2)
•It is quite common to first solve a problem for a
particular case
•Then for another

•And, possibly another

•And watch for patterns and trends that emerge

•And to use the knowledge form those patterns and

trends in coming up with a general solution
•And this general solution is called …………….
 Early History:
Search for a Generic Algorithm
• The study of algorithms began with mathematicians and
was a significant area of work in the early years

• The goal of those early studies was to find a single,

general algorithm that could solve all problems of a single
type
 Origin of the Term “Algorithm”
• The name derives from the title of a Latin book:
Algoritmi de numero Indorum

• That book was a translation of an Arabic book: Al-

Khwarizmi Concerning the Hindu Art of Reckoning

• That book was written by the famous 9-th century

Muslim mathematician, Muhammad ibn Musa al-
Khwarizmi
 Al-Khwarzmi

• Al-Khwarizmi lived in Baghdad, where he worked at the

Dar al-Hikma
• Dar al-Hikma acquired and translated books on science and
philosophy, particularly those in Greek, as well as
publishing original research
• The word Algebra has its origins in the title of another Latin
book which was a translation of yet another book written by
Al-Khwarzmi:
Kitab al-Mukhtasar fi Hisab al-Jabr wa'l-Muqabala
 Al-Khwarizmi’s Golden Principle
All complex problems can be and must be solved
using the following simple steps:

1. Break down the problem into small, simple sub-

problems
2. Arrange the sub-problems in such an order that each of
them can be solved without effecting any other
3. Solve them separately, in the correct order
4. Combine the solutions of the sub-problems to form the
solution of the original problem
Algorithms to Programs
Problem
Algorithm: A sequence of
instructions describing how
to do a task

High Level Language

Program
21
 Algorithm & Programming
Algorithm
 Basic element of programming
 A mathematical entity independent of programming languages,
operating system & compiler
 Scientific way of handling general programming techniques
Project / Software
 Software projects (small, large or huge) have macro issues &
micro issues
 Macro issues are the subject of software engineering practices
 Micro issues involve variables, controls, I/O, data conversion,
classes, functions, interfaces, exceptions, threads etc.
 Often a small part of a project has major difficulty in
programming the code
 While Designing Algorithms
They need to be understood by people (not by machines)
Algorithms need to be simple, and modifiable in case parameters are
changed
Flexibility of present-ability
Need mathematical model of computation to present an algorithm
Reasonable generic abstraction of single processor machine (RAM)
Quantitative measures to evaluate & compare algorithms
Algorithms are measured in terms of space, time & other resources
Most important factor is time (Why?)
There may be other important factors as ease of debugging, maintainability
Algorithmic Functions … Ceil, Floor

Example:
x  5.3
Ceil will return 6
Floor will return 5
Algorithmic Functions … Power
Expression Simplification
Xa.Xb Xa+b
Xa/Xb Xa-b
(Xa)b Xab
Xa+Xa 2Xa
2a.2a 22a
Algorithmic Functions … Logarithmic Expressions

Expression Simplification
X = log2 y 2x=y
Logab logcb / logca
log ab log a + log b
log a/b log a – log b
(log a)b b log a

Note: While studying computer science we normally consider logarithmic

functions with base value 2
 Permutations
A permutation of a set of distinct objects is an ordered
arrangement of these objects.

 Order of elements matters

 Values (in set) must be distinct
 A permutation can use either few or all the elements of a set
 If all values of set have to be used for a permutation, overall n! (n
factorial) permutations exist
For example for set {a, b, c} all permutations are: abc, acb, bac, bca,
cab, cba
 Permutations and Combinations
An ordered arrangement of r elements of a set is called an r-
permutation.

 The number of r-permutations of a set with n elements is denoted by

P(n, r)
 One can calculate P(n, r) using the formula:
P(n, r) = n!/(n-r)!
 One can calculate P(n, r) also by:
P(n, r) = n * (n-1)*(n-2)*(n-3)*…..*(n-r+1)
 Permutations and Combinations …
Examples
 In how many ways we can arrange three flags from five different
flags?
 In how many ways can five flags be arranged?
 Write down all 2-permutations from set S = {x, y, z}
 How many ways are there to select a winner and a runner up from a
race of 10 athletes? (There are no ties)