Skip to main content
Engineering LibreTexts

4.5: Exercises

  • Page ID
    7338
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Exercise \(4.1\)

    In Section \(4.1\) we estimated the monetary cost of large computations, using pricing information from Amazon EC2 cloud computing service. This reflects the cost of doing a huge computation using a general-purpose \(C P U\). For long-lived computations, the dominating cost is not the one-time cost of the hardware, but rather the cost of electricity powering the hardware. Because of that, it can be much cheaper to manufacture special-purpose hardware. Depending on the nature of the computation, special-purpose hardware can be significantly more energy-efficient.

    This is the situation with the Bitcoin cryptocurrency. Mining Bitcoin requires evaluating the SHA-256 cryptographic hash function as many times as possible, as fast as possible. When mining Bitcoin today, the only economically rational choice is to use specialpurpose hardware that does nothing except evaluate SHA-256, but is millions (maybe billions) of times more energy efficient than a general-purpose CPU evaluating SHA-256.

    1. The relevant specs for Bitcoin mining hardware are wattage and giga-hashes (or terahashes) per second, which can be converted into raw energy required per hash. Search online and find the most energy efficient mining hardware you can (e.g., least joules per hash)
    2. Find the cheapest real-world electricity rates you can, anywhere in the world. Use these to estimate the monetary cost of computing \(2^{40}, 2^{50}, \ldots, 2^{120} \mathrm{SHA}-256\) hashes
    3. Money is not the only way to measure the energy cost of a huge computation. Search online to find out how much carbon dioxide \(\left(\mathrm{CO}_{2}\right)\) is placed into the atmosphere per unit of electrical energy produced, under a typical distribution of power production methods. Estimate how many tons of \(\mathrm{CO}_{2}\) are produced as a side-effect of computing \(2^{40}, 2^{50}, \ldots, 2^{120}\) SHA-256 hashes.
    4. \(\star\) Estimate the corresponding \(\mathrm{CO}_{2}\) concentration (parts per million) in the atmosphere as a result of computing \(2^{40}, 2^{50}, \ldots, 2^{120} \mathrm{SHA}-256\) hashes. If it is possible without a PhD in climate science, try to estimate the increase in average global temperature caused by these computations.
    Exercise \(4.2\)

    Which of the following are negligible functions in \(\lambda\) ? Justify your answers. \[\frac{1}{2^{\lambda / 2}} \quad \frac{1}{2^{\log \left(\lambda^{2}\right)}} \quad \frac{1}{\lambda^{\log (\lambda)}} \quad \frac{1}{\lambda^{2}} \quad \frac{1}{2^{(\log \lambda)^{2}}} \quad \frac{1}{(\log \lambda)^{2}} \quad \frac{1}{\lambda^{1 / \lambda}} \quad \frac{1}{\sqrt{\lambda}} \quad \frac{1}{2^{\sqrt{\lambda}}}\]

    Exercise \(4.3\)

    Suppose \(f\) and \(g\) are negligible.

    1. Show that \(f+g\) is negligible.
    2. Show that \(f \cdot g\) is negligible.
    3. Give an example \(f\) and \(g\) which are both negligible, but where \(f(\lambda) / g(\lambda)\) is not negligible.
    Exercise \(4.4\)

    Show that when \(f\) is negligible, then for every polynomial \(p\), the function \(p(\lambda) f(\lambda)\) not only approaches 0 , but it is also negligible itself.

    Hint: Use the contrapositive. Support that \(p\left ( \lambda  \right )f\left ( \lambda  \right )\) is non-negligible, where \(p\) is a polynomial. Conclude that \(f\) must also be non-negligible.

    Exercise \(4.5\)

    Prove that the \(\approx\) relation is transitive. Let \(f, g, h: \mathbb{N} \rightarrow \mathbb{R}\) be functions. Using the definition of the \(\approx\) relation, prove that if \(f \approx g\) and \(g \approx h\) then \(f \approx h\). You may find it useful to invoke the triangle inequality: \(|a-c| \leqslant|a-b|+|b-c|\).

    Exercise \(4.6\)

    Prove Lemma 4.6.

    Exercise \(4.7\)

    Prove Lemma 4.7.

    Exercise \(\star 4.8\)

    A deterministic program is one that uses no random choices. Suppose \(\mathcal{L}_{1}\) and \(\mathcal{L}_{2}\) are two deterministic libraries with a common interface. Show that either \(\mathcal{L}_{1} \equiv \mathcal{L}_{2}\), or else \(\mathcal{L}_{1} \&\) \(\mathcal{L}_{2}\) can be distinguished with advantage \(1 .\)

    Exercise \(4.9\)

    Algorithm \(\mathcal{B}\) in Section \(4.4\) has worst-case running time \(O\left(q^{2}\right)\). Can you suggest a way to make it run in \(O(q \log q)\) time? What about \(O(q)\) time?

    Exercise \(4.10\)

    Assume that the last 4 digits of student ID numbers are assigned uniformly at this university. In a class of 46 students, what is the exact probability that two students have ID numbers with the same last 4 digits?

    Compare this exact answer to the upper and lower bounds given by Lemma 4.10.

    Exercise \(4.11\)

    Write a program that experimentally estimates the BirthdayProb \((q, N)\) probabilities.

    Given \(q\) and \(N\), generate \(q\) uniformly chosen samples from \(\mathbb{Z}_{N}\), with replacement, and check whether any element was chosen more than once. Repeat this entire process \(t\) times to estimate the true probability of BirthdayProb \((q, N)\).

    Generate a plot that compares your experimental findings to the theoretical upper/lower bounds of \(0.632 \frac{q(q-1)}{2^{\lambda+1}}\) and \(\frac{q(q-1)}{2^{\lambda+1}}\).

    Exercise \(4.12\)

    Suppose you want to enforce password rules so that at least \(2^{128}\) passwords satisfy the rules. How many characters long must the passwords be, in each of these cases?

    1. Passwords consist of lowercase a through z only.
    2. Passwords consist of lowercase and uppercase letters \(a-z\) and \(A-Z\).
    3. Passwords consist of lower/uppercase letters and digits \(0-9\).
    4. Passwords consist of lower/uppercase letters, digits, and any symbol characters that appear on a standard US keyboard (including the space character).

    This page titled 4.5: Exercises is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Rosulek (Open Oregon State) via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.