# Untitled

Sep 20th, 2020
936
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. Finite state machine:
2. \item[vi.] $$\{ w : w \text{ contains an even number of 0s or exactly two 1s} \}$$ \\
3.     \begin{tikzpicture}[shorten >= 1pt, node distance = 2cm, on grid, auto]
4.         \node[state, accepting, initial] (s00) {};
5.         \node[state, above of = s00] (s10) {};
6.         \node[state, accepting, right of = s00] (s01) {};
7.         \node[state, right of = s10] (s11) {};
8.         \node[state, accepting, right of = s01] (s02) {};
9.         \node[state, accepting, right of = s11] (s12) {};
10.         \node[state, accepting, right of = s02] (s03) {};
11.         \node[state, right of = s12] (s13) {};
12.         \draw[->]
13.             (s00)
14.                 edge[bend left] node {0} (s10)
15.                 edge node {1} (s01)
16.             (s10)
17.                 edge[bend left] node {0} (s00)
18.                 edge node {1} (s11)
19.             (s01)
20.                 edge[bend left] node {0} (s11)
21.                 edge node {1} (s02)
22.             (s11)
23.                 edge[bend left] node {0} (s01)
24.                 edge node {1} (s12)
25.             (s02)
26.                 edge[bend left] node {0} (s12)
27.                 edge node {1} (s03)
28.             (s12)
29.                 edge[bend left] node {0} (s02)
30.                 edge node {1} (s13)
31.             (s03)
32.                 edge[bend left] node {0} (s13)
33.                 edge[loop right] node {1} ()
34.             (s13)
35.                 edge[bend left] node {0} (s03)
36.                 edge[loop right] node {1} ()
37.         ;
38.     \end{tikzpicture}
39.
40. B+ tree (don't do this lol):
41. \begin{tikzpicture}[shorten >= 1pt, node distance = 0.3cm, on grid, auto]
42.     \node (11) {$|$};
43.     \node[right of = 11] (12) {12};
44.     \node[right of = 12] (13) {$|$};
45.     \node[right of = 13] (14) {13};
46.     \node[right of = 14] (15) {$|$};
47.     \node[right of = 15] (16) {17};
48.     \node[right of = 16] (17) {$|$};
49.     \node[right of = 17] (18) {18};
50.     \node[right of = 18] (19) {$|$};
51.
52.     \node[right of = 19] (20) {};
53.
54.     \node[right of = 20] (21) {$|$};
55.     \node[right of = 21] (22) {22};
56.     \node[right of = 22] (23) {$|$};
57.     \node[right of = 23] (24) {39};
58.     \node[right of = 24] (25) {$|$};
59.     \node[right of = 25] (26) {40};
60.     \node[right of = 26] (27) {$|$};
61.     \node[right of = 27] (29) {$|$};
62.
63.     \node[right of = 29] (30) {};
64.
65.     \node[right of = 30] (31) {$|$};
66.     \node[right of = 31] (32) {45};
67.     \node[right of = 32] (33) {$|$};
68.     \node[right of = 33] (34) {53};
69.     \node[right of = 34] (35) {$|$};
70.     \node[right of = 35] (37) {$|$};
71.     \node[right of = 37] (39) {$|$};
72.
73.     \node[right of = 39] (40) {};
74.
75.     \node[right of = 40] (41) {$|$};
76.     \node[right of = 41] (42) {55};
77.     \node[right of = 42] (43) {$|$};
78.     \node[right of = 43] (44) {56};
79.     \node[right of = 44] (45) {$|$};
80.     \node[right of = 45] (47) {$|$};
81.     \node[right of = 47] (49) {$|$};
82.
83.     \node[right of = 49] (50) {};
84.
85.     \node[right of = 50] (51) {$|$};
86.     \node[right of = 51] (52) {58};
87.     \node[right of = 52] (53) {$|$};
88.     \node[right of = 53] (54) {60};
89.     \node[right of = 54] (55) {$|$};
90.     \node[right of = 55] (56) {69};
91.     \node[right of = 56] (57) {$|$};
92.     \node[right of = 57] (59) {$|$};
93.
94.     \node[right of = 59] (60) {};
95.
96.     \node[right of = 60] (61) {$|$};
97.     \node[right of = 61] (62) {71};
98.     \node[right of = 62] (63) {$|$};
99.     \node[right of = 63] (64) {91};
100.     \node[right of = 64] (65) {$|$};
101.     \node[right of = 65] (66) {98};
102.     \node[right of = 66] (67) {$|$};
103.     \node[right of = 67] (69) {$|$};
104.
105.     \node[above of = 15] (15_) {};
106.     \node[above of = 25] (25_) {};
107.     \node[above of = 35] (35_) {};
108.     \node[above of = 44] (44_) {};
109.     \node[above of = 55] (55_) {};
110.     \node[above of = 65] (65_) {};
111.
112.     \node[above of = 21] (21_) {};
113.     \node[above of = 21_] (21__) {};
114.     \node[above of = 21__] (__A1) {};
115.     \node[above of = __A1] (_A1) {};
116.
117.     \node[above of = _A1] (A1) {$|$};
118.     \node[right of = A1] (A2) {22};
119.     \node[right of = A2] (A3) {$|$};
120.     \node[right of = A3] (A4) {45};
121.     \node[right of = A4] (A5) {$|$};
122.     \node[right of = A5] (A7) {$|$};
123.     \node[right of = A7] (A9) {$|$};
124.
125.     \node[below of = A3] (_A3) {};
126.     \node[below of = A5] (_A5) {};
127.     \node[below of = A7] (_A7) {};
128.     \node[below of = A9] (_A9) {};
129.
130.     \node[above of = 51] (51_) {};
131.     \node[above of = 51_] (51__) {};
132.     \node[above of = 51__] (__B1) {};
133.     \node[above of = __B1] (_B1) {};
134.
135.     \node[above of = _B1] (B1) {$|$};
136.     \node[right of = B1] (B2) {58};
137.     \node[right of = B2] (B3) {$|$};
138.     \node[right of = B3] (B4) {71};
139.     \node[right of = B4] (B5) {$|$};
140.     \node[right of = B5] (B7) {$|$};
141.     \node[right of = B7] (B9) {$|$};
142.
143.     \node[below of = B3] (_B3) {};
144.     \node[below of = B5] (_B5) {};
145.     \node[below of = B7] (_B7) {};
146.     \node[below of = B9] (_B9) {};
147.
148.     \node[above of = A4] (A4_) {};
149.     \node[above of = B4] (B4_) {};
150.
151.     \node[above of = 35] (35_) {};
152.     \node[above of = 35_] (35__) {};
153.     \node[above of = 35__] (35___) {};
154.     \node[above of = 35___] (35____) {};
155.     \node[above of = 35____] (____) {};
156.     \node[above of = ____] (____1) {};
157.     \node[above of = ____1] (___1) {};
158.     \node[above of = ___1] (__1) {};
159.     \node[above of = __1] (_1) {};
160.
161.     \node[above of = _1] (1) {$|$};
162.     \node[right of = 1] (2) {55};
163.     \node[right of = 2] (3) {$|$};
164.     \node[right of = 3] (5) {$|$};
165.     \node[right of = 5] (7) {$|$};
166.     \node[right of = 7] (9) {$|$};
167.
168.     \node[below of = 3] (_3) {};
169.     \node[below of = 5] (_5) {};
170.     \node[below of = 7] (_7) {};
171.     \node[below of = 9] (_9) {};
172.
173.     \draw[->]
174.         (_1) edge node {} (A4_)
175.         (_3) edge node {} (B4_)
176.
177.         (_A1) edge node {} (15_)
178.         (_A3) edge node {} (25_)
179.         (_A5) edge node {} (35_)
180.         (_B1) edge node {} (44_)
181.         (_B3) edge node {} (55_)
182.         (_B5) edge node {} (65_)
183.     ;
184. \end{tikzpicture}
185.
186. Plotted graph:
187. \item[3.]
188.     Find an optimal solution of the following linear program.
189.
190.     \begin{tabular}{ l c c c }
191.         maximise & $$x + 3y$$ & & \\
192.         subject to & $$3x + y$$ & $\geq$ & $6$ \\
193.         & $$x + 7y$$ & $\leq$ & $14$ \\
194.         & $$y$$ & $\geq$ & $x$ \\
195.         & $$x, y$$ & $\geq$ & $0$ \\
196.     \end{tabular}
197.
198.     Sketch: \\
199.     \begin{tikzpicture}[line width = 0.3mm, fill opacity = 0.2]
200.         \clip (0,0) rectangle (7, 7);
201.
202.         \draw[line width=0.1mm] (0, 0) grid (15, 15);
203.
204.         \draw[fill = gray] (2, 0) -- (0, 6) -- (0, 0) -- cycle;
205.         \draw[fill = gray] (14, 0) -- (0, 2) -- (0, 15) -- (15, 15) -- (15, 0) -- cycle;
206.         \draw[fill = gray] (0, 0) -- (15, 15) -- (15, 0) -- cycle;
207.     \end{tikzpicture}
208.
209. Instruction assignment (a bit long, probably should have done some of this with macros):
210. \begin{tikzpicture}[shorten >= 1pt, node distance = 2.5cm, on grid, auto]
211.     \node (s1) {STOREW};
212.     \node[below left of = s1, node distance = 5cm] (s2) {OFFSET};
213.     \node[below left of = s2] (s3) {GLOBAL \_a};
214.     \node[below right of = s2] (s4) {LSL};
215.     \node[below left of = s4] (s5) {LOADW};
216.     \node[below of = s5] (s6) {OFFSET};
217.     \node[below left of = s6] (s7) {GLOBAL \_a};
218.     \node[below right of = s6] (s8) {LSL};
219.     \node[below left of = s8] (s9) {LOADW};
220.     \node[below of = s9] (s10) {LOCAL \_i};
221.     \node[below right of = s8] (s11) {CONST 2};
222.     \node[below right of = s4] (s12) {CONST 2};
223.     \node[below right of = s1, node distance = 7.5cm] (s13) {PLUS};
224.     \node[below left of = s13] (s14) {LOADW};
225.     \node[below of = s14] (s15) {OFFSET};
226.     \node[below left of = s15] (s16) {GLOBAL \_a};
227.     \node[below right of = s15] (s17) {LSL};
228.     \node[below left of = s17] (s18) {LOADW};
229.     \node[below of = s18] (s19) {LOCAL \_i};
230.     \node[below right of = s17] (s20) {CONST 2};
231.     \node[below right of = s13] (s21) {LOADW};
232.     \node[below of = s21] (s22) {LOCAL \_i};
233.
234.     \begin{pgfonlayer}{background}
235.         \foreach \nodename in {s1, s2, s3, s4, s5, s6, s7, s8, s9, s10, s11, s12, s13, s14, s15, s16, s17, s18, s19, s20, s21, s22} {
236.             \coordinate (\nodename') at (\nodename);
237.         }
238.
239.         \path[draw=red,line width=2cm,line cap=round,line join=round] (s1')--(s2')--(s2')--(s4')--(s12');
240.         \path[draw=white,line width=1.9cm,line cap=round,line join=round] (s1')--(s2')--(s2')--(s4')--(s12');
241.
242.         \path[draw=blue,fill=blue] (s3') circle(1cm);
243.         \path[fill=white,draw=white] (s3') circle(0.95cm);
244.
245.         \path[draw=green,line width=2cm,line cap=round,line join=round] (s5')--(s6')--(s8')--(s11');
246.         \path[draw=white,line width=1.9cm,line cap=round,line join=round] (s5')--(s6')--(s8')--(s11');
247.
248.         \path[draw=blue,fill=blue] (s7') circle(1cm);
249.         \path[fill=white,draw=white] (s7') circle(0.95cm);
250.
251.         \path[draw=yellow,line width=2cm,line cap=round,line join=round] (s9')--(s10');
252.         \path[draw=white,line width=1.9cm,line cap=round,line join=round] (s9')--(s10');
253.
254.         \path[draw=cyan,fill=cyan] (s13') circle(1cm);
255.         \path[fill=white,draw=white] (s13') circle(0.95cm);
256.
257.         \path[draw=green,line width=2cm,line cap=round,line join=round] (s14')--(s15')--(s17')--(s20');
258.         \path[draw=white,line width=1.9cm,line cap=round,line join=round] (s14')--(s15')--(s17')--(s20');
259.
260.         \path[draw=blue,fill=blue] (s16') circle(1cm);
261.         \path[fill=white,draw=white] (s16') circle(0.95cm);
262.
263.         \path[draw=yellow,line width=2cm,line cap=round,line join=round] (s18')--(s19');
264.         \path[draw=white,line width=1.9cm,line cap=round,line join=round] (s18')--(s19');
265.
266.         \path[draw=yellow,line width=2cm,line cap=round,line join=round] (s21')--(s22');
267.         \path[draw=white,line width=1.9cm,line cap=round,line join=round] (s21')--(s22');
268.
269.     \end{pgfonlayer}
270.
271.     \draw[->]
272.         (s1) edge node {str} (s2)
273.             (s2) edge node {u3} (s3)
274.             (s2) edge node {} (s4)
275.                 (s4) edge node {u2} (s5)
276.                     (s5) edge node {ldr} (s6)
277.                         (s6) edge node {u1} (s7)
278.                         (s6) edge node {} (s8)
279.                             (s8) edge node {u0} (s9)
280.                                 (s9) edge node {ldr} (s10)
281.                             (s8) edge node {} (s11)
282.                 (s4) edge node {} (s12)
283.         (s1) edge node {u8} (s13)
284.             (s13) edge node {u6} (s14)
285.                 (s14) edge node {ldr} (s15)
286.                     (s15) edge node {u5} (s16)
287.                     (s15) edge node {} (s17)
288.                         (s17) edge node {u4} (s18)
289.                             (s18) edge node {ldr} (s19)
290.                         (s17) edge node {} (s20)
291.             (s13) edge node {u7} (s21)
292.                 (s21) edge node {ldr} (s22)
293.     ;
294.
295.     \node[above right of = s13, node distance = 0.7cm] () {add};
296. \end{tikzpicture}
297. \begin{lstlisting}
298. ldr u0, [fp, #_i]
299. set u1, #_a
300. ldr u2, [u1, u0, LSL #2]
301. set u3, #_a
302. ldr u4, [fp, #_i]
303. set u5, #_a
304. ldr u6, [u5, u4, LSL #2]
305. ldr u7, [fp, #_i]