* Data Structures & Algorithms
:PROPERTIES:
:ANKI_DECK: soft-eng::dsa
:END:

** How many digits are there (at maximum) for a number N?          :dasgupta:
   :PROPERTIES:
   :ANKI_NOTE_TYPE: Basic
   :ANKI_NOTE_ID: 1763087705421
   :ANKI_NOTE_HASH: 2183103fc06e8c6f34b4550861902c91
   :END:

\[\mathcal{O}(\log_b(N))\]

** Front                                                                :epi:
   :PROPERTIES:
   :ANKI_NOTE_TYPE: Basic
   :ANKI_PREPEND_HEADING: nil
   :ANKI_NOTE_ID: 1763628836304
   :ANKI_NOTE_HASH: 739b8faa883668a2c00dfc46e36dd762
   :END:


What does =x & ~(x-1)= do?

Where =&= is bitwise _and_ and =~= is _not_.

*** Back

Isolates the lowest bit that is 1 in $x$.


** Rank the following time complexities from fastest to slowest for large $n$: :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_PREPEND_HEADING: t
:ANKI_NOTE_ID: 1763361368371
:ANKI_NOTE_HASH: 82439a567bf608d06c483cb991e9a4d9
:END:


1. $\sqrt{n}$
2. $\log(n)$
3. $n!$
4. $2^n$
5. $n\log(n)$
6. $n^2$
7. $n$

*** Back

\[ \log(n) \ll \sqrt{n} \ll n \ll n\log(n) \ll n^2 \ll 2^n \ll n!\]

   
** FFT recurrence relation and time complexity?                    :dasgupta:
   :PROPERTIES:
   :ANKI_NOTE_TYPE: Basic
   :ANKI_NOTE_ID: 1763087705434
   :ANKI_NOTE_HASH: e43fe0ac466a016d6251f88890c627df
   :END:

\[T(n) = 2T\left(\frac{n}{2}\right)+\mathcal{O}(n) = \mathcal{O}(n\log(n))\]

** Recurrence relation and time complexity of Strassen's multiplication algorithm? :dasgupta:
   :PROPERTIES:
   :ANKI_NOTE_TYPE: Basic
   :ANKI_NOTE_ID: 1763087705439
   :ANKI_NOTE_HASH: 5445cf21f09fedb2edd6c85a5379d513
   :END:

\[T(n) = 7T(\frac{n}{2})+\mathcal{O}(n^2)\]
\[\mathcal{O}(n^{\log_{2}7})\approx\mathcal{O}(n^{2.81})\]

** Recurrence relation for mergesort? Corresponding time complexity? :dasgupta:
   :PROPERTIES:
   :ANKI_NOTE_TYPE: Basic
   :ANKI_NOTE_ID: 1763087705444
   :ANKI_NOTE_HASH: 8ff09837b8e5387fd7726b41d1a72c89
   :END:

\[T(n) = 2T(\frac{n}{2})+\mathcal{O}(n)\]
by the master theorem *case 2*, with $a=2$, $b=2$ and $d=1$:
\[\mathcal{O}(n\log(n))\]

** Recurrence relation for binary search? Correspondingly, what is the time complexity? :dasgupta:
   :PROPERTIES:
   :ANKI_NOTE_TYPE: Basic
   :ANKI_NOTE_ID: 1763087705449
   :ANKI_NOTE_HASH: ccd361effc2d5b101ee2f330ff031a71
   :END:

\[T(n) = T(\left\lceil\frac{n}{2}\right\rceil)+\mathcal{O}(1)\]
by the master theorem *case 2*, with $a=1$, $b=2$ and $d=0$:
\[\mathcal{O}(\log(n))\]

** What is the Master Theorem?                                     :dasgupta:
   :PROPERTIES:
   :ANKI_NOTE_TYPE: Basic
   :ANKI_NOTE_ID: 1763087705454
   :ANKI_NOTE_HASH: b3512053d79ab13e09a163be7f64820b
   :END:

Hint: General form is:
\[T(n) = aT\left(\left\lceil\frac{n}{b}\right\rceil\right) + \mathcal{O}(n^d)\]

\[    T(n) = \begin{cases}
    \mathcal{O}(n^d), & \text{if $d>\log_{b}a$ }\\
    \mathcal{O}(n^d \log(n)), & \text{if $d=\log_{b}a$ }\\
    \mathcal{O}(n^{\log_{b}(a)}), & \text{if $d<\log_{b}a$ }
    \end{cases}\]

** When do we classify a graph as being sparse? What about dense?  :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763363309458
:ANKI_NOTE_HASH: 3f1d6063b3a23492daa7ae05bcda196e
:END:

'dense': when $|E| \rightarrow |V|^2$ (the maximum number of edges)
'sparse': when $|E|\approx |V|$



** What are the maximum number of edges in a Graph $(V,E)$?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763522846736
:ANKI_NOTE_HASH: 1ab2f14921bc53b7b3b59a0b0703eb21
:END:

$|E|=|V|^2$

** What are the two representations of a graph? Which one is better for which problem? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763363309476
:ANKI_NOTE_HASH: 54430e5f74bf5a2634fcfc50ee9c866d
:END:

*adjacency list* and *adjacency matrix*. good for /sparse/ and /dense/ graph problems respectively



** When is an adjacency list a good idea for graph representation? When is an adjacency matrix? What are the trade-offs? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763363309489
:ANKI_NOTE_HASH: 5d616b6af203287cef3f933c4eca7e58
:END:

adjacency matrix:
- requires $\mathcal{O}(n^2)$ space -- it is array-based after all.
- is therefore wasteful if there are not many edges
- $\mathcal{O}(1)$ look-up "checking-edge"
adjacency list:
- $|V|$ linked lists. one per vertex. $\mathcal{O}(|E|)$ space. each edge in one linked list.
- $\mathcal{O}(|V|)$ time ?



** Time complexity of Depth First Search?                          :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763363309494
:ANKI_NOTE_HASH: 873f447be2c314900fce69d567bf2305
:END:

linear-time. two-steps: $\mathcal{O}(|V|)$ and $\mathcal{O}(|E|)$; therefore $\huge \mathcal{O}(|V| + |E|)$.

