#+TITLE: Software Engineering * Java :PROPERTIES: :ANKI_DECK: soft-eng::java :END: ** In Java, how many bits are bytes, short, int and long? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763087705395 :ANKI_NOTE_HASH: 1f777ace85184d321501920a4871de59 :END: 8, 16, 32, 64. ** How to erase the lowest bit in a word with a single operation? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763087705404 :ANKI_NOTE_HASH: d449995a49d1e260ea13daa3357d83a8 :END: =x&(x-1)= where =&= is bitwise and. * Python :PROPERTIES: :ANKI_DECK: soft-eng::python :END: ** In Python, how can you push off the right-most digit? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763087705407 :ANKI_NOTE_HASH: ba6f561ebbdbd811d9e639ea42506286 :END: =n//=10= ** What is the /nonlocal/ keyword in Python? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763087705410 :ANKI_NOTE_HASH: 3d4534755f70eb9d40aa9781ca19399e :END: refers to the variable (non-global) outside the functions' current scope. ** what is the difference between =.sort()= and =sorted()= in Python? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763087705413 :ANKI_NOTE_HASH: c160a694069ddeca7b9a111eac29a0bb :END: =.sort()= changes the variable in-place. =sorted()= takes in an iterable and gives a new object. ** what is the difference between list and List in Python? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763087705417 :ANKI_NOTE_HASH: d622072001ceac13c0d84575dbf3bcf8 :END: prior to python3.9 =from typing import List= was used to accomplish type hints and checking. now, we can just use the lowercase form with the same functionalities. * 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). * Git :PROPERTIES: :ANKI_DECK: soft-eng::shell :END: ** Is it true that =git add= is a multi-purpose command? if so, what are some things it can do? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763629959831 :ANKI_NOTE_HASH: c624046693c2638f21d8e475610cb360 :END: True. it can track new files, stage files, and mark merge-conflicted files as resolved. it may also be able to do more things. ** What is the checksumming algorithm used by Git? What is the length of the values? What are the value strings composed of? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836314 :ANKI_NOTE_HASH: 345194254614dae014c40588b1ef657c :END: SHA1 hash. 40 length. Hex; i.e. 0-9 + a-f ** What are the three main states files can reside in? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836317 :ANKI_NOTE_HASH: 4e221309c4b87673c6511ca39002c469 :END: 1. modified 2. staged 3. committed ** What does the staging area look like? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836319 :ANKI_NOTE_HASH: 1c7208e708f12ce654946c5ec3660697 :END: it is a _file_ called *index*. ** What are the three scopes of =git config= and where are each of the configuration files stored? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836321 :ANKI_NOTE_HASH: 348371e4231f0f968f20dd547cb53549 :END: - =--system= | all users: =/etc/gitconfig= - =--global= | current user; all repos: =~/.gitconfig= or =~/.config/git/config= - =--local== | =.git/config= per repo control ** Does =/etc/gitconfig= trump =.git/config=? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836322 :ANKI_NOTE_HASH: 552558b7241ae3d6a898a6570bfdd066 :END: No. local trumps global which trumps system. This is also the case for configuration files more generally. ** What command can you use to check the git configuration settings? What about a specific key? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836324 :ANKI_NOTE_HASH: 4274727fee4b07b26241fffdd9778859 :END: =git config --list= =git config = ; where key can be something such as =user.name= or =user.email=, =core.editor=, etc. ** What are the two types of files from gits' perspective? What kind of files belong in each type? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836325 :ANKI_NOTE_HASH: 5555e68d564b26ef5b84da3c88ba2990 :END: 1. *tracked:* things previously staged; newly staged files. - can be modified, unmodified or staged 2. *untracked:* everything else. the stuff git doesn't know about. ** How to =git add= recursively? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836327 :ANKI_NOTE_HASH: cde3847394fca71bb8c306dec41c2d57 :END: trick question; =git add= automatically adds directories recursively. ** What does =git add= do? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836328 :ANKI_NOTE_HASH: 5d597fe0a15d47f7e66c80e3562af84e :END: it begins /tracking/ the file and stages it for committing. it is multi-purpose and can do even more. think of it as "add precisely this content to the next commit" ** How to get a short git status? what do the LHS columns mean here? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_PREPEND_HEADING: t :ANKI_NOTE_ID: 1763629926820 :ANKI_NOTE_HASH: 51cd7d76242bdd62b678d6de67975fb0 :END: #+BEGIN_SRC bash $ git status -s M README MM Rakefile A lib/git.rb M lib/simplegit.rb ?? LICENSE.txt #+END_SRC *** Back =git status --short= or =-s=. - =m= : modified - =mm= : modified, staged, modified - =a= : added to staging - =??= : untracked ** What files do =*.[oa]= and =*.~= ignore in the =.gitignore=? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836331 :ANKI_NOTE_HASH: 866c02f2597fae6c8a6e7ccc723b576c :END: files ending with =.o= OR =.a= and files ending with =.~=. ** How do you write comments in =.gitignore= file? how do you specify a directory to ignore? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836333 :ANKI_NOTE_HASH: 0fc8c5fb7486b56bb7ad10190db7863c :END: =#= end the directory name with =/= note, unless you add the prefix slash, it will ignore that named directory at all levels! the prefix slash means 'not recursively' ** What are glob patterns? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_PREPEND_HEADING: t :ANKI_NOTE_ID: 1763628836334 :ANKI_NOTE_HASH: b69b3194758ea5021efacfb4a9b12ce3 :END: *** Front What do these ones do? - =*= - =[abc]= - =?= - ~[0-9]~ - ~a/**/z~ *** Back they are simplified regular expressions. - =*= : matches zero or more characters. - =[abc]= : matches any character inside the brackets - =?= : a single character - ~[0-9]~ : matches any character between the range - ~a/**/z~ : nested directories; matches ~a/b/c/z~, ~a/z~, ~a/b/z~, etc. ** What do the following instructions do in a =.gitignore= file? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_PREPEND_HEADING: t :ANKI_NOTE_ID: 1763629926825 :ANKI_NOTE_HASH: 51320c3469150c174e4e013f2cb1d51a :END: - =*.a= - =!lib.a= - =/TODO= - =build/= - =doc/*.txt= - =doc/**/*.pdf= *** Back - ignore all =*.a= files - but track =lib.a= - only ignore =TODO= file in current directory. not =subdir/TODO=. recall that prefix =/= avoids recursivity - ignore all files in _any_ directory named =build= - ignore =doc/notes.txt=, but not =doc/server/notes.txt= - ignore all =.pdf= files in =doc/= and subdirs ** Can a repo only have 1 =.gitignore= file? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836337 :ANKI_NOTE_HASH: 834d5c190cec2767927c33c7381f5963 :END: no, it can have *one* in each subdirectory if required. ** What does =git diff= do? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836339 :ANKI_NOTE_HASH: 2077e20d702c518eec161cb1a1a41adb :END: it compares what is in your working directory with what is in your staging area. ** How can you use =git diff= to compare your staged changes to the last commit? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836340 :ANKI_NOTE_HASH: 5b60e2464f9286245ef4c4a6c9e6f3d8 :END: =git diff --staged= ** What is the difference between =git diff --staged= and =git diff --cached=? What do they do? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836341 :ANKI_NOTE_HASH: d351a853b66c36a5b7da18485a7a92b3 :END: they're synonyms! shows the /diff/ between last commit and what is staged ** What does =-v= do in =git commit=? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836343 :ANKI_NOTE_HASH: c0382fe68a443b590e87df3e84296e6e :END: adds a =git diff= to the commit popup so you can see exactly what you are committing. ** How can you skip the staging area? What is there to be careful of? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836344 :ANKI_NOTE_HASH: d6ec5004f89c3200e3bd20f608ae873f :END: =git commit -a -m ""= this will only commit the files that were already being tracked. no new files. ** How do you remove a file from git? precisely what does the command for this do? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836346 :ANKI_NOTE_HASH: aa00032bfc6e8830824d605638f5075b :END: you must remove the file from the tracked files (staging area) and then commit. =git rm= does this and also deletes the file from the working directory (so it's not "unstaged" later) ** When should you do the =-f= option for =git rm=? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836347 :ANKI_NOTE_HASH: 93de1c52d2be7c3513a166851caa99d6 :END: if you modified the file or added it to the staging area. it's a safety feature to prevent removal of files that aren't in a snapshot. ** How to remove a file from staging area, but keep it in working directory? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836349 :ANKI_NOTE_HASH: abf5b06c3cfd389eca7094e73545aa96 :END: =git rm --cached = ** What order does =git log= show commits in? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836350 :ANKI_NOTE_HASH: d56065d3b76a7f70626b69b95092350e :END: reverse chronological order -- most recent commits first. ** What does =git log -p -2= do? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836351 :ANKI_NOTE_HASH: 93e492cd38a06a6b6780254fadad7142 :END: shows only last 2 commits with diff (or patch) details ** What do =git log --stat= and =git log --pretty= do? what values can pretty take? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836353 :ANKI_NOTE_HASH: 8842885e0cd3c9379b739a8014d40612 :END: =--stat= prints a list of modified files below each entry. how many such files, and how many lines were changed. =--pretty= has options: oneline, short, full, fuller, format: _____, etc. ** What does =git log -n= do where =n= is integral? How can you get commits made in the last 2 weeks? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836354 :ANKI_NOTE_HASH: a3ea0c1341d8c259e9a47baad86d402b :END: shows last 2 commits. =git log --since=2.weeks= also, =--until= is useful too. dates can be ="2008-01-15"= or even relative: "2 years 1 day 3 minutes ago" ** What =git log= flag is commonly referred to as the pick axe? What does this pickaxe do? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836355 :ANKI_NOTE_HASH: 04fea03df8b34497e0566409aedcee4f :END: =git log -s = shows only those commits that changed the number of occurrences of =function_name= ** How can you filter in =git log= based on path? where in the command should this filter go? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836357 :ANKI_NOTE_HASH: 4a45b76389dab6a5c47091ee471f8ea3 :END: at the very end, separated by =--= to segregate from the other options: =git log -- path/to/file= ** What flag allows you to declutter the log history from merge commits when using =git log=? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836358 :ANKI_NOTE_HASH: bc51922a94ed11965040fc8389a1fdbc :END: =--no-merges= ** How can you fix a commit message / add an extra file to your commit (that hasn't been pushed yet)? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836360 :ANKI_NOTE_HASH: da1a62587db71e04a94ef9060690c134 :END: =git commit --amend= note that you get a new hash, and the old commit never exists in the history. ** What does =git checkout -- = do? Are there perils? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836361 :ANKI_NOTE_HASH: 6148cae027c1eae89920a1879bdae748 :END: Yes, perils - you can lose work! It deletes changes and brings the file back to the last staged or committed version. ** Which 2 commands does =git reset= replace? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836362 :ANKI_NOTE_HASH: 1a894dc684d31a2bd37151d74e2d1589 :END: =git reset HEAD = and =git checkout -- = ** What is the command to add a new remote with shortname and URL? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836363 :ANKI_NOTE_HASH: 22cd9937b8a725af23f64dc1dcbd8837 :END: =git remote add = ** What does =git fetch = do? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836365 :ANKI_NOTE_HASH: 56e09e099ae4a7db4625309e230c39e4 :END: it just downloads the data from whichever remote is the argument, and places it in the =.git= folder. no merging occurs. ** What does =git reset HEAD = do? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836366 :ANKI_NOTE_HASH: 4c6328a96c1f6ca5a22e441ee382d8d9 :END: it unstages the file. (but I thought =git rm --cached= does that too...) ** How to see the URLs of *all* the remotes? What about a single remote? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836367 :ANKI_NOTE_HASH: 8a2322b7b43c888c474164c3f5d1b4cd :END: =git remote -v= OR for more info on a single remote: =git remote show origin= ** How can you list tags? How can you (optionally filter them)? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836368 :ANKI_NOTE_HASH: b0e66c7a8eb7bf1039f23d280a272c72 :END: =git tag= with optional =-l= that respects globs =-l ""= ** What are the 2 types of tags? What do they do? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836369 :ANKI_NOTE_HASH: 6420673bcc9a961c1279b28c738c51e2 :END: lightweight: pointer to a specific commit annotated: full objects. checksummed; contain metadata: tagger name, email, date, message. ** How do you push tags? how can you delete them? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836372 :ANKI_NOTE_HASH: 0782acbff1fa79a2a6b57cfde9d0b901 :END: =git push = or for lots: =git push --tags= delete: =git tag -d = (which does so locally) followed by =git push --delete = ** How can you create an annotated tag with message? how can you tag an old commit? how do you see tag data? :git: :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763628836371 :ANKI_NOTE_HASH: 46d0bbdf727191a6b94f17baff14c5d7 :END: =git tag -a -m ""= =git tag -a = =git show = ** When is *rebasing* a bad idea? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763944597353 :ANKI_NOTE_HASH: 1c84f3d86b7fa518888df4293af71752 :END: when other people have based work on your commits. do *not* rebase those. ** How can you rebase =server= branch onto =master= without checking out =server= first? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763944597366 :ANKI_NOTE_HASH: b85f50437b9cdb4dcc21e01651d46e93 :END: =git rebase master server= "replay the commits *onto* master *from* server branch" ** What does =git rebase master= do? Assuming you're on the =experiment= branch? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_PREPEND_HEADING: t :ANKI_NOTE_ID: 1763944597389 :ANKI_NOTE_HASH: 1134d89ab05e6d088f2613f808674594 :END: [[file:img/rebase1.png]] *** Back goes to common ancestor; gets diff of every commit -- saves them into a temp file; resets =experiment= branch to same commit as =master=. applies each patch. you will then need to fast-forward by checking out =master= and merging =experiment= into it. file:img/rebase2.png file:img/rebase3.png ** What are the commands for a basic rebase? How are they different to a merge? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763947431084 :ANKI_NOTE_HASH: 22df707cd9fb701837ab8d76f489c2a6 :END: rebase: =git checkout experiment= =git rebase master= "go to experiment branch, apply patches to master" merge: =git checkout master= =git merge experiment= "merge changes *into* current branch" ** What does rebasing do? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763947431105 :ANKI_NOTE_HASH: 87ca5c9e2da5abf73d422b0fc1c506d5 :END: takes all the changes committed on one branch and replays them on another branch file:img/rebase2.png ** What is a small gotcha vis-a-vis the =git branch -vv= command and the information it returns? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763947431113 :ANKI_NOTE_HASH: fa1dc1fbedba6f9c1cf4ac9a10f433db :END: it's telling you information about what we have cached from the last =fetch=. we are better off running =git fetch --all; git branch -vv= ** What does the =-vv= flag do to =git branch=? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763947431119 :ANKI_NOTE_HASH: bd11b048a074723daaa4c81ff6dcd75f :END: shows what tracking branches have been set-up. lists out _local_ branches with more information; what each branch is tracking and if the local branch is ahead, behind or both. ** What is =@{u}= short for? What is an alternative short-form for this? What does =git merge @{u}= do? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763947431127 :ANKI_NOTE_HASH: a3b1af8637049a450605dd2e61492cfb :END: short for the upstream url. hence =@{upstream}= is another short-form. =git merge @{u}= merges the current branches' upstream into the current branch. ** If you already have a local branch and want to set it to a remote branch you just pulled down, or want to change the upstream branch you're tracking, the command is {{c1:: =git branch -u origin/=}} :PROPERTIES: :ANKI_NOTE_TYPE: Cloze :ANKI_NOTE_ID: 1763947431139 :ANKI_NOTE_HASH: 7bd13a5475a1461745b2cce0c9b5e837 :END: ** What is =git checkout serverfix= an alias for, where you don't have the remote serverfix branch? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763947431145 :ANKI_NOTE_HASH: 0120f12f09ae4a1b1fe04f00f652834b :END: =git checkout --track origin/serverfix= which itself is shorthand for =git checkout -b serverfix origin/serverfix= ** When you =git fetch= from a remote (=git fetch origin=), does that give you editable copies of the new branches? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763947431152 :ANKI_NOTE_HASH: 7f59596789402c23c0347b506f678b0a :END: no, only unmodifiable pointers. you need to run =git merge origin/= which pulls in the changes into your _current_ branch. to make a new branch, use =git checkout -b serverfix origin/serverfix= ** How to push a branch up to a particular remote? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763947431157 :ANKI_NOTE_HASH: 01420a95d7c036c54c1e36abc3ceea0d :END: =git push = (will creating a branch and then running =git push= automatically push the branch?) ** How to pull changes down from a certain remote? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763947431162 :ANKI_NOTE_HASH: 07f5c408bda8561688018ed1124c6a9d :END: =git fetch = ** How can we get a full list of remote references? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763947431165 :ANKI_NOTE_HASH: 6417c4aed3daece8724fdaf957d9ab10 :END: =git ls-remote = OR =git remote show = ** How do you rename a branch? Are there perils? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763947431173 :ANKI_NOTE_HASH: c9aa9a36b00dd94e57b4b84a32e7e1c8 :END: Yes, perils! Check collaborators. =git branch --move = (performs the change locally) =git push --set-upstream origin = (pushes the changes to the remote) =git push origin --delete = (deletes old branch from the remote) ** What does =git branch --no-merged master= do? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763947431178 :ANKI_NOTE_HASH: 3581f6124d15c4ef72b8a0996e72a3cc :END: shows you which branches have not been merged into master. You can give the final argument to see info on a branch you don't have checked out. ** What do the =--merged= and =--no-merged= options do on =git branch=? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763947431182 :ANKI_NOTE_HASH: da08ac34f03e96dc44120236f422ba73 :END: shows you which branches are already merged into the branch you're on. =--no-merged= shows the branches that have work that you have not merged in. ** What happens when you run =git branch= with no arguments? What about if you add =-v=? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763947431189 :ANKI_NOTE_HASH: 74d0965fc35c3b7a7390ab389b82d17e :END: naked is a simple listing. #+BEGIN_SRC bash git branch iss53 ,* master testing #+END_SRC note that =*= tells you what is currently checked out! (i.e. where the HEAD points) =-v= also shows the last commit on each branch: #+BEGIN_SRC bash $ git branch -v iss53 93b412c Fix javascript issue ,* master 7a98805 Merge branch 'iss53' testing 782fd34 Add scott to the author list in the readme #+END_SRC ** How can you solve merge-conflicts? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763949559427 :ANKI_NOTE_HASH: c73461ee76bd266763537d9d01167835 :END: edit the files and choose the correct code. =git add= and =git commit= (staging the file marks it as resolved). you could also use =git mergetool= ** What happens when you do a =git merge= and the commit of the branch you're on is not a _direct_ ancestor of the branch you're merging in? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763949559435 :ANKI_NOTE_HASH: b116cef7a25f1c3d5a642f11985b873e :END: simple three-way merge. uses the two snapshots pointed to by the branch tips and the common ancestor of the two. [[file:img/three-way-merge.png]] [[file:img/merge-commit.png]] ** How to merge =hotfix= branch into =main=? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763949559440 :ANKI_NOTE_HASH: a266acfee369fd10892c7eadf90fb8da :END: =git checkout main= =git merge hotfix= note if you can fast-forward then you should delete the hotfix branch after merging: =git branch -d hotfix= ** What is "fast-forward"? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763949559461 :ANKI_NOTE_HASH: 9412b9842a2d8548a5edafb7599f5e3d :END: When the merge has no divergent work to merge together it just moves the branch pointer forward file:img/rebase2.png file:img/rebase3.png ** How can you create a new branch and switch to it in the same command? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763949559466 :ANKI_NOTE_HASH: 4cb37676c218ce9647733f8bdd1fd19c :END: =git checkout -b = alternatively you can now use =git switch= with =--create= / =-c= for a new branch. note =git switch -= changes to the last branch. [[file:img/change-head.png]] ** Is it expensive to create and delete branches? Explain. :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763949559473 :ANKI_NOTE_HASH: c8850816bba1aaf25a3ef713ff8bd925 :END: No, the pointers are just simple text files with the 40 character SHA1-hash checksums of the commit it points to. 41 bytes cost (+ newline) ** Which branches does =git log= show branches for? How can you modify this behaviour? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763949559497 :ANKI_NOTE_HASH: a7eeefa177717fd387e8a2b81ebeb109 :END: =git log = shows logs for an arbitrary branch =git log --all= shows for all branches but by default, it's whatever =HEAD= is pointing to. ** What is the command to switch an existing branch? How can you create a _new_ branch? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763949559503 :ANKI_NOTE_HASH: 254ed7ac16c76b8df8c512f4e9378884 :END: =git checkout = =git branch = [[file:img/new-branch.png]] ** What command can we use to see where the branch pointers are pointing? i.e. HEAD :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763949559507 :ANKI_NOTE_HASH: 8368e7b31a7fb5a423f03a8cdbfad839 :END: =git log --oneline --decorate= [[file:img/head-branch.png]] ** How does Git know what branch you're on? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763949559512 :ANKI_NOTE_HASH: dc2092b89f799b9cd1b911cf49706b5e :END: Keeps a special pointer called =HEAD= that is a pointer to the local branch [[file:img/head-branch.png]] ** How many pointers are in a commit object? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763949559518 :ANKI_NOTE_HASH: 49f62260caf81bf36596f767b4f5c2da :END: - 0 for the initial commit (no parents) - 1 for regular commits - multiple (2?) for merge commits [[file:img/commit-parents.png]] ** What happens when you make a commit? What does Git store? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763949559522 :ANKI_NOTE_HASH: b9af0d5954ee646e792a8abfc6bfd1e8 :END: stores a commit object with a pointer to the _snapshot_. also contains metadata + pointer/s to directly previous commits. [[file:img/commit-tree.png]] ** A branch in Git is simply a lightweight, movable {{c1::pointer}} to a commit. :PROPERTIES: :ANKI_NOTE_TYPE: Cloze :ANKI_NOTE_ID: 1763949559529 :ANKI_NOTE_HASH: 4ceee5895a54bc0abbea2a7911dcc879 :END: ** When does a file get a checksum? What does this imply has happened? :PROPERTIES: :ANKI_NOTE_TYPE: Basic :ANKI_NOTE_ID: 1763949559535 :ANKI_NOTE_HASH: ff2764a49ecb8d3f2f5ea6665a8ad71b :END: when the file is _staged_. implies a verison of the file has been stored. (called blobs) # local variables: # eval: (anki-editor-mode +1) # end: