L01

Principles of Computer
Algorithms
Problem Solving: Main Steps
1. Problem definition
2. Algorithm design / Algorithm specification
3. Algorithm analysis
4. Implementation
5. Testing
6. [Maintenance]

04/18/2024 Principles of Computer Algorithms 2

Problem Definition
What is the task to be accomplished?
What are the time / space / speed / performance
requirements?

04/18/2024 Principles of Computer Algorithms 3

 Algorithm Design / Specifications
Algorithm: Finite set of instructions that, if followed,
accomplishes a particular task.
Describe: in natural language, pseudo-code, diagrams,
etc.
Criteria to follow:
 Input: Zero or more quantities
 Output: One or more quantities
 Definiteness: Clarity, precision of each instruction
 Finiteness: The algorithm has to stop after a finite (may be
very large) number of steps
 Effectiveness: Each instruction has to be basic enough and
feasible (can be implemented by a computer)

04/18/2024 Principles of Computer Algorithms 4

Implementation, Testing, Maintenance
Implementation
 Decide on the programming language to use
 C, C++, Lisp, Java, Perl, Prolog, assembly, etc. , etc.
 Write clean, well documented code

Test, test, test

Integrate feedback from users, fix bugs, ensure

compatibility across different versions  Maintenance

04/18/2024 Principles of Computer Algorithms 5

Algorithm Analysis
Space complexity
How much space is required
Time complexity
How much time does it take to run the algorithm

Often, we deal with estimates!

04/18/2024 Principles of Computer Algorithms 6

Space Complexity
Space complexity: the amount of memory required by an
algorithm during the execution.
 Core dumps = the most often encountered cause is “memory leaks”
– the amount of memory required larger than the memory available
on a given system
Some algorithms may be more efficient if data completely
loaded into memory
 Need to look also at system limitations
 E.g. Classify 2GB of text in various categories [politics, tourism,
sport, natural disasters, etc.] – can I afford to load the entire
collection?

04/18/2024 Principles of Computer Algorithms 7

Space Complexity
1. Fixed part: The size required to store certain
data/variables, that is independent of the size of the
problem:
- e.g. name of the data collection

2. Variable part: Space needed by variables, whose size is

dependent on the size of the problem:
- e.g. actual text
- load 2GB of text VS. load 1MB of text

04/18/2024 Principles of Computer Algorithms 8

Space Complexity
S(P) = c + S(instance characteristics)
 c = constant
Example:
void float sum ( float a[])
{
float s = 0;
for(int i = 0; i<a.length; i++) {
s+ = a[i];
}
return s;
}

04/18/2024 Principles of Computer Algorithms 9

Time Complexity
Often more important than space complexity
 space available (for computer programs!) tends to be larger and
larger
 time is still a problem for all of us

3-4GHz processors on the market

 still …
 researchers estimate that the computation of various
transformations for 1 single DNA chain for one single protein on 1
TerraHZ computer would take about 1 year to run to completion
Algorithms running time is an important issue

04/18/2024 Principles of Computer Algorithms 10

Running Time
Problem: prefix averages
 Given an array X
 Compute the array A such that A[i] is the average of elements
X[0] … X[i], for i=0..n-1
Solution 1
 At each step i, compute the element A[i] by traversing the array
X and determining the sum of its elements, respectively the
average
Solution 2
 At each step i update a sum of the elements in the array A
 Compute the element X[i] as sum/I

Big question: Which solution to choose?

04/18/2024 Principles of Computer Algorithms 11
Running time
5 ms worst-case
4 ms

3 ms
}
average-case?
best-case
2 ms

1 ms

A B C D E F G
Input

Suppose the program includes an if-then statement that may

execute or not:  variable running time
Typically algorithms are measured by their worst case
04/18/2024 Principles of Computer Algorithms 12
Experimental Approach
Write a program that implements the algorithm
Run the program with data sets of varying size.
Determine the actual running time

Problems?

04/18/2024 Principles of Computer Algorithms 13

Experimental Approach-- problems
It is necessary to implement and test the algorithm in
order to determine its running time.
Experiments can be done only on a limited set of
inputs, and may not be indicative of the running time
for other inputs.
The same hardware and software should be used in
order to compare two algorithms. – condition very
hard to achieve!

04/18/2024 Principles of Computer Algorithms 14

Use a Theoretical Approach
Based on high-level description of the algorithms,
rather than language dependent implementations
Makes possible an evaluation of the algorithms that is
independent of the hardware and software
environments
 Generality

04/18/2024 Principles of Computer Algorithms 15

Algorithm Description
 How to describe algorithms independent of a programming
