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
- 

## 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|))$

- 

- 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
- 
- 

## Matrix Multiplication Algorithm
- 

# Lecture 3: Amortized analysis
## Best, worst, average case

## 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
#### Example

### Framework of Potential Method
- Look slide 28 for the start...

- Exmaple

# Lecture 4 - External memory algorithms and data structures

## 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)

## 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:


### Some numbers

## 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


## External Memory Algorithms (DBMS)
- The typical working pattern for algorithms:
- 
- 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

- Use indexing to do faster search.
- Indexing will be the key pointer

### Multi-level indexing

- Structure for Multi-level indexing is B-tree

### B trees for multi-level indexing


#### Searching on B trees

### B+ trees

#### Searcing on B+ trees

#### B+ trees: Insertion

#### B+ trees: node splitting

#### B+ trees: Deletion (under-full)

### R trees

### kd trees

### kdb tree

## Main memory merge sort

### Example

## External-memory Sorting
### Example - External-memory merge sort

## External two-way merge

### Example

# Lecture 5: Multithreaded algorithms

## 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.

## Work, Span, Parallelism

### Work law and span law

## Speedup

## Slackness and Parallelism

## Cheatsheet

## Goal of the multi-threaded algorithm design