1.
Introduction to Algorithms:
An Algorithm is a set of steps of operation to solve a particular
problem/
An Algorithm is a finite sequence of well-defined, computer-
implementable instructions designed to solve a specific problem or
perform a computation. An algorithm can be represented either using flowcharts,
or using pseudocode.
Properties of an Algorithm.
The Algorithm must have
[Link]:
The Algorithm must have zero or more inputs
[Link]:
The Algorithm must produce the output, from a specified set of input
values…at least one output
[Link]:
The Algorithm must terminate after a finite number of steps
[Link]:
All steps of the Algorithm must be precisely defined. Every
instruction/step within the Algorithm should be clear and unambiguous
[Link] Algorithm must describe how the computation is to be
carried out.
Example of algorithm that does not satisfy definiteness
eg1. An Algorithm that contain Diving a number by zero, Which is
mathematically undefifined,
eg2. An Algorithm that attempts to calculate square root of a negative
number,since the squae root of a nagative number is not a real number but
it is a complex number
Effectiveness:
Steps that can be performed in a finite time. It refers to the ablitiy of
an algorithm to consistently and accurately produce a meaningful and
correct result for all the possible valid input within the finite amount of time.
Algorithm analysis and the importance of efficient algorithms.
. Recurrence Relations: Techniques for analyzing algorithms that are defined recursively
(e.g., divide and conquer algorithms). 3. Algorithm Design Techniques: Backtracking:
Exploring all possible solutions systematically, often used for search and optimization
problems. Branch and Bound: A technique for solving optimization problems by
systematically searching the solution space, pruning branches that cannot lead to optimal
solutions. Randomized Algorithms:
1. Time Complexity: Analyzing how the running time of an algorithm grows with the
input size.
2. Space Complexity: Analyzing how much memory an algorithm uses as a function
of input size.
3. Asymptotic Notation: Using Big-O, Big-Omega, and Big-Theta to describe the
growth rate of functions and analyze algorithm efficiency.
4. Recurrence Relations: Techniques for analyzing algorithms that are defined
recursively (e.g., divide and conquer algorithms).
Algorithm Design Techniques:
1. Divide and Conquer:
Breaking down a problem into smaller subproblems, solving them recursively, and
combining the results (e.g., merge sort, quicksort).
[Link] Algorithms:
Making locally optimal choices at each step with the hope of finding a global
optimum (e.g., Dijkstra's algorithm for shortest paths).
[Link] Programming:
Solving problems by breaking them down into overlapping subproblems and storing
the results to avoid recomputation.
[Link]:
Exploring all possible solutions systematically, often used for search and
optimization problems.
[Link] and Bound:
A technique for solving optimization problems by systematically searching the
solution space, pruning branches that cannot lead to optimal solutions.
[Link] Algorithms:
Algorithms that use random numbers to influence their computation, often
improving efficiency or providing probabilistic guarantees of correctness.