by linear, we mean in the size of the input. recall a graph $G = (V, E)$.

it takes this long to even read the adjacency list, so DFS is a great algorithm.

** When is a graph connected? Computationally, how can we check when a graph $(V,E)$ is connected? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763363309499
:ANKI_NOTE_HASH: b0fefb2b79a4309db18d25c26531bdeb
:END:

if there is a path between any pair of vertices.

be careful about directed / undirected graphs. directed will require an explicit connection in the opposing direction.

computationally, we can use Depth First Search and if the visited set is equal to the set of vertices then the graph is connected.


** What kind of graphs are guaranteed to have a topological ordering? i.e. are linearisable? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763363309502
:ANKI_NOTE_HASH: bee1ca88c103c317d0cd613c3d2d2f32
:END:

Directed Acyclic Graphs. i.e. dags.

** What is the relationship between acyclicity, linearisability (topological orderings) and the absence of back edges (of the DFS tree) in a graph? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763363309506
:ANKI_NOTE_HASH: 30391c3b4d65bd5d5b6cb241d5fdacf9
:END:

they are all equivalent!

** What does dag stand for in Graph Theory? What are they useful for modelling? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763363309509
:ANKI_NOTE_HASH: 2ab9313d3a8fd0ce5a26e7827215e264
:END:

Directed Acyclic Graph.

good for modelling, causalities, hierarchies and temporal dependencies.

** What is an acyclic graph? Computationally, what method can we use to test acyclicity? What is the time-complexity of this method? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763363309512
:ANKI_NOTE_HASH: a7bf527e11d88d995dc04e177f406205
:END:

cycle: $v_0 \rightarrow v_1 \rightarrow \ldots \rightarrow v_k \rightarrow v_0$

acyclic is a graph without such cycles.

can be tested for in linear time with a single DFS. we know there is a cycle if there exists any back-edges to ancestors in the DFS tree.


** What is the time complexity of Breadth First Search? Is it Linear? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763363309517
:ANKI_NOTE_HASH: fc4a55196674daae7f374983e57f8fc2
:END:

Yes, linear: $\mathcal{O}(|V|+|E|)$

each vertex is put on the queue once. $2|V|$ queue operations. we look at each edge once for directed, and twice for undirected.

** Can BFS be used to find shortest paths? If so, what are the limitations and how can they be overcome? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763363309522
:ANKI_NOTE_HASH: cca5ae4cb0bc132ac8e33d725efb2bfe
:END:

Yes, but only unit length. We can handle more complex graphs by adding dummy nodes. But this causes BFS to calculate distances to nodes we don't care about. Use Dijkstra instead.


** How is Dijkstra's algorithm related to the BFS algorithm?       :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763363309526
:ANKI_NOTE_HASH: 95ac6a2d29e1c7be00a416a8709f058d
:END:

BFS uses a naked, regular queue.

Dijkstra uses a priority queue (usually implemented with a heap). This allows us to take edge lengths into account. BFS can only find shortest paths on graphs with unit-length edges.


** What are the time complexities for Dijkstra's algorithm with array and binary heap implementations of the binary queue? When should you prefer one over the other? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763363309529
:ANKI_NOTE_HASH: cc6330a868e16f3201d5aac98b9352ec
:END:

$\mathcal{O}(|V|^2)$ -- array -- dense $|E| = \Omega(|V|^2)$

$\mathcal{O}((|V|+|E|)\log|V|)$ -- binary heap -- sparse. use when $|E| < \frac{|V|^2}{\log|V|}$

** Does Dijkstra's algorithm work for negative weights? If not, what is the alternative? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763363309532
:ANKI_NOTE_HASH: 7052246d1c32da2fb97f0be16589338d
:END:

It does _not_.

Use the *Bellman-Ford* algorithm.


** What happens when you look for shortest paths in a Graph with negative cycles? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763363309535
:ANKI_NOTE_HASH: 9a0af62f865d22eadc3e4b736e9f9b3d
:END:

it breaks the algorithm. it does not make sense to find the shortest path in such a garph, because you can just "farm" lesser and lesser weights by looping through the negative cycle.

** What are the two classes of graphs that cannot have negative cycles? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763363309538
:ANKI_NOTE_HASH: cb61334abd7190c3326457c9e0373602
:END:

1. graphs without negative edges, and;
2. graphs without cycles


** What is the time complexity of single-source shortest path in a directed acyclic graph? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763363309542
:ANKI_NOTE_HASH: 37b122ba5885ec648f16d16a784f0f2d
:END:

$\mathcal{O}(|V|+|E|)$ (probably)

1. linearise with DFS
2. visit vertices in sorted order, updating edges out of each. 


** What is a binary heap?                                          :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763380484819
:ANKI_NOTE_HASH: e680c6d51c97604b88773ff8630eb204
:END:

a complete binary tree with the additional constraint that each parent node is _less than_ or equal to its children nodes.

for max-heap it is 'greater-than or equal-to'.

importantly, the root always contais the smallest / largest element.

