## root / latex / note_w11.tex @ 4ca27bae

History | View | Annotate | Download (2.24 KB)

1 |
%!TEX root = note.tex |
---|---|

2 | |

3 |
%%%%%%%%%%%%%%%%%% |

4 |
% WEEK 11 |

5 |
%%%%%%%%%%%%%%%%%% |

6 |
\section{Week 11} |

7 |
\subsection{ipkg = Itsy Package Management System} |

8 |
ipkg, or the Itsy Package Management System, is a lightweight package management system designed for embedded devices that resembles Debian's dpkg. |

9 | |

10 |
opkg is the fork of ipkg |

11 | |

12 |
http://lists.openmoko.org/pipermail/devel/2008-July/000496.html |

13 | |

14 |
\subsection{Shortest Path Problems} |

15 | |

16 |
Single-source Shortest-Paths |

17 |
\begin{itemize} |

18 |
\item Dijkstra |

19 |
\begin{itemize} |

20 |
\item priority queue: $O(|V|^2)$ |

21 |
\item binary heap: $O(|E| log|V|)$ |

22 |
\item fibonacci heap: $O(|V| log|V| + |E|)$ |

23 |
\end{itemize} |

24 |
\item Bellman-Ford: $O(|V|\times|E|)$, worst case: $O(|V|^3)$ |

25 |
\end{itemize} |

26 | |

27 |
Algorithms for the All-Pairs Problem |

28 |
\begin{itemize} |

29 |
\item Iteration $O(|V|^4)$ |

30 |
\item Iteration with Doubling Up $O(|V|^3 \times log|V|$ |

31 |
\item Floyd-Warshall Algorithm: $O(|V|^3)$ |

32 |
\end{itemize} |

33 | |

34 |
\subsection{Matrix} |

35 |
\textbf{Multiplication} of $n \times n$-matrices |

36 | |

37 |
$A \otimes B = (c_{ij})$ where $c_{ij} = \oplus_{k=1}^{n} a_{ik} \otimes b_{kj}$ |

38 | |

39 |
$k$-th \textbf{power} of matrix A: |

40 | |

41 |
$A^k = (d_{ij}$ where $d_{ij} = \oplus_{r = 0}^{k - 1} a_{ir} \otimes a_{rj}, A^0 = I$ |

42 | |

43 |
\textbf{XXX} I have the feeling that the definition from the \href{https://www.iam.unibe.ch/~run/talks/2008-06-05-Bern-Jonczy.pdf}{slide} is wrong. Wolfram gave a different definition \href{http://mathworld.wolfram.com/MatrixPower.html}{here} |

44 | |

45 |
The \textbf{closure} of the matrix A: $A^{*} = \oplus_{k >= 0} A^k$ |

46 | |

47 |
\subsubsection{Other materials} |

48 |
Check out slide for ICS 6D in \texttt{reading/w11 - MatrixMultiplication}. It details how the matrix multiplication works |

49 | |

50 |
\subsection{Algebraic Path Problem (APP)} |

51 |
https://www.iam.unibe.ch/~run/talks/2008-06-05-Bern-Jonczy.pdf |

52 | |

53 |
The Algebraic Path Problem consists in performing a special unary operation, called the closure , over a square matrix with entries in a semiring [Fink, 1992] |

54 | |

55 | |

56 |
For example, Problem of computing the length of the shortest path (for all pairs): APP over graph \texttt{G} and tropical semiring \texttt{Trop}. |

57 | |

58 |
\textbf{XXX But I don't really understand...} |