1. Basic Concepts


1.1 Allocation and deallocation of memory 

int main()
{
int i, *pi;
if ( !(pi = (int *)malloc(sizeof(int))) )
{
fprintf(stderr, “Insufficient memory”);
exit(0);
}
*pi = 3;
printf(“%d\n”, *pi);
free(pi);
return 0;
} 


1.2 Algorithm Specification 

Definition: An algorithm is a finite set of instructions that, if followed, accomplishes a particular task. In addition, all algorithms must satisfy the following criteria. 
1) Input. There are zero or more quantities that are externally supplied.
2) Output. At least one quantity is produced.
3) Definiteness. Each instruction is clear and unambiguous.
4) Finiteness. If we trace out the instructions of an algorithm, then for all cases, the algorithm terminates after a finite number of steps.
5) Effectiveness. Every instruction must be basic enough to be carried out, in principle, by a person using only pencil and paper. It is not enough that each operation be definite as in 3); it also must be feasible. 

In computational theory, one distinguishes between an algorithm and a program, the latter of which does not have to satisfy the fourth condition. For example, we can think of an operating system that continues in a wait loop until more jobs are entered. 

Example 

[Selection sort] Suppose we must devise a program that sorts a set of n ≥ 1 integers.
STEP 1. From those integers that are currently unsorted, find the smallest and place it next in the sorted list.
STEP 2. Write it partially in C and partially in English 

for (i=0; i<n; i++)
{
Examine list[i] to list[n1] and suppose that
the smallest integer is at list[min];
Interchange list[i] and list[min];
} 


#include <stdio.h>
#include <stdlib.h> // rand()
#define SWAP(x, y, t) ((t)=(x), (x)=(y), (y)=(t))
void sort(int list[], int n);
int main(void)
{
int i, list[100];
for (i=0; i<100; i++) list[i] = rand() % 1000;
sort(list, i);
for (i=0; i<100; i++) printf("%d\n", list[i]);
return 0;
}
void sort(int list[], int n)
{
int i, j, min, temp;
for (i=0; i<n1; i++) {
min = i;
for (j=i+1; j<n; j++)
if (list[j]<list[min]) min = j;
SWAP(list[i], list[min], temp);
}
} 


1.3 Performance Analysis 

One of the goals of this course to develop your skills for making evaluative judgments about programs. 
1) Does the program meet the original specifications of the task?
2) Doest it work correctly?
3) Doest the program contain documentation that shows how to use it and how it works?
4) Doest the program effectively use functions to create logical units?
5) Is the program’s code readable?
6) Does the program efficiently use primary and secondary storage?
7) Is the program’s running time acceptable for the task? 
These criteria focus on performance evaluation, we can loosely divide into two distinct fields:
space complexity and time complexity. 

1.3.1 Space Complexity 

The amount of memory that it needs to run to completion. 
Fixed space requirement 
– Space requirements that do not depend on the number and size of the program’s input and outputs.
– Include the instruction space, space for simple variables, fixedsize structured variables (such as structs), and constants. 
Variable space requirement 
– The space needed by structured variables whose size depends on the particular instance, I, for the problem being solved.
– Include the additional space required when a function uses recursion. 
The total space requirement = fixed + variable 
S(P) = c + SP(I) 
– c: constant representing the fixed space requirements.
– SP(I) : the variable space requirement of a program P working on an instance I. It is represented by SP(n) if n is the only instance characteristic of the instance I. 

Example: summing a list of numbers 

Iterative function: Ssum(n) = 0 
float sum(float list[], int n)
{
int i; float tempsum = 0;
for (i=0; i<n; i++) tempsum += list[i];
return tempsum;
} 


Recursive function: Srsum(n) = 12*n bytes 
float rsum(float list[], int n)
{
if (n) return rsum(list, n1) + list[n1];
return 0;
} 


Type 
Name 
Number of bytes 
array pointer 
list[ ] 
4 
integer 
n 
4 
return address 

4 
Total per recursive call 

12 


1.3.2 Time Complexity 

The amount of computer time that it needs to run to completion.
The time, T(P) taken by a program, P,
T(P) = compile time + TP(I) 
– The compile time is similar to the fixed space component.
– TP(I): program run (or execution) time 
Machinedependent estimate of TP(I) 
– Not easy task because it
– Letting n denote the instance characteristic, we might express
TP(n) = caADD(n) + csSUB(n) + clLDA(n) + cstSTA(n)
– where are constants that refer to the time needed to perform each operation, and ADD, SUB, LDA, STA are number of additions, subtractions, loads, and stores that are performed.

Machineindependent estimate of TP(I) 
– Program step


Program Step 

Definition: A program step is a syntactically or semantically meaningful program segment whose execution time is independent of the instance characteristics. 

Step count for summing 



Step count for recursive summing 



Step count for summing 



1.4 Asymptotic Notation 

Definition: [Big “oh”] f(n) = O(g(n)) (read as “f of n is big oh g of n”) iff (if and only if) there exist positive constants c and n0 such that f(n) ≤ cg(n) for all n, n ≥ n0. 

Example 

3n+2 = O(n) 
3n+2 ≤ 4n for all n ≥ 2 
100n+6 = O(n) 
100n+6 ≤ 101n for all n ≥ 10 
10n2+4n+2 = O(n2) 
10n2+4n+2 ≤ 11n2 for all n ≥ 5 
6*2n+n2 = O(2n) 
6*2n+n2 ≤ 7*2n for all n ≥ 4 


O(1) 
a computing time is constant 
O(n) 
linear 
O(n2) 
quadratic 
O(n3) 
cubic 
O(2n) 
exponential 


The seven computing times 
– O(1), O(log n), O(n), O(n log n), O(n2), O(n3), O(2n)




1.5 Performance Measurement 

We discuss on measuring time.
There are actually two different methods for timing events in C, by using C’s standard library accessed through #include <time.h> 
Method 1: clock() 
– This function gives the amount of processor time, as the builtin type clock_t, that has elapsed since the program began running.

Method 2: time() 
– This function returns the time, measured in seconds, as the builtin type time_t.



Method 1 
Method 2 
Start timing 
start = clock(); 
start = time(NULL); 
Stop timing 
stop = clock(); 
stop = time(NULL); 
Type returned 
clock_t 
time_t 
Result in seconds 
duration =
((double)(stopstart))
/CLOCKS_PER_SEC; 
duration =
(double)
difftime(stop, start); 


Example: timing program for worstcase sorting 

O(n) vs O(n2) 
#include <stdio.h>
#define MAX_SIZE 1001
void sort(int list[], int n);
int main(void)
{
int i, n, step = 10;
int a[MAX_SIZE];
double duration;
clock_t start;
for (n=0; n<MAX_SIZE; n+=step) {
for (i=0; i<n; i++)
a[i] = ni;
start = clock();
sort(a, n);
duration = ((double)(clock()start))/CLOCK_PER_SEC;
printf(“%d\t%f\n”, n, duration);
if (n==100)
step = 100;
}
return 0;
} 

