Algorithms
Lab 1
Agenda
1. Introduction to Algorithms
2. Data Structures & Algorithms Overlapping
3. Analysis of Algorithms
1. Iterative Approach
2. Recursive Approach
Introduction To Algorithms
What Are Algorithms?
• An algorithm is a precise set of instructions designed to solve a
specific problem.
• It's like a recipe for solving a computational task.
• Algorithms form the basis of computer programming.
Importance in Computing
• Algorithms are the backbone of computing.
• They enable us to process data, make decisions, and perform tasks
efficiently in various applications.
Efficiency and Optimization
• Algorithms are not just about solving problems; they are also about
solving them efficiently.
• Efficient algorithms are key to saving time, computational
resources, and energy. They're essential in today's computing
environments.
Algorithmic Thinking
• Algorithmic thinking is the ability to break down complex
problems into smaller, solvable components.
• It's a valuable skill in the world of technology.
DS & Algorithms Overlapping
Data Structures & Algorithms Overlapping
• Designing a contact book application (List vs. Map)
• Keeping track with min or max grade of some students (List vs. Heap)
Analysis Of Algorithms
Performance vs Complexity
• Performance: How much time/memory/disk/etc. is used when a
program is run. This depends on the machine, compiler, etc. as well as
the code we write.
• Complexity: How do the resource requirements of a program or
algorithm scale, ( what happens as the size of the problem being solved
by the code gets larger).
Introduction to Analysis of Algorithms
• Algorithm Analysis: It is an important part of computational
complexity theory, which provides theoretical estimation for the
required resources of an algorithm to solve a specific computational
problem.
• Analysis of algorithms is the determination of the amount of time and
space resources required to execute it.
• Analyzing algorithms helps us understand their performance, make
informed design choices, and select the most suitable algorithm for a
given problem.
Type of Analysis
• Space Complexity Analysis : Measures how the algorithm's
memory usage increases as the input size increases.
• Execution Time Complexity Analysis : Measures how the algorithm's
runtime grows according to the input size.
Space Complexity Analysis
• Space complexity measures the amount of memory an
algorithm requires as a function of the size of its input.
• It helps identify algorithms with minimal memory overhead.
Execution Time Complexity Analysis
• Time complexity quantifies ( count ) the number of basic operations
that the algorithm performs as a function of the size of its input.
• Common notations include :
o Best Case: Minimum time required for program execution (Ω Notation)
o Average Case: Average time required for program execution (θ Notation)
o Worst Case: Maximum time required for program execution (Big Ο Notation)
Asymptotic notation
• Asymptotic Notation is used to describe the running time of an
algorithm - how much time an algorithm takes with a given input n.
• There Are Three Main Notations :
o Big Omega (Ω) Notation
o Big Theta (Θ) Notation
o Big O Notation
Big Omega (Ω) Notation
• Describes the lower bound of an algorithm's complexity.
• It provides a best-case analysis.
• We compute the big-Ω by counting how many iterations an algorithm will
take in the best-case scenario based on an input of N.
• For example, a Sort algorithm has a running time of Ω(N) because in
the best-case scenario the list is already sorted, and the sort will
terminate after the first iteration.
Big Theta (Θ) Notation
• Big Theta notation combines Big O (Upper Bound) and Big Omega
(Lower Bound) to describe the tight bounds of an algorithm's
complexity.
• It offers a more precise analysis.
• We compute the big-Θ of an algorithm by counting the number of
iterations the algorithm usually takes with an input of n.
Big O Notation
• Big-O notation describes the worst-case running time of a program.
• We compute the Big-O of an algorithm by counting how many iterations
an algorithm will take in the worst-case scenario with an input of N.
• We typically consult the Big-O because we must always plan for the
worst case.
• For example, O(N^2) describes the Big-O of a Bubble Sort algorithm if
all elements in the list need to be sorted are sorted in a reverse order.
Common Runtimes
Common Runtimes Cont'd
Logarithmic: O(log n) Linear: O(n)
Common Runtimes Cont'd
Linear Logarithmic: O(n log n) Quadratic: O(n^2)
Common Runtimes Cont'd
Cubic: O(n^3) Exponential: O(2^n)
Problem
Thank You!