language
 Pseudo-Code = a description of an algorithm that is
 more structured than usual prose but
 less formal than a programming language
 (Or diagrams)
 Example: find the maximum element of an array.
Algorithm arrayMax(A, n):
Input: An array A storing n integers.
Output: The maximum element in A.
currentMax  A[0]
for i 1 to n -1 do
if currentMax < A[i] then currentMax  A[i]
return currentMax
04/18/2024 Principles of Computer Algorithms 16
Pseudo Code
 Expressions: use standard mathematical symbols
 use  for assignment
 use = for the equality relationship
 Method Declarations: -Algorithm name(param1, param2)
 Programming Constructs:
 decision structures: if ... then ... [else ..]
 while-loops while ... do
 repeat-loops: repeat ... until ...
 for-loop: for ... do
 array indexing: A[i]
 Methods
 calls: object method(args)
 returns: return value
 Use comments
 Instructions have to be basic enough and feasible!
04/18/2024 Principles of Computer Algorithms 17
 Algorithm Examples

Example: an algorithm that finds the maximum element in a

finite sequence a1, a2, …, an
Input is a1, a2, …, an
Output is max (maximum element in the sequence
 The algorithm:
Algorithm max(a1, a2, …, an: integers)
max  a1
for i  2 to n
if max < ai then max  ai
{max is the largest element}

04/18/2024 Principles of Computer Algorithms 18

 Algorithm Examples
Another example: a linear search algorithm, that is, an
algorithm that linearly searches a sequence for a particular
element.
Algorithm linear_search(x: integer; a1, a2, …, an: integer)
location = 0;
for i  1 to n
if x = ai then location  i
{location is the subscript of the term that equals x, or is zero if x is not
found}

04/18/2024 Principles of Computer Algorithms 19

Low Level Algorithm Analysis
Based on primitive operations (low-level computations
independent from the programming language)
E.g.:
Make an addition = 1 operation
Calling a method or returning from a method = 1 operation
Index in an array = 1 operation
Comparison = 1 operation etc.
 Method: Inspect the pseudo-code and count the number
of primitive operations executed by the algorithm

04/18/2024 Principles of Computer Algorithms 20

 Example
Sequence of operations: Conditional statement :
Int x = 1; ---------- 1 operation  if-then-else statements
x = x + 2 ------------ 2 operation if (condition) { --- 1 operation
Print (x) ------------ 1 operation (S1) x = 1 --- 1 operation
total:: 4 operations }else {
(E1) y = x + 1 --- 2 operations
The time complexity of a sequence (E2) print(x) --- 1 operation
is the sum of the number of }
operation in the sequence. Here we either execute the statement S1 (body of if)
or the statements E1 and E2 (body of else)
depending on whether the condition true or false.
Thus, the complexity could be:
Either : 2 (when we execute the body of if)
Or: 4 (when we execute the body of else).

04/18/2024 Principles of Computer Algorithms 21

 Example
1: for (int i = 0; i < N; i++)
2: {
3: if (arr[i] != invalidChar)
4: {
5: arr[ptr] = arr[i];
6: ptr++;
7: }
{1+(N+1)+N}+N+N+N = 5N+2
8: }

04/18/2024 Principles of Computer Algorithms 22

Example
What is the time complexity?
//1 one time

4 operations * M (4*M + 2)*N

After finishing outer loop
(4*M + 2)*N + 2 + 1 (because of //1)
Total: 4MN + sN + 3
Complexity is O(MN) = O(N2)
04/18/2024 Principles of Computer Algorithms 23
Back to our example (slide 11)
Prefix average of an array
Solution 1 Solution 2
For i = 0 ; i<n; i++ s = X[0]
s = X[0] For i = 0; i< n; i++
For j = 1 j<= i; j++ s = s + X[i]
s = s + X[j] A[i] = s / (i + 1)
End For End For
A[i] = s / (i + 1)
End For
Solution 2 has n
Solution 1 has n2 complexity
complexity
Therefore, solution 2 is better than solution 1

04/18/2024 Principles of Computer Algorithms 24

Example
Algorithm arrayMax(A, n):
Input: An array A storing n integers.
Output: The maximum element in A.
currentMax A[0]
for i  1 to n -1 do
if currentMax < A[i] then
currentMax  A[i]
return currentMax
How many operations ?

04/18/2024 Principles of Computer Algorithms 25

Asymptotic Notation
Need to abstract further
Give an “idea” of how the algorithm performs
n steps vs. n+5 steps
n steps vs. n2 steps

04/18/2024 Principles of Computer Algorithms 26