Problems in this course

Matrix-vector multiplication

Input:

$(n \times m)$ matrix $A$

$m$ element vector $\vec v$

Output:

$\vec u = A \cdot \vec v$

$u[i] = \sum A [i, j]\cdot v[j]$

Matrix-matrix multiplication

Input:

$(n \times l)$ matrix $A$

$(l \times m)$ matrix $B$

Output:

$(n \times m)$ matrix $C$

$C = A \cdot B$

$C[i, j]=\sum A[i, k] \cdot B[k, j]$

Solving linear equation

Input:

matrix $A$

vector $\vec b$

Output:

$A$ must be preprocessed, such that solutions can be easily found for any $\vec b$ .

An $\vec x$ such that

$\vec b = A \cdot \vec x$

Stencil computation

Input:

$(n \times m)$ matrix $A$

Output:

Updated version of $A$ such that a convergence criteria is met

Matrix borders must be handled in a suitable way

iterate {
for all (i, j) {
A[i,j] <- (A[i-1,j] + A[i+1,j] + A[i,j-1] + A[i,j+1])/4
}
} until (convergence)

Merge and sort two arrays

Input:

Array of size $n$

Array of size $m$

Output:

Merged array of size $n+m$

Get all prefix-sums

Input:

Array of size $n$ with elements of type $S$

Associative operation $+$

Output:

$B[i]= \sum_{0 \leq j < i} A[j]$

Example

$A: 1,2,3,4,\dots$

$B: x, 1,3,6,10,15, \dots$

Sort array

Sorting a sequence of objects such as (real numbers, integers, objects with an order relation) in an array.

Graph search

Input:

$G = (V,E)$

with a start $s \in V$

Output:

computed DFS or BFS traversal of $G$ from $s$

Graph analysis:

Given undirected $G$ , find all the connected components $CC$

Given directed $G$ , find all strongly connected components $SCC$

Graph analytics

Input:

$G = (V,E)$

Output:

computed property, ie. “betweenness centrality” for all $V$