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

History | View | Annotate | Download (2.24 KB)

1 | 1bac9234 | Quynh PX Nguyen | %!TEX root = note.tex |
---|---|---|---|

2 | |||

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

4 | % WEEK 11 |
||

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

6 | \section{Week 11} |
||

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

8 | b56a7ca2 | Quynh PX Nguyen | 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...} |