Statistics
| Branch: | Revision:

root / latex / note_w11.tex @ b56a7ca2

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