$ /Developer/NVIDIA/CUDA-5.0/samples/bin/darwin/release/deviceQuery

/Developer/NVIDIA/CUDA-5.0/samples/bin/darwin/release//deviceQuery Starting...

 CUDA Device Query (Runtime API) version (CUDART static linking)

Detected 1 CUDA Capable device(s)

Device 0: "GeForce 320M"
  CUDA Driver Version / Runtime Version          5.0 / 5.0
  CUDA Capability Major/Minor version number:    1.2
  Total amount of global memory:                 253 MBytes (265027584 bytes)
  ( 6) Multiprocessors x (  8) CUDA Cores/MP:    48 CUDA Cores
  GPU Clock rate:                                950 MHz (0.95 GHz)
  Memory Clock rate:                             1064 Mhz
  Memory Bus Width:                              128-bit
  Max Texture Dimension Size (x,y,z)             1D=(8192), 2D=(65536,32768), 3D=(2048,2048,2048)
  Max Layered Texture Size (dim) x layers        1D=(8192) x 512, 2D=(8192,8192) x 512
  Total amount of constant memory:               65536 bytes
  Total amount of shared memory per block:       16384 bytes
  Total number of registers available per block: 16384
  Warp size:                                     32
  Maximum number of threads per multiprocessor:  1024
  Maximum number of threads per block:           512
  Maximum sizes of each dimension of a block:    512 x 512 x 64
  Maximum sizes of each dimension of a grid:     65535 x 65535 x 1
  Maximum memory pitch:                          2147483647 bytes
  Texture alignment:                             256 bytes
  Concurrent copy and kernel execution:          Yes with 1 copy engine(s)
  Run time limit on kernels:                     Yes
  Integrated GPU sharing Host Memory:            Yes
  Support host page-locked memory mapping:       Yes
  Alignment requirement for Surfaces:            Yes
  Device has ECC support:                        Disabled
  Device supports Unified Addressing (UVA):      No
  Device PCI Bus ID / PCI location ID:           0 / 0
  Compute Mode:
     < Default (multiple host threads can use ::cudaSetDevice() with device simultaneously) >

deviceQuery, CUDA Driver = CUDART, CUDA Driver Version = 5.0, CUDA Runtime Version = 5.0, NumDevs = 1, Device0 = GeForce 320M

Some Installation Notes

== Installing MPICH2 ==
http://www.underworldproject.org/documentation/MpichDownload.html#What_is_MPICH_and_do_I_need_to_i
http://stackoverflow.com/questions/13157260/having-open-mpi-related-issues-while-making-cuda-5-0-samples-mac-os-x-ml

./configure --enable-shared --enable-sharedlibs=osx-gcc --enable-fast=all --prefix=/usr/local/mpich2-optimized --disable-f77 --disable-fc
make
sudo make install
sudo ln -s /usr/local/mpich2-optimized/mpicxx /usr/bin/mpicxx
sudo ln -s /usr/local/mpich2-optimized/mpic++ /usr/bin/mpic++

    == output message == 
    "Installed SLOG2SDK in /usr/local/mpich2-optimized
    /usr/local/mpich2-optimized/sbin/mpeuninstall may be used to remove the installation
    Installed MPE2 in /usr/local/mpich2-optimized
    /usr/local/mpich2-optimized/sbin/mpeuninstall may be used to remove the installation"


== Verifying CUDA-5.0 installation ==
https://developer.nvidia.com/cuda-downloads?sid=229597

cd /Developer/NVIDIA/CUDA-5.0/samples
export PATH=/usr/local/mpich2-optimized/bin:$PATH
make clean

# Note all sample built succesfully except "simpleSeparateCompilation" which I needed to move away for the rest to build
make

P = NP would mean every computational problem can be solved in polynomial time.
P $\ne$ NP would mean no NP-complete problems could be solved in polynomial time.
There are NP-complete problems that are "easier" to solve in practice than others.
The ability to solve some instances of an NP-complete problem implies P = NP.
Showing a problem is NP-complete means it can't be solved in polynomial.

Which one(s) of the above are true ?

See Problem Set 2 at Intro to Theoretical Computer Science.

What happens if you show one NP-complete problem to be solvable only in exponential time on a Deterministic RAM ?

Some problems in NP only solvable in exponential time
All NP-complete problems only solvable in exponential time
All problems in NP only solvable in exponential time

Which one(s) of the above are true ?

See Unit 2.5 at Intro to Theoretical Computer Science.

