Programming Basics for Logistics Algorithms: Lecture 3

Tatiana Polishchuk

Associate Professor, 

Linköping University, KTS�

http://weber.itn.liu.se/~tatpo46/

​

1

Course Overview

2

• Introduction to programming
• Variables and data types
• Algorithms and scripts
• Input/output statements
• Conditional statements
• Loops, nested loops
• Vectors
• Matrices and graphs
• Plotting: graphical functions
• Good programming practices
• Data management

​

Course Overview

3

• Introduction to programming
• Variables and data types
• Algorithms and scripts
• Input/output statements
• Conditional statements
• Loops, nested loops
• Vectors
• Matrices and graphs
• Plotting: graphical functions
• Good programming practices
• Data management

​

​

​

flashback: Lecture 2

4

Algorithms

What is algorithm? (watch video 5 min)

​

• a set of rules to be followed in calculations or other problem-solving operations, especially by a computer

​

or simply:

• a sequence of steps needed to solve a problem

​

Pseudocode

- a simplified programming language, used in program design

5

Algorithm

6

Input

Output

Calculations

A typical sequential structure. Can be more complicated inside…

​

Algorithm

7

if/else/elseif

8

• Basic flow-control, common to all languages
• MATLAB syntax is somewhat unique

IF

if cond

commands end

ELSE

if cond

commands1 else

commands2 end

ELSEIF

if cond1

commands1 elseif cond2

commands2 else

commands3 end

Conditional statement: evaluates to true or false

• No need for parentheses: command blocks are between reserved words

Switch

9

SWITCH

switch switch_expression

​

case case_expression 1

commands 1

case case_expression 2

commands 2

case case_expression 3

commands 3

... can be many of cases

otherwise (optional)

commands

end

- expression: scalar or string

- case_expressions are values

- one case at a time

​

when no cases match

​

for

10

for

n=1:100

commands

end

• for loops: use for a known number of iterations
• MATLAB syntax:

Loop variable

for i = range commands

end

• The loop variable
• Is defined as a vector
• Is a scalar within the command block
• Does not have to have consecutive values (but it's usually cleaner if they're consecutive)
• The command block
• Anything between the for line and the end

Nested for loops

11

i = 1

j = 1

j = 2

​

i = 2

j = 1 %repeat

j = 2

​

i = 3

j = 1 %repeat

j = 2

inner loop

outer loop

while

12

• The while is like a more general for loop:
• No need to know number of iterations

WHILE

​

while cond commands

end

• The command block will execute while the conditional expression is true
• Beware of infinite loops! CTRL+C?!

​

​

​

Arrays

13

What does an image look like to a computer?

14

A computer ‘sees’ an image as an array of numbers…

…. the value of each pixel represents its intensity (or colour)

We call each number a pixel (or in 3D a voxel)…

Arrays

• Matlab was originally designed to allow efficient and intuitive processing of vectors and matrices
• Understanding how to use arrays is the key to successfully working with Matlab
• Later we’ll see more on how images in Matlab are just arrays of numbers

15

1D Arrays: vectors

16

●

• row = [ 1 2 3.2 4 6 5.4 ];
• row = [ 1, 2, 4, 7, 4.3, 1.1 ];

​

●

●

1D Arrays: vectors

17

●

• col = [ 1; 2; 3.2; 4; 6; 5.4 ];

​

​

●

●

1D Arrays: vectors

18

●

○

○

○

Automatic Initialization

19

)

