Michael Rivera mikedll

Exercise 3.3-1

Suppose $m \le n$, and $f(m) + g(m) > f(n) + g(n)$. Then $f(m) - f(n) + g(m) - g(n) > 0$. Consider $f(m) - f(n)$. We know that $f(m) \le f(n)$. So $f(m) - f(n) \le 0$. Similarly for $g(m) - g(n)$. So their sum cannot be greater than 0. This contradicts our earlier assertion, so $f(m) + g(m) \le f(n) + g(n)$, and $f(n) + g(n)$ is monotonically increasing.

Suppose $m \le n$, and $f(g(m)) \gt f(g(n))$. Then $f(g(m)) - f(g(n)) \gt 0$. We know $g(m) \le g(n)$. Let $o = g(m)$ and $p = g(n)$. We have $o \le p$. So $f(o) \le f(p)$. So $f(o) - f(p) \le 0$. This contradicts our assumption that $f(g(m)) - f(g(n)) \gt 0$. So $f(g(m))$ is monotonically increasing.

Exercise 3.2-1

Let $n_0$ be some $n$ such that $f(n) \ge 0$ and $g(n) \ge 0$ for all $n \ge n_0$. This is given to us since both functions are asymptotically nonnegative. Let $c_1 = 1/2$ and $c_2 = 4$. Let $i(n)= max \{ f(n) , g(n) \}$ and let $h(n)=f(n)+g(n)$.

Then we will conclude that $0 \le c_1 i(n) \le h(n) \le c_2 i(n)$ for all $n \ge n_0$. This will show that $h(n) = θ(i(n))$, which I proved by accident, but I will then invoke the θ property of symmetry to finally assert that $i(n) = θ(h(n))$.

We take on the right-hand side of this inequality first. Suppose $c_2i(k) \lt h(k)$ for some $k \ge n_0$. Then

Exercise 3.1-1

Let $x = n \mod 3$. Divide the input array A into 3 sections, with the left $x$ sections being $\lceil n/3 \rceil$ cells large, and the right $3-x$ sections being $\lfloor n/3 \rfloor$ cells large. Suppose the $n/3$ largest values are in the leftmost section. We need to move them to the rightmost section to achieve a sort.

This means they must pass through the middle section. The middle of A is either $n/3 + 1$ cells large, or $n/3$ cells large. So to migrate through the middle section, $n/3 + 1$ or $n/3$ executions of line 6 are required. We have $n/3$ values to move through the middle section. So that's either $(n/3 + 1)(n/3)$ or $(n/3)(n/3)$ executions of line 6 that are required. These both amount to $Ω(n^2)$ cost, so the worst-case running time of InsertionSort is $Ω(n^2)$.

Problem 2-1.a

If we divide an array of size $n$ into $n/k$ sublists of size $k$, and we run InsertionSort on each of those sublists, a given InsertionSort call will take $θ(k^2)$ time to finish in the worst case. We have $n/k$ of these calls to make. So that's $n/k \cdot k^2 = θ(nk)$ cost for the InsertionSort calls.

Problem 2-1.b

The code for merge sort with insertion sort on small arrays is here.

This is an attempt to solve the rod cutting problem by enumerating all of the ways the rod can be cut. This algorithm is here

$$ \begin{align} T(n) &= n + \sum_{i=0}^{n-1}b_i \\ \end{align} $$

$b_i$ is the cost of the for loop at $i$. We introduce a function $U(n, m, j, k)$ for it. $n$ is the number of rod values, and we want a solution for a rod of this length. $m$ is the number of smaller rods for a given number of cuts $m-1$ of the full rod. $j$ is an offset into $m$, where we're enumerating how long a cut at $j$ can be and still be part of a sequence of cuts adding up to $n$. $k$ is the sum of the rod lengths we've enumerated so far at offset $j$ of $m$.

Exercise 2.1-2

At the start of the for loop, sum contains the sum of values in the subarray A[1:i-1].

Initialization: i=1, and sum is 0, so it contains the sum of the empty array A[1:0].

Maintenance: sum increases by A[i]. So If it held A[1:i-1], then it now holds

Exercise 14.1-1

Here is the recursive CutRod algorithm:

CutRod(p, n)
  if n == 0
    return 0
   
 q = -1

Show that "divides" (|) is a partial ordering of the positive integers $\mathbb{Z}^+$. Explain why $(\mathbb{Z}^*, |)$ is not a posit.

Let S = ($\mathbb{Z}^+$,|)

Reflexive:

Every number divides itself with quotient 1. So xRx for all x in $\mathbb{Z}^+$.

Antisymmetric:

	require 'test/unit'

	class Nisoku
	def theMax(input)
	max_so_far = -1

	input = input.map { \|e\| e.to_f }.sort

	s = 0
	while s <= input.length

	using System;
	using System.Collections.Generic;
	using System.Linq;
	using System.Text;

	namespace TopCoderCSharp
	{
	class PeopleYouMayKnow
	{
	const int MaxFriendDepth = 4;