In an introductory statistics course, the same number of students scored below 75% as above 75% on the final exam. Which shape(s) could the distribution of final exam scores have ? Check all that apply.

Uniform
Normal
Bimodal
Positively Skewed
Negatively Skewed

What do you think ?

See Question 25 of Problem Set 3 at Statistics.

Rotate a straight line by angle $\theta$ from the origin with a starting coordinate:

1. $(1,0) \rightarrow (\cos \theta, \sin \theta)$
2. $(0,1) \rightarrow (-\sin \theta, \cos \theta)$
3. $(x,0) \rightarrow (x\cos \theta, x\sin \theta)$
4. $(0,y) \rightarrow (-y\sin \theta, y\cos \theta)$
5. $(x,y) \rightarrow (x\cos \theta - y\sin \theta, x\sin \theta + y\cos \theta)$

Therefore, if we rotate $(1,0)$ first by $\alpha$ and then by $\beta$, we would end up first at $(\cos \alpha, \sin \alpha)$, and then at

$(\cos \alpha \cos \beta - \sin \alpha \sin \beta,   \cos \alpha \sin \beta + \sin \alpha \cos \beta)$

On the other hand, if we rotate $(1,0)$ by $\alpha + \beta$, we would end up at

$(\cos(\alpha + \beta),   \sin(\alpha + \beta))$

This means:

$$\begin{aligned} \cos(\alpha + \beta) &= \cos \alpha \cos \beta - \sin \alpha \sin \beta \\ \sin(\alpha + \beta) &= \cos \alpha \sin \beta + \sin \alpha \cos \beta \end{aligned}$$

$$\begin{aligned} \dfrac{d}{dx} sin(x) &= cos(x) \\ \\ \dfrac{d}{dx} tan(x) &= sec^2(x) \\ \\ \dfrac{d}{dx} sec(x) &= sec(x) \cdot tan(x) \\ \end{aligned}$$

$$\begin{aligned} \dfrac{d}{dx} cos(x) &= -sin(x) \\ \\ \dfrac{d}{dx} cot(x) &= -csc^2(x) \\ \\ \dfrac{d}{dx} csc(x) &= -csc(x) \cdot cot(x) \\ \end{aligned}$$

$$\begin{aligned} \dfrac{d}{dx} sin^{-1}(x) &= \frac{1}{\sqrt{1 - x^2}} \\ \\ \dfrac{d}{dx} tan^{-1}(x) &= \frac{1}{1 + x^2} \\ \\ \dfrac{d}{dx} sec^{-1}(x) &= \frac{1}{x \cdot \sqrt{x^2 - 1}} \\ \end{aligned}$$

$$\begin{aligned} \dfrac{d}{dx} cos^{-1}(x) &= \frac{-1}{\sqrt{1 - x^2}} \\ \\ \dfrac{d}{dx} cot^{-1}(x) &= \frac{-1}{1 + x^2} \\ \\ \dfrac{d}{dx} csc^{-1}(x) &= \frac{-1}{x \cdot \sqrt{x^2 - 1}} \\ \end{aligned}$$

Take the last trig function as an example. Let $f(x) = csc^{-1}(x)$,

$$\begin{aligned} f(csc(x)) &= csc^{-1}(csc(x)) = x \\ f'(csc(x)) \cdot csc'(x) &= 1 \\ f'(csc(x)) &= \frac{1}{csc'(x)} \\ &= \frac{-1}{csc(x) \cdot cot(x)} \\ \end{aligned}$$

Since $sin^2(x) + cos^2(x) = 1$, divide both sides by $sin^2(x)$:

$$\begin{aligned} 1 + cot^2(x) &= csc^2(x) \\ cot(x) &= \sqrt{csc^2(x) - 1}\\ \end{aligned}$$

From above,

$$\begin{aligned} f'(csc(x)) &= \frac{-1}{csc(x) \cdot cot(x)} \\ f'(csc(x)) &= \frac{-1}{csc(x) \cdot \sqrt{csc^2(x) - 1}} \\ f'(x) &= \frac{-1}{x \cdot \sqrt{x^2 - 1}} \\ \therefore \dfrac{d}{dx} csc^{-1}(x) &= \frac{-1}{x \cdot \sqrt{x^2 - 1}} \\ \end{aligned}$$

Reducing a problem $X$ to a problem $Y$ implies:

$X$ is at least as hard to solve as $Y$
$Y$ is at least as hard to solve as $X$
If $X$ can be solved in polynomial time, then so can $Y$
If $Y$ can be solved in polynomial time, then so can $X$

What do you think ?

See Unit 2.3 at Intro to Theoretical Computer Science.

Compute a clique (ie fully connected subgraph) from a given graph $G$, and then invert the original graph into $G'$, the vertexes of the clique form an Independent Set in $G'$ !

Complement the Independent Set of $G'$, we get the Vertex Cover of $G'$ !

See Unit 1.4 at Intro to Theoretical Computer Science.

But why ? Observe that

$\varphi(n)$ is equal to the number of integers between $0$ and $n-1$ that are relatively prime to $n$.

Trivially, $gcd(0,n) = n$ as $n$ divides $0$, but $gcd(0,n) = 1$ only when $n = 1$. In other words, zero is relatively prime to $n$ only in the case when $n = 1$. Therefore, zero only counts in $\lvert \mathbb{Z_1} \rvert$. $\Box$

Let $n \in \mathbb{Z}$ with $n > 1$. Show that $n$ is prime if and only if $(n − 1)! \equiv −1 \pmod n$.

== Attempt ==

$\implies$

Based on Wilson's theorem, we know that $(n − 1)! \equiv −1 \pmod n$ if $n$ is an odd prime. Clearly, this also holds when $n = 2$, since $(2-1)! \equiv 1 \equiv -1 \pmod 2$. Therefore, if $n$ is prime, $(n − 1)! \equiv −1 \pmod n$.

$\impliedby$

Suppose $n$ is not prime, and $(n − 1)! \equiv −1 \pmod n$. Observe that $(n − 1) \equiv −1 \pmod n$ and $gcd(n-1,n) = 1$. Therefore,

$$\begin{aligned} \frac{(n − 1)!}{(n-1)} &\equiv \frac{−1}{-1} \pmod n \\ (n − 2)! &\equiv 1 \pmod n \\ \end{aligned}$$

Since $n$ is not prime, there must exist an integer $i$ in $[1, n-2]$ such that $i$ has no multiplicative inverse in $\mathbb{Z_n}$. Let $ij = (n-2)!$ for some integer $j$. We know $j$ exists, since $i$ divides $(n-2)!$. So $(n - 2)! = ij \equiv 1 \pmod n$. But this means $j$ is a multiplicative inverse of $i$ - a contradiction. Therefore, if $(n − 1)! \equiv −1 \pmod n$, $n$ must be prime.

$\Box$

Calculate the square roots of 1 modulo 4, 8 and 16.

Observe that $\varphi(4), \varphi(8)$ and $\varphi(16)$ can be calculated using Theorem 2.10 of Shoup: Let $p$ be a prime and $e$ be a positive integer. Then

$$\begin{aligned} \varphi(p^e) &= p^{e-1}(p-1) \\ \end{aligned}$$

In particular,

$$\begin{aligned} \varphi(2^2) &= 2^{2-1}(2-1) = 2 \\ \varphi(2^3) &= 2^{3-1}(2-1) = 4 \\ \varphi(2^4) &= 2^{4-1}(2-1) = 8 \\ \end{aligned}$$

However, note that the general formula for calculating

$\displaystyle\lvert (\mathbb{Z_n^*})^2 \rvert = \prod_{i=1}^{r}(\varphi(p_i^{e_i})/2) = \varphi(n)/2^r$

cannot be applied to this problem, for Theorem 2.26 of Shoup is only applicable when $p$ is odd.

In any case, it turns out the square roots are $\{1\}$ for modulo $4$, $\{1, 3, 5, 7\}$ for modulo $8$ and $\{1, 7, 9, 15\}$ for modulo $16$, as can be verified below.

for n in [4, 8, 16]:
    for i in xrange(1,n):
        r = i**2 % n
        if r == 1:
            print '%2d^2 &\equiv %d \pmod{%2d} \\\\' % (i, r, n)

Output:

$$\begin{aligned} 1^2 &\equiv 1 \pmod{ 4} \\ 3^2 &\equiv 1 \pmod{ 4} \\ 1^2 &\equiv 1 \pmod{ 8} \\ 3^2 &\equiv 1 \pmod{ 8} \\ 5^2 &\equiv 1 \pmod{ 8} \\ 7^2 &\equiv 1 \pmod{ 8} \\ 1^2 &\equiv 1 \pmod{16} \\ 7^2 &\equiv 1 \pmod{16} \\ 9^2 &\equiv 1 \pmod{16} \\ 15^2 &\equiv 1 \pmod{16} \\ \end{aligned}$$

Let $p$ be an odd prime and $\alpha \in \mathbb{Z_p^*}$. Let $\mathcal{P} := \{ S \subset \mathbb{Z_p^*}: \lvert S \rvert = 2\}$, and define $\mathcal{C} := \{ \{\kappa, \lambda\} \in \mathcal{P} : \kappa\lambda = \alpha\}$. Note that for every $\kappa \in \mathbb{Z_p^*}$, there is a unique $\lambda \in \mathbb{Z_p^*}$ such that $\kappa \lambda = \alpha$, namely $\displaystyle \lambda := \frac{\alpha}{\kappa}$; moreover, $\kappa \ne \lambda$. Define $\mathcal{D} := \{ \{\kappa, \lambda\} \in \mathcal{P} : \kappa\lambda = 1\}$. Calculate the sets $\mathcal{C}$ and $\mathcal{D}$ in the case $p = 11$ and $\alpha = -1$.

== Solution ==

$\mathcal{C}: \{\{1,10\}, \{2,5\}, \{3,7\}, \{4,8\}, \{6, 9\}\}$
$\mathcal{D}: \{\{2,6\}, \{3,4\}, \{5,9\}, \{7,8\}\}$

Let $n, m \in \mathbb{Z}$, where $n \gt 0$, and let $d := gcd(m,\varphi(n))$. Show that:

(a) if $d =1$, then $(\mathbb{Z_n^*})^m = (\mathbb{Z_n^*})$;
(b) if $\alpha \in (\mathbb{Z_n^*})^m$, then $\alpha^{\varphi(n)/d} = 1$.

== Attempt ==

For (a), consider Theorem 2.17 in Shoup:

Let $n$ be a positive integer. For each $\alpha \in \mathbb{Z_n^*}$, and all $l, m \in \mathbb{Z}$ with $gcd(l,m) = 1$, if $\alpha^l \in (\mathbb{Z_n^*})^m$, then $\alpha \in (\mathbb{Z_n^*})^m$

Given $d = gcd(m,\varphi(n)) = 1$, setting $l := \varphi(n)$, this means for each $\alpha \in \mathbb{Z_n^*}$, if $\alpha^{\varphi(n)} \in (\mathbb{Z_n^*})^m$, then $\alpha \in (\mathbb{Z_n^*})^m$. But by Euler's theorem, $\alpha^{\varphi(n)} \equiv 1 \pmod n$ and $1 = 1^m \in (\mathbb{Z_n^*})^m$. In other words, all members of $\mathbb{Z_n^*}$ are also members of $(\mathbb{Z_n^*})^m$. Therefore $(\mathbb{Z_n^*})^m = (\mathbb{Z_n^*})$.

For (b), consider Theorem 2.15 in Shoup:

Suppose $\beta \in \mathbb{Z_n^*}$ has multiplicative order $k$. Then for every $m \in \mathbb{Z}$, the multiplicative order of $\beta^m$ is $\displaystyle\frac{k}{gcd(m,k)}$

Let $\alpha \equiv \beta^m \pmod n$ and $k$ be the multiplicative order of $\beta$, then the multiplicative order of $\alpha$ is $\displaystyle k' = \frac{k}{gcd(m,k)}$. It remains to show that $k'$ divides $\displaystyle\frac{\varphi(n)}{d} = \frac{\varphi(n)}{gcd(m,\varphi(n))}$.

By Euler's theorem, we know that $k$ divides $\varphi(n)$. Let $k \cdot l = \varphi(n)$ for some positive integer $l$.

Consider:

$$\begin{aligned} \frac{\varphi(n)}{gcd(m,\varphi(n))} \div k' &= \frac{\varphi(n)}{gcd(m,\varphi(n))} \cdot \frac{gcd(m,k)}{k} \\ &= \frac{\varphi(n)}{gcd(m, kl)} \cdot \frac{gcd(m,k)}{k} \\ &= \frac{\varphi(n)}{gcd(m, l)} \cdot \frac{1}{k} \end{aligned}$$

Since $gcd(m, l) \mid l$, $k \cdot gcd(m, l) \mid kl = \varphi(n)$. This shows that $k'$, the multiplicative order of $\alpha$, divides $\displaystyle\frac{\varphi(n)}{d}$. Therefore $\alpha^{\varphi(n)/d} = 1$. $\Box$