---
# System prepended metadata

title: Algorithms and Computability Course

---

Algorithmns and Computability

[TOC]

# Algorithms and Computability Course

# Lecture 2: All-pairs Shortest Paths

### Applications of all-pairs shortest paths:
- Google Maps, FlexDanmark

### How to solve the problem efficiently?
- Repeatedly run one-to-all shortest paths |V| times.
- Repeated squaring
- The floyd-warshall algorithm

When working with all-pairs shortest path alogrithms, we represent the graph as an adjacency-matrix. Space used is $\Theta(|V|^2)$



## Relaxation
- For each vertex v in the graph, we maintain v.d
    - v.d is the estimated distance of the shorts path from s to v;
    - v.d is initalized to infinite at the beginning.
- Definition: relaxing an edge (u, v) means testing whether we can improve the shortst path distance to v found so far by going through u.
- A predecessor node is the node before the destination node in a shortest path
- The shortest path is the path from the source to the destination with the least sum of edge weights
- ![](https://i.imgur.com/b3KMhO4.png)


## One-to-all shortest path problem
- Given a graph G and a source vertex s, find shortest paths from s to the other vertices in G
- Maintain two matrices
    - Distance matrix: Contains the shortest distances
    - Predecessor matrix: contains the path
- Use **dijkstra's algorithm**
    - In the init-step, we initialise the dist form source to source to 0.
    - Then in the predessesor matrix to NIL.
    - We run the algorithm for each node, to calculate all-pairs shortest paths.
    - The running time for a single run of Dijkstra's alg. is $O(|E|*lg(|V|))$

- ![](https://i.imgur.com/fjiGGXR.png)


- If there is an negative-cycle, we need to use **Bellman-Ford algorithm**.
    - The algorithm is slower, but can handle negative-cycles in the graph.
    - Is has a running-time of $O(|V|*|E|)$, and if we need to find all-pairs, the running-time is: $O(|V|^2*|E|)$
 

## All-pairs shortest path definition
Given a weighted directed graph (or digraph) $G=(V, E)$ with a
weight function $w: E ∈ \mathbb{R}$ that maps edges to real-valued
weights, we wish to determine the **length of the shortest path**
(i.e., sum of weights) between **all pairs of vertices** in G. Here
we assume that there are no cycles with **zero or negative
weight**.


- Let $n = |V|$
- Input
    - Adjacency matrix $W = W(w_{ij})$ is an n by n matrix, where w__ij
        - 0, if i = j;
        - The weight of directed edge (i,j), if i!=j and (i,j) is in E.
        - Infinity, if i!=j and (i,j) is not in E.
- Output
    - Distance matrix $D=(d_{ij})$ is an n by n matrix where $d_{ij}$
        - the weight of a shortest path from vertex i to vertex j.
    - Predecessor matrix $P=(p_{ij})$ is an n by n matrix, where $p_{ij}$
        - Nil, if i=j or there is no path from vertex i to vertex j.
        - The rpedecessor of j on a shortest path from i.
    - The i-th row of the predecessor matrix encodes the shortest-path tree with root i.
        - One-to-all shortest path finding identifies a row of the predecessor matrix.


## Dynamic Programming
- We divide the problem into sub-problems
### Sub-problems
- We first define sub-problems for dynamic programming
- ![](https://i.imgur.com/0JIs6hd.png)
- ![](https://i.imgur.com/0uuAxTN.png)

## Matrix Multiplication Algorithm
- ![](https://i.imgur.com/rhN8d8E.png)

# Lecture 3: Amortized analysis
## Best, worst, average case
![](https://i.imgur.com/7qLGX0o.png)


## Amortized Analysis
- Just analyzing the worst-case time of a single operation may not say too much
- Amortized analysis is a worst-case analysis of a sequence of operations => We are considering the worst-case average cost per operation in a sequence of operations
- Probability is not involved in amortized analysis but is involved in average-case analysis

### Framework of Aggregate Analysis
- We do not consider the worst-case cost of each operation individually
- We consider the worst-case of a sequence of n operations, then dividing it by the number of operations, (i.e., n).
- We do not have any distribution assumption

### Framework of Accounting Method
![](https://i.imgur.com/2I37vsA.png)
#### Example
![](https://i.imgur.com/6sFqMGc.png)

### Framework of Potential Method
- Look slide 28 for the start...
![](https://i.imgur.com/9MWPmfH.png)

- Exmaple
    ![](https://i.imgur.com/EdBMJ4q.png)
    ![](https://i.imgur.com/AWUBL81.png)






# Lecture 4 - External memory algorithms and data structures
![](https://i.imgur.com/gJE3xp3.png)


## Memory Structure
- A computer system usually has a hierarchical memory structure for storage
    - E.g., CPU Register -> CPU Cache -> DRAM -> External Memory
    - Data in Cache/DRAM will be lost when power off
    - Data in external memory will be kept after power off
- In real systems, we need to cope with data that is in the external memory (e.g., hard disk drive)
![](https://i.imgur.com/6PGXq5j.png)

## Hard disk drive (HDD), magnetic disks
- Key concepts
    - Track is a circle band on the disk
    - Sector is a sector portion on the disk
    - Block is the interaction portion of track and section
- Read/Write data from/to the disk:
    - Seek with the head
    - Wait while the necessary sector rotates under the head
    - Transfer the data
    - block address = [track number, sector number]
- Inside a block, data is indexed by offset
    - E.g., 512 bytes in a block: Offeset 0-511:

![](https://i.imgur.com/07IeCl7.png)


### Some numbers
![](https://i.imgur.com/pAKnOMr.png)

## SSD
- The same, although to less extent is true for flash-based solid-state drives (SSDs):
    - missed something here??

## External Memory Model
- Two principal components of the running time analysis:
    - Not only, the CPU time, i.e., the computing time
    - But also, and more importantly, the number of disk page accesses, i.e., the number of I/O

![](https://i.imgur.com/kxuN31d.png)

## External Memory Algorithms (DBMS)
- The typical working pattern for algorithms:
- ![](https://i.imgur.com/o5uZnv9.png)
- If the object referred to by x resides on disk, DiskRead(x) needs to read object x into main memory before we can access or modify x.
- If the object referred to by x is already in main memory, DiskRead(x) does nothing and does not incur another time disk access.

## Indexing
![](https://i.imgur.com/IrrxybJ.png)

- Use indexing to do faster search.
- Indexing will be the key pointer
![](https://i.imgur.com/ZKjT4fZ.png)


### Multi-level indexing
![](https://i.imgur.com/R8cKyWo.png)

- Structure for Multi-level indexing is B-tree

### B trees for multi-level indexing
![](https://i.imgur.com/XD9zHnU.png)

![](https://i.imgur.com/xV1Sohg.png)

#### Searching on B trees
![](https://i.imgur.com/OU5RVoj.png)

### B+ trees
![](https://i.imgur.com/kVyAkxW.png)

#### Searcing on B+ trees
![](https://i.imgur.com/5sKcHJI.png)

#### B+ trees: Insertion
![](https://i.imgur.com/V2kHAHm.png)

#### B+ trees: node splitting
![](https://i.imgur.com/EHXnOiD.png)

#### B+ trees: Deletion (under-full)
![](https://i.imgur.com/7qAbCjl.png)

### R trees
![](https://i.imgur.com/tcYB9Ki.png)

### kd trees
![](https://i.imgur.com/fz35ooX.png)
![](https://i.imgur.com/8PA96PX.png)

### kdb tree
![](https://i.imgur.com/pN3GQWS.png)
![](https://i.imgur.com/IXGgd0G.png)

## Main memory merge sort
![](https://i.imgur.com/rGb7KMt.png)

### Example
![](https://i.imgur.com/eOKkG2M.png)

## External-memory Sorting
![](https://i.imgur.com/GWSrFlc.png)
![](https://i.imgur.com/Z6r3mzG.png)
### Example - External-memory merge sort 
![](https://i.imgur.com/sF9led2.png)
![](https://i.imgur.com/yO0xstD.png)

## External two-way merge
![](https://i.imgur.com/RdbUNHb.png)

### Example
![](https://i.imgur.com/0jkj9t1.png)


# Lecture 5: Multithreaded algorithms
![](https://i.imgur.com/1lsxuW8.png)


## Parallel computers
- Computers with multiple processing units
    - Chip multiprocessors/low price
        - A single multi-core chip has multiple processing cores
    - Clusters /intermediate price
        - Individual computers that are connected with a dedicated network.
    - Supercomputers / high price
        - Combination of custom architectures and custom networks to deliver the highest performance.
- Memory models
    - Shared memory: all processors can access any location of memory.
    - Distributed memory: where each processor has a private memory.
    - No agreement on a single architectural model for parallel computers so far.

## Static vs dynamic threading
- Static threading
    - Each thread maintains an associated program counter and executes code independently of the other threads.
    - Threads persist for the duration of a computation
    - Directly using static threading is difficult and error-prone.

- Dynamic threading
    - Specify parallelism in applications without worrying implementation details.
    - A concurrency platform's scheduler does communication, load balancing, etc.
    - Nested parallelism and parallel loops.
        ![](https://i.imgur.com/rTiSA3O.png)

## Work, Span, Parallelism
![](https://i.imgur.com/AdoHchm.png)


### Work law and span law
![](https://i.imgur.com/gm57t6G.png)

## Speedup
![](https://i.imgur.com/iIWkvYJ.png)

## Slackness and Parallelism
![](https://i.imgur.com/FdMTsNb.png)

## Cheatsheet
![](https://i.imgur.com/Q96mZEq.png)
![](https://i.imgur.com/sGi2JfJ.png)

## Goal of the multi-threaded algorithm design
![](https://i.imgur.com/d1mk1mA.png)



