Lecture 1

Introduction

1
Introduction
 A program is written in order to solve a problem
 A solution to a problem actually consists of two things:
 A way to organize the data
 Sequence of steps to solve the problem
 The way data are organized in a computers memory is said
to be Data Structure and the sequence of computational
steps to solve a problem is said to be an algorithm
 A famous quote:
 Program = Algorithm + Data Structure.
 Hence for an “efficient” programs, one has to use
efficient algorithm and data structures

2
Cont…
 How many cities are there with more than 250,000
people ?
 How many people in Ethiopia make over 100,000 birr per
year?
 To answer questions like these, it is not enough to have
the necessary information.
 We must organize that information in a way that allows us to
find the answers in time to satisfy our needs.
In this course, we will look at:
 Algorithms
 Sequence of steps the needs to be followed to solve problems
 Data structures
 A means for efficiently storing, accessing, and modifying data

3
 Algorithm Design
 You have a problem to solve
 Analyze the problem and identify the requirements
 Design an efficient algorithm
 Use good data structures
 Show that your algorithm works!
 Prove its correctness
 Study the efficiency of your algorithm
 Run time
 Storage required

 For a problem given we might come up with different

algorithms
4
Example
• Two algorithms for computing the Factorial
• Which one is better?

2)
1) int factorial (int n)
int factorial (int n) {
{ if (n<=1) return 1;
if (n <= 1) return 1; else {
else fact = 1;
return n * factorial(n-1); for (k=2; k<=n; k++)
} fact *= k;
return fact;
}
5
 Data types ,Abstract data type, and Data
Structures
 A data type is a classification of various types of data
such as integer and real that determines
 The possible values for that type
 The operation that can be done on values of that type
 The way values of that data can be stored
 Example: int type
 Represents 4byte of integer
 Allows operation such as addition and subtraction

6
 Abstract data type
 Any type that does not specify an implementation is
an abstract data type
 Theoretical entities to formally describe type system of
programming languages
 ADT can be implemented by specific data
types/structures
 For example stack ADT can be implemented as
 Array
 Linked list

7
 An ADT for a list of integers might specify the following
operations:
 Insert a new integer at a particular position in the list.
 Return true if the list is empty.
 Reinitialize the list.
 Return the number of integers currently in the list.
 Delete the integer at a particular position in the list.
 From this description, the input and output of each
operation should be clear,
 but the implementation for lists has not been specified.

8
 Data structure
 A data structure is an actual implementation of a
particular abstract data type
 In the most general sense, a data structure is any data
representation and its associated operations.
 Example, int and float can be viewed as simple data structures
 More typically, a data structure is meant to be an
organization or structuring for a collection of data items
 Example, List of integers stored in an array
 Goal is organizing data in a computer so that it can be used
efficiently

9
How to select a good data structure ?
 There are different ways to organize data in
computer
 Different data structures
 However, each data structure has associated costs
and benefits(trade-offs)
 There is no ultimate data structure...
 The choice depends on our requirements

10
Cont…
 When selecting a data structure to solve a problem, you
should follow these steps.
 1. Analyze your problem to determine the basic
operations that must be supported. Examples
 inserting a data item into the data structure,
 deleting a data item from the data structure, and
 finding a specified data item.
 2. Quantify the resource constraints for each operation.
 3. Select the data structure that best meets these
requirements.

11
Algorithms
 An algorithm is a well-defined computational procedure that
takes some value or a set of values as input and produces
some value or a set of values as output.
 Data structures model the static part of the world. They are
unchanging while the world is changing.
 In order to model the dynamic part of the world we need to
work with algorithms.
 Algorithms are the dynamic part of a program’s world model.
 An algorithm transforms data structures from one state to
another state in two ways:
 An algorithm may change the value held by a data structure
 An algorithm may change the data structure itself

12
Algorithms
 The quality of data structure and algorithms is
determined by their ability to work together well.

 Correct data structures lead to simple and efficient

algorithms and correct algorithms lead to accurate and
efficient data structures

13
Properties of Algorithm
 Finiteness
 Definiteness
 Sequence
 Feasibility
 Correctness
 Language Independence
 Completeness
 Effectiveness
 Efficiency
 Generality

14
Algorithm Analysis Concepts
 Algorithm analysis refers to the process of determining the amount of
computing time and storage space required by different algorithms
 Computing Resources
 Running time (Most precious)
 Memory usage
 Communication bandwidth etc
 Why need algorithm analysis ?
 Writing a working program is not good enough
 The program may be inefficient!

 If the program is run on a large data set, then the running time becomes an
issue
 Goal is to pick up an efficient algorithm for the problem at hand
15
Cont’d…
 Two approaches to measure algorithms efficiency
 Empirical
 Implement the algorithms and
 Trying them on different instances of input
 Use/plot actual clock time
 Theoretical
 Determine quantity of resource required mathematically
needed by each algorithms (execution time, memory space)
 It is applicable

16
Drawbacks of empirical methods
 It is difficult to use actual clock because clock time varies
based on
 Specific processor speed
 Current processor load
 Specific data for a particular run of the program
 Input size
 Input properties
 Programming language (C++, java, python …)
 The programmer (You, Me, Billgate …)
 Operating environment/platform (PC, sun, smartphone etc)
 Therefore, it is quite machine dependent

17
Example
 Problem: Need to multiply two positive integers a and b
 Algorithm 1: Multiply a and b
 Algorithm 2:
 V = a, W = b
 While W > 1
 V =V + a;
 W=W-1
 Output V
 First algorithm has 1 multiplication.
 Second has b additions and subtractions.
 For some computer architectures, 1 multiplication is more expensive
than 2 additions and subtractions.
 Ideally, we would like to program all choices and run all of them in the
machine we are going to use and find which is efficient!-Very difficult

18
Machine independent analysis
 Efficiency of an algorithm is measured in terms of the number of
basic operations it performs.
 Not based on actual time-clock
 We assume that every basic operation takes constant time.
 Arbitrary time
 Examples of Basic Operations:
 Single Arithmetic Operation (Addition, Subtraction, Multiplication)
 Assignment Operation
 Single Input/Output Operation
 Single Boolean Operation
 Function Return
 We do not distinguish between the basic operations.
 Examples of Non-basic Operations are
 Sorting, Searching.

19
Examples: Count of Basic Operations T(n)

 Sample Code
int count()
{
Int k=0;
cout<< “Enter an integer”;
cin>>n;
for (i = 0;i < n;i++)
k = k+1;
return 0;
}

9
Examples: Count of Basic Operations T(n)
Count of Basic Operations
Sample Code (Time Units)
int count()
{
 1 for the assignment statement: int k=0
Int k=0;
cout<< “Enter an integer”;  1 for the output statement.

cin>>n;  1 for the input statement.

 In the for loop:
for (i = 0;i < n;i++)  1 assignment, n+1tests, and n increments.
k = k+1;  n loops of 2 units for an assignment, and an addition.
return 0;  1 for the return statement.
}
 T (n) = 1+1+1+(1+n+1+n)+2n+1 = 4n+6

10
Examples: Count of Basic Operations T(n)
int total(int n)
{
Int sum=0;
for (inti=i;i<=n;i++)
sum=sum+i;
return sum;
}

11
Examples: Count of Basic Operations T(n)
Count of Basic Operations
Sample Code (Time Units)

int total(int n)
{
 1 for the assignment statement: int sum=0
Int sum=0;
 In the for loop:
for (inti=i;i<=n;i++)  1 assignment, n+1tests, and n increments.
sum=sum+i;  n loops of 2 units for an assignment, and an
return sum; addition.
 1 for the return statement.
}

 T (n) = 1+ (1+n+1+n)+2n+1 = 4n+4

12
Examples: Count of Basic Operations T(n)
void func()
{
Int x=0;
Int i=0;
Int j=1;
cout<< “Enter an Integer value”;
cin>>n;
while (i<n){
x++;
i++;
}
while (j<n)
{
j++;
}
}

13
Examples: Count of Basic Operations T(n)

Sample Code Count of Basic Operations (Time Units)

void func()
{
Int x=0;  1 for the first assignment statement: x=0;
Int i=0;  1 for the second assignment statement: i=0;
Int j=1;  1 for the third assignment statement: j=1;
cout<< “Enter an Integer value”;  1 for the output statement.
cin>>n;  1 for the input statement.
while (i<n){  In the first while loop:
x++;  n+1tests
i++;  n loops of 2 units for the two increment (addition)
} operations
while (j<n)
 In the second while loop:
{
 n tests
j++;
 n-1 increments
}
 T (n) = 1+1+1+1+1+n+1+2n+n+n-1 = 5n+5
}

14
Examples: Count of Basic Operations T(n)
 Sample Code
int sum (int n)
{
int partial_sum= 0;
for (int i = 1; i <= n; i++)
partial_sum= partial_sum+ (i * i * i);
return partial_sum;
}

15
Examples: Count of Basic Operations T(n)

Sample code Count of Basic Operations (Time Units)

int sum (int n)

{
int partial_sum= 0;  1 for the assignment.
for (int i = 1; i <= n; i++)  1 assignment, n+1tests, and n increments.
partial_sum= partial_sum+ (i * i * i);  n loops of 4 units for an assignment, an
addition, and two multiplications.
return partial_sum;
 1 for the return statement.
}
 T (n) = 1+(1+n+1+n)+4n+1 =
6n+4

16
Simplified Rules to Compute Time Units
 for Loops:
 In general, a for loop translates to a summation. The index and
bounds of the summation are the same as the index and
bounds of the for loop.

𝑁
for ( int i = 1; i <= N; i++) { 𝑖=1 2=2N
sum = sum+i;
}

17
Simplified Rules to Compute Time Units
 Nested Loops:

𝑁 𝑀
for ( int i = i; i <= N; i++) { 𝑖=1 𝑗=1 3𝑀 =3MN
for ( int j = 1; j <= M; j++) {
sum = sum+i+j;
}
}

18
Simplified Rules to Compute Time Units
 Consecutive Statements

for ( int i = 1; i <= N; i++) {

sum = sum+i;
}
𝑁 𝑁 𝑁
| 𝑖=1 2| +| 𝑖=1 𝑗=1 3| = 2𝑁 + 3𝑁2
for ( int i = 1; i <= N; i++) {
for ( int j = 1; j <= N; j++) {
sum = sum+i+j;
}
}

19
Simplified Rules to Compute Time Units
 Conditionals:
 If (test) s1 else s2: Compute the maximum of the
running time for s1 and s2.

if (test == 1) {
for ( int i = 1; i <= N; i++) {
sum = sum+i;
}}
else for ( int i = 1; i <= N; i++) {
for ( int j = 1; j <= N; j++) {
sum = sum+i+j;
}}

20
Example: Computation of Run-time
 Suppose we have hardware capable of executing 106
instructions per second. How long would it take to
execute an algorithm whose complexity function was T
(n) = 2n2 on an input size of n =108?

21
Example: Computation of Run-time
 Suppose we have hardware capable of executing 106
instructions per second. How long would it take to
execute an algorithm whose complexity function was T
(n) = 2n2 on an input size of n =108?

The total number of operations to be performed would be T(108):

T(108) = 2*(108)2 =2*1016
The required number of seconds would be given by
T(108)/106 so:
Running time = 2*1016/106 = 2*1010
The number of seconds per day is 86,400 so this is about 231,480 days
(634 years).

22
Order of Growth and Asymptotic Analysis
 Suppose an algorithm for processing a retail store’s inventory takes:
 10,000 millisecondsto read the initial inventory from disk, and then
 10 millisecondsto process each transaction (items acquired or sold).
 Processing n transactions takes (10,000 + 10 n) milliseconds.
 Even though 10,000 >> 10, the "10 n" term will be more important if the
number of transactions is very large.
 We also know that these coefficients will change if we buy a faster
computer or disk drive, or use a different language or compiler.
 we want to ignore constant factors (which get smaller and smaller as technology
improves)
 In fact, we will not worry about the exact values, but will look at “broad
classes" of values.

23
 To compare two algorithms with running times
f(n) and g(n), we need a rough measure that
characterizes how fast each function grows.
 Hint: use rate of growth
 Compare functions in the limit, that is,
asymptotically!
(i.e., for large values of n)

24
 Rate of Growth
 Consider the example of buying elephants and goldfish:
Cost: cost_of_elephants + cost_of_goldfish
Cost ~ cost_of_elephants (approximation)
 The low order terms in a function are relatively
insignificant for large n
n4 + 100n2 + 10n + 50 ~ n4
i.e., we say that n4 + 100n2 + 10n + 50 and n4 have the same
rate of growth
More Examples:
 fB(n)=n2+1 ~ n2
 fA(n)=30n+8 ~ n
25
Visualizing Orders of Growth
 On a graph, as
you go to the
right, a faster
growing

Value of function 
function fA(n)=30n+8
eventually
becomes
larger...
fB(n)=n2+1

Increasing n 

26
Order of Growth
 Let there be n inputs.
 If an algorithm needs n basic operations and another needs 2n
basic operations, we will consider them to be in the same
efficiency category.
 However, we distinguish between exp(n),n, log(n)

27
Asymptotic Notation
 Big-Oh Notation
 The Big-Oh Notation-is a way of comparing algorithms
and is used for computing the complexity of algorithms;
i.e., the amount of time that it takes for computer
program to run.
 It’s only concerned with what happens for a very large value of
n.

28
Asymptotic notations
 Big-Oh Notation

29
Big-O Visualization
 O(g(n)) is the set
of functions with
smaller or same order
of growth as g(n)
Big-O
 Demonstrating that a function f(n) is in big-O of a
function g(n) requires that we find specific constants c
and no for which the inequality holds.
 The following points are facts that you can use for Big-Oh
problems:
 1<= n for all n >= 1
 n <= n2 for all n >= 1
 2n <= n! for all n >= 4
 log2n <= n for all n >= 2
 n <= nlog2n for all n >= 2

31
Examples
 f(n) = 10n + 5 and g(n) = n. Show that f(n) is in O(g(n)).
 To show that f(n) is O(g(n)) we must show constants c and no
such that
 f(n) <= c.g(n) for all n >= no
 Or 10n + 5 <= c.n for all n >= no
 Try c = 15. Then we need to show that 10n + 5 <= 15n
 Solving for n we get: 5 < 5n or 1 <= n.
 So f(n) =10n + 5 <= 15.g(n) for all n >= 1.
 (c = 15, no = 1).

32
Examples
 2n2 = O(n3): 2n2 ≤ cn3  2 ≤ cn  c = 1 and n0= 2

 n2 = O(n2): n2 ≤ cn2  c ≥ 1  c = 1 and n0= 1

 1000n2+1000n = O(n2):

1000n2+1000n ≤ 1000n2+ n2 =1001n2 c=1001 and n0 = 1000

 n = O(n2): n ≤ cn2  cn ≥ 1  c = 1 and n = 1

0

33
More Examples
 Show that 30n+8 is O(n).
 Show c,n0: 30n+8  cn, n>n0 .
 Let c=31, n0=8. Assume n>n0=8. Then
cn = 31n = 30n + n > 30n+8, so 30n+8 < cn.

34
Big-O example, graphically
 Note 30n+8 isn’t
less than n
anywhere (n>0).
cn =
 It isn’t even
31n

Value of function 
30n+8
less than 31n
everywhere.
 But it is less than 30n+8
31n everywhere to
the right of n=8.
n
O(n)
n>n0=8 
Increasing n 

35
No Uniqueness
 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 = 5 and c = 101 is a solution

 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
36
Implication of Big-Oh notation
 We use Big-Oh notation to say how slowly code might
run as its input grows.
 Suppose we know that our algorithm uses at most
O(f(n)) basic steps for any n inputs, and n is sufficiently
large, then we know that our algorithm will terminate
after executing at most constant times f(n) basic steps.
 We know that a basic step takes a constant time in a
machine.
 Hence, our algorithm will terminate in a constant times
f(n) units of time, for all large n.

37
 End of Lecture Two

38