(1,69

• Initialize a vector of ones, zeros, or random numbers

» o=ones(1,10)

• Row vector with 10 elements, all 1

» z=zeros(23,1)

• Column vector with 23 elements, all 0

» r=rand(1,45)

• Row vector with 45 elements (uniform (0,1))

» n=nan

• Row vector of NaNs (representing uninitialized variables)

1D Arrays: Indexing and

accessing elements

20

Indexing vectors: starting from “1”

​

>> newvector=[1 3 5 7 9 3 6 9 12 15]

​

​

​

Accessing elements of the vector: vector(index) or vector(index vector)

​

>> newvector(3)

ans = 5

>> newvector(4:6)

ans = 7 9 3

>> newvector([1 10 5])

ans = 1 15 9 index vector

​

first element

1D Arrays: Concatenation

21

Add elements to the empty vector

>> myvector=[]

>> myvector = [myvector 4]

ans=

4� >> myvector = [myvector 2]

ans=

4 2

​

Can be continued as many times as needed!

1D Arrays: Concatenation

22

Similarly we can create vectors of strings or chars

​

>> myvector=['Anna', 'Olga', 'Kalle', 'Jan']

​

>> myvector = [myvector, 'Bob']

​

23

Questions?

​

​

Next: 2D Arrays = Matrices

24

2D Arrays: Matrices

• Creating:

​

• Explicitly
• A = [1 2 3 4; 5 6 7 8];
• Use a space or , for each new column
• Use ; for each new row

​

>> A =

1 2 3 4

5 6 7 8

​

• Using ‘ones’, ‘zeros’, ‘rand’, ‘randi’ etc
• A = rand(5,5);

​

25

2D Arrays: Matrices

26

>> A = zeros (5,5)

​

A =

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

​

​

​

>> B = ones (3,4)

​

B =

1 1 1 1

1 1 1 1

1 1 1 1

​

>> C = rand (2,3)

​

​

C =

​

0.5504 0.0791 0.8982

0.5963 0.5766 0.4633

​

range

2D Arrays: Matrices

• Combining other vector and matrices

​

• A = rand(2,3); B = ones(1,3); C = zeros(3,2);
• D = [ [A; B] C];

>>

D =

​

0.8147 0.1270 0.6324 0 0

0.9058 0.9134 0.0975 0 0

1.0000 1.0000 1.0000 0 0

​

​

27

A

B

C

Matrix Indexing

28

• Matrices can be indexed in two ways
• using subscripts (row and column)
• using linear indices (as if matrix is a vector)
• Matrix indexing: subscripts or linear indexing

b(1)

b(2)

b(3)

b(4)

b(1,1)

b(1,2)

b(1,1)

b(2,1)

b(1,2)

b(2,2)

Matrix Indexing

• All matrices are indexed row then column
• A(row, column)
• We can access individual elements by
• giving row and column subscripts
• b = A(2, 3); 3^rd column of the 2^nd row
• giving a single index
• b = A(10)
• We can access whole rows or columns using :
• b = A(2,:); b is 1x4, the 2^nd row of A
• c = A(:,4); c is 4x1, the 4^th column of A

​

EXAMPLE:

A = 3 3 4 7 A(2, 3) = 2

5 3 2 1 A(9) = 4

2 3 2 1 A(2,:) = [5 3 2 1]

1 3 1 1

​

​

29

A(:,4) =

7

1

1

1

​

Matrix Indexing

30

To select rows or columns of a matrix, use the :

» d=c(1,:);

» e=c(:,2);

» c(2,:)=[3 6];

% d=[12 5];

% e=[5;13];

% replaces second row of c:

c=

12 5

3 6

Matrix Indexing

• We can access specific ranges
• b = A(1, 2:4); b is 1x3, the 2^nd, 3^rd and 4^th elements of the 1^st row
• C = A(2:3,2:3); C is 2x2, the middle 4 elements of A
• D = A(2:3, [1 4]); D is 2x2, the 1^st and 4^th elements of the 2^nd and 3^rd rows

​

• When accessing arrays, ‘end’ acts a special (and very useful!) keyword that refers to the size of that dimension

>>A = rand(4,5);

• b = A(1, 2:end); b is 1x4, the 2^nd to 5^th elements of the 1^st row
• c = A(2:end-1,3); c is 2x1, the 3^rd column of the 2^nd to 3^rd rows
• d = A(1:end/2,:); d is 2x5, all columns of the first 2 rows

31

Matrix Modification

32

Modifying matrix elements assigning a new value:

​

EXAMPLE:

​

A = 3 3 4 7 A(1,2)= 13 3 13 4 7

5 3 2 1 5 3 2 1

2 3 2 1 2 3 2 1

1 3 1 1 1 3 1 1

Matrix Modification

33

Modifying matrix elements assigning a new value:

​

EXAMPLE:

​

A = 3 3 4 7 A(1,2)= 13 3 13 4 7

5 3 2 1 5 3 2 1

2 3 2 1 2 3 2 1

1 3 1 1 1 3 1 1

​

​

A = 3 3 4 7 A(:,4)= [ 5; 5; 5; 5] 3 13 4 5

5 3 2 1 5 3 1 5

2 3 2 1 2 3 2 5

1 3 1 1 1 3 1 5

​

Matrix Indexing

• We can also use indexing on the LHS of equations to assign parts of an array to an array of the same size

>> A = zeros(5,5); B = rand(4,4)

​

A =

​

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

​

>> A(1:4,1:4) = B;

​

34

B =

​

0.9953 0.4912 0.3607 0.9074

0.7076 0.4466 0.8807 0.0943

0.0806 0.4868 0.7444 0.1813

0.0433 0.1659 0.4168 0.9466

​

A =

​

0.9953 0.4912 0.3607 0.9074 0

0.7076 0.4466 0.8807 0.0943 0

0.0806 0.4868 0.7444 0.1813 0

0.0433 0.1659 0.4168 0.9466 0

0 0 0 0 0

Matrix Indexing

• We can also use indexing on the LHS of equations to assign parts of an array to an array of the same size

>> A = zeros(5,5); B = rand(4,4)

​

A =

​

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

​

>> A(3:5,4:end) = B(1:3, [1 4]);

​

35

B =

​

0.9953 0.4912 0.3607 0.9074

0.7076 0.4466 0.8807 0.0943

0.0806 0.4868 0.7444 0.1813

0.0433 0.1659 0.4168 0.9466

​

A =

​

0 0 0 0 0

0 0 0 0 0

0 0 0 0.9953 0.9074

0 0 0 0.7076 0.0943

0 0 0 0.0806 0.1813

Matrix Indexing

• We can also use indexing on the LHS of equations to assign parts of an array to an array of the same size

>> A = zeros(5,5); B = rand(4,4)

​

A =

​

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0 0 0 0

​

>> A([1 5 9]) = B([2 4 11]);

​

36

B =

​

0.9953 0.4912 0.3607 0.9074

0.7076 0.4466 0.8807 0.0943

0.0806 0.4868 0.7444 0.1813

0.0433 0.1659 0.4168 0.9466

​

A =

​

0.7076 0 0 0 0

0 0 0 0 0

0 0 0 0 0

0 0.7444 0 0 0

0.0433 0 0 0 0

Out-of-bounds indexing

• If we try and access an element using an index larger than the dimensions of an array, we get an out-of-bounds error
• A = rand(5,5);
• b = A(5,6); -> error!
• b = A(26); -> error!
• b = A(end+1,2); -> error!
• If we assign to out-of-bounds indices, Matlab automatically extends the target array
• A(5,6) = 1; A is now 5x6
• A(end+3,2) = 2; A is now 8x6
• A(:,end+1) = rand(7,1); A is now 8x7
• Negative numbers, zeros, and non-integers can never be used in indexes, either accessing or assigning!

37

Adding Elements to Matrix

38

It is not possible to add just 1 element to the matrix!

But we can add entire rows or columns:

​

EXAMPLE:

​

A = 3 3 4 A(:,4)= [1, 1, 1, 1]’ 3 13 4 1

5 3 2 5 3 2 1

2 3 2 2 3 2 1

1 3 1 1 3 1 1

​

​

A = 3 3 4 A(:,5)= [1,1,1,1]’ 3 13 4 0 1

5 3 2 5 3 2 0 1

2 3 2 2 3 2 0 1

1 3 1 1 3 1 0 1

​

Removing Elements from Matrix

39

It is not possible to remove just 1 element to the matrix!

But we can remove entire rows or columns:

​

EXAMPLE:

​

A = 3 3 4 4 A(3, : )= [ ] A = 3 13 4 4

5 3 2 4 5 3 2 4

2 3 2 3 1 3 1 1

1 3 1 1

​

B = 1 2 1 B (4) = [ ] B = 1 1 1 1 1 1 1 1

1 1 1 reshaping

1 1 1

​

​

​

Size, Length and Numel

• Size function returns the vector [#rows, #columns]:

A =

10 2 9

7 4 6

• Length function returns either # rows, or #columns, whichever is largest:

>> length(A) =

ans =

3

• Numel function returns the total number of elements in the array

>> numel(A) =

ans =

6

​

​

40

>> size(A)

ans =

2 3

​

Matrix Reshaping

41

Function reshape () changes dimension of the matrix:

>> mat = randi(100, 3, 4)

​

14 61 2 94

21 28 75 47

20 20 45 42

​

To rearrange matrix into 2x6:

​

>> reshape(mat,2,6)

​

ans =

14 20 28 2 45 47

21 61 20 75 94 42

Matrix Transpose and Rotation

42

‘ function transposes matrix = flips the matrix over its diagonal = switches the row and column indices

​

​

​

​

​

​

​

EXAMPLE:

A = 1 2 A’= 1 3 5 (A’)’ = A

3 4 2 4 6

5 6

size(A)= 3 x 2 size(A’) = 2 x 3

​

*Check other functions for flipping and rotating matrices:

rot(90), flipud, reshape

​

​

​

Next: Vector & Matrix Algebra

43

Questions?

Vector & Matrix Algebra

​

IMPORTANT: there are two types of matrix operations

​

• element-wise operations

​

• linear algebra operations

​

​

44

Vector & Matrix Algebra

Standard mathematical operators apply the rules of linear algebra

​

• if A is n x m and B is p x q
• C = A*B; is only valid when m = q (C will be n x q)

​

• A^2; means A*A, is only valid if A is square

​

45

Operators

Matrix Operations

46

●

●

○

●

​

​

=

Addition and Subtraction

Matrix Operations

47

●

●

Element-wise operations

• Sometimes it is useful to have 1D an 2D arrays that are just collections of numbers (like images!)
• We do not apply the rules of linear algebra
• We want to apply the same operation to every element

C = A.*B; means C(i,j) =A(i,j)*B(i,j)

Also C=A./B; C=A.^2

​

​

48

Element-wise functions

Element-wise operations

49

●

○

●

​

●

○

○

Element-wise functions

Matrix Operations - Examples

50

●

●

​

​

Try

​

a=[1 2 3] % row vector

b=[4;2;1] % column vector

​

>> a.*b

Error using .*

Matrix dimensions must agree.

​

a.*b , a./b , a.^b → all errors a.*b.', a./b.’, a.^(b.’) → all valid

Matrix Operations - Examples

51

Same vectors

>> a=[1 2 3] % row vector

>> b=[4;2;1] % column vector

​

​

Element-wise *

​

>> c = a.*b' % transpose b to make it row vector

c =

​

4 4 3

​

Matrix multiplication

​

>> d = a*b

​

d = 11

​

​

​

a = 1 2 3

b’ = 4 2 1

c = 4 4 3

​

a = 1 2 3

b = 4

2

1

d = 1*4 + 2*2 + 3*1 = 11

Summary

• Understanding how arrays work is the key to successful programming
• [] – square brackets create new arrays
• () – access parts of an array
• *,^ etc. perform linear algebra (matrix) operations
• .*,.^ etc. perform element-wise operations

​

Quiz from previous lecture: Arrays and Matrices

​

52

MATLAB makes arrays easy!

That’s its power!

​

​

Next: Graphs

53

Questions?

Application of Graph Theory in Google Maps (watch youtube video 4 min)

​

​

​

​

54

Introduction to Graph Theory

Graphs

• A graph is a pair (V, E), where
• V is a set of nodes, called vertices
• E is a collection of pairs of vertices, called edges
• Vertices and edges are positions and store elements
• Example:
• A vertex represents an airport and stores the three-letter airport code
• An edge represents a flight route between two airports and stores the mileage of the route

55

ORD

PVD

MIA

DFW

SFO

LAX

LGA

HNL

849

802

1387

1743

1843

1099

1120

1233

337

2555

142

Applications

• Electronic circuits
• Printed circuit board
• Integrated circuit
• Transportation networks
• Highway network
• Flight network
• Computer networks
• Local area network
• Internet
• Web
• Databases
• Entity-relationship diagram

56

Graphs: applications

57

Graphs: applications

• Can you think of other examples of graphs modelling real-world situations?
• What are the nodes? (what data is stored)
• What are the edges? (what data is stored)

​

58

2 Edge Types

• Directed edge (ARROW)
• ordered pair of vertices (u,v)
• first vertex u is the origin
• second vertex v is the destination
• e.g., a flight
• Undirected edge (no arrow)
• unordered pair of vertices (u,v)
• e.g., a flight route
• Directed graph
• all the edges are directed
• e.g., route network
• Undirected graph
• all the edges are undirected
• e.g., flight network

59

ORD

PVD

flight

AA 1206

ORD

PVD

849

miles

A road between two points

Could be one way (directed)

Or two way (undirected)

​

Could have more than one edge

(e.g. toll road and public road)

Terminology

• End vertices (or endpoints) of an edge
• U and V are the endpoints of an edge a
• Edges incident on a vertex
• a, d, and b are incident on V
• Adjacent vertices
• U and V are adjacent
• Degree of a vertex
• X has degree 5
• Parallel edges
• h and i are parallel edges
• Self-loop
• j is a self-loop

60

Terminology (cont.)

• Path
• sequence of alternating vertices and edges
• begins with a vertex
• ends with a vertex
• each edge is preceded and followed by its endpoints
• Simple path
• path such that all its vertices and edges are distinct
• Examples
• P₁=(V,b,X,h,Z) is a simple path
• P₂=(U,c,W,e,X,g,Y,f,W,d,V) is a path that is not simple (has repeated vertex W)

61

P₁

X

U

V

W

Z

Y

a

c

b

e

d

f

g

h

P₂

Terminology (cont.)

• Cycle
• circular sequence of alternating vertices and edges
• each edge is preceded and followed by its endpoints
• Simple cycle
• cycle such that all its vertices and edges are distinct
• Examples
• C₁=(V,b,X,g,Y,f,W,c,U,a,↵) is a simple cycle
• C₂=(U,c,W,e,X,g,Y,f,W,d,V,a,↵) is a cycle that is not simple

62

C₁

X

U

V

W

Z

Y

a

c

b

e

d

f

g

h

C₂

Terminology (cont.)

Edges can be assigned weights�

Weights can indicate distance, cost, relationship, other values, depending on the underlying application

​

​

Example: flight network

​

in directed network - flight id can be different for 2 directions

​

in undirected network - same value on the edge

63

ORD

PVD

flight AA 1206

ORD

PVD

849

miles

Connectivity

• A graph is connected if there is a path between every pair of vertices

​

​

• A connected component of a graph G is a maximal connected subgraph of G

64

Connected graph

Not connected graph with two connected components

Trees and Forests

• A tree is an undirected graph T such that
• T is connected
• T has no cycles

​

• A forest is an undirected graph without cycles

​

• The connected components of a forest are trees

65

Tree

Forest

Operations on Graphs

• What operations do you think we can do to a graph
• add an edge
• add a node
• Others……

66

67

Main Methods of the Graph ADT

• Vertices and edges
• are positions
• store elements
• Accessor (get) methods
• endVertices(e): an array of the two endvertices of e
• opposite(v, e): the vertex opposite of v on e
• areAdjacent(v, w): true iff v and w are adjacent
• replace(v, x): replace element at vertex v with x
• replace(e, x): replace element at edge e with x

• Update (set or mutator) methods
• insertVertex(o): insert a vertex storing element o
• insertEdge(v, w, o): insert an edge (v,w) storing element o
• removeVertex(v): remove vertex v (and its incident edges)
• removeEdge(e): remove edge e
• collection methods
• incidentEdges(v): edges incident to v
• vertices(): all vertices in the graph
• edges(): all edges in the graph

68

Implementing a Graph

• To program a graph data structure, what information would we need to store?
• For each vertex?
• For each edge?

​

69

i

j

Implementing a Graph

• What kinds of questions would we want to be able to answer (quickly?) about a graph G?
• Where is vertex v?
• Which vertices are adjacent to vertex v?
• What edges touch vertex v?
• What are the edges of G?
• What are the vertices of G?
• What is the degree of vertex v?

70

i

j

Representation

• There are different ways to represent a graph
• List of edges
• For each node – a list of adjacent nodes
• Adjacency matrix

71

72

Edge List: Pros and Cons

• advantages
• easy to loop/iterate over all edges

​

• disadvantages
• hard to tell if an edge�exists from A to B
• hard to tell how many edges�a vertex touches (its degree)

​

73

74

75

Adjacency Matrix: Pros and Cons�

• advantages
• fast to tell whether edge exists between any two vertices i and j (and to get its weight)

​

• disadvantages
• consumes a lot of memory on sparse graphs (ones with few edges)
• redundant information for undirected graphs

76

​

​

Thank you!

​

77