What is an Algorithm? (1/2)
• Definition
– A
computable set of steps to achieve a desired result
What is an Algorithm? (2/2)
• Properties
– Finiteness ->
an algorithm terminates after a finite numbers of steps
– Definiteness ->
each step in algorithm is unambiguous. This means that the action specified by
the step cannot be interpreted (explain the meaning of) in multiple ways &
can be performed without any confusion
– Input ->
an algorithm accepts zero or more inputs
– Output ->
it produces at least one output
– Effectiveness ->
it consists of basic instructions that are realizable. This means that the
instructions can be performed by using the given inputs in a finite amount of
time
Classes of Algorithm (1/4)
• There
is no universally accepted breakdown for the various types of algorithms, but
there are common classes that algorithms are frequently agreed to belong to
e.g.
• Dynamic
Programming Algorithms: This class remembers older results and attempts
to use this to speed the process of finding new results.
Classes of Algorithm (2/4)
• Greedy
Algorithms: Greedy algorithms attempt not only to find a
solution, but to find the ideal solution to any given problem.
• Brute
Force Algorithms: The brute force approach starts at some random
point and iterates through every possibility until it finds the solution.
• Randomized
Algorithms: This class includes
any algorithm that uses a random number at
any point during its process.
Classes of Algorithm (3/4)
• Branch
and Bound Algorithms: Branch and bound algorithms form a tree of
subproblems to the primary problem, following each branch until it is either
solved or lumped in with another branch.
• Simple
Recursive Algorithms: This type of algorithm goes for a direct solution
immediately, then backtracks to find a simpler solution.
Classes of Algorithm (4/4)
• Backtracking
Algorithms: Backtracking algorithms test for a solution, if
one is found the algorithm has solved, if not it recurs once and tests again,
continuing until a solution is found.
• Divide
and Conquer Algorithms: A divide and conquer algorithm is similar to a
branch and bound algorithm, except it uses the backtracking method of recurring
in tandem with dividing a problem into subproblems.
Algorithm Analysis (1/15) • Why should we analyze algorithms?
– A
problem may have numerous algorithmic solutions.
– In
order to choose the best algorithm for a
particular task, you need to be able to judge how long a particular solution
will take to run.
– Or,
more accurately, you need to be able to judge how long two solutions will take
to run, and choose the better of the two.
– You
don't need to know how many minutes and seconds they will take, but you do need
some way to compare algorithms against one another.
Algorithm Analysis (2/15)
• Most
algorithms transform input objects into output objects.
• The running time of an algorithm typically grows with the input size.
• Average
case time is often difficult to determine.
• We
focus on the worst case running time.
– Easier
to analyze
– Crucial
to applications such as games, finance and robotics
Algorithm Analysis (3/15)
• How
to Calculate Running Time
– Write
a program implementing the algorithm
– Run
the program with inputs of varying size and composition
– Use a
method like System.currentTimeMillis() to get an accurate measure of the actual
running time
– Plot
the results
Algorithm Analysis (4/15)
• Limitations
– It is
necessary to implement the algorithm, which may
be difficult.
– Results
may not be indicative of the running time on other inputs not included in the
experiment.
– In
order to compare two algorithms, the same hardware and
software environments must be used.
Algorithm Analysis (5/15)
• Theoretical Analysis
– Uses
a high-level description of the algorithm instead of an implementation
– Characterizes
running time as a function of the input size, n.
– Takes
into account all possible inputs
– Allows
us to evaluate the speed of an algorithm independent of the hardware/software
environment
Algorithm Analysis (6/15)
• Primitive
Operations
– Basic
computations performed by an algorithm
– Identifiable
in pseudocode
– Largely
independent from the programming language
– Exact
definition not important (we will see why later)
– Assumed
to take a constant amount of time in the RAM model
Algorithm Analysis (7/15)
• Primitive
Operations Examples: – Evaluating
an expression
– Assigning
a value to a variable
–
Indexing into an array
– Calling
a method
– Returning
from a method
Algorithm Analysis (8/15)
• Counting Primitive
Operations
• By
inspecting the pseudocode, we can
determine the maximum number of primitive
operations executed by an algorithm, as a
function of the input size
Algorithm arrayMax(A, n) currentMax ¬ A[0]
for i ¬
1 to n - 1 do
if A[i] > currentMax then currentMax ¬ A[i]
{ increment counter i }
return currentMax
# operations 1
n
(n - 1) (n - 1) (n - 1) 1
4n - 1
Total
Algorithm Analysis (9/15)
• Estimating Running
Time
– Algorithm
arrayMax executes 4n - 1 primitive operations in the worst
case.
– Define:
• a = Time taken by the
fastest primitive operation
• b = Time taken by the slowest primitive operation
– Let
T(n) be worst-case time of arrayMax. Then • a(4n-1)<=T(n)<=b(4n-1)
– Hence,
the running time T(n) is bounded by two linear functions
Algorithm Analysis (10/15)
• Growth Rate Vs Running
Time
– Changing
the hardware/ software environment
• Affects T(n) by a constant factor, but
• Does not alter the growth
rate of T(n)
– The
linear growth rate of the running time T(n) is an intrinsic property of
algorithm arrayMax
Algorithm Analysis (11/15)
• Worst-case
Complexity
– Maximum steps the algorithm takes for
any possible input.
– Most tractable measure.
• Average-case
Complexity
– Average of the running times of all possible
inputs.
– Demands a definition of probability of
each input,
which
is usually difficult to provide and to analyze.
• Best-case
Complexity
– Minimum number
of steps for any possible input. – Not a useful measure.
Algorithm Analysis: (12/15)
Example
Alg.: MIN (a[1],
..., a[n]) m ← a[1];
for i ← 2 to n if
a[i] < m
then m ← a[i]; Running
time:
– the
number of primitive operations (steps)
executed before termination
T(n) =1 [first step] + (n) [for loop] + (n-1) [if
condition] + (n-1) [the assignment in
then] = 3n - 1
Order (rate) of growth:
– The
leading term of the formula
– Expressestheasymptoticbehaviorofthealgorithm
Algorithm Analysis: (13/15) • Typical Running Time
Functions
– 1
(constant running time):
• Instructions are executed once or a few times
– logN
(logarithmic)
•
A big problem is solved by cutting the original problem in smaller
sizes, by a constant fraction at each step – N (linear)
• A
small amount of processing is done on each input element – N logN
• A
problem is solved by dividing it into smaller problems, solving them
independently and combining the solution
Algorithm Analysis: (14/15) • Typical Running Time
Functions
– N2 (quadratic)
• Typical for algorithms
that process all pairs of data items (double
nested loops) – N3 (cubic)
• Processing
of triples of data (triple nested loops)
– NK (polynomial)
– 2N (exponential)
• Few exponential
algorithms are appropriate for practical use
Algorithm Analysis: (15/15)
•
Asymptotic Notations
A way to describe behavior of functions in the
limit – Abstracts
away low-order terms and constant factors
– How we indicate running times of algorithms
– Describe the running
time of an algorithm as n grows to ¥
• •
•
O notation: (Big Oh)
– asymptotic “less
than”:
W notation: (Big Omega) – asymptotic “greater
than”:
Q notation: (Big Theta) – asymptotic “equality”:
f(n) “≤” g(n) f(n) “≥” g(n) f(n) “=” g(n)
O(Big Oh) -Notation
O(Big Oh) - Example
• 2n2 = O(n3):
• 1000n2+1000n = O(n2):
2n2 ≤cn3Þ2≤cnÞc=1andn0=2 • n2 = O(n2): n2 ≤ cn2 Þ c ≥ 1 Þ c = 1 and n0= 1
1000n2+1000n ≤
1000n2+
1000n2 =
2000n2
Þ c=2000 and n0 = 1
• n = O(n2): n
≤ cn2 Þ cn ≥ 1 Þ c = 1 and n0= 1
• 2n
+ 10 = O(n) :
• n2¹O(n)
• 7n
-2 = O(n)
• 3n3 + 20n2 + 5 = O(n3)
• 3
logn + log log n = O(log n)
W (Big Omega) - Notation
• Intuitively: W(g(n)) = the set of functions with a larger or same order of growth as g(n)
W (Big Omega) - Example – 5n2 = W(n)
$ c, n0 such that: 0 £ cn £ 5n2 Þ
cn £ 5n2 – 100n +
5 ≠ W(n2)
$c,n0 suchthat:0£cn2 £100n+5
100n + 5 £ 100n + 5n (" n
³ 1) = 105n
cn2 £ 105n
Since
n is positive Þ cn – 105 £ 0
Þ c = 1 and n0 = 1
Þ n(cn – 105) £ 0
Þ contradiction: n cannot
be smaller than a constant
– n
= W(2n), n3 = W(n2), n = W(logn)
Þ n £ 105/c
• Intuitively Q(g(n)) = the set of functions with the same order of growth as g(n)
Q (Big Theta) - Example • n2/2 –n/2 = Q(n2)
• 1⁄2 n2 - 1⁄2 n ≤ 1⁄2
n2 "n ≥ 0
Þ c2=
1⁄2
• 1⁄2 n2 - 1⁄2 n ≥ 1⁄2
n2 - 1⁄2
n * 1⁄2 n ( "n ≥ 2 ) = 1⁄4 n2 Þ c1= 1⁄4
– n≠Q(n2):c1 n2 ≤n≤c2 n2 Þ only
holds for: n ≤ 1/c1
6n3 ≠ Q(n2):c1 n2 ≤6n3 ≤c2 n2 Þ only holds for: n
≤ c2 /6
n≠Q(logn):c1 logn≤n≤c2 logn
Þ c2 ≥ n/logn, " n≥
n0 – impossible
Asymptotic Notations - Exercise
• For
each of the following pairs of functions, either f(n) is O(g(n)), f(n) is Ω(g(n)),
or f(n) is Θ(g(n)). Determine which relationship is correct.
– f(n) = log n2; g(n) = log
n + 5
– f(n) = n; g(n) = log n2
– f(n) = log log n; g(n) =
log n
– f(n) = n; g(n) = log2 n
– f(n) = n log n + n; g(n)
= log n
– f(n) = 10; g(n) = log 10
– f(n) = 2n; g(n) = 10n2
– f(n) = 2n; g(n) = 3n
f(n) = Q (g(n))
f(n) = W(g(n)) f(n) = O(g(n)) f(n) = W(g(n))
f(n) = W(g(n)) f(n) = Q(g(n))
f(n) = W(g(n)) f(n) = O(g(n))
More on Asymptotic Notations
• There
is no unique set of values for n0 and c
in proving the asymptotic bounds
• Prove
that 100n + 5 = O(n2)
– 100n+5≤100n+n=101n≤101n2
for all n
≥ 5
n0 =5andc=101isasolution
– 100n+5≤100n+5n=105n≤105n2 for
all n ≥ 1
n0 = 1 and c = 105 is
also a solution
Must find SOME constants
c and n0 that
satisfy the asymptotic notation relation
Comparisons of Functions
•
Theorem:
f(n) = Q(g(n))
Û f = O(g(n)) and f = W(g(n))
• Transitivity:
– f(n) =
Q(g(n)) and g(n)
= Q(h(n)) Þ f(n)
= Q(h(n))
– SameforOandW
• Reflexivity:
– f(n)
= Q(f(n))
– SameforOandW
• Symmetry:
– f(n)
= Q(g(n)) if and only if g(n)
= Q(f(n))
• Transpose
symmetry:
– f(n)
= O(g(n)) if and only if g(n) = W(f(n))
•
Asymptotic Notations in Equations
On the right-hand side
– Q(n2) stands
for some anonymous function in Q(n2) 2n2 + 3n + 1 =
2n2 + Q(n)
means:
There exists a function f(n) Î Q(n) such that
2n2 + 3n + 1 = 2n2 + f(n)
On the left-hand side
2n2 + Q(n) = Q(n2)
No matter how the anonymous
function is chosen on the left-hand side, there is a way to choose the
anonymous function on the right-hand side to make the equation valid.
Sorting Algorithms
Name
|
Best
|
Average
|
Worst
|
Method
|
Quick
|
n log n
|
n log n
|
n2
|
Partitioning
|
Merge
|
n log n
|
n log n
|
n log n
|
Merging
|
Heap
|
n log n
|
n log n
|
n log n
|
Selection
|
Insertion
|
n
|
n2
|
n2
|
Insertion
|
Selection
|
n2
|
n2
|
n2
|
Selection
|
Bubble
|
n2
|
n2
|
n2
|
Exchanging
|
Other Sorting Algorithms
• Introsort
• Timsort
• Shell sort
• Binary Tree sort • Cycle sort
• Library
sort
• Patience
sort • Smoothsort
• Strand
sort • Tournament
sort
• Cocktail sort • Comb sort
• Gnome sort • Bogosort
Comparison
Sort
Other Sorting Algorithms
• Pigeonhole
sort • Bucket
sort
• Counting
sort
• LSD
Radix sort
• MSD
Radix sort • Spreadsort
Non
Comparison Sort
______________________________________________________________________________________
Introduction to Data Structures
– Understanding the problem – Designing a solution
– Implementing the solution
• What exactly is a solution? – A solution = a program
• An algorithm is a sequence of steps that take us from the input to the output.
• Properties of Algorithm
– Input: may or may not some input data
– Output: at least one output
– Definiteness: every step must be clear and unambiguous
– Finiteness: It must terminate after a finite number of steps
– Effectiveness: the steps must be basic steps so that dry-run will be possible
• Any algorithm we come up with will have to manipulate data in some way
– The way we choose to organize our data directly affects the efficiency of our algorithm
• Solution = algorithm + data organization
– Both components are strongly interconnected.
• Data structure: An arrangement of data in a computer’s memory (or sometimes on a disk).
• conceptual and concrete ways to organize data for efficient storage and efficient manipulation
– Arrays, linked lists, stacks, trees, hash tables.
• Algorithms manipulate the data in these
structures in order to accomplish some task. – Inserting an item, search for an item, sorting.
How are Data structures used • As an actual way to store real-world data
• As a tool to be used only within a program
(not visible to the user)
– E.g., stacks, queues, priority queues
• As a model of real-world situations – e.g., graphs
Why different data structures
• Each data structure has different advantages and disadvantages, and will be useful for different types of applications.
• Fast access: if we know the index of the item we are looking for • Insertion and Deletion is slow
– Maintain a Job Queue • Queuecanbeused
– Hierarchy of employees of an organization • Tree can be used
• A primitive data type holds a single piece of data – e.g. in Java: int, long, char, boolean etc.
– Legal operations on integers: + - * / ...
• Adatastructurestructuresdata!
– Usually more than one piece of data
– Should provide legal operations on the data
– The data might be joined together (e.g. in an array): a
• An Abstract Data Type (ADT) is a data type together with the operations, whose properties are specified independently of any particular implementation.
• Encapsulation:Providingdataandoperationsonthe data
• Abstraction:hidingthedetails.
– e.g. A class exhibits what it does through its methods; however, the details of how the methods work is hidden from the user
• Modularity: Splitting a program into pieces.
– An object-oriented program is a set of classes (data structures) which work together.
– There is usually more than one way to split up a program .
__________________________________________________________________________________________________________________________________________________________________
A
|
R
|
R
|
A
|
Y
|
\0
|
|
|
|
|
|
|
327
|
328
|
329
|
330
|
331
|
332
|
• An
array is an indexed sequence of components
–
The array occupies sequential storage locations
–
The length of the array is determined when
the array is created, and cannot be changed
–
Each component of the array has a fixed, unique index
• Indices range from a lower bound to
an upper bound
–
Any component of the array can be inspected or updated by using its index
•
This is an efficient operation: O(1) = constant time
Array
Dimensions
•
The simplest form of array is a ‘one- dimensional’ array
•
The dimension of an array can be 1 or more than 1
•
1-D array – int A[10];
•
2-D array
– int A[3][5];
General
Info
•
The
two basic operations that access an array are
– Extraction x = A[i]; – Storing
A[i] = x;
•
The
smallest index of the array is called ‘lower bound’ (0 always in ‘C’) and
highest index is ‘upper bound’
• The number of elements in an array is – upper
- lower + 1
General
Info
•
Neither
the upper nor the lower bound of an array can be changed during program
execution (Static)
•
One
very useful technique is to declare a bound as a constant identifier (MACRO)
1-D
Array • Declaration
–
int A[100];
•
The
address of first element (A[0]) is called the
‘base address’ let it be denoted
by base(A)
•
Suppose
the size of each individual element of
the array is esize
Then the reference to the A[i] is to the
element at location base(A) + i * esize
•
int a[5]; • int *p;
• p = a;
‘a’
is a constant pointer pointing to the first
1-D Array & Pointer
• Array of pointers – int *a[10];
– Array a can store 10 addresses – Ex. a[0] = &p, a[1] = &q like that
• Pointer to an array
– int (*a)[10];
– a is a pointer pointing to an array of 10 integers
Declaration
– int A[3][5];
• This defines a new array containing 3
elements
• Each of these elements is itself an array containing 5 integers
2-D Array
• A 2-D array actually stored as a linear array
– int numbers[3][4];
- int A [3][4];
- • int (*p)[4];
Array Operations
• Traversal
• Searching
• Sorting
• Insertion
– At begin, end, specific position, after element, before
element
• Deletion
– From begin, end, specific position, after element, before element, element
• Merging
• Reversing
Inserting an Element
1. If array is full then print “overflow”
2. Else shift the elements to right from the position where you want to insert
3. Insert the new element at that position
