Transcript Chapter 2 Templates Data Struct and Algorithm v1.0.0

Chapter 2: Templates,
Introduction To Data Structures &
Algorithms Analysis And Basic
Algorithm Analysis
1
Templates
 Function Templates
 Class Templates
2
Templates
 Basic Template Concepts
Generated
Function
Function
Template
Generated
Function
Generated
Function
Generated
Class
Class
Template
Generated
Class
Generated
Class
3
Templates
 There are 4 functions that receive different types of data but
doing the same task. What can we do about it?
int max(int x, int y)
{
return (x>y)?x:y;
}
float max(float x, float y)
{
return (x>y)?x:y;
}
long max(long x, long y)
{
return (x>y)?x:y;
}
double max(double x, double y)
{
return (x>y)?x:y;
}
4
Program Example
Example: Two functions are doing the same task.
//Sum.cpp
#include <iostream>
using namespace std;
//Add 2 integer
void Add(int, int);
//Add 2 double
void Add(double, double);
void main()
{
Add(10, 12);
Add(5.5, 3.8);
}
//method call for int
//method call for double
5
Program Example
Example: Two functions are doing the same task (cont).
//Function implementation
void Add(int x, int y)
{
cout << "Integer: " << x << " + " << y << " = " << x + y << endl;
}
void Add(double x, double y)
{
cout << "Double: " << x << " + " << y << " = " << x + y << endl;
}
6
Program Example
Example: Two functions are doing the same task (cont).
Output :
Integer : 10 + 12 = 22
Double : 5.5 + 3.8 = 9.3
 When the first method is called, the compiler will define
that there are two integer numbers being send to the
equivalent method that receive two integers. Same goes
with the second method that receive two doubles.
 During executions, both functions will add two numbers
together but the difference is the types of data.
 What will happen if we have 5 types of data? Do we have
to create 5 functions then?
 Templates can solve this problem.
7
Function Templates
 A function applies actions to one or more objects and may
create and return one object.
 Function Templates can create multiple functions each with
potentially different arguments and return types.
 The template prototype is known as template prefix.
 Syntax Declaration:
template <class identifier>
 Example:
template <class T>
template <class data>
template <class dataType>
*Note : T, data and dataType must be a valid identifier.
8
Function Templates
 The declaration for standard data types:
int x; double y;
 The declaration for class generic data types:
template <class T>
T x;
OR
template <class dataType>
dataType x;
*Note : T and dataType will be the class generic type that can represent
any type of standard data type
9
Program Example
Example: Function Templates.
//Sum.cpp
#include <iostream>
using namespace std;
template <class T>
//template prefix
void Add (T x, T y)
{
cout << x << " + " << y << " = "
<< x + y << endl;
}
void main()
{
Add (10, 12);
Add (5.5, 3.8);
}
10
Function Templates
 Only one function template needed to allow any method call
with different data types being send to its parameters.
 The class generic data type will change according to the
type of data being send to them.
 The function will add two numbers and prints out the result
according to the data type.
11
Function Templates
 Function Template With More Than One Parameter
 A function template can have more than one parameter.
 Syntax Declaration:
template <class T1, class T2>
 T1 and T2 can be two different data types. For example,
T1 can be used to represent an integer while T2 can be
used to represent a char.
 Both templates are separated by comma during its
definition.
12
Program Example
Example: Function Template with more than one parameter.
//Printing.cpp
#include <iostream>
using namespace std;
template < class T1, class T2 >
void printData (T1 var1, T2 var2)
{
cout << “First value is " << var1;
cout << “\nSecond value is " << var2;
}
void main ()
{
int v1;
char v2;
cout << " Enter an integer and a char : ";
cin >> v1 >> v2;
printData (v1, v2);
}
13
Program Example
Example: Function Template with more than one parameter (cont).
Output :
Enter an integer and a char: 5 A
The first value is: 5
The second value is: A
 Both generic data types can be used to represent two
different data types at the same time.
 The first class generic data type T1 will be used to
represent an integer while the second class generic data
type T2 will be used to represent a char.
14
Function Templates
 Function Template With Multiple Type Of Parameters
 Besides the generic data type, the parameter in the
function can also be other standard data types such as
integer, float, double, boolean and char.
 At least one of the parameter must be the class generic
data type.
 Syntax Declaration:
template <class T>
void Maximum (T x, int y);
15
Program Example
Example: Function Template with multiple type of parameter.
//PrintArray.cpp
#include <iostream>
using namespace std;
template <class T>
void printArray (T *array, int count) {
for (int i=0; i<=count-1; ++i)
cout << array [i] << " ";
}
void main() {
char arrayA [] = “Success";
float arrayB [] = {10.5, 40.7, 21.3, 41.5};
cout << " The values in arrayA : ";
printArray(arrayA, 8);
cout << " \nThe values in arrayB : ";
printArray(arrayB, 4);
}
16
Program Example
Example: Function Template with multiple type of parameter (cont).
Output :
The values in arrayA: Success
The values in arrayB: 10.5 40.7 21.3 41.5
17
Class Templates
 Sometimes there is a situation that needed a generic class
being declared.
 Class Template is defined to have the data member with
the generic type.
 The declaration of class template is just the same as the
function template:
template <class T>
 The difference is that the generic parameters must be used
to at least one of the class data member.
18
Program Example
Example: Class Template.
//Maximum.h
#ifndef MAXIMUM_H
#define MAXIMUM_H
template <class T>
class Maximum {
private:
T val1, val2;
public:
Maximum(T v1, T v2);
void findMax();
};
#endif
19
Program Example
Example: Class Template (cont).
template <class T>
Maximum<T>::Maximum(T v1, T v2) {
val1 = v1;
val2 = v2;
}
template <class T>
void Maximum<T>::findMax() {
T max;
if (val1 > val2)
max = val1;
else
max = val2;
cout << “The maximum value is " << max;
}
20
Program Example
Example: Class Template (cont).
//MaxMain.cpp
#include <iostream>
#include "Maximum.h"
using namespace std;
void main()
{
Maximum <int> object1(100, 13);
Maximum <char> object2('a', 'A');
object1.findMax();
cout << "\n";
object2.findMax();
}
21
Program Example
Example: Class Template (cont).
Output :
The maximum value is : 100
The maximum value is : a
 The template prefix must be define before the declaration
of each class and each functions implementation.
 The class interface and implementation must be included
into one header file.
 Template will be compiled only when it is requested
(compile on demand) and it won’t be compiled until the
object instantiation is requested.
22
Intro to Data Structures & Algorithm
 Although several tools are used to define algorithms, one of
the most common is pseudocode.
 Pseudocode is an English-like representation of the code
required for an algorithm.
 It is part English, part structured code.
 The English part provides a relaxed syntax that is easy to
read.
 The code part consists of an extended version of the basic
algorithmic constructs such as sequence, selection and
iteration.
23
Algorithm Header
 Each algorithm begins with a header that names it,
describe its parameters and lists any pre- and
postconditions.
 This information is important because the programmer
using the algorithm often sees only the header information
not the complete algorithm.
 Therefore the header information must be complete enough
to communicate to the programmer everything that must
know to use the algorithm.
24
Algorithm Header

Example of Algorithm Header:
Algorithm search (val list <array>,
val argument <integer>,
ref location <index>)
Search array for specific item and return index location
Pre
list contains data array to be searched
argument contains data to be located in list
Post location contains index of element matching argument -orundetermined if not found
Return
<Boolean> true if found, false if not found.
25
Algorithm Header
 Example of Pseudocode:
Algorithm
Pre
Post
average
nothing
average and numbers printed
1 i=0;
2 loop(not end of file)
1 read number into array[i]
2 sum = sum + number
3 i = i + 1;
3 end loop
4 average = sum /i
5 print (average)
end average
26
Algorithm Analysis
 Algorithm – A set of instructions that must be
followed by the computer to solve problems.
 Algorithm Analysis – A technique to analyze an
algorithm, its efficiency and the usage of memory
to find the best algorithm.
 An algorithm should have such characteristic:
 Solve the problem successfully
 An efficient use of memory
 Fast run time
 The run time usually depends on:
 Input size of the program
 Code quality
 Computer speed
 Algorithm complexity
27
Algorithm Analysis
 There are two types of algorithm:
 Algorithm 1 – The algorithm is easier to
understand, encode and debug.
 Algorithm 2 – The algorithm that use the
computer resource like CPU memory and speed
with efficient.
 Algorithm 1 can be used if the function / method is
only used a few times in the program.
 This is to minimize the cost and input size.
 Algorithm 2 can be used if the function / method is
used a lot of times and using a bigger input size.
 This is because it is important to minimize the cost in
developing the program.
28
Algorithm Analysis
 Example of the program:
Example 1:
total = 0;
for (int i=0; i <= n; i++)
total = total + i;
Example 2:
total = n * (n + 1)/2;
 Both algorithms are doing the same task but the
Example 1 can be understand easily while the
Example 2 is much simpler.
29
Algorithm Analysis
Example 1 
needs to execute
instruction total
for n times.
Example 2 
needs to execute
instruction total
only once.
n
total (Eg 1)
total (eg 2)
5
5
1
10
10
1
15
15
1
20
20
1
Number of
Executions
1
n
30
Algorithm Analysis
 There are 3 scenario to estimate the efficiency is using
computer resource during run time:
 Worst Case Scenario
 Best Case Scenario
 Average Case Scenario / Theta Notation
 The important of analyzing the efficiency depends on the
type of software application being developed.
 For example, the critical application such as the air traffic
control, medical system and application for army need to
have the worst case scenario analyzed.
31
Algorithm Efficiency
 Brassard and Bratley used the term algorithmics which
defines as “The systematic study of the fundamental
techniques used to design and analyze efficient algorithms.”
 If a function is linear (contains no loops) then its efficiency is a
function of the number of instructions it contains.
f(n) = efficiency
 Linear Loops
1 i=1
2 loop (i<=1000)
1 application code
2 i = i + 1
3 end loop
 Assuming i is an integer, the loop is repeated for 1000 times.
f(n) = n
32
Algorithm Efficiency
 Linear loops with the number of iterations is half the loop
factor. The higher the factor the lower the number of loops.
1 i=1
2 loop (i<=1000)
1 application code
2 i = i + 2
3 end loop
 Assuming i is an integer, the loop is repeated for 500 times.
f(n) = n / 2
33
Algorithm Efficiency
 Logarithmic Loops:
 Multiply Loops
1 i=1
2 loop (i<1000)
1 application code
2 i = i * 2
3 end loop
 Divide Loops
1 i=1
2 loop (i<1000)
1 application code
2 i = i / 2
3 end loop
 How many times has the loops repeated?
34
Algorithm Efficiency
Multiply
Divide
Loop
Value of i
Loop
Value of i
1
1
1
1000
2
2
2
500
3
4
3
250
4
8
4
125
5
16
5
62
6
32
6
31
7
64
7
15
8
128
8
7
9
256
9
3
10
512
10
1
(exit)
1024
(exit)
0
35
Algorithm Efficiency
 The number of iterations is 10 in both cases.
 The reason is that in each iteration the value of i doubles
for the multiply loop and is cut in half for the divide loop.
 The number of iterations is a function of the multiplier or
divisor, in this case is 2.
 The loop continues while the condition shown below is true.
Multiply: 2ⁿ< 1000
Divide: 1000 / 2ⁿ>= 1
n = iterations
 Iterations in loops that multiply or divide are determined by
the following formula.
f(n) = [log₂ n]
36
Algorithm Efficiency
 Nested Loops must be determined on how many iterations
each loops completes.
 The total is then the product of the number of iterations in
the inner loop and the number of iterations in the outer
loop.
 The loop continues while the condition shown below is true.
Iterations = outer loop iterations x
inner loop iterations
 There are three types of nested loops; linear logarithmic,
dependent quadratic and quadratic
37
Algorithm Efficiency
 Linear Logarithmic
1 i=1
2 loop (i<=10)
1 j=1
2 loop(j<=10)
1 application code
2 j = j * 2
3 end loop
4 i = i + 1
3 end loop
 The number of iterations in the inner loop is therefore
[log₂ 10]
38
Algorithm Efficiency
 However, because the inner loop is controlled by an outer
loop, the above formula must be multiplied by the number of
times the outer loop executes which is 10.
10 x [log₂ 10]
 Which is generalized as
f(n) = [nlog₂ n]
39
Algorithm Efficiency
 Dependent Quadratic
1 i=1
2 loop (i<=10)
1 j=1
2 loop(j<=i)
1 application code
2 j = j + 1
3 end loop
4 i = i + 1
3 end loop
40
Algorithm Efficiency

The outer loop is the same as the previous loop. However
the inner loop depends on the outer loop for one of its
factors. The number of iterations in the body of the inner
loop is calculate as shown below
1 + 2 + 3 + . . . + 9 + 10 = 55

Multiplying the inner loop by the number of times the outer
loop is executed gives the following formula for a
dependent quadratic
f(n) = n n + 1
2
41
Algorithm Efficiency
 Quadratic
1 i=1
2 loop (i<=10)
1 j=1
2 loop(j<=10)
1 application code
2 j = j + 1
3 end loop
4 i = i + 1
3 end loop
42
Algorithm Efficiency
 Each loop executes the same number of times.
 The outer loop is executed ten times. For each of its
iterations, the inner loop is also executed ten times.
10 x 10 = 100
 This formula generalizes to
f(n) = n²
43
Big O Notation
• With the speed of computers today, we are not
concerned with an exact measurement.
• Let say 2 algorithms executed:
• First algorithm: 15 iterations
• Second algorithm: 25 iterations
• Both are so fast, we cannot see the differences
• But if the second algorithm produces 1500
iterations, therefore we should consider the
used of first algorithm.
44
Big O Notation
• Since the exact measurement is not needed, Big
O notation will be used to see the result only.
• Big-O notation as in ‘on the order of’ and
written as O(n) – ‘on the order of n’.
• Thus, if an algorithm used is quadratic, its
efficiency is:
O(n2)
45
6.8 Limitations of Big-Oh Analysis
• Big-Oh is an estimate tool for algorithm analysis. It ignores the costs
of memory access, data movements, memory allocation, etc. => hard
to have a precise analysis.
Ex: 2nlogn vs. 1000n. Which is faster? => it depends on n
EASY WAY TO CALCULATE BIG O
1. Nested loops are multiplied together.
2. Sequential loops are added.
3. Only the largest term is kept, all others are
dropped.
4. Constants are dropped.
5. Conditional checks are constant (i.e. 1).
LET’S RIDE
Here we iterate 'n' times. Since
nothing else is going on inside
the loop (other then constant
time printing), this algorithm is
said to be O(n).
LET’S RIDE
Each loop is 'n'. Since the inner
loop is nested, it is n*n, thus it is
O(n^2). Hardly efficient. We can
make it a bit better by doing the
following:
LET’S RIDE
Outer loop is still 'n'. The inner
loop now executes 'i' times, the
end being (n-1). We now have
(n(n-1)). This is still in the bound
of O(n^2), but only in the worst
case.
LET’S RIDE
At first you might say that the upper bound is O(2n);
however, we drop constants so it becomes O(n).
Mathematically, they are the same since (either way) it
will require 'n' elements iterated (even though we'd
iterate 2n times).
LET’S RIDE
You wouldn't do this exact example in implementation,
but doing something similar certainly is in the realm of
possibilities.
In this case we add each loop's Big O, in this case
n+n^2. O(n^2+n) is not an acceptable answer since we
LET’S RIDE
Outer loop is 'n', inner loop is 2, this we have 2n,
dropped constant gives up O(n).
LET’S RIDE
There are n iterations, however, instead of simply
incrementing, 'i' is increased by 2*itself each run. Thus
the loop is log(n).
LET’S RIDE
This example is n*log(n). (Remember that nested
loops multiply their Big O's.)
CONCLUSION OF BIG O
• In short Big O is simply a way to measure the efficiency of an
algorithm. The goal is constant or linear time, thus the various data
structures and their implementations.
• Keep in mind that a "faster" structure or algorithm is not necessary
better.
• For example, see the classic hash table versus binary tree debate. While
not 100% factual, it often said that a a hash-table is O(1) and is therefore
better then a tree.
REFERENCE:
http://www.dreamincode.net/forums/topic/125427-determining-
Types of data structures
What we will learn???
Linear Data Structures
Because we arrange it linearly
Array
List
Stack
Queue
Non-Linear Data Structures
The data is not necessarily need to arrange in order
Graph
Trees
Operation of Data Structures
Traverse
Insert /
Add
Delete /
Remove
Merge
Sort
Search
Swap
Characteristic of Data Structures
DATA STRUCTURE
ADVANTAGES
DISADVANTAGES
Array
Quick inserts
Fast access if index known
Slow search
Slow deletes
Fixed size
Ordered Array
Faster search than
unsorted array
Slow inserts
Slow deletes
Fixed size
Stack
Last-in, first-out access
Slow access to other
items
Queue
First-in, first-out access
Slow access to other
items
Linked-list
Quick inserts
Quick deletes
Slow search
Binary Tree
Quick search
Quick inserts
Quick deletes
(If the tree remains
balanced)
Deletion algorithm is
complex
Characteristic of Data Structures
DATA
STRUCTURE
ADVANTAGES
DISADVANTAGES
2-3-4 Tree
Quick search
Quick inserts
Quick deletes
(Tree always remains
balanced)
(Similar trees good for disk
storage)
Complex to implement
Hash Table
Very fast access if key is
known
Quick inserts
Slow deletes
Access slow if key is not
known
Inefficient memory
usage
Heap
Quick inserts
Quick deletes
Access to largest item
Slow access to other
items
Graph
Best models real-world
situations
Some algorithms are
slow and very complex
DATA TYPE
Move into the next one
DATA TYPE
• The basic stuff. What do you need to have before cooking nasi
goreng?
• Nasi putih
• Perencah Adabi
• Ikan bilis
• But how much?
• Nasi putih around 600 gram
• Perencah Adabi around 30.5 gram
• 30 – 40 ikan bilis
DATA TYPE
• The basic stuff. What do you need to have before cooking nasi goreng?
• Nasi putih
• Perencah Adabi
• Ikan bilis
• But how much?
This is what we’ve called Da
• Nasi putih around 600 gram
• Perencah Adabi around 30.5 gram
• 30 – 40 ikan bilis
• Data type of a variable is the set of values that the
variable may assume.
• Basic Data Types in C++ :
int , char , double, String, Boolean, etc.
Abstract data type (adt)
Now let us look deeper
ADT
Collection of data
Set of operations on that data
Specifications of an ADT indicate : What the ADT
operations do, not how to implement them
Implementation of an ADT : Includes choosing a
particular data structure
ADT(2)
C++ and JAVA
(because of classes
system) -> ADT
Example of ADT :
Stack and Queue
Example
ADT and Data Structures?
• A Data Structure is an implementation of an ADT. That is it is a
translation of ADT into statements of a programming language.
It consists of:
• The declarations that define a variable to be of that ADT
type.
• The operations defined on the ADT(using procedures of
the programming language).
• An ADT implementation chooses a data structure to
represent the ADT
• Each data structure is built up from the basic data types of the
underlying programming language using the available data
structuring facilities , such as arrays, pointers , files , sets, etc.
Example:
• A ” Queue ” is an abstract data type which can be defined as a
sequence of elements with operations such as Enqueue(x,q),
Dequeue(q).
This can be implemented using data structures such as:
•
•
•
•
Array
Singly linked list
Doubly linked list
Circular array
Key words:
• Data Structures & Algorithms – Definition
• A data structure is an arrangement of data in a
computer's memory or even disk storage. An example of
several common data structures are arrays, linked lists,
queues, stacks, binary trees, and hash tables.
• Algorithms, on the other hand, are used to manipulate the
data contained in these data structures as in searching
and sorting. Many algorithms apply directly to a specific
data structures. When working with certain data
structures you need to know how to insert new data,
search for a specified item, and deleting a specific item.
Key words:
 Data types
◦ When we consider a primitive type we are actually referring to two things: a
data item with certain characteristics and the permissible operations on
that data
◦ The data type's permissible operations are an inseparable part of its
identity; understanding the type means understanding what operations can
be performed on it
 Example:
◦ An int in Java or C++, for example, can contain any whole-number value
from -2,147,483,648 to +2,147,483,647. It can also be used with the
operators +, -, *, and /
Key words:
 Abstract Data Type (ADT)
◦ Is a class considered without regard to its implementation.
◦ It can be thought of as a "description" of the data in the class and a list
of operations that can be carried out on that data and instructions on
how to use these operations.
◦ An end user (or class user), you should be told what methods to call,
how to call them, and the results that should be expected, but not
HOW they work.
 Consider for example the stack class.
◦ The end user knows that push() and pop() exist and how they work.
◦ The user doesn't and shouldn't have to know how push() and pop()
work, or whether data is stored in an array, a linked list, or some other
data structure like a tree.