8 files changed, 331 insertions, 0 deletions
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);
+}