blob: 73916bf38cb4a7778cf60da8dd2ced39932f81fc (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
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}
|
