\documentclass{amsbook} \usepackage{graphicx} \usepackage{makecell} \newtheorem{theorem}{Theorem}[chapter] \newtheorem{lemma}[theorem]{Lemma} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{xca}[theorem]{Exercise} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \numberwithin{section}{chapter} \numberwithin{equation}{chapter} \begin{document} \frontmatter \title{Minqi's Solutions to the Exercises and Problems of Cormen, Leiserson, Rivest, Stein (2009), Introduction to Algorithms (3rd Edition)} \author{Minqi Pan\footnote{Website: http://www.minqi-pan.com}} \date{\today} \maketitle \setcounter{page}{4} \tableofcontents \listoffigures \mainmatter \chapter{The Role of Algorithms in Computing} \section{Exercise 1.1-1: Real-world Examples of Sorting and Computing a Convex Hull} Give a real-world example that requires sorting or a real-world example that requires computing a convex hull. \begin{proof}[Answer] Microsoft Windows provides a feature to sort all files in a folder by their sizes. Computing a convex hull is required in ethology to estimate an animal's home range based on the points where the animal has been observed. \end{proof} \section{Exercise 1.1-2: Other Measures of Efficiency} Other than speed, what other measures of efficiency might one use in a real-world setting? \begin{proof}[Answer] Number of CPU cycles / CPU instructions, memory usage, and scalability. \end{proof} \section{Exercise 1.1-3: Strengths and Limitations of a Data Structure} Select a data structure that you have seen previously, and discuss its strengths and limitations. \begin{proof}[Answer] A red-black tree automatically keeps its height small in the face of arbitrary item insertions and deletions. Thus it has the strength of faster search operations which takes time proportional to the height of the tree. But it has the limitation of slowing down insertion and deletion operations because of additional rebalancing procedures. \end{proof} \section{Exercise 1.1-4: Comparing Shortest-path and Traveling-salesman Problems} How are the shortest-path and traveling-salesman problems given above similar? How are they different? \begin{proof}[Answer] Both are trying to optimize path lengths to the shortest. The traveling-salesman problem has more constraints than the shortest-path problem, in that it requires all nodes to be visited and the path to be a loop. The shortest-path problem, on the other hand, does not require any particular set of nodes to be visited other than the source node and/or the destination node, nor does it require the path to be a loop. \end{proof} \section{Exercise 1.1-5: Real-world Problems Requiring Strict and Non-strict Optimizations} Come up with a real-world problem in which only the best solution will do. Then come up with one in which a solution that is approximately'' the best is good enough. \begin{proof}[Answer] Consider a delivery company with a central depot. Each day, it loads up each delivery truck at the depot and sends it around to deliver goods to several addresses. At the end of the day, each truck must end up back at the depot so that it is ready to be loaded for the next day. Suppose that the company has already purchased many delivery trucks and is trying to determine whether the fuel tank of each truck is big enough to finish a one-day delivery tour without refueling. Also suppose that the fuel tank capacities are relatively small, so that it is not obvious to decide. Then only the best solution (i.e., the shortest tour route) can answer this question. On the other hand, suppose that the delivery company has not purchased its delivery trucks yet, then the company can use the approximately'' best solution (i.e., the approximately'' shortest tour route) to decide the minimal fuel-tank capacity of the trucks to purchase. \end{proof} \section{Exercise 1.2-1: An Example of Application-level Algorithms} Give an example of an application that requires algorithmic content at the application level, and discuss the function of the algorithms involved. \begin{proof}[Answer] The Nest Learning Thermostat is a smart thermostat that optimizes heating and cooling of homes and businesses to conserve energy. This application requires energy load management and HVAC control algorithms to make it smart and helpful, whether that be through sensing, machine perception, control systems, pattern recognition, or preference learning. The function of the algorithms involved is to keep its users comfortable while saving them money and reducing the world's energy consumption. \end{proof} \section{Exercise 1.2-2: Comparing Insertion Sort with Merge Sort} Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size $n$, insertion sort runs in $8n^2$ steps, while merge sort runs in $64n\lg n$ steps. For which values on $n$ does insertion sort beat merge sort? \begin{proof}[Answer] For $n=1, 2, \dots, 43$, insertion sort beats merge sort. See Figure~\ref{Exercise 1.2-2}. \begin{figure}[ht] \begin{center} \includegraphics[width=.8\textwidth]{clrs_e_1_2_2.png} \end{center} \caption{Exercise 1.2-2: Comparing Insertion Sort with Merge Sort} \label{Exercise 1.2-2} \end{figure} \end{proof} \section{Exercise 1.2-3: Comparing $100n^2$ and $2^n$ Algorithms} What is the smallest value of $n$ such that an algorithm whose running time is $100n^2$ runs faster than an algorithm whose running time is $2^n$ on the same machine? \begin{proof}[Answer] The smallest value of $n$ is $15$. See Figure~\ref{Exercise 1.2-3}. \begin{figure}[ht] \begin{center} \includegraphics[width=.8\textwidth]{clrs_e_1_2_3.png} \end{center} \caption{Exercise 1.2-3: Comparing $100n^2$ and $2^n$ Algorithms} \label{Exercise 1.2-3} \end{figure} \end{proof} \section{Problem 1-1: Comparison of Running Times} For each function $f(n)$ and time $t$ in the following table, determine the largest size $n$ of a problem that can be solved in time $t$, assuming that the algorithm to solve the problem takes $f(n)$ microseconds. \begin{proof}[Answer] See Table~\ref{Problem 1-1}. \begin{table}[ht] \centering \begin{tabular}{c|c|c|c|c|c|c|c} & \makecell{1\\second} & \makecell{1\\minute} & \makecell{1\\hour} & \makecell{1\\day} & \makecell{1\\month} & \makecell{1\\year} & \makecell{1\\century} \\\hline $\lg n$ & $\approx 10^{10^6}$ & $\approx 10^{10^8}$ & $\approx 10^{10^9}$ & $\approx 10^{10^{10}}$ & $\approx 10^{10^{11}}$ & $\approx 10^{10^{12}}$ & $\approx 10^{10^{14}}$ \\\hline $\sqrt{n}$ & $10^{12}$ & $\approx 10^{15}$ & $\approx 10^{19}$ & $\approx 10^{21}$ & $\approx 10^{24}$ & $\approx 10^{26}$ & $\approx 10^{30}$ \\\hline $n$ & $10^{6}$ & $\approx 10^7$ & $\approx 10^9$ & $\approx 10^{10}$ & $\approx 10^{12}$ & $\approx 10^{13}$ & $\approx 10^{15}$ \\\hline $n\lg n$ & $62,746$ & $\approx 10^6$ & $\approx 10^8$ & $\approx 10^9$ & $\approx 10^{10}$ & $\approx 10^{11}$ & $\approx 10^{13}$ \\\hline $n^2$ & $1,000$ & $7,745$ & $60,000$ & $\approx 10^5$ & $\approx 10^6$ & $\approx 10^6$ & $\approx 10^7$ \\\hline $n^3$ & $100$ & $391$ & $1,532$ & $4,420$ & $13,737$ & $31,594$ & $146,645$ \\\hline $2^n$ & $19$ & $25$ & $31$ & $36$ & $41$ & $44$ & $51$ \\\hline $n!$ & $9$ & $11$ & $13$ & $14$ & $16$ & $17$ & $18$ \end{tabular} \caption{Problem 1-1: Comparison of Running Times} \label{Problem 1-1} \end{table} \end{proof} \end{document}