[usth/MATH2.3] Mathemate Discretely

35 files changed, 1196 insertions, 0 deletions

diff --git a/usth/MATH2.3/1/README.pdf b/usth/MATH2.3/1/README.pdf
new file mode 100644
index 0000000..2458e44
--- /dev/null
+++ b/usth/MATH2.3/1/README.pdf
Binary files differdiff --git a/usth/MATH2.3/1/README.tex b/usth/MATH2.3/1/README.tex
new file mode 100644
index 0000000..73916bf
--- /dev/null
+++ b/usth/MATH2.3/1/README.tex
@@ -0,0 +1,50 @@
+\documentclass[a4paper,12pt]{article}
+\usepackage[english,vietnamese]{babel}
+\usepackage{amsmath}
+\usepackage{hyperref}
+\usepackage{lmodern}
+\usepackage{mathtools}
+
+\title{Discrete Mathematics: Algorithm}
+\author{Nguyễn Gia Phong---BI9-184}
+\date{\dateenglish\today}
+
+\begin{document}
+\maketitle
+\section{Problem 3}
+The program \verb|coin.c| takes an integer $n$ from \verb|stdin| and print
+the least coin exchange of $n$ cents to \verb|stdout|.
+
+\section{Problem 4}
+The program \verb|schedule.c| take an integer $n$ and $n$ integral
+time intervals from \verb|stdin| and print to \verb|stdout| the chosen talks
+intervals in chronological order.
+
+\section{Problem 5}
+\verb|search.c| contains two searching implementations, linear search
+(\verb|lsearch|) and binary search (\verb|bsearch|).
+
+It is trivial that \verb|lsearch| has \verb|nmemb| or $\Theta(n)$
+time complexity.
+
+For \verb|binary_search| (which is wrapped by \verb|bsearch|),
+the time complexity (in term of number of comparisons) is can be seen as
+\begin{align*}
+  T(n) &= T\left(\frac{n}{2}\right) + \Theta(1)\\
+  &= T\left(\frac{n}{2}\right) + \Theta\left(n^{\log_2 1}\right)
+\end{align*}
+since \verb|mid = (lo + high) / 2)|.
+\pagebreak
+
+By the master theorem\footnote{Let $a \ge 1$ and $b > 1$ be constants,
+and let $T(n)$ be defined on the nonnegative integers by the recurrence
+\[T(n) = aT\left(\frac{n}{b}\right) + \Theta\left(n^{\log_b a}\right)\]
+where $n/b$ is interpreted as either $\lfloor n/b\rfloor$ or $\lceil n/b\rceil$,
+then \[T(n) = \Theta\left(n^{\log_b a}\lg n\right)\]},
+\[T(n) = \Theta\left(n^{\log_2 1}\lg n\right) = \Theta(\lg n)\]
+
+\section{Copying}
+This report along with the source files are licensed under a
+\href{https://creativecommons.org/licenses/by-sa/4.0/}{Creative Commons
+Attribution-ShareAlike 4.0 International License}.
+\end{document}
diff --git a/usth/MATH2.3/1/[Ch_Algorithm]_Practical.pdf b/usth/MATH2.3/1/[Ch_Algorithm]_Practical.pdf
new file mode 100644
index 0000000..057ee0b
--- /dev/null
+++ b/usth/MATH2.3/1/[Ch_Algorithm]_Practical.pdf
Binary files differdiff --git a/usth/MATH2.3/1/coin.c b/usth/MATH2.3/1/coin.c
new file mode 100644
index 0000000..d4fe339
--- /dev/null
+++ b/usth/MATH2.3/1/coin.c
@@ -0,0 +1,17 @@
+#include <stdio.h>
+
+int main()
+{
+	int pennies;
+	scanf("%d", &pennies);
+	int quarters = pennies / 25;
+	pennies %= 25;
+	int dimes = pennies / 10;
+	pennies %= 10;
+	int nickels = pennies / 5;
+	pennies %= 5;
+
+	printf("%d quarters, %d dimes, %d nickels and %d pennies\n",
+	       quarters, dimes, nickels, pennies);
+	return 0;
+}
diff --git a/usth/MATH2.3/1/schedule.c b/usth/MATH2.3/1/schedule.c
new file mode 100644
index 0000000..6b70ca7
--- /dev/null
+++ b/usth/MATH2.3/1/schedule.c
@@ -0,0 +1,30 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+struct talk {
+	int start, end;
+};
+
+int cmp(const void *x, const void *y)
+{
+	return ((struct talk *) x)->end - ((struct talk *) y)->end;
+}
+
+int main()
+{
+	size_t n;
+	scanf("%zu", &n);
+	struct talk *a = malloc(n * sizeof(struct talk));
+	for (size_t i = 0; i < n; ++i)
+		scanf("%d %d", &a[i].start, &a[i].end);
+
+	qsort(a, n, sizeof(struct talk), cmp);
+	int start = a->start;
+	for (size_t i = 0; i < n; ++i)
+		if (a[i].start >= start) {
+			printf("%d %d\n", a[i].start, a[i].end);
+			start = a[i].end;
+		}
+
+	return 0;
+}
diff --git a/usth/MATH2.3/1/search.c b/usth/MATH2.3/1/search.c
new file mode 100644
index 0000000..c9dd06d
--- /dev/null
+++ b/usth/MATH2.3/1/search.c
@@ -0,0 +1,50 @@
+#include <stdio.h>
+
+void *lsearch(const void *key, const void *base,
+              size_t nmemb, size_t size,
+              int (*compar)(const void *, const void *))
+{
+	for (const char *p = base; nmemb--;)
+		if (compar(key, p))
+			p += size;
+		else
+			return (void *) p;
+	return NULL;
+}
+
+void *binary_search(const void *key, const void *base,
+                    int lo, int hi, size_t size,
+                    int (*compar)(const void *, const void *))
+{
+	if (lo > hi)
+		return NULL;
+
+	int mid = (lo + hi) >> 1;
+	int c = compar(key, (char *) base + mid * size);
+	if (c > 0)
+		return binary_search(key, base, mid + 1, hi, size, compar);
+	if (c < 0)
+		return binary_search(key, base, lo, mid - 1, size, compar);
+	return (char *) base + mid * size;
+}
+
+void *bsearch(const void *key, const void *base,
+              size_t nmemb, size_t size,
+              int (*compar)(const void *, const void *))
+{
+	return binary_search(key, base, 0, nmemb, size, compar);
+}
+
+int cmp(const void *x, const void *y)
+{
+	return *(int *) x - *(int *) y;
+}
+
+int main()
+{
+	int a[] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 88};
+	int *l = lsearch(a + 7, a, sizeof(a) / sizeof(int), sizeof(int), cmp);
+	int *b = bsearch(a + 7, a, sizeof(a) / sizeof(int), sizeof(int), cmp);
+	printf("%zu %zu\n", l - a, b - a);
+	return 0;
+}
diff --git a/usth/MATH2.3/2/README.md b/usth/MATH2.3/2/README.md
new file mode 100644
index 0000000..df599a5
--- /dev/null
+++ b/usth/MATH2.3/2/README.md
@@ -0,0 +1,59 @@
+# Graphs
+## Problem 1
+`bipartite.cc` (C++17) takes an natural number `n` of edges and `n` lines
+of pairs of connected vertices from stdin and print either `yes` or `no` to
+stdout if the given graph is or is not bipartite respectively.
+
+## Problem 2
+`adjmat2edges.cc` takes an natural number `n` and a `n`-by-`n` adjacent matrix
+of natural numbers from stdin and print triplets (`u`, `v`, `m`) separated by
+spaces to stdout, where `u`, `v` are vertices and `m > 0` is the number of edges
+connecting these two.
+
+## Problem 3
+`incidentmat2edges.cc` take 2 natural numbers `v`, `e` and a `v`-by-`e`
+incidental matrix from stdin and print each edge along with number of its
+appearance to stdout, e.g.
+
+### Input
+    2 2
+    1 1
+    1 1
+
+### Output
+    0 1 2
+
+## Problem 4
+`dijkstra.cc` (C++17) takes a natural number `n` of edges, 2 positive numbers
+`s` and `e` (starting and ending of path), then `n` pairs of connected vertices
+(both in `1..1023`) and the edge's weight.  The output to stdout is the path
+and the length, e.g.
+
+### Input
+    9 1 6
+    1 2 4
+    1 3 2
+    2 3 1
+    2 4 5
+    3 5 10
+    3 4 8
+    4 5 2
+    4 6 6
+    5 6 3'
+
+### Output
+    1 3 2 4 5 6 (length of 13)
+
+## Problem 5
+`connected.cc` (C++17) takes a natural number `n` and `n` pairs of connected
+vertices from stdin and print the number of connected components of the given
+undirected graph to stdout, e.g.
+
+### Input
+    3
+    1 2
+    3 4
+    4 5
+
+### Output
+    2
diff --git a/usth/MATH2.3/2/[Ch_GraphTheory]_Practical.pdf b/usth/MATH2.3/2/[Ch_GraphTheory]_Practical.pdf
new file mode 100644
index 0000000..3ac3407
--- /dev/null
+++ b/usth/MATH2.3/2/[Ch_GraphTheory]_Practical.pdf
Binary files differdiff --git a/usth/MATH2.3/2/adjmat2edges.cc b/usth/MATH2.3/2/adjmat2edges.cc
new file mode 100644
index 0000000..d9cf14f
--- /dev/null
+++ b/usth/MATH2.3/2/adjmat2edges.cc
@@ -0,0 +1,18 @@
+#include <iostream>
+
+using namespace std;
+
+int
+main ()
+{
+  size_t n;
+  int b;
+  cin >> n;
+  for (size_t i = 0; i < n; ++i)
+    for (size_t j = 0; j < n; ++j)
+      {
+        cin >> b;
+        if (i <= j && b > 0)
+          cout << i << " " << j << " " << b << endl;
+      }
+}
diff --git a/usth/MATH2.3/2/bipartite.cc b/usth/MATH2.3/2/bipartite.cc
new file mode 100644
index 0000000..49b8dfd
--- /dev/null
+++ b/usth/MATH2.3/2/bipartite.cc
@@ -0,0 +1,55 @@
+#include <iostream>
+#include <queue>
+#include <unordered_map>
+#include <set>
+
+using namespace std;
+
+int
+main ()
+{
+  unordered_map<size_t, unordered_map<size_t, size_t>> adj;
+  size_t n, u, v;
+  cin >> n;
+  while (n--)
+    {
+      cin >> u >> v;
+      adj[u][v]++;
+      adj[v][u]++;
+    }
+
+  queue<size_t> q;
+  set<size_t> one, another;
+  q.push (u);
+  one.insert (u);
+
+  while (!q.empty ())
+    {
+      u = q.front ();
+      q.pop ();
+      if (adj[u][u])
+        {
+          cout << "no" << endl;
+          return 0;
+        }
+      for (auto const& [v, b] : adj[u])
+        {
+          if (!b)
+            continue;
+          if (one.count (v) && one.count (u)
+              || another.count (v) && another.count (u))
+            {
+              cout << "no" << endl;
+              return 0;
+            }
+          if (one.count (v) || another.count (v))
+            continue;
+          q.push (v);
+          if (one.count (u))
+            another.insert (v);
+          else
+            one.insert (v);
+        }
+    }
+  cout << "yes" << endl;
+}
diff --git a/usth/MATH2.3/2/connected.cc b/usth/MATH2.3/2/connected.cc
new file mode 100644
index 0000000..0659094
--- /dev/null
+++ b/usth/MATH2.3/2/connected.cc
@@ -0,0 +1,44 @@
+#include <iostream>
+#include <unordered_map>
+#include <unordered_set>
+#include <vector>
+
+using namespace std;
+
+int
+main ()
+{
+  size_t n, a, b;
+  unordered_map<size_t, unordered_set<size_t>> edges;
+
+  cin >> n;
+  for (size_t i = 0; i < n; ++i)
+    {
+      cin >> a >> b;
+      edges[a].insert (b);
+      edges[b].insert (a);
+    }
+
+  unordered_set<size_t> s;
+  size_t count = 0;
+  for (auto const& [v, p] : edges)
+    {
+      if (s.count (v))
+        continue;
+      count++;
+      vector<size_t> fifo {v};
+      while (!fifo.empty ())
+        {
+          size_t u = fifo.back ();
+          fifo.pop_back ();
+          if (s.count (u))
+            continue;
+          s.insert (u);
+          for (auto const& w : edges[u])
+            if (!s.count (w))
+              fifo.push_back (w);
+        }
+    }
+
+  cout << count << endl;
+}
diff --git a/usth/MATH2.3/2/dijkstra.cc b/usth/MATH2.3/2/dijkstra.cc
new file mode 100644
index 0000000..e8a7931
--- /dev/null
+++ b/usth/MATH2.3/2/dijkstra.cc
@@ -0,0 +1,55 @@
+#include <iostream>
+#include <deque>
+#include <queue>
+#include <unordered_map>
+#include <vector>
+
+#define ENCODE(w, c, p) (((w) << 20) + ((c) << 10) + (p))
+#define WEIGHT(x) ((x) >> 20)
+#define CUR(x) ((x) >> 10 & 1023)
+#define PREV(x) ((x) & 1023)
+
+using namespace std;
+
+int
+main ()
+{
+  size_t n, a, b, w, s, e;
+  unordered_map<size_t, unordered_map<size_t, size_t>> edges;
+
+  cin >> n >> s >> e;
+  for (size_t i = 0; i < n; ++i)
+    {
+      cin >> a >> b >> w;
+      edges[a][b] = edges[b][a] = w;
+    }
+
+  unordered_map<size_t, size_t> prev;
+  priority_queue<size_t, vector<size_t>, greater<size_t>> pq;
+  pq.push (ENCODE (0, s, s));
+
+  while (!pq.empty ())
+    {
+      size_t p = pq.top ();
+      a = PREV (p);
+      b = CUR (p);
+      w = WEIGHT (p);
+      if (!prev[b])
+        prev[b] = a;
+      if (b == e)
+        break;
+      pq.pop ();
+
+      for (auto const& [i, v] : edges[b])
+        if (!prev[i])
+          pq.push (ENCODE (w + v, i, b));
+    }
+
+  deque<size_t> d;
+  for (; e != s; e = prev[e])
+    d.push_front (e);
+  d.push_front (e);
+  for (auto const& i : d)
+    cout << i << " ";
+  cout << "(length of " << w << ")" << endl;
+}
diff --git a/usth/MATH2.3/2/incidentmat2edges.cc b/usth/MATH2.3/2/incidentmat2edges.cc
new file mode 100644
index 0000000..2fe5d79
--- /dev/null
+++ b/usth/MATH2.3/2/incidentmat2edges.cc
@@ -0,0 +1,33 @@
+#include <iostream>
+#include <map>
+#include <utility>
+
+using namespace std;
+
+int
+main ()
+{
+  int v, e, b;
+  map<pair<int, int>, int> m;
+
+  cin >> v >> e;
+  for (int i = 0; i < v; ++i)
+    {
+      pair<int, int> p {-1, -1};
+
+      for (int j = 0; j < e; ++j)
+        {
+          cin >> b;
+          if (!b)
+            continue;
+          if (p.first < 0)
+            p.first = p.second = j;
+          else
+            p.second = j;
+        }
+      m[p]++;
+    }
+
+  for (auto const& [p, c] : m)
+    cout << p.first << " " << p.second << " " << c << endl;
+}
diff --git a/usth/MATH2.3/3/README.md b/usth/MATH2.3/3/README.md
new file mode 100644
index 0000000..fed19eb
--- /dev/null
+++ b/usth/MATH2.3/3/README.md
@@ -0,0 +1,76 @@
+# Trees
+## Problem 1
+`graph-is-tree.cc` (C++17) take a natural numbers `n` and a `n`-by-`n` adjacent
+matrix from stdin and print to stdout either yes or no depending on whether the
+given graph is a tree or not, e.g.
+
+### Input
+    3
+    0 1 0
+    1 0 1
+    0 1 0
+
+### Output
+    yes
+
+## Problem 2
+`binary-search-tree.c` takes a natural number `n` and `n` integers from stdin
+and print to stdout a horizontal binary search tree formed (naïvely) from the
+given input, e.g.
+
+### Input
+    7
+    34 45 21 65 12 546 23
+
+### Output
+            12
+        21
+            23
+    34
+        45
+            65
+                546
+
+## Problem 3
+`dc.cc` takes from stdin a list of numbers and operator, each terminated by a
+semi-colon and print to stdout the evaluation of the given postfix arithmetic
+expression, e.g.
+
+### Input
+    6.9;4.20;+;2;^;6.9;4;-;3;/;+;
+
+### Output
+    124.177
+
+## Problem 4
+`st-dfs.cc` (C++17) takes a natural number `n` and an `n`-by-`n` adjacent
+matrix from stdin and print the edges on a spanning tree of the given graph to
+stdout, e.g.
+
+### Input
+    4
+    0 1 1 1
+    1 0 1 1
+    1 1 0 1
+    1 1 1 0
+
+### Output
+    2 3
+    0 3
+    1 2
+
+## Problem 5
+`sum-set.cc` takes a natural number `n` and a line of positive integers on one
+line from stdin and print numbers whose sum are `n`, separated by a newline, to
+stdout, e.g.
+
+### Input
+    7
+    1 2 3 4 5 6 7 8 9
+
+### Output
+    1 2 4
+    1 6
+    2 5
+    3 4
+    7
diff --git a/usth/MATH2.3/3/[Ch_Trees]_Practical.pdf b/usth/MATH2.3/3/[Ch_Trees]_Practical.pdf
new file mode 100644
index 0000000..cd0bef4
--- /dev/null
+++ b/usth/MATH2.3/3/[Ch_Trees]_Practical.pdf
Binary files differdiff --git a/usth/MATH2.3/3/a.out b/usth/MATH2.3/3/a.out
new file mode 100755
index 0000000..e3f63ce
--- /dev/null
+++ b/usth/MATH2.3/3/a.out
Binary files differdiff --git a/usth/MATH2.3/3/binary-search-tree.c b/usth/MATH2.3/3/binary-search-tree.c
new file mode 100644
index 0000000..725fa44
--- /dev/null
+++ b/usth/MATH2.3/3/binary-search-tree.c
@@ -0,0 +1,68 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#define MKTREE(entry, left, right) (cons((entry), cons((left), cons((right), NULL))))
+#define ENTRY(tree) (car((tree)))
+#define LEFT(tree) (car(cdr((tree))))
+#define RIGHT(tree) (car(cdr(cdr((tree)))))
+
+typedef struct list construct;
+struct list {
+	void *car;
+        construct *cdr;
+};
+
+construct *cons(void *first, construct *rest)
+{
+	construct *list = malloc(sizeof(construct));
+	list->car = first;
+	list->cdr = rest;
+	return list;
+}
+
+void *car(construct *list)
+{
+	return list->car;
+}
+
+construct *cdr(construct *list)
+{
+	return list->cdr;
+}
+
+construct *insert(void *a, construct *tree)
+{
+	if (tree == NULL)
+		return MKTREE(a, NULL, NULL);
+	if (*(int *) a < *(int *) ENTRY(tree))
+		return MKTREE(ENTRY(tree), insert(a, LEFT(tree)), RIGHT(tree));
+	return MKTREE(ENTRY(tree), LEFT(tree), insert(a, RIGHT(tree)));
+}
+
+void display(construct *tree, size_t indent)
+{
+	if (tree == NULL)
+		return;
+	display(LEFT(tree), indent + 1);
+	for (size_t i = 0; i++ < indent; putchar(9));
+	printf("%d", *(int *) ENTRY(tree));
+	putchar(10);
+	display(RIGHT(tree), indent + 1);
+}
+
+int main()
+{
+	size_t n;
+	scanf("%zu", &n);
+
+	construct *tree = NULL;
+	while (n--) {
+		int *a = malloc(sizeof(int));
+		scanf("%d", a);
+		tree = insert(a, tree);
+	}
+
+	display(tree, 0);
+
+	return 0;
+}
diff --git a/usth/MATH2.3/3/dc.cc b/usth/MATH2.3/3/dc.cc
new file mode 100644
index 0000000..b69742a
--- /dev/null
+++ b/usth/MATH2.3/3/dc.cc
@@ -0,0 +1,43 @@
+#include <cmath>
+#include <iostream>
+#include <sstream>
+#include <string>
+#include <vector>
+
+using namespace std;
+
+int
+main ()
+{
+  double num, x, y;
+  string op;
+  vector<double> v;
+
+  while (cin.peek () != '\n')
+    {
+      getline (cin, op, ';');
+      stringstream s {op};
+      s >> num;
+      if (s)
+        {
+          v.push_back (num);
+          continue;
+        }
+
+      y = v.back ();
+      v.pop_back ();
+      x = v.back ();
+      v.pop_back ();
+      if (op == "^")
+        v.push_back (pow (x, y));
+      else if (op == "+")
+        v.push_back (x + y);
+      else if (op == "-")
+        v.push_back (x - y);
+      else if (op == "*")
+        v.push_back (x * y);
+      else if (op == "/")
+        v.push_back (x / y);
+    }
+  cout << v.back () << endl;
+}
diff --git a/usth/MATH2.3/3/graph-is-tree.cc b/usth/MATH2.3/3/graph-is-tree.cc
new file mode 100644
index 0000000..f79564d
--- /dev/null
+++ b/usth/MATH2.3/3/graph-is-tree.cc
@@ -0,0 +1,56 @@
+#include <iostream>
+#include <unordered_map>
+#include <unordered_set>
+#include <vector>
+
+using namespace std;
+
+int
+main ()
+{
+  size_t n;
+  int b;
+  unordered_map<size_t, unordered_set<size_t>> edges;
+
+  int m = 0;
+  cin >> n;
+  for (size_t i = 0; i < n; ++i)
+    for (size_t j = 0; j < n; ++j)
+      {
+        cin >> b;
+        if (!b || i > j)
+          continue;
+        edges[i].insert (j);
+        edges[j].insert (i);
+        m++;
+      }
+
+  if (n - m - 1)
+    {
+      cout << "no" << endl;
+      return 0;
+    }
+
+  unordered_set<size_t> s;
+  int count = -1;
+  for (auto const& [v, p] : edges)
+    {
+      if (s.count (v))
+        continue;
+      count++;
+      vector<size_t> lifo {v};
+      while (!lifo.empty ())
+        {
+          size_t u = lifo.back ();
+          lifo.pop_back ();
+          if (s.count (u))
+            continue;
+          s.insert (u);
+          for (auto const& w : edges[u])
+            if (!s.count (w))
+              lifo.push_back (w);
+        }
+    }
+
+  cout << (count ? "no" : "yes") << endl;
+}
diff --git a/usth/MATH2.3/3/st-dfs.cc b/usth/MATH2.3/3/st-dfs.cc
new file mode 100644
index 0000000..89814dd
--- /dev/null
+++ b/usth/MATH2.3/3/st-dfs.cc
@@ -0,0 +1,44 @@
+#include <iostream>
+#include <unordered_map>
+
+using namespace std;
+
+void
+dfs (unordered_map<size_t, unordered_map<size_t, int>>& graph, 
+     unordered_map<size_t, int>& been, size_t current)
+{
+  been[current] = 1;
+  for (auto const& [i, b] : graph[current])
+    if (b > 0)
+      if (been[i])
+        graph[current][i] = graph[i][current] = 0;
+      else
+        {
+          graph[current][i] = graph[i][current] = -1;
+          dfs (graph, been, i);
+        }
+}
+
+int
+main ()
+{
+  size_t n;
+  unordered_map<size_t, unordered_map<size_t, int>> edges;
+
+  cin >> n;
+  for (size_t i = 0; i < n; ++i)
+    for (size_t j = 0; j < n; ++j)
+      {
+        cin >> edges[i][j];
+        edges[j][i] = edges[i][j];
+      }
+
+  unordered_map<size_t, unordered_map<size_t, int>> st;
+  unordered_map<size_t, int> been;
+  dfs (edges, been, 0);
+
+  for (auto const& [i, m] : edges)
+    for (auto const& [j, b] : m)
+      if (b && i <= j)
+        cout << i << " " << j << endl;
+}
diff --git a/usth/MATH2.3/3/sum-set.cc b/usth/MATH2.3/3/sum-set.cc
new file mode 100644
index 0000000..880fc6d
--- /dev/null
+++ b/usth/MATH2.3/3/sum-set.cc
@@ -0,0 +1,44 @@
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+void
+backtrack (vector<size_t>& big, vector<size_t>& smol, size_t& n, size_t index)
+{
+  size_t sum = 0;
+  for (auto const& i : smol)
+    sum += i;
+  if (sum == n)
+    {
+      for (auto const& i : smol)
+        cout << i << " ";
+      cout << endl;
+    }
+  else
+    for (size_t i = index; i < big.size (); ++i)
+      if (sum + big[i] <= n)
+        {
+          smol.push_back (big[i]);
+          backtrack (big, smol, n, i + 1);
+          smol.pop_back ();
+        }
+}
+
+int
+main ()
+{
+  size_t n;
+  size_t tmp;
+  vector<size_t> s;
+
+  cin >> n;
+  for (size_t i = 0; i < n; ++i)
+    {
+      cin >> tmp;
+      s.push_back (tmp);
+    }
+
+  vector<size_t> r;
+  backtrack (s, r, n, 0);
+}
diff --git a/usth/MATH2.3/4/README.md b/usth/MATH2.3/4/README.md
new file mode 100644
index 0000000..880dacf
--- /dev/null
+++ b/usth/MATH2.3/4/README.md
@@ -0,0 +1,71 @@
+# Booleans
+## Problem 1
+`deg3.c` prints the a table listing the set of values of all 256 Boolean
+functions of degree three to stdout.
+
+## Problem 2
+`sum-of-products.c` takes 2 natural numbers `n` and `f` from stdin, where `f`
+is the encoded truth table of a Boolean function of degree `n`, for example,
+
+|   x0  |   x1  | value |
+| :---: | :---: | :---: |
+|   0   |   0   |   1   |
+|   0   |   1   |   0   |
+|   1   |   0   |   1   |
+|   1   |   1   |   0   |
+
+will be encoded as `0b0101 = 5`.  The program then print the bitwise arithmetic
+sum-of-products expression to stdout, e.g.
+
+### Input
+    2 5
+
+### Output
+    ~x0&~x1 | ~x0&x1
+
+## Problem 3
+`k-map`, e.g.
+
+### Input
+    0 0 0 1
+    0 0 1 0
+    0 1 0 1
+    1 0 0 0
+    1 1 1 0
+    0 1 1 0
+    1 1 0 1
+    1 0 1 0
+
+### Output
+       00  01  10  11
+    0   1   0   1   1
+    0   0   0   0   0
+
+## Problem 4
+`threshold.c` takes in natural number `n`, a real threshold value `t` and `n`
+weights, then `n` boolean values from stdin and print to stdout the output of
+the given threshold gate, e.g.
+
+### Input
+    7 0.25051534245890184
+    0.11609819805105248
+    0.7924365005827357
+    0.9835187780201641
+    0.4235209817923591
+    0.08303890030044114
+    0.7196176517110272
+    0.988645113198539
+    1 1 0 1 1 0 1
+
+### Output
+    1
+
+## Problem 5
+`sum.c` takes similar input format from stdin and print the bitwise arithmetic
+expression using only bit flip (`~`) and addition (`|`) to stdout, e.g.
+
+### Input
+    3 69
+
+### Output
+    ~(~x0 | x1 | x2) | ~(~x0 | ~x1 | x2) | ~(~x0 | ~x1 | ~x2)
diff --git a/usth/MATH2.3/4/[Ch_Boolean]_Practical.pdf b/usth/MATH2.3/4/[Ch_Boolean]_Practical.pdf
new file mode 100644
index 0000000..fd3680e
--- /dev/null
+++ b/usth/MATH2.3/4/[Ch_Boolean]_Practical.pdf
Binary files differdiff --git a/usth/MATH2.3/4/deg3.c b/usth/MATH2.3/4/deg3.c
new file mode 100644
index 0000000..a4f5726
--- /dev/null
+++ b/usth/MATH2.3/4/deg3.c
@@ -0,0 +1,18 @@
+#include <stdio.h>
+
+int main()
+{
+	printf("(x y z)");
+	for (int i = 0; i < 8; ++i)
+		printf("\t(%d %d %d)", i & 4 && 1, i & 2 && 1, i & 1 && 1);
+	putchar(10);
+
+	for (int i = 0; i < 256; ++i) {
+		printf("f%02x", i);
+		for (int j = 0; j < 8; ++j)
+			printf("\t%d", i & 1 << j && 1);
+		putchar(10);
+	}
+
+	return 0;
+}
diff --git a/usth/MATH2.3/4/k-map.c b/usth/MATH2.3/4/k-map.c
new file mode 100644
index 0000000..ef19b80
--- /dev/null
+++ b/usth/MATH2.3/4/k-map.c
@@ -0,0 +1,16 @@
+#include <stdio.h>
+
+int main()
+{
+	int x, y, z, f[8];
+
+	for (int i = 0; i < 8; ++i) {
+		scanf("%d %d %d", &x, &y, &z);
+		scanf("%d", f + x + (y << 1) + (z << 2));
+	}
+
+	printf("\t00\t01\t10\t11\n0\t%d\t%d\t%d\t%d\n0\t%d\t%d\t%d\t%d\n",
+	       f[0], f[1], f[2], f[3], f[4], f[5], f[6], f[7]);
+
+	return 0;
+}
diff --git a/usth/MATH2.3/4/sum-of-products.c b/usth/MATH2.3/4/sum-of-products.c
new file mode 100644
index 0000000..3fac72b
--- /dev/null
+++ b/usth/MATH2.3/4/sum-of-products.c
@@ -0,0 +1,25 @@
+#include <stdio.h>
+
+int main()
+{
+	size_t n, f;
+	int b = 0;
+
+	scanf("%zu %zu", &n, &f);
+	for (size_t i = 0; !(i >> n); ++i) {
+		if (!(f & 1 << i))
+			continue;
+		if (b)
+			printf(" | ");
+		b = 1;
+		printf(i & 1 ? "x0" : "~x0");
+		for (size_t j = 1; j < n; ++j)
+			if (i & 1 << j)
+				printf("&x%zu", j);
+			else
+				printf("&~x%zu", j);
+	}
+	putchar(10);
+
+	return 0;
+}
diff --git a/usth/MATH2.3/4/sum.c b/usth/MATH2.3/4/sum.c
new file mode 100644
index 0000000..8fd28f3
--- /dev/null
+++ b/usth/MATH2.3/4/sum.c
@@ -0,0 +1,26 @@
+#include <stdio.h>
+
+int main()
+{
+	size_t n, f;
+	int b = 0;
+
+	scanf("%zu %zu", &n, &f);
+	for (size_t i = 0; !(i >> n); ++i) {
+		if (!(f & 1 << i))
+			continue;
+		if (b)
+			printf(" | ");
+		b = 1;
+		printf(i & 1 ? "~(x0" : "~(~x0");
+		for (size_t j = 1; j < n; ++j)
+			if (i & 1 << j)
+				printf(" | ~x%zu", j);
+			else
+				printf(" | x%zu", j);
+		putchar(41);
+	}
+	putchar(10);
+
+	return 0;
+}
diff --git a/usth/MATH2.3/4/threshold.c b/usth/MATH2.3/4/threshold.c
new file mode 100644
index 0000000..5c39b3c
--- /dev/null
+++ b/usth/MATH2.3/4/threshold.c
@@ -0,0 +1,23 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+int main()
+{
+	size_t n;
+	scanf("%zu", &n);
+
+	double t, *weights = malloc(n * sizeof(double));
+	scanf("%lf", &t);
+	for (size_t i = 0; i < n; ++i)
+		scanf("%lf", weights + i);
+
+	int tmp;
+	for (size_t i = 0; i < n; ++i) {
+		scanf("%d", &tmp);
+		t -= tmp && weights[i];
+	}
+
+	putchar((t <= 0) + 48);
+	putchar(10);
+	return 0;
+}
diff --git a/usth/MATH2.3/5/README.md b/usth/MATH2.3/5/README.md
new file mode 100644
index 0000000..70e52fa
--- /dev/null
+++ b/usth/MATH2.3/5/README.md
@@ -0,0 +1,105 @@
+# Computations
+## Problem 1
+`automata.c`, e.g.
+
+### Input
+    4
+    1 1 3
+    0 1 2
+    0 3 0
+    1 1 2
+    4 0011
+
+### Output
+    yes
+
+## Problem 2
+`nfa.cc` takes a state table of a non-deterministic finite-state automaton, its
+final states and a string from stdin and print either `yes` or `no` to stdout
+to answer whether this string is recognized by the automaton, e.g.
+
+### Input
+    12
+    0 0 0
+    0 0 1
+    0 1 3
+    1 0 0
+    1 1 1
+    1 1 3
+    2 1 0
+    2 1 2
+    3 0 0
+    3 0 1
+    3 0 2
+    3 1 1
+    2
+    2 3
+    101
+
+### Output
+    yes
+
+## Problem 3
+`automata-to-grammar.c`
+
+### Input
+    4
+    1 1 3
+    0 1 2
+    0 3 0
+    1 1 2
+
+### Output
+    S -> $
+    S -> 0T
+    S -> 1V
+    T -> 0T
+    T -> 1U
+    U -> 0V
+    U -> 1S
+    V -> $
+    V -> 0T
+    V -> 1U
+
+## Problem 4
+`grammar-to-automata.cc` (C++17)
+
+### Input
+    10
+    S -> $
+    S -> 0T
+    S -> 1V
+    T -> 0T
+    T -> 1U
+    U -> 0V
+    U -> 1S
+    V -> $
+    V -> 0T
+    V -> 1U
+
+### Output
+    4
+    V       T       U       1
+    U       V       S       0
+    S       T       V       1
+    T       T       U       0
+
+## Problem 5
+`turing.cc` (C++17) takes a natural number `n` and `n` 5-tuples representing a
+Turing machine (with `-1` being the blank), a natural number `m` and a string
+of `m` binaries from stdin, then print the output string to stdout, e.g.
+
+### Input
+    7
+    0 0 0 0 1
+    0 1 1 1 1
+    0 -1 3 -1 1
+    1 0 0 0 1
+    1 1 2 0 -1
+    1 -1 3 -1 1
+    2 1 3 0 1
+    6
+    0 1 0 1 1 0
+
+### Output
+    010000
diff --git a/usth/MATH2.3/5/[Ch_Automata]_Practical.pdf b/usth/MATH2.3/5/[Ch_Automata]_Practical.pdf
new file mode 100644
index 0000000..47d14ce
--- /dev/null
+++ b/usth/MATH2.3/5/[Ch_Automata]_Practical.pdf
Binary files differdiff --git a/usth/MATH2.3/5/automata-to-grammar.c b/usth/MATH2.3/5/automata-to-grammar.c
new file mode 100644
index 0000000..430782a
--- /dev/null
+++ b/usth/MATH2.3/5/automata-to-grammar.c
@@ -0,0 +1,16 @@
+#include <stdio.h>
+
+int main()
+{
+	int n, b, j, k;
+
+	scanf("%d", &n);
+	for (int i = 0; i < n; ++i) {
+		scanf("%d %d %d", &b, &j, &k);
+		if (b)
+			printf("%c -> $\n", 'S' + i);
+		printf("%c -> 0%c\n%c -> 1%c\n", i+83, j+83, i+83, k+83);
+	}
+
+	return 0;
+}
diff --git a/usth/MATH2.3/5/automata.c b/usth/MATH2.3/5/automata.c
new file mode 100644
index 0000000..d18ca1e
--- /dev/null
+++ b/usth/MATH2.3/5/automata.c
@@ -0,0 +1,24 @@
+#include <stdio.h>
+
+int main() {
+	int n;
+	scanf("%d", &n);
+
+	int F[n], f[n][2];
+	for (int i = 0; i < n; ++i)
+		scanf("%d %d %d", F + i, f[i], f[i] + 1);
+
+	int m;
+	scanf("%d ", &m);
+
+	char c[m + 1];
+	scanf("%s", c);
+
+	int state = 0;
+	for (int i = 0; i < m; ++i)
+		state = f[state][c[i] - 48];
+
+	puts(F[state] ? "yes" : "no");
+
+	return 0;
+}
diff --git a/usth/MATH2.3/5/grammar-to-automata.cc b/usth/MATH2.3/5/grammar-to-automata.cc
new file mode 100644
index 0000000..125b3c9
--- /dev/null
+++ b/usth/MATH2.3/5/grammar-to-automata.cc
@@ -0,0 +1,29 @@
+#include <iostream>
+#include <string>
+#include <unordered_map>
+
+using namespace std;
+
+int
+main ()
+{
+  int n;
+  cin >> n;
+
+  unordered_map<char, unordered_map<int, char>> automata;
+  unordered_map<char, int> finals;
+  for (int i = 0; i < n; ++i)
+    {
+      char c;
+      string s, t;
+      cin >> c >> t >> s;
+      if (s == "$")
+        finals[c] = 1;
+      else
+        automata[c][s[0] - '0'] =  (s.length () == 1) ? '$' : s[1];
+    }
+
+  cout << automata.size () << endl;
+  for (auto& [c, m] : automata)
+    cout << c << '\t' << m[0] << '\t' << m[1] << '\t'  << finals[c] << endl;
+}
diff --git a/usth/MATH2.3/5/nfa.cc b/usth/MATH2.3/5/nfa.cc
new file mode 100644
index 0000000..8401202
--- /dev/null
+++ b/usth/MATH2.3/5/nfa.cc
@@ -0,0 +1,45 @@
+#include <iostream>
+#include <string>
+#include <unordered_map>
+#include <vector>
+
+using namespace std;
+
+bool
+recognize (unordered_map<int, unordered_map<int, vector<int>>>& f,
+           unordered_map<int, bool>& F, string& s, int i, int r)
+{
+  if (i >= s.size ())
+    return F[r];
+  for (auto const& t : f[r][s[i] - '0'])
+    if (recognize (f, F, s, i + 1, t))
+      return true;
+  return false;
+}
+
+int
+main ()
+{
+  int n;
+  unordered_map<int, unordered_map<int, vector<int>>> f;
+  cin >> n;
+  while (n--)
+    {
+      int s, i, r;
+      cin >> s >> i >> r;
+      f[s][i].push_back (r);
+    }
+
+  unordered_map<int, bool> F;
+  cin >> n;
+  while (n--)
+    {
+      int s;
+      cin >> s;
+      F[s] = true;
+    }
+
+  string s;
+  cin >> s;
+  cout << (recognize (f, F, s, 0, 0) ? "yes" : "no") << endl;
+}
diff --git a/usth/MATH2.3/5/turing.cc b/usth/MATH2.3/5/turing.cc
new file mode 100644
index 0000000..7ef5deb
--- /dev/null
+++ b/usth/MATH2.3/5/turing.cc
@@ -0,0 +1,56 @@
+#include <iostream>
+#include <deque>
+#include <tuple>
+#include <unordered_map>
+
+using namespace std;
+
+int
+main ()
+{
+  int n;
+  unordered_map<int, unordered_map<int, tuple<int, int, int>>> tuples;
+  cin >> n;
+  while (n--)
+    {
+      int s, x, t, y, d;
+      cin >> s >> x >> t >> y >> d;
+      tuples[s][x] = {t, y, d};
+    }
+
+  deque<int> input;
+  cin >> n;
+  while (n--)
+    {
+      int i;
+      cin >> i;
+      input.push_back (i);
+    }
+
+  int o {0}, i {0}, s {0}, x, d;
+  for (;;)
+    {
+      tie (s, x, d) = tuples[s][input[i - o]];
+      if (!d)
+        break;
+
+      if (i < o)
+        {
+          input.push_front (x);
+          o++;
+        }
+      else if (i - o == input.size ())
+        input.push_back (x);
+      else
+        input[i - o] = x;
+
+      if (d < 0)
+        i--;
+      else
+        i++;
+    }
+
+  for (auto const& i : input)
+    cout << i;
+  cout << endl;
+}