Introduction to Algorithm
Basic:
Algorithm
An algorithm is the sequence of computational steps that transform the input into the
output.
An algorithm is any well-defined computational procedure that takes some value, or set of
values, as input and produces some value, or set of values, as output.
sorting problem:
Input: a sequence of n numbers(a1, a2,......,an)
Output: A permutation (reordering) {a1’, a2’,…..an’} of the input sequence in such that
a1’<=a2’<=….<=an.
Example:
For example, given the input sequence (31; 41; 59; 26; 41; 58), a sorting algorithm returns
as output the sequence (26; 31; 41; 41; 58; 59).
Such an input sequence is called an instance of the sorting problem. In general, an
instance of a problem consists of the input (satisfying whatever constraints are imposed
in the problem statement) needed to compute a solution to the problem.
An algorithm is said to be correct if, for every input instance, it halts with the correct
output. We say that a correct algorithm solves the given computational problem. An
incorrect algorithm might not halt at all on some input instances, or it might halt with an
incorrect answer. Contrary to what you might expect, incorrect algorithms can sometimes
be useful, if we can control their error rate.
What kinds of problems are solved by
algorithms?
The Internet enables people all around the world to quickly access and
retrieve large amounts of information.
Electronic commerce enables goods and services to be negotiated and
exchanged electronically. Such as Amazon, ebay, Daraz etc.
Manufacturing and other commercial enterprises often need to allocate
scarce resources in the most beneficial way.
Google Map is also a good example.
Write an algorithm to make tea.
Pour water in a pan.
Add tea leaves.
Add sugar.
Add milk.
Bring it to boil.
Pour in a cup.
How we analyze the efficiency of an
algorithm:
Time consumption
Memory efficient
There is always a contrast b/w time and memory.
The algorithm consuming more time will take less memory and the algorithm
getting more memory will consume less time.
Important terms to be noted:
Data structure:
A data structure is a way to store and organize data in order to facilitate access
and modifications. No single data structure works well for all purposes, and so it is
important to know the strengths and limitations of several of them.
Techniques:
There are different aspects of algorithmic problem solving. Some are address
specific problems, such as finding medians and order statistics, computing
minimum spanning trees, divide-and-conquer approach and dynamic
programming.
Hard problems :
Our usual measure of efficiency is speed, i.e., how long an algorithm takes to
produce its result. There are some problems, however, for which no efficient
solution is known. There are an interesting subset of these problems, which are
known as NP-complete problem which can not be solved in a given time interval.
Parallelism:
Multithreaded approach and multi-core techniques to run programs in parallel.
Data structures:
Arrays
Linked list, double linked list
Queues, De-queues
Stacks
Heap
Graphs
Comparison of running time:
Solve this to execute different running time.
Asymptotic notation:
we use to describe the asymptotic running time of an algorithm are defined in
terms of functions whose domains are the set of natural numbers N (0,1,2,…..).
Comparing functions properties:
Transitivity: f(n)= 0(g(n))==g(n)=O(h(n)) imply f(n)=O(h(n))
and so on…………
Reflexivity: f(n)= O(f(n))
and so on………...
Symmetry: f(n)= θ(g(n)) if and only if g(n)= θ(f(n))