Data Structures and Algorithms (COM1029)
https://www.inf.ed.ac.uk/teaching/courses/inf2b/algnotes/note02.pdf
(Data Structures and Algorithms Notes | University of Edinburgh)
https://sd.blackball.lv/library/Introduction_to_Algorithms_Third_Edition_(2009
).pdf
(Introduction to Algorithms Book)
https://www.vlebooks.com/Product/Index/2025761?page=0
(Algorithmics Book)
https://www.cs.bham.ac.uk/~jxb/DSA/dsa.pdf
(Data Structures and Algorithms Notes | University of Birmingham)
https://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE.pdf
(Algorithms Notes)
https://www.geeksforgeeks.org/data-structures/?ref=shm
(Data Structure Notes)
https://www.geeksforgeeks.org/fundamentals-of-algorithms/?ref=shm
(Algorithm Notes)
1) What is an Algorithm? An algorithm is a finite sequence of rigorous
instructions, typically used to solve a class of
specific problems or to perform a computation.
2) What is a Program? A program is a sequence or set of instructions in a
programming language for a computer to
execute.
,3) Why do we analyse algorithms? ● To predict the behaviour of an algorithm
without implementing it on a specific
computer.
● It is much more convenient to have
simple measures for the efficiency of an
algorithm than to implement the
algorithm and test the efficiency every
time a certain parameter in the
underlying computer system changes.
● It is impossible to predict the exact
behaviour of an algorithm. There are too
many influencing factors.
● The analysis is thus only an
approximation; it is not perfect.
● More importantly, by analysing different
algorithms, we can compare them to
determine the best one for our purpose.
Types of Algorithm Analysis:
● Best case
● Worst case
● Average case
Best case: Define the input for which algorithm
takes less time or minimum time. In the best case,
calculate the lower bound of an algorithm.
Example: In the linear search when search data is
present at the first location of large data then the
best case occurs.
Worst Case: Define the input for which algorithm
takes a long time or maximum time. In the worst
case, calculate the upper bound of an algorithm.
Average case: In the average case take all random
inputs and calculate the computation time for all
inputs. And then we divide it by the total number
of inputs.
Average case =
all random case time / total no of case.
,4) What is Algorithm Efficiency? Algorithmic efficiency is a property of an
algorithm which relates to the amount of
computational resources used by the algorithm.
An algorithm must be analysed to determine its
resource usage, and the efficiency of an algorithm
can be measured based on the usage of different
resources.
To measure how efficient an algorithm is,
two resources are commonly considered in
algorithm execution:
5) What is Time Complexity? How do we The time complexity is the computational
measure it? complexity that describes the amount of computer
time it takes to run an algorithm.
Time complexity is commonly estimated by
counting the number of elementary operations
performed by the algorithm, supposing that each
elementary operation takes a fixed amount of
time to perform. Thus, the amount of time taken
and the number of elementary operations
performed by the algorithm are related by a
constant factor.
, 6) How do we use Time Complexity to
Compute the Average of an Array of Size
N?
7) What are Linear Time Algorithms? An algorithm is said to take linear time, or
O(n) time, if its time complexity is O(n).
Informally, this means that the running time
increases at most linearly with the size of the
input.
More precisely, this means that there is a constant
c such that the running time is at most cn for
every input of size n. For example, a procedure
that adds up all elements of a list requires time
proportional to the length of the list, if the adding
time is constant, or, at least, bounded by a
constant.
https://www.inf.ed.ac.uk/teaching/courses/inf2b/algnotes/note02.pdf
(Data Structures and Algorithms Notes | University of Edinburgh)
https://sd.blackball.lv/library/Introduction_to_Algorithms_Third_Edition_(2009
(Introduction to Algorithms Book)
https://www.vlebooks.com/Product/Index/2025761?page=0
(Algorithmics Book)
https://www.cs.bham.ac.uk/~jxb/DSA/dsa.pdf
(Data Structures and Algorithms Notes | University of Birmingham)
https://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE.pdf
(Algorithms Notes)
https://www.geeksforgeeks.org/data-structures/?ref=shm
(Data Structure Notes)
https://www.geeksforgeeks.org/fundamentals-of-algorithms/?ref=shm
(Algorithm Notes)
1) What is an Algorithm? An algorithm is a finite sequence of rigorous
instructions, typically used to solve a class of
specific problems or to perform a computation.
2) What is a Program? A program is a sequence or set of instructions in a
programming language for a computer to
execute.
,3) Why do we analyse algorithms? ● To predict the behaviour of an algorithm
without implementing it on a specific
computer.
● It is much more convenient to have
simple measures for the efficiency of an
algorithm than to implement the
algorithm and test the efficiency every
time a certain parameter in the
underlying computer system changes.
● It is impossible to predict the exact
behaviour of an algorithm. There are too
many influencing factors.
● The analysis is thus only an
approximation; it is not perfect.
● More importantly, by analysing different
algorithms, we can compare them to
determine the best one for our purpose.
Types of Algorithm Analysis:
● Best case
● Worst case
● Average case
Best case: Define the input for which algorithm
takes less time or minimum time. In the best case,
calculate the lower bound of an algorithm.
Example: In the linear search when search data is
present at the first location of large data then the
best case occurs.
Worst Case: Define the input for which algorithm
takes a long time or maximum time. In the worst
case, calculate the upper bound of an algorithm.
Average case: In the average case take all random
inputs and calculate the computation time for all
inputs. And then we divide it by the total number
of inputs.
Average case =
all random case time / total no of case.
,4) What is Algorithm Efficiency? Algorithmic efficiency is a property of an
algorithm which relates to the amount of
computational resources used by the algorithm.
An algorithm must be analysed to determine its
resource usage, and the efficiency of an algorithm
can be measured based on the usage of different
resources.
To measure how efficient an algorithm is,
two resources are commonly considered in
algorithm execution:
5) What is Time Complexity? How do we The time complexity is the computational
measure it? complexity that describes the amount of computer
time it takes to run an algorithm.
Time complexity is commonly estimated by
counting the number of elementary operations
performed by the algorithm, supposing that each
elementary operation takes a fixed amount of
time to perform. Thus, the amount of time taken
and the number of elementary operations
performed by the algorithm are related by a
constant factor.
, 6) How do we use Time Complexity to
Compute the Average of an Array of Size
N?
7) What are Linear Time Algorithms? An algorithm is said to take linear time, or
O(n) time, if its time complexity is O(n).
Informally, this means that the running time
increases at most linearly with the size of the
input.
More precisely, this means that there is a constant
c such that the running time is at most cn for
every input of size n. For example, a procedure
that adds up all elements of a list requires time
proportional to the length of the list, if the adding
time is constant, or, at least, bounded by a
constant.
