$ /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\)