Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Introduction:
Algorithms are an important subject in computer science, and are typically taught in courses
such as Algorithm Design and Analysis
...

An algorithm is a design that is created before a program is implemented
...
While some programming languages, such as C, are
commonly used in algorithm design, algorithms can be written in any programming
language that is suitable for the task at hand
...
While C is a popular and widely used
programming language, there are many other languages that are also important in
computer science, such as Python, Java, and JavaScript
...


Priori Analysis and Posteriori Testing:
Priori Analysis:
● In the context of algorithms, Priori Analysis involves analyzing an algorithm's
theoretical properties, such as its time and space complexity, before
implementing it
...


Posteriori Testing:
● Posteriori Testing is a type of dynamic testing that is performed on an algorithm
after it has been implemented and executed
...

● Posteriori Testing can help identify and debug issues that may not have been
apparent in the theoretical analysis, such as edge cases or unexpected inputs
...
Input - Every algorithm takes zero or more inputs
...
Output - Every algorithm produces at least one output
...
Definiteness - Every step of the algorithm must be clear and unambiguous
...
Finiteness - The algorithm must terminate after a finite number of steps
...
Feasibility - Each step of the algorithm must be computationally feasible and able
to be performed within a reasonable amount of time
...
Correctness - The algorithm must produce the correct output for all valid inputs
...
Generality - The algorithm must be applicable to a wide range of inputs
...
Optimality - The algorithm should be as efficient as possible, in terms of both time
and space complexity
...
For example,
by analyzing the input and output of an algorithm, we can understand its purpose and
potential use cases
...
Finiteness and feasibility help
ensure that the algorithm is practical and can be executed within reasonable
constraints
...


How Write and Analyze Algorithm:
1
...
This involves identifying the
inputs, outputs, and constraints of the problem
...
Choose appropriate data structures and algorithms: Once you understand the
problem, you need to choose appropriate data structures and algorithms to solve
it
...

3
...
It should include all of the steps
involved in solving the problem and be clear and unambiguous
...
Analyze the time and space complexity: Once you have written the algorithm,
you need to analyze its time and space complexity
...

5
...
This will help
you identify any bugs or inefficiencies in the algorithm and refine it as necessary
...
Iterate: If the algorithm is not efficient enough, you may need to iterate and try
different data structures or algorithms until you find a more optimal solution
...

Examples of pseudocodes:
Linear Search:
function linearSearch(array, target):
for each item in array:
if item equals target:
return index of item
return -1

Binary Search:
function binarySearch(sortedArray, target):
low = 0
high = length of sortedArray - 1
while low <= high:
mid = (low + high) // 2
if sortedArray[mid] == target:
return mid
elif sortedArray[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1

How to Find Time Complexity?:
To find the time complexity of an algorithm for analysis of algorithms, you can follow
these steps:
1
...
These can include
arithmetic operations, comparisons, assignments, and function calls
...
Determine how many times each basic operation is performed as a function of
the input size
...

3
...

4
...

5
...
This term represents the time complexity of
the algorithm
...
Express the time complexity using big-O notation, which provides an upper
bound on the growth rate of the function
...
The basic operation is addition
...
The addition operation is performed once for each element in the array, so the
count is n, where n is the length of the array
...
The count of the addition operation is n
...
The total count of the algorithm is n, since there is only one basic operation
...
The dominant term of the total count is n, which represents the time complexity of
the algorithm
...
The time complexity is expressed as O(n)
...
This
means that as the size of the input increases, the running time of the algorithm
increases linearly
...
These classes are defined using big-O notation, which provides an
upper bound on the growth rate of a function
...
O(1): This class represents algorithms whose running time is constant,
regardless of the input size
...


2
...
Examples of such algorithms include binary
search or finding the height of a balanced binary tree
...
O(n): This class represents algorithms whose running time grows linearly with the
input size
...

4
...
Examples of such algorithms include quicksort or
mergesort
...
O(n^c): This class represents algorithms whose running time grows polynomially
with the input size, where c is a constant greater than 1
...

6
...
Examples of such
algorithms include exhaustive search or the traveling salesman problem
...
O(n!): This class represents algorithms whose running time grows factorially with
the input size
...

It is important to note that these classes represent upper bounds on the growth rate of
an algorithm's running time, and that the actual running time of an algorithm may be
lower than its upper bound for certain inputs
...




---