diff options
Diffstat (limited to 'usth/MATH2.3/1')
| -rw-r--r-- | usth/MATH2.3/1/README.pdf | bin | 0 -> 206588 bytes | |||
| -rw-r--r-- | usth/MATH2.3/1/README.tex | 50 | ||||
| -rw-r--r-- | usth/MATH2.3/1/[Ch_Algorithm]_Practical.pdf | bin | 0 -> 32000 bytes | |||
| -rw-r--r-- | usth/MATH2.3/1/coin.c | 17 | ||||
| -rw-r--r-- | usth/MATH2.3/1/schedule.c | 30 | ||||
| -rw-r--r-- | usth/MATH2.3/1/search.c | 50 |
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; +} |