\[
\begin{tikzpicture}[scale=1,transform shape,very thick,
  level/.style={sibling distance=70mm/#1}]
\tikzstyle{vertex}=[draw,fill=black!15,circle,minimum size=18pt,inner sep=0pt]
\node [vertex] (r){$-4$}
  child {
    node [vertex] (a) {$2$}
    child {
      node [vertex] {$5$}
      child {
        node [vertex] {$6$}
        child {node [vertex] {$20$}}
      }
      child {
        node [vertex] {$9$}
      }
    }
    child {
      node [vertex] {$3$}
      child {node [vertex] {$19$}}
      child {node [vertex] {$7$}}
    }
  }
  child {
    node [vertex] {$-3$}
    child {
      node [vertex] {$8$}
      child {node [vertex] {$17$}}
      child {node [vertex] {$17$}}
    }
    child {
      node [vertex] {$2$}
      child {node [vertex] {$11$}}
      child {node [vertex] {$17$}}
    }
  };
\end{tikzpicture}
\]


** What is a binary search tree?                                   :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763380271817
:ANKI_NOTE_HASH: 8585062bd8a82082250925a2bbd5966c
:END:

it is a binary tree such that the left child is smaller than the parent node and the right child is greater than the parent node.

\[
\begin{tikzpicture}[scale=1,transform shape,very thick,
  level/.style={sibling distance=60mm/#1}]
\tikzstyle{vertex}=[draw,fill=black!15,circle,minimum size=20pt,inner sep=0pt]
\node[vertex] {$8$}
  child { % left of 8
    node[vertex] {$3$}
      child { % left of 3
        node[vertex] {$-3$}
          child { node[vertex] {$-4$} }
          child { node[vertex] {$2$}
            child[missing] {}
            child { node[vertex] {$2$} }
          }
      }
      child { % right of 3
        node[vertex] {$6$}
          child { node[vertex] {$5$} }
          child { node[vertex] {$7$} }
      }
  }
  child { % right of 8
    node[vertex] {$17$}
      child { % left of 17
        node[vertex] {$9$}
          child[missing] {}
          child { node[vertex] {$11$} }
      }
      child { % right of 17
        node[vertex] {$19$}
          child { node[vertex] {$17$}
            child[missing] {}
            child { node[vertex] {$17$} }
          }
          child { node[vertex] {$20$} }
      }
  };
\end{tikzpicture}
\]


** What is a balanced binary tree?                                 :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763381755262
:ANKI_NOTE_HASH: e79217a9411787599fd5ae28ddb90511
:END:

it depends on the definition, but usually =k=1=, and so at each node, the differences in heights of the left subtrees and right subtrees must never exceed $k$.

note, height can be seen by counting edges from node in question to the leaf.

\[
\begin{tikzpicture}[scale=1,transform shape,very thick,
  level/.style={sibling distance=60mm/#1}]
\tikzstyle{vertex}=[draw,fill=black!15,circle,minimum size=20pt,inner sep=0pt]
\node[vertex] {$8$}
  child { % left of 8
    node[vertex] {$3$}
      child { node[vertex] {$1$} }
      child[missing] {}
  }
  child { % right of 8
    node[vertex] {$17$}
      child { node[vertex] {$12$} }
      child { node[vertex] {$19$} }
  };
\end{tikzpicture}
\]


** What is a full binary tree?                                     :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763381755264
:ANKI_NOTE_HASH: 04f3ced201c983e2d177789d802cb7f7
:END:

every node has either 0 or 2 children.

no node can have a single child.

\[
\begin{tikzpicture}[scale=1,transform shape,very thick,
  level/.style={sibling distance=60mm/#1}]
\tikzstyle{vertex}=[draw,fill=black!15,circle,minimum size=20pt,inner sep=0pt]
\node[vertex] {$1$}
  child { node[vertex] {$2$} } % leaf: 0 children
  child {
    node[vertex] {$3$}
      child { node[vertex] {$4$} }
      child { node[vertex] {$5$} }
  };
\end{tikzpicture}
\]


** What is a complete binary tree?                                 :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763381755266
:ANKI_NOTE_HASH: 949c69ef8b66143b867f155d10759ea4
:END:

every level is filled except possibly the last and all nodes on the last level appear as far to the left as possible.

\[
\begin{tikzpicture}[scale=1,transform shape,very thick,
  level/.style={sibling distance=60mm/#1}]
\tikzstyle{vertex}=[draw,fill=black!15,circle,minimum size=20pt,inner sep=0pt]
\node[vertex] {$1$}
  child {
    node[vertex] {$2$}
      child { node[vertex] {$4$} }
      child { node[vertex] {$5$} }
  }
  child {
    node[vertex] {$3$}
      child { node[vertex] {$6$} }
      child[missing] {}
  };
\end{tikzpicture}
\]


** What is a perfect binary tree?                                  :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763381755267
:ANKI_NOTE_HASH: 41e59b3ff92e8b6f6ca26ccc9ad2a803
:END:

both full and complete; all internal nodes have 2 children, and all leaves lie at the same depth.

\[
\begin{tikzpicture}[scale=1,transform shape,very thick,
  level/.style={sibling distance=60mm/#1}]
\tikzstyle{vertex}=[draw,fill=black!15,circle,minimum size=20pt,inner sep=0pt]
\node[vertex] {$1$}
  child {
    node[vertex] {$2$}
      child { node[vertex] {$4$} }
      child { node[vertex] {$5$} }
  }
  child {
    node[vertex] {$3$}
      child { node[vertex] {$6$} }
      child { node[vertex] {$7$} }
  };
\end{tikzpicture}
\]



** A tree on $n$ nodes has {{c1::$n-1$}} edges                     :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Cloze
:ANKI_NOTE_ID: 1763521549057
:ANKI_NOTE_HASH: 4058cebe0b5603d63c5aa8113e3bc1c5
:END:


** Any connected, undirected graph $G=(V,E)$, with $|E|=|V|-1$ is  :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763522846837
:ANKI_NOTE_HASH: 0d4aa1db588b2b413f9fb265d444d6f5
:END:

a tree.


** An undirected graph is a {{c1::tree}} if and only if there is a unique path between any {{c1::pair of nodes}} :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Cloze
:ANKI_NOTE_ID: 1763522846842
:ANKI_NOTE_HASH: 5a271a643081e27ee13236641af0abd7
:END:


** What are 2 algorithms to determine the MST (minimum spanning tree) of a graph? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763522846845
:ANKI_NOTE_HASH: fc9529bd54113204f4c1e486be1117c4
:END:

Kruskal and Prim


** What is the rule for Kruskal's algorithm? What kind of algorithm is this? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763522846849
:ANKI_NOTE_HASH: 7dd56620c5a3969e7181f0417a9c6eab
:END:

"Repeatedly add the next lightest edge that doesn't produce a cycle"

*Greedy*


** A connected, acyclic, undirected graph is called a              :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763522846853
:ANKI_NOTE_HASH: dc64c4abd2a7d3bb1f07a032f9cc843b
:END:

tree


** What kind of data structure is used to implement Kruskal's algorithm? What are the corresponding time complexities? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763522846857
:ANKI_NOTE_HASH: 0b033e54319554bca575e958e15c3d66
:END:

union-find.

$\mathcal{O}(|E|\log|V|)$ for sorting the edges (recall that $\log|E|\approx \log|V|$), plus another $\mathcal{O}(|E|\log|V|)$ for the union and find operations.


** What can we do if the edge pairs are already sorted in Kruskal's algorithm? (or the weights are small) What becomes the bottleneck? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763522846860
:ANKI_NOTE_HASH: bd7ca3339b4e6762bb08df6697f45a52
:END:

union-find becomes the bottleneck.

we should use _path-compression_, which reduces /unions and finds/ 'drop' (function?) from $\mathcal{O}(\log n)$ to $\mathcal{O}(1)$ amortised.


** What is the relationship between Prim's algorithm and Dijkstra's? What are their run-times? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763522846864
:ANKI_NOTE_HASH: 0c1b3ef80043b02edb514bfe69aeac7b
:END:

the pseudocode is almost identical -- only difference is in the key values by which the priority-queue is ordered.

run-time depends on priority-queue implementation, but $\mathcal{O}((|V|+|E|)\log|V|)$ for *binary-heap*.


** What is the prefix-free property in Huffman encoding?           :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763522846869
:ANKI_NOTE_HASH: 3e26e8b43f4ae206c1963b375d109d02
:END:

no codeword can be a prefix of another codeword.

i.e. =00=, =001= are not allowed because strings would then not be uniquely decipherable.


** What kind of algorithm is Huffman encoding? What is its runtime? What data structure is used? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763522846873
:ANKI_NOTE_HASH: 06991645415c9bc058c15d4b4604bb56
:END:

*Greedy*.

$\mathcal{O}(n\log(n))$ for /priority queue/ with _binary heap_ implementation

** Any prefix-free encoding can be represented by a {{c1::full}} binary tree :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Cloze
:ANKI_NOTE_ID: 1763522846878
:ANKI_NOTE_HASH: 4683a10646b875c421b64e2534a34e20
:END:

*** Back Extra

recall that *full* means each child has 0 or 2 children. never 1 child.

** Can set cover be solved by a Greedy algorithm? If not, how close can we get? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763522846883
:ANKI_NOTE_HASH: 5f7e627c26235849bc9036cba04cea8b
:END:

No. it is close, but not optimal.

There is no polynomial-time algorithm for this problem.

the ratio of difference is bounded above by $\ln n$




** How is dynamic programming related to dags?                     :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763773384904
:ANKI_NOTE_HASH: d11e1744a8c4e510c8f44952116f5d4b
:END:

every problem that can be solved with DP can be represented with a DAG.

the nodes are the subproblems and edges are dependencies between the subproblems




** Why does recursion work well for divide and conquer             :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763773384921
:ANKI_NOTE_HASH: 68f1b65d15c6773376191ee72b8e08bc
:END:

because the subproblems are substantially smaller ($\approx \frac{1}{2}$ the size).

and due to this sharp drop in problem size, the full tree only has logarithmic depth and a polynomial number of nodes.



** Why is recursion a bad idea for some problems that should be solved with DP? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763773384928
:ANKI_NOTE_HASH: 81830403d8d9100a7d10cb754c6743fd
:END:

recursion solves the same subproblems over and over.

DP subproblems tend to depend on each other, and are only slightly smaller than one another.

As such, we have trees of polynomial depth and an exponential amount of nodes.



** What is the time complexity of the *edit distance* problem? What technique should be used to solve it? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763773384934
:ANKI_NOTE_HASH: 223451b5d99cc5e4a4547f91824d1b9d
:END:

Dynamic Programming: $\mathcal{O}(mn)$, i.e. the size of the table where $m$ and $n$ are the two lengths of the input strings.




** How can a problem of finding the _longest increasing subsequence_ be translated into a question about the dag? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763773384941
:ANKI_NOTE_HASH: c0685d4cd413c65a4851a77924094681
:END:

"find the longest path in the dag", where the nodes are the numbers of the sequence and the edges are the 'is less than' relationship

\[
\begin{tikzpicture}[thick]
\tikzset{
  vertex/.style={draw,circle,minimum size=18pt,inner sep=0pt}
}

% nodes ----------------------------------------------------
\node[vertex] (n1) at (0,0)  {5};
\node[vertex] (n2) at (2,0)  {2};
\node[vertex] (n3) at (4,0)  {8};
\node[vertex] (n4) at (6,0)  {6};
\node[vertex] (n5) at (8,0)  {3};
\node[vertex] (n6) at (10,0) {6};
\node[vertex] (n7) at (12,0) {9};
\node[vertex] (n8) at (14,0) {7};

% edges between consecutive nodes (drawn straight) --------
\draw[->] (n2) -- (n3);   % 2 -> 8
\draw[->] (n5) -- (n6);   % 3 -> 6
\draw[->] (n6) -- (n7);   % 6 -> 9

% remaining edges (curved) --------------------------------
% from 5
\draw[->] (n1) to[bend left=20] (n3);
\draw[->] (n1) to[bend left=25] (n4);
\draw[->] (n1) to[bend left=35] (n6);
\draw[->] (n1) to[bend left=40] (n7);
\draw[->] (n1) to[bend left=45] (n8);

% from 2
\draw[->] (n2) to[bend right=20] (n4);
\draw[->] (n2) to[bend right=25] (n5);
\draw[->] (n2) to[bend right=30] (n6);
\draw[->] (n2) to[bend right=35] (n7);
\draw[->] (n2) to[bend right=40] (n8);

% from 8
\draw[->] (n3) to[bend left=30] (n7);

% from first 6
\draw[->] (n4) to[bend right=25] (n7);
\draw[->] (n4) to[bend right=30] (n8);

% from 3
\draw[->] (n5) to[bend left=20] (n7);
\draw[->] (n5) to[bend left=25] (n8);

% from second 6
\draw[->] (n6) to[bend right=20] (n8);

\end{tikzpicture}
\]



** What is the time complexity of solving _longest increasing subsequence_ with DP? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763773384947
:ANKI_NOTE_HASH: d0c22b67bf6d2d3835253f33f142a0b7
:END:

linear in the number of edges. thus worst-case $\mathcal{O}(n^2)$, which happens when the input array is sorted in increasing order.



** What is the knapsack problem?                                   :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763773384954
:ANKI_NOTE_HASH: c23fb0b0500905cb38c6e8e2a3671e1a
:END:

an optimisation problem where we pick $n$ items with $w_i$ weights of $v_i$ value such that $\sum w_i \leq w$ and $\sum v_i$ is maximised.



** What time complexity can the knapsack problem be solved in?     :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763773384960
:ANKI_NOTE_HASH: b7006ad62be6070ba242406166a1a022
:END:


$\mathcal{O}(nW)$ (note that this is for knapsack _with_ repetition)

whilst the /same/ time complexity holds for knapsack _without_ repetition -- i.e. you can only take one of each item -- the subproblems are different.



** Is matrix multiplication commutative? Is it associative?        :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763773384965
:ANKI_NOTE_HASH: ba55c103239f600ba452eac5edfb5393
:END:

\[A\times B \neq B \times A \]

(not commutative)

\[A\times (B\times C) = (A\times B) \times C\]

(is associative)



** What is the difference between Dynamic Programming and memoisation? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763773384971
:ANKI_NOTE_HASH: c12f0330f4916f2ff0cbb2abe511cec9
:END:

DP writes out a recursive formula to express large problems in terms of smalller ones. We then fill out a table of solutions in a _bottom-up_ manner, from smallest subproblem to largest.

This means we solve _every_ subproblem. Meanwhile, *recursion* with memoisation just solves what it needs. 




** What is a computational approximation to multiply two matrices $A^{m\times n}$ and $B^{n\times p}$ together? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763773384977
:ANKI_NOTE_HASH: 5c9b34768902829b154b8799d5bd714d
:END:


\[mnp\]



** Is there a difference in doing matrix multiplication as         :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_PREPEND_HEADING: t
:ANKI_NOTE_ID: 1763773384982
:ANKI_NOTE_HASH: aac4680b7a3b5aaf66324fbaa608893e
:END:

\[ (A \times (B \times (C \times D))) \]
or
\[ (A \times B) \times (C \times D) \]
or
\[ (((A \times B) \times C) \times D) \]
?

*** Back

Yes, big difference.

We can use a dynamic programming algorithm to model the placement of parenthesis as a full binary tree and then run DP on this tree.

Greedy will not work.



** What technique can we use to find the optimal order of multiplying matrices :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_PREPEND_HEADING: t
:ANKI_NOTE_ID: 1763773384989
:ANKI_NOTE_HASH: a497b4864c951eac81931b0bfed65a88
:END:

\[A_1^{m_0\times m_1} \times A_2^{m_1\times m_2} \times \ldots \times A_n^{m_{n-1}\times m_n}\]

**** Back

use dynamic programming on the full binary tree parenthesisation.

note greedy does not work here.

the subproblems form a 2D table with $\mathcal{O}(n)$ time per entry $\implies \mathcal{O}(n^3)$


** Define 'Greedy Algorithm'                                       :dasgupta:

an attractive algorithmic strategy due to its simplicity and occasional effectiveness.

it is a myopic behaviour that always chooses the next piece with maximal benefit.

is good for scrabble and MSTs, not for chess.



** How can we solve the problem of wanting a shortest path through a graph, with the added constraint that we should use no more than $k$ edges? Can we still use Dijkstra? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763773384995
:ANKI_NOTE_HASH: 3402512e0e1dc12e84662ef7ed1463c4
:END:

No. Dijkstra does not remember the number of hops in each path which is now crucial information.

We need to use dynamic programming and define the subproblems carefully.



** What is the time-complexity of the Bellman-Ford algorithm? What is it used for? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763773385001
:ANKI_NOTE_HASH: 8240b4a08058d557dfac4460b5f370bd
:END:


\[\mathcal{O}(|V|\times|E|)\]

used for finding the _shortest path_ from source $s$ to all other vertices.

differs from Dijkstra in that it can handle *negative weights*



** How can we compute the shortest paths for _all-pairs_ in a graph? Should we just run the Bellman-Ford or Dijkstra algorithm $|V|$ times? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763773385007
:ANKI_NOTE_HASH: b5c7cfafb3e391b9fd0742a52963cfe0
:END:

no, Bellman-Ford would cost $\mathcal{O}(|V|^2|E|)$ which is $\mathcal{O}(|V|^4)$ worst case.

we should use Floyd-Warshall: $\mathcal{O}(|V|^3)$ which is based on dynamic programming.



** What is the travelling salesman problem?                        :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763773385013
:ANKI_NOTE_HASH: b5d0d2fb156befed9fde29324b79cf98
:END:

the travelling salesman wants to conduct a tour of $n$ cities, minimising his travelling distance and returning back home at the end.



** What is the time-complexity of brute-forcing TSP (travelling salesman problem)? Can we do better? If so, by how much? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763773385018
:ANKI_NOTE_HASH: 5a103bfa3199505cc0cdc2d6cd62860b
:END:

$(n-1)!$ possibilities $\implies \mathcal{O}(n!)$.

dynamic programming can do $\mathcal{O}(n^2 2^n)$ -- still not polynomial though.



** How can we (often times) understand the time complexity of a DP problem from the dag of the subproblems? Can we make comments about the space complexity? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763773385024
:ANKI_NOTE_HASH: 516979cf3fefd12d0babf6df4c55f231
:END:

time-complexity is often just the total number of edges in the dag. we visit these nodes in a linearised order and do a constant amount of work.

space: an upper bound is the number of vertices (subproblems), but we can usually do better by releasing the smaller problem from memory once we have solved the longer problem.



** Is finding the independent set of a graph tractable? What about the independent set of a tree? What are the strategies and the complexities of each? :dasgupta:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1763773385030
:ANKI_NOTE_HASH: 7f484f489045d2dcb9fb6bf7a3b2f0af
:END:

intractable.

tree: dp, $\mathcal{O}(|V|+|E|)$ (linear)




** What is the time complexity for solving linear programming problems? What about _integer_ linear programs?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764032221466
:ANKI_NOTE_HASH: 5a455864d87e3e31f88f754c4f07514c
:END:

P vs NP




** Linear Programming describes a broad class of {{c1::optimisation}} tasks in which both the {{c1::constraints}} and the optimisation {{c1::criterion}} are {{c1::linear}} functions.
:PROPERTIES:
:ANKI_NOTE_TYPE: Cloze
:ANKI_NOTE_ID: 1764032221476
:ANKI_NOTE_HASH: 80234b67e228af5876315d92f0e121d0
:END:



** It is a general rule of linear programs that the optimum is achieved at a {{c1::vertex}} of the feasible region.
:PROPERTIES:
:ANKI_NOTE_TYPE: Cloze
:ANKI_NOTE_ID: 1764032221481
:ANKI_NOTE_HASH: 964c540a7a38a3c9f58f692857cbb069
:END:

*** Back Extra
Note: the only exceptions are when the program is _infeasible_ or; the region is _unbounded_.



** The maximum-flow problem reduces to {{c1::linear programming}}
:PROPERTIES:
:ANKI_NOTE_TYPE: Cloze
:ANKI_NOTE_ID: 1764032221486
:ANKI_NOTE_HASH: c735f72c52aa45976f1c4a141316d40a
:END:

*** Back Extra

(our goal is to assign values to edge capacities that satisfy linear constraints and maximise a linear objective function)



** Max flow is the same as {{c1::min cut}}. This is an instance of {{c1::duality theorem}}.
:PROPERTIES:
:ANKI_NOTE_TYPE: Cloze
:ANKI_NOTE_ID: 1764032221492
:ANKI_NOTE_HASH: 49d6c714ec7a68347c08b56d48d90a42
:END:



** What is the time complexity for max-flow?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764032221497
:ANKI_NOTE_HASH: 66e5295a14f900fe0106d22f0b68bcab
:END:

\[\mathcal{O}(|V|\cdot |E|^2)\]



** Bipartite matching can be reduced to {{c1::max flow}}, which can thus be reduced to {{c1::linear programming}}.
:PROPERTIES:
:ANKI_NOTE_TYPE: Cloze
:ANKI_NOTE_ID: 1764032259050
:ANKI_NOTE_HASH: d4b9af05a6bebc9830b686629e607e95
:END:


** What does bipartite mean?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764032221506
:ANKI_NOTE_HASH: 4b7990d2d03a6c2636a5e9d95e8c000c
:END:

A partitioning of a graph such that all edges are _between_ the graphs and there are no edges from one member of the group to another member of the same group.




** The simplex algorithm is synonymous to performing {{c1::hill-climbing}} along the vertices of a convex polyhedron.
:PROPERTIES:
:ANKI_NOTE_TYPE: Cloze
:ANKI_NOTE_ID: 1764032221511
:ANKI_NOTE_HASH: 03c8ccbcd3a4973cc955aeacd5afd592
:END:



** What is the time complexity of Gaussian elimination? Why is it so?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764032221516
:ANKI_NOTE_HASH: ac5afb21a0724485b5d39fbf101d9006
:END:

it costs \(\mathcal{O}(n^2)\) operations to reduce problem size from $n$ to $n-1$. This happens $n$ times, therefore total time complexity is $\mathcal{O}(n^3)$



** More strictly, what is the time complexity of simplex algorithm per iteration? Is the algorithm linear?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764032221520
:ANKI_NOTE_HASH: 9bcf58ec5fb475ae7ad4b9e5798b4fd4
:END:

\(\mathcal{O}(mn)\) where $n$ is the number of variables and there are $m$ inequality constraints.

since it is *per* iteration and there can be \(\large \binom{m+n}{n}\) iterations -- the complexity of the simplex algorithm is theoretically exponential (although in practice it often ends up being polynomial)



** What are another 2 algorithms for linear programming beyond the simplex method?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764032221525
:ANKI_NOTE_HASH: 4ed122a4acf32d5b4df9a36813999f3a
:END:

ellipsoid algorithm: solves any LP (linear program) in polynomial time; performs worse in practice.

interior point method: provably polynomial too --- performs well in practice!



** What is the Circuit Evaluation problem and what is its significance?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764032221528
:ANKI_NOTE_HASH: d20fb4cd97029fb12cf208f4ae593ebc
:END:

it simulates logic gates, i.e. any polynomial time algorithm.

as such, any polynomial time algorithm can be reduced to LP and therefore solveable by LP!




** What is the maximum number of iterations of the simplex algorithm? Explain.
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721214
:ANKI_NOTE_HASH: 6f3a9e70b9901f5b7f0e9c9569fbba26
:END:

\[\large\binom{m+n}{n}\]

** What is the *space* complexity in the best case of the "edit distance" problem?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721218
:ANKI_NOTE_HASH: 3f92693d952e7ef2a400ebd62a00063a
:END:

order of the length of the shorter string. time complexity is $\mathcal{O}(mn)$



** What physics process inspired simulated annealing?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721221
:ANKI_NOTE_HASH: 1d471e60d1b297e47640778ec708c4ed
:END:

crystallisation




** What is simulated annealing? How should we tune the temperature?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721224
:ANKI_NOTE_HASH: 59add0058c1e507fb8fb7dd1e8d1d7dd
:END:

start with a high temp, then gradually reduce it; reducing the stochasticity of the method and becoming more strict.

simulated annealing is an augmentation to local search. it is a way of allowing the cost to increase with the hopes that the search will be pulled out of dead-ends.

this becomes necessary because often, as the problem sizes increase, so do the ratio of bad to good local optima.

** What are some NP-complete problem/s that can be approximated via local search?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721226
:ANKI_NOTE_HASH: 9fe71e453c8b76a379eca914a8b409fd
:END:

Graph partitioning. Particularly Balanced Cut.

Min-cut is also a type of graph partitioning algorithm, but this one can be solved in $P$ time with efficient classical and randomised algorithms.


** What is local search and which problems can it be applied to?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721228
:ANKI_NOTE_HASH: 2c05498875bb7d5db1b55e330645e5a4
:END:

incremental process of introducing small mutations, trying them out and keeping them if they work well.

can be applied to any optimisation task.


** Which NP-complete problem/s can be approximated with arbtirarily low error?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721230
:ANKI_NOTE_HASH: 8fb16efc786326cc587ef00ec9383c56
:END:

Knapsack.

** Give examples of algorithms with minimum approximation ratios.
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721232
:ANKI_NOTE_HASH: d2f66fdf3d4aaaa45bdff4d77f857323
:END:

- Vertex Cover
- K-cluster
- Travelling Salesman Problem with $\Delta$-ineq

** Is an approximation algorithm possible for TSP? What if there is no metric-space structure?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721233
:ANKI_NOTE_HASH: 58f8e7245b5993672715473cc174260f
:END:

Approximation Ratio can be as low as 2 or even 1.5 when you have $\Delta$-inequality.

Without it though, there is no approximation algorithm and we are stuck with the worst time complexity: $\mathcal{O}(n!)$

** What is the approximation guarantee to the set cover problem? What kind of technique is used for the approximation algorithm?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721235
:ANKI_NOTE_HASH: 484b5f175e45195d02d473a6fee9781f
:END:

\[\log(n)\]
Greedy

** What is the fastest way to solve min-cut? What kind of algorithm is this?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721237
:ANKI_NOTE_HASH: 756a9fd8ef3354a3d485a96b080bc0c0
:END:

\[\mathcal{O}(n^2 \log(n))\]

Randomised Algorithm!

** What algorithm is the randomised min-cut algorithm related to?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721240
:ANKI_NOTE_HASH: a4816749ab657a48987ab74a63dc32d2
:END:

Kruskal's Minimum Spanning Tree algorithm


** Are both Prim's and Kruskal's algorithms Greedy? What are these algorithms for?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721241
:ANKI_NOTE_HASH: f3e595db61dd6fb509c88fa9d080cebe
:END:

Yep Greedy; they find the Minimum Spanning Tree (MST)



** What is a data structure you should consider when you run into disjoint sets?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721243
:ANKI_NOTE_HASH: 619f3309b8ab5c6c6c819a4e2ff21a92
:END:

Union Find


** AES is a type of {{c1::private}}-key cryptography whereas RSA is an example of {{c1::public}}-key cryptography
:PROPERTIES:
:ANKI_NOTE_TYPE: Cloze
:ANKI_NOTE_ID: 1764220721245
:ANKI_NOTE_HASH: 4c0cae82a8861a4b3275d1feeeddb778
:END:

** What does AES stand for? What about RSA?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721246
:ANKI_NOTE_HASH: b96879da2337bc44980cf63226100045
:END:

Advanced Encryption Standard

Rivest, Shamir, Adleman


** Give a couple examples of Randomised Algorithms
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721248
:ANKI_NOTE_HASH: 48bde91ee60b70e236aa9b29bdb33a32
:END:

- Primality testing, min-cut (monte carlo style)
- Hashing (las vegas style)

** What are the two /varieties/ of randomised algorithms? Describe them briefly.
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721249
:ANKI_NOTE_HASH: 98196036514c9b04465ac26e9b528978
:END:

- Monte Carlo algorithms *always* run fast, but their output has a small change of being incorrect.
  - primality testing is an example of such a variety
- Las Vegas algorithms always output the correct answer, but instead guarantee a *short running time* with high probability.
  - hashing is an example of this; always correct, but infrequently slow.


** What are randomised algorithms?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721251
:ANKI_NOTE_HASH: 4f2f689407a402d345445f6a7927849a
:END:

algorithms whose outputs are allowed to be _incorrect_ with small probability.

** How can we check primality quickly? Are there any pathological exceptions?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721252
:ANKI_NOTE_HASH: 4429da3b08001d2a0bd25e2aa3c8df97
:END:

Yes, check \(a^{N-1}\equiv 1 \bmod N\).

If true, then prime, else false.

Carmichael numbers break this, but are pathologically rare. So we just run the algorithm a few times; "randomised algorithm" -- probability of incorrect answer diminishes

** Factoring is {{c1::hard}}, whilst checking primality is {{c1::easy}}.
:PROPERTIES:
:ANKI_NOTE_TYPE: Cloze
:ANKI_NOTE_ID: 1764220721254
:ANKI_NOTE_HASH: 9603591f14c3d66031cd16f69b415660
:END:




** Give an example of a problem that can have a typical polynomial runtime by using the branch and bound technique.
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721256
:ANKI_NOTE_HASH: 8e68cc6782b03ef489c6cbbcf929b478
:END:

travelling salesman tour.

note; branch and bound uses an assumption about /typical structure/ -- this is where the saving in time complexity comes from. worst-case is still exponential.



** A backtracking algorithm requires a test that looks at a subproblem and quickly declares one of three outcomes:
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721257
:ANKI_NOTE_HASH: ac39b0dfff47e81a6facdf9541865d58
:END:

1. Failure: the subproblem has no solution.
2. Success: a solution to the subproblem is found.
3. Uncertainty: keep expanding this subtree.

** How does backtracking prune the search space?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721259
:ANKI_NOTE_HASH: 9f67b0908f43a4692032e0f74afaa633
:END:

it checks a /partial assignment/ and if this assignment can be rejected then the hwole subtree can be pruned.

** What are 2 intelligent exhaustive search strategies?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721261
:ANKI_NOTE_HASH: f9de5c743d59c13dd2ab6ed8b868241b
:END:

back-tracking and branch-and-bound.

** Is Bipartite Matching $P$ or $NP$? What about 3D matching (tri-partite, with boys, girls and pets)?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721263
:ANKI_NOTE_HASH: fd52065757e47d958e5554f2b970b733
:END:

Bipartite matching can be reduced to max-flow. 3D Matching is $NP$.



** What is the Vertex Cover problem and what is it a special case of?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721265
:ANKI_NOTE_HASH: 77b240321576084baf6639f69604d151
:END:

input(Graph G, budget b)

we try find $b$ vertices that touch every edge.

special case of set cover. related to /largest independent set problem/.



** P or NP-complete?
:PROPERTIES:
:ANKI_NOTE_TYPE: Cloze
:ANKI_PREPEND_HEADING: t
:ANKI_NOTE_ID: 1764217301123
:ANKI_NOTE_HASH: 8787c1c2a0d270e689fde322e1bd011b
:END:

*** Text

| Problem                    | complexity  |
| 3Sat                       | {{c1::NPC}} |
| 2Sat                       | {{c2::P}}   |
| Horn Sat                   | {{c3::P}}   |
| TSP                        | {{c4::NPC}} |
| Longest Path               | {{c5::NPC}} |
| Min Cut                    | {{c6::P}}   |
| Euler Path                 | {{c7::P}}   |
| Independent Set on Trees   | {{c8::P}}   |
| Rudrata Path               | {{c9::NPC}} |
| Balanced Cut               | {{c10::NPC}} |
| Knapsack                   | {{c11::NPC}} |
| 3D Matching                | {{c12::NPC}} |
| Independent Set            | {{c13::NPC}} |
| Integer Linear Programming | {{c14::NPC}} |
| Linear Programming         | {{c15::P}}  |
| Unary Knapsack             | {{c16::P}}  |
| Shortest Path              | {{c17::P}}  |
| Bipartite Matching         | {{c18::P}}  |
| Minimum Spanning Tree      | {{c19::P}}  |


** What does NP stand for in complexity theory? What does it mean?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721268
:ANKI_NOTE_HASH: 1158f8ef05742376569f9f78aeb09ef7
:END:

means "non-deterministic polynomial time".

is a way to condense the logic of programs we don't know are "polynomial" into a black-box to reason about them. recall we still need a proof for $P\neq NP$, which is why the reduction is some-what justified.

this method of abstraction is similiar to $\sqrt{-1} = i$, in that by collecting all the 'non-deterministic polynomial time' parts of an algorithm, we can continue to study other parts of the algorithm / problem.


** NP Reductions                                           
:PROPERTIES:
:ANKI_NOTE_TYPE: Cloze
:ANKI_NOTE_ID: 1764220569508
:ANKI_NOTE_HASH: 087e1e3d7b03bbd413f3a350203f06ed
:END:

*** Text
# raw
[latex]
\begin{tikzpicture}[
  level distance=1.6cm,
  level 1/.style={sibling distance=40mm},
  level 2/.style={sibling distance=55mm},
  level 3/.style={sibling distance=40mm},
  level 4/.style={sibling distance=28mm},
  edge from parent/.style={->,draw},
  every node/.style={font=\large}
]
\node (np) { {{c1::All of $\mathbf{NP}$}} }
  child { node { {{c2::SAT}} }
    child { node { {{c3::3SAT}} }
      child { node { {{c4::Independent set}} }
        child { node { {{c5::Vertex cover}} } }
        child { node { {{c6::Clique}} } }
      }
      child { node { {{c7::3D matching}} }
        child { node { {{c8::ZOE}} }
          child { node { {{c9::Subset sum}} } }
          child { node { {{c10::ILP}} } }
          child { node { {{c11::Rudrata cycle}} }
            child { node { {{c12::TSP}} } }
          }
        }
      }
    }
  };
\end{tikzpicture}
[/latex]



** What is a cycle in Graph Theory?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721270
:ANKI_NOTE_HASH: 9b56d0a22a115d8c345870cea8cec175
:END:

cycle: $v_0 \rightarrow v_1 \rightarrow \ldots \rightarrow v_k \rightarrow v_0$

a path of length $\geq 3$ where only the first and last vertices are the same.


** What is a planar graph?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721271
:ANKI_NOTE_HASH: fd6135257e133d6044e1d6d5ba15cd92
:END:

a graph that can be drawn without crossings

** What is the largest independent set problem?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_PREPEND_HEADING: t
:ANKI_NOTE_ID: 1764220721273
:ANKI_NOTE_HASH: 799dbf68f27262e8ea59b5929c6a73ff
:END:

*** Back

\[
\begin{tikzpicture}[node distance=2cm]
  % Nodes
  \node[circle, draw] (1) at (0,0) {1};
  \node[circle, draw] (2) at (3,0) {2};
  \node[circle, draw] (3) at (0,-2) {3};
  \node[circle, draw] (4) at (3,-2) {4};
  \node[circle, draw] (5) at (5.5,-1) {5};
  \node[circle, draw] (6) at (8,-1) {6};
  
  % Edges
  \draw (1) -- (2);
  \draw (1) -- (3);
  \draw (3) -- (4);
  \draw (2) -- (5);
  \draw (4) -- (5);
  \draw (5) -- (6);
\end{tikzpicture}
\]

There are a couple largest independent sets: $\set{2,4,6}$ or $\set{2,3,6}$



** What is an Eulerian Tour?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721274
:ANKI_NOTE_HASH: 3349a8ddaf3b56d9245ed7606b84d097
:END:

is a cycle in an undirected graph that is allowed to pass through each vertex multiple times, but must use each edge exactly once.




** Do unsolveable problems exist?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721276
:ANKI_NOTE_HASH: 6aaf4d5c847d2d36b2415e13338142aa
:END:

Yes. See "The Halting Problem" by Turing.



** What is the difference between a cycle and a tour?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721277
:ANKI_NOTE_HASH: 3150393b43559fc65377dae80d9ce7a4
:END:

a cycle is localised: $v_0 \rightarrow v_1 \rightarrow \ldots \rightarrow v_k \rightarrow v_0$

but a tour insists that every vertex is visited.



** What is a Hamiltonian cycle / tour?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721279
:ANKI_NOTE_HASH: 4fbc1defee4bea8e0874f096abb4f313
:END:

When you go through every vertex exactly once.

(is it even possible to repeat edges?)


** What is a practical way to check if a path is Eulerian?
:PROPERTIES:
:ANKI_NOTE_TYPE: Basic
:ANKI_NOTE_ID: 1764220721281
:ANKI_NOTE_HASH: 98745b9511b5b9e9a4a76e6ef75873e4
:END:

draw the graph without lifting pen from paper; i.e. vertices may be repeated, but edges cannot be (must be visited exactly once).