[usth/MATH2.3] Mathemate Discretely

6 files changed, 147 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;
+}