Data Structure Midterm Exercise
===============================
###### tags: `Data Structure`
## Chapter 1
### 1. The fatorial function $n!$ has value $1$ when $n \leq 1$ and value $n\times(n−1)!$ when $n > 1$. Write both a recursive and an iterative C function to compute $n!$.
> ```c=
> int recursive_fatoral(int n){
> if(n<=1) return 1;
> return n*resursive_fatoral(n-1);
> }
>
> int iterative_fatoral(int n){
> int re=1;
> for(int i=2; i<=n; i++)
> {
> re*=i;
> }
> return re;
> }
> ```
> [name=張聖岳][time=Fri, Nov 1, 2019 11:57 AM]
### 2. The Fibonacci numbers are defined as :$f_0 = 0,f_1 = 1,$ and $f_i = f_{i−1} + f_{i−2}$ for $i > 1$. Write both a recursive and an iterative C function to compute $f_i$.
> ```c=
> int recursive_fibonacci(int n){
> if(n==0) return 0;
> if(n==1) return 1;
> return recursive_fibonacci(n-1)+recursive_fibonacci(n-2);
> }
>
> int iterative_fibonacci(int n){
> int f[n+1];
> f[0]=0;
> f[1]=1;
> for(int i=2; i<=n; i++)
> {
> f[i]=f[i-1]+f[i-2];
> }
> return f[n];
> }
> ```
> [name=張聖岳][time=Fri, Nov 1, 2019 11:58 AM]
### 3. Write an iterative function to compute a binomial coeffcient, then transform it into an equivalent recursive finction.
> ```c=
> int iterative_C(int n, int k){
> int a=1, b=1;
> for(int i=0; i<k; i++)
> {
> a*=(n-i);
> b*=(i+1);
> }
> return a/b;
> }
> int recursive_C(int n, int k){
> if(k<0 || k>n) return 0;
> if(n==2) return 1;
> return recursive_C(n-1, k-1)+recursive_C(n-1, k);
> }
> ```
> [name=張聖岳][time=Fri, Nov 1, 2019 11:58 AM]
### 4. [$Towers$ $of$ $Hanoi$] There are three towers and $64$ disks of different diameters placed on the first tower. The disks are in order of decreasing diameter as one scans up the tower. Monks were reputedly supposed to move the disk from tower $1$ to tower $3$ obeying the rule:
#### (a) Only one disk can be moved at any time.
#### (b) No disk can be placed on top of a disk with a smaller diameter.
#### Write a recursive function that print out the sequence of moves needed to accomplish this task.
> ```c=
> int hanoi_tower(int n, int a, int b, int c)
> {// move n disks from a to b
> if(n==1) printf("%d->%d\n", a, c);
> else
> hanoi_tower(n-1, a, c, b);
> hanoi_tower(1, a, b, c);
> hanoi_tower(n-1, b, a, c);
> }
> ```
> [name=張聖岳][time=Fri, Nov 1, 2019 11:58 AM]
### 5. Show that the following statement are correct:
#### (a.) $5n^2 −6n = \Theta(n^2)$
> Let $f(n)=5n^2-6n,g(n)=n^2$
> $5n^2 −6n = \Theta(n^2)\\\Rightarrow\exists c_1,c_2>0\rightarrow c_1\times g(n)\leq f(n) \leq c_2\times g(n)$
>
> There exist $c_1=4, c_2=6$ correspond to the statement
>
> [name=張聖岳][time=Fri, Nov 1, 2019 11:58 AM]
#### (b.) $n! = O(n^n)$
> Let $f(n)=n!, g(n)=n^n$
> $n! = O(n^n)\\\Rightarrow \exists c>0\rightarrow f(n)\leq c \times g(n)$
>
> $n^n \gg n!$
> $\therefore$ the statement is true
>
> [name=張聖岳][time=Fri, Nov 1, 2019 11:59 AM]
#### (c.) $2n^2 + n\log n = \Theta(n^2)$
> Supposed that $2n^2 + n\log n = \Theta(n^2)$
> $\Rightarrow \exists c_1,c_2>0 \rightarrow c_1\times n^2 \leq (2n^2 + n\log n)\leq c_2\times n^2$
>
> Let $c_1=1 \\\Rightarrow n^2\leq (2n^2 + n\log n)\\\Rightarrow n^2 \geq n\log n\\\Rightarrow n\geq\log n, n>0$
> Let $c_2= 3\\\Rightarrow 3n^2\geq(2n^2 + n\log n)\\\Rightarrow n^2\geq n\log n\\\Rightarrow n\geq\log n, n>0$
>
> $\therefore$ the statement is true.
>
> [name=張聖岳][time=Fri, Nov 1, 2019 11:59 AM]
#### (d.) $\sum^n_{i=0} i^2 = \Theta(n^3)$
> Supposed that $\sum^n_{i=0} i^2 = \Theta(n^3)$
> $\Rightarrow\exists c_1, c_2 >0\rightarrow c_1\times n^3\leq\sum^n_{i=0} i^2\leq c_2\times n^3$
>
> Let $c_1=\dfrac{1}{2}\\\Rightarrow \dfrac{n^3}{8}\leq\sum^n_{i=0} i^2 = \dfrac{n(n-1)(n-2)}{6}\\\Rightarrow 6n^3\leq 8n(n-1)(n-2)\\\Rightarrow 6n^3\leq 8n^3-24n^2+16n\\\Rightarrow2n^3\geq24n^2+16n\\\Rightarrow n^2\geq12n+8, n\geq20$
> Let $c_2=1\\\Rightarrow n^3\geq\sum^n_{i=0} i^2\\\Rightarrow n^3\geq\dfrac{n(n-1)(n-2)}{6}\\\Rightarrow6n^3\geq n^3-3n^2+2n\\\Rightarrow6n^2\geq n^2-3n+2\\\Rightarrow5n^2\geq -3n+2, n\geq1$
>
> $\therefore$ the statement is true.
>
> [name=張聖岳][time=Fri, Nov 1, 2019 11:59 AM]
#### (e.) $\sum^n_{i=0} i^3 = \Theta(n^4)$
> $\sum^n_{i=0} i^3 = (\dfrac{n(n-1)}{2})^2 = \dfrac{n^4-2n^3+n^2}{4}$
>
> Supposed that $\sum^n_{i=0} i^3 = \Theta(n^4)$
> $\Rightarrow \exists c_1,c_2\geq0\rightarrow c_1\times n^4\leq \sum^n_{i=0} i^3\leq c_2\times n^4$
>
> Let $c_1=\dfrac{1}{2}\\\Rightarrow \dfrac{1}{8}n^4\leq\dfrac{n^4-2n^3+n^2}{4}\\\Rightarrow4n^4\geq16n^3-8n^2\\\Rightarrow n^2\geq4n+2,n\geq5$
> Let $c_2=1\\\Rightarrow n^4\leq\dfrac{n^4-2n^3+n^2}{4}\\\Rightarrow 4n^4\leq n^4-2n^3+n^2\\\Rightarrow 3n^4\leq -2n^3+n^2\\\Rightarrow 3n^2\leq -2n+1, n\geq1$
>
> $\therefore$ the statement is true.
>
> [name=張聖岳][time=Fri, Nov 1, 2019 11:59 AM]
#### (f.) $n^{2^n} + 6\times2^n = \Theta(n^{2^n})$
> Let $k=2^n$
> Supposed $n^k+6k=\Theta(n^k)$
> $\Rightarrow \exists c_1, c_2>0\rightarrow c_1\times n^k\leq n^k+6k\leq c_2\times n^k$
>
> Let $c_1=\dfrac{1}{2}\\\Rightarrow\dfrac{1}{2}\times n^k\leq n^k+6k\\\Rightarrow n^k\leq2n^k+12k\\\Rightarrow n^k\geq12k\\\Rightarrow n^{2^n}\geq12\times2^n, n\geq3$
> Let $c_2=2\\\Rightarrow 2n^k\geq n^k+12k\\\Rightarrow n^k\geq 12k\\\Rightarrow n^{2^n}\geq12\times2^n, n\geq3$
>
> $\therefore$ the statement is true.
>
> [name=張聖岳][time=Fri, Nov 1, 2019 12:13 PM]
#### (g.) $n^3 + 10^6n^2 = \Theta(n^3)$
> Supposed that $n^3 + 10^6n^2 = \Theta(n^3)$
> $\Rightarrow \exists c_1, c_2>0\rightarrow c_1\times n^3\leq n^3 + 10^6n^2\leq c_2\times n^3$
>
> Let $c_1=1\\\Rightarrow n^3\leq n^3 + 10^6n^2\\\Rightarrow0\leq10^6n^2, n\geq0$
> Let $c_2=10^6+1\\\Rightarrow10^6n^3\geq10^6n^2\\\Rightarrow n\geq1, n_0\geq1$
>
> $\therefore$ the statement is true.
>
> [name=張聖岳][time=Fri, Nov 1, 2019 12:20 PM]
#### (h.) $\dfrac{6n^3}{(\log n + 1)} = O(n^3)$
> Supposed that $\dfrac{6n^3}{(\log n + 1)} = O(n^3)$
> $\Rightarrow \exists c>0\rightarrow \dfrac{6n^3}{(\log n + 1)} \leq c\times n^3$
>
> Let $c=6$
> $\dfrac{6n^3}{(\log n + 1)} \leq 6\times n^3$
> $\Rightarrow 1\leq\log n+1$
> $\Rightarrow 0\leq\log n, n_0>0$
>
> $\therefore$ the statement is true.
>
> [name=張聖岳][time=Fri, Nov 1, 2019 12:27 PM]
#### (i.) $n^{1.001} + n\log n = \Theta(n^{1.001})$
> know that $\lim_{n\to\infty}\dfrac{\log n}{n^k}=\lim_{n\to\infty}\dfrac{\frac{d}{dn}\log n}{\frac{d}{dn} n^k}=\lim_{n\to\infty}\dfrac{1}{kn^k}=0(k>1)$
>
> Supposed that $n^{1.001} + n\log n = \Theta(n^{1.001})$
> $\Rightarrow \exists c_1,c_2\geq0\rightarrow c_1\times n^{1.001}\leq n^{1.001} + n\log n\leq c_2\times n^{1.001}$
>
> Let $c_1=1\\\Rightarrow n^{1.001}\leq n^{1.001} + n\log n\\\Rightarrow 0\leq n\log n, n_0>0$
> Let $c_2=2\\\Rightarrow 2n^{1.001}\geq n^{1.001}+n\log n\\\Rightarrow n^{1.001}\geq n\log n\\\Rightarrow\dfrac{1}{n}\geq\dfrac{\log n}{n^{1.001}}\\\Rightarrow\lim_{n\to1.001}\dfrac{1}{n}\geq\lim_{n\to1.001}\dfrac{\log n}{n^{1.001}}\\\Rightarrow 0\geq0, n\sim\infty$
>
> $\therefore$ the statement is true.
>
> [name=張聖岳][time=Fri, Nov 1, 2019 12:55 PM]
#### (j.) $n^k + n + n^k \log n = \Theta(n^k \log n)$ for all $k \geq 1$
> Supposed that $n^k + n + n^k \log n = \Theta(n^k \log n)$
> $\Rightarrow \exists c_1, c_2>0\rightarrow c_1\times n^k\log n\leq n^k+n+n^k\log n\leq c_2\times n^k\log n$
>
> Let $c_1=1\\\Rightarrow n^k\log n\leq n^k+n+n^k\log n\\\Rightarrow0\leq n^k+n, n_0\geq0$
> Let $c_2=2\\\Rightarrow2n^k\log n\geq n^k+n+n^k\log n\\\Rightarrow n^k\log n\geq n^k+n\\\Rightarrow n^k(\log n-1)\geq n, n_0\geq100$
>
> $\therefore$ the statement is true.
>
> [name=張聖岳][time=Fri, Nov 1, 2019 4:05 PM]
#### (k.) $10n^3 + 15n^4 + 100n^22^n = O(n^22^n)$
> Supposed that $10n^3 + 15n^4 + 100n^22^n = O(n^22^n)$
> $\Rightarrow \exists c>0\rightarrow 10n^3 + 15n^4 + 100n^22^n \leq c\times n^22^n \\\Rightarrow10n+15n^2+100\times2^n\leq c\times2^n$
>
> Let $c=130$
> $\Rightarrow 30\times2^n\geq10n+15n^2$
> $\Rightarrow 6\times2^n\geq2+3n^2, n\geq1$
>
> $\therefore$ the statement is true.
>
> [name=張聖岳][time=Fri, Nov 1, 2019 4:14 PM]
### 6. Show that the following statement are incorrect:
#### (a.) $10n^2 + 9 = O(n)$
> For every positive $c$, the LHS (left hand side) is greater than $c_n$ whenever $n$ is greater than $\dfrac{c}{10}$. So, there are no positive constants $c$ and $n_0$ that satisify the definition of big O.
>
> [name=張聖岳][time=Fri, Nov 1, 2019 4:21 PM]
#### (b.) $n^2 \log n = \Theta(n^2)$
> Supposed that $n^2 \log n = \Theta(n^2)$
> $\Rightarrow\exists c_1,c_2\rightarrow c_1n^2\leq n^2\log n\leq c_2n^2$
>
> $c_1n^2\leq n^2\log n \Leftrightarrow c_1\leq \log n$
> which imply that $c$ is not a constant.
> This is a complict.
>
> $\therefore$ the statement is false.
>
> [name=張聖岳][time=Fri, Nov 1, 2019 4:27 PM]
#### (c.) $\dfrac{n^2}{\log n} = \Theta(n^2)$
> Supposed that $\dfrac{n^2}{\log n} = \Theta(n^2)$
> $\Rightarrow \exists c_1,c_2>0\rightarrow c_1n^2\leq \dfrac{n^2}{\log n} \leq c_2n^2$
>
> $c_1n^2\leq \dfrac{n^2}{\log n}\Leftrightarrow c_1\leq\dfrac{1}{\log n}$
> which imply that $c_1$ is not a constant.
> This is a complict.
>
> $\therefore$ the statement is false.
>
> [name=張聖岳][time=Fri, Nov 1, 2019 4:31 PM]
#### (d.) $n^32^n + 6n^23^n = O(n^22^n)$
> Supposed that $n^32^n + 6n^23^n = O(n^22^n)$
> $\Rightarrow \exists c_1,c_2>0\rightarrow c_1n^22^n\leq n^32^n + 6n^23^n\leq c_2n^22^n$
>
> $c_1n^22^n\leq n^32^n + 6n^23^n\Rightarrow c_12^n\leq n2^n+6\times3^n\Leftrightarrow c_1\leq n+6\times\dfrac{3^n}{2^n}$
> which imply that $c_1$ is not a constant.
> This is a complict.
>
> $\therefore$ the statement is false.
>
> [name=張聖岳][time=Fri, Nov 1, 2019 4:38 PM]
#### (e.) $3^n = O(2^n)$
> Supposed that $3^n = O(2^n)$
> $\Rightarrow \exists c>0\rightarrow 3^n\geq c2^n$
> $\Rightarrow c\leq\dfrac{3^n}{2^n}$
> which imply that $c_1$ is not a constant.
> This is a complict.
>
> $\therefore$ the statement is false.
>
> [name=張聖岳][time=Fri, Nov 1, 2019 4:40 PM]
### 7. Determine the worst-case complexity of the Program.
```c=
void printMatrix(int matrix[][MAX_SIZE], int rows, int cols)
{
int i, j;
for (i = 0; i < rows; i++){
for (j = 0; j < cols; j++)
printf("%d",matrix[i][j])
printf("\n");
}
}
```
> _Ans._ $O(rows\times cols)$
>
> [name=張聖岳][time=Fri, Nov 1, 2019 7:48 PM]
### 8. Determine the wrorst-case complexity of the Program.
```c=
void transpose(int a[][MAX_SIZE])
{
int i, j, temp;
for (i = 0; i < MAX_SIZE - 1; i++)
for (j = i+1; j < MAX_SIZE; j++)
SWAP(a[i][j], a[j][i], temp);
}
```
> _Ans._ $O(MAX\_SIZE^2)$
>
> [name=張聖岳][time=Fri, Nov 1, 2019 7:49 PM]
## Chapter 2
### 1. Make the fewest number of changes to the program so as to obtain a function that creates a two-dimensional array all of whose elements are set to 0. Test your new function.
```c=
int** make2dArray(int rows, int cols)
{/* create a two dimensional rows * cols array */
int **x, i;
/*get memory for row pointers */
MALLOC(x, rows * sizeof (*x));
/* get memory for each row */
for (i = 0; i < rows; i++)
MALLOC(x[i], cols * sizeof(**x));
return x;
}
```
> ```c=
> #include <string.h>
> int** make2dArray(int rows, int cols)
> {/* create a two dimensional rows * cols array */
> int **x, i;
> /*get memory for row pointers */
> MALLOC(x, rows * sizeof (*x));
> /* get memory for each row */
> for (i = 0; i < rows; i++){
> MALLOC(x[i], cols * sizeof(**x));
> memset(x[i], 0, sizeof(int)*cols);
> }
> return x;
> }
> ```
> [name=張聖岳][time=Sat, Nov 2, 2019 11:52 AM]
### 2. Write a function, $pmult$, that multiplies two polynomials. Figure out the computing time of your function.
> ```c=
> #include <string.h>
> double *pmult(double *a, double *b, int mx_a, int mx_b)
> {
> double result[MAX_EXP];
> int i, j;
> memset(result, 0, sizeof(result));
> for(i=0; i<MAX_EXP/2; i++){
> for(j=0; j<MAX_EXP/2;j++){
> result[i+j] += a[i]*b[j];
> }
> }
> return result;
> }
> ```
> $O(mx\_a*mx\_b)$
>
> [name=張聖岳][time=Sat, Nov 2, 2019 11:53 AM]
### 3. Write a function, $peval$, that evaluates a polynomial at some value, $x_0$. Try to minimize the number of operations.
> ```c=
> #include <string.h>
> #include <math.h>
> typedef struct{
> int exp;
> double coff;
> }term;
>
> double peval(term* poly, double x0, int siz){
> term* t;
> double result = 0;
> for(t=poly; t<poly+siz; t++){
> result+=t->coff*pow(x0, t->exp);
> }
> return result;
> }
> ```
> [name=張聖岳][time=Sat, Nov 2, 2019 12:07 PM]
### 4. Obtain an addressing formula for the element $a[i_0][i_1]...[i_n−1]$ in an array declared as $a[upper_0]...a[upper_{n−1}]$. Assume a column major representation of column major order, the entries are stored by columns first. For example, the array $a[3][3]$ would be stored as $a[0][0], a[1][0], a[2][0], a[0][1], a[1][1] , a[2][1], a[0][2], a[1][2], a[2][2]$.
> expect to address $a[i][j]$
> $\Rightarrow$ $a+j*rows+i$
>
> [name=張聖岳][time=Sat, Nov 2, 2019 12:13 PM]
### 5. Write a function, $strndel$. that accepts a string and two integers, start and length. Return a new string that is equivalent to the original string, except that length characters beginning at start have been removed.
> ```c=
> char *strndel(char *a,int start,int l)
> {
> int i=start;
> while(a[i+l]!='\0' && a[i] != '\0')
> {
> a[i]=a[i+l];
> i++;
> }
> a[++i]='\0';
> return a-1;
> }
> ```
> [name=張聖岳][time=Sat, Nov 2, 2019 12:36 PM]
### 6. Write a function, $strdel$. that accepts a string and a character. The function returns string with the first occurence of character removed.
> ```c=
> char *strdel(char *str, char ch)
> {
> int i, j;
> for(i=0; str[i]!='\0'; i++)
> {
> if(str[i]==ch){
> j=i
> while(str[j]!='\0'){
> str[j]=str[j+1];
> j++;
> }
> str[j]='\0';
> break;
> }
> }
> return str;
> }
> ```
> [name=張聖岳][time=Sat, Nov 2, 2019 12:42 PM]
### 7. Write a function, $strsearch$. that uses the sequential method for pattern matching. That is, assuming we have a string and a pattern, $strsearch$ examines each character in string until it either finds the pattern or it reaches the end of the string.
> ```c=
> void strsearch(chat *str, char *pat){
> int len=strlen(pat);
> int i, j, flag;
> for(i=0; str[i]!='\0'; i++){
> flag=1;
> for(j=0; j<len; j++){
> if(str[i+j]!=pat[j]) {
> flag=0;
> break;
> }
> }
> if(flag) {
> printf("find pattern \'%s\' in %d\n", pat, i)
> return;
> }
> }
> printf("there is no pattern\n");
> }
> ```
> [name=張聖岳][time=Sat, Nov 2, 2019 12:56 PM]
### 8. Compute the failure function for each of the following patterns:
#### (a.) $a$ $a$ $a$ $a$ $b$
> -1 0 1 2 3 -1
> [name=張聖岳][time=Sat, Nov 2, 2019 1:00 PM]
#### (b.) $a$ $b$ $a$ $b$ $a$ $a$
> -1 -1 0 1 2 0
> [name=張聖岳][time=Sat, Nov 2, 2019 1:00 PM]
#### (c.) $a$ $b$ $a$ $a$ $b$ $a$ $a$ $b$
> -1 -1 0 0 1 2 3 4
> [name=張聖岳][time=Sat, Nov 2, 2019 1:01 PM]
## Chapter 3
### 1. Implement the $queueFull$ and $queueEmpty$ functions for the noncircular queue.
> ```c=
> typedef struct{
> int key;
> }element;
> element queue[MAX_SIZE];
> int front=-1;
> int back=-1;
> bool queueFull(){
> return back==MAX_SIZE;
> }
> bool queueEmpty(){
> return front==back;
> }
> ```
> [name=張聖岳][time=Sat, Nov 2, 2019 4:09 PM]
### 2. Implement the $queueFull$ and $queueEmpty$ functions for the circular queue.
> ```c=
> typedef struct{
> int key;
> }element;
> element queue[MAX_SIZE];
> int front=-1;
> int back=-1;
> bool queueFull(){
> return ((back+1)%MAX_SIZE==front || (back==MAX_SIZE-1 && front==-1));
> }
> bool queueEmpty(){
> return front==back;
> }
> ```
> [name=張聖岳][time=Sat, Nov 2, 2019 4:24 PM]
### 3. Implement the $Inqueue$ and $Dequeue$ functions for the noncircular queue.
> ```c=
> typedef struct{
> int key;
> }element;
> element queue[MAX_SIZE];
> int front=-1;
> int back=-1;
> bool Inqueue(element* e){
> if(queueFull()) return false;
> queue[++back] = *e;
> return true;
> }
> bool Dequeue(element* e){
> if(queueEmpty()) return false;
> *e = queue[front++];
> return true;
> }
> ```
> [name=張聖岳][time=Sat, Nov 2, 2019 4:32 PM]
### 4. Write the postfix from of the following expressions :
#### (a.) $a \times b \times c$
> _Ans._ $ab \times c\times$
> [name=張聖岳][time=Sat, Nov 2, 2019 4:35 PM]
#### (b.) $−a + b − c + d$
> _Ans._ $a-b+c-d+$
> [name=張聖岳][time=Sat, Nov 2, 2019 4:36 PM]
#### (c.) $a \times −b + c$
> _Ans._ $ab-\times c+$
> [name=張聖岳][time=Sat, Nov 2, 2019 4:37 PM]
#### (d.) $(a + b) \times d + e/(f + a \times d) + c$
> _Ans._ $ab+d\times efad\times+/+ c+$
> [name=張聖岳][time=Sat, Nov 2, 2019 4:38 PM]
### 5. Obtain a data representation that maps a stack and a queue into a single array, memory[$MEMORY\_SIZE$]. Write C functions that add and delete elements from these two data objects. What can you say about the suitability of your data representation?
> ```c=
> typedef struct{
> int key;
> } element;
> int top=MEMORY_SIZE/2;
> int button=MEMORY_SIZE/2;
> int front=-1;
> int back=-1;
> element memory[MEMORY_SIZE];
> bool push(element *e){
> if((top+1)%MEMORY_SIZE==front || (top==MEMORY_SIZE && front==-1))
> return false;
> memory[++top] = *e;
> return true;
> }
> bool pop(element *e){
> if(top==button) return false;
> *e = memory[top--];
> return true;
> }
> bool add(element *e){
> if((back+1)%MEMORY_SIZE==button) return false;
> memory[++back] = *e;
> return true;
> }
> bool delete(element *e){
> if(front==back) return false;
> *e = memory[front++];
> return true;
> }
> ```
> [name=張聖岳][time=Sat, Nov 2, 2019 4:58 PM]
### 6. We must represent two stacks in an array, memory[$MEMORY\_SIZE$]. Write C functions that add and delete an item from stack $i, 0 \leq i < n$. Your functions should be able to add elements to the stacks as long as the total number of elements in both stacks is less than $MEMORY\_SIZE − 1$.
> ```c=
> typedef struct{
> int key;
> } element;
> int top2=MEMORY_SIZE;
> int button2=MEMORY_SIZE;
> int top1=-1;
> int button1=-1;
> element memory[MEMORY_SIZE];
> bool push1(element *e){
> if((top1+1)==top2)
> return false;
> memory[++top1] = *e;
> return true;
> }
> bool pop1(element *e){
> if(top1==button1) return false;
> *e = memory[top1--];
> return true;
> }
> bool push2(element *e){
> if((top2-1)==top1) return false;
> memory[--top2] = *e;
> return true;
> }
> bool pop2(element *e){
> if(top2==button2) return false;
> *e = memory[top2++];
> return true;
> }
> ```
> [name=張聖岳][time=Sat, Nov 2, 2019 5:09 PM]
### 7. Write a C function that transforms a infix expression into a postfix one.
> ```c=
> int top=-1;
> char stack[MAX_SIZE];
> void push(char e){ stack[++top] = e; }
> void pop(char e){ stack[top--]=e; }
> bool isEmpty(){ return top==-1; }
> char peek(){ return (top>=0)?stack[top]:NULL; }
>
> int prec(char c){
> switch(c){
> case '+':
> case '-':
> return 1;
> case '*':
> case '/':
> return 2;
> }
> }
> bool infixToPostfix(char *exp){
> char *tok;
> int k=-1;
> for(tok=exp; tok!='\0'; tok++)
> {
> char t=*tok;
> if(('A'<=t && t<='Z')||('a'<=t && t<='z'))
> exp[++k] = t;
> else if(t=='(')
> push(t);
> else if(t==')'){
> char tmp;
> while(!isEmpty() && tmp=peek()!='('){
> exp[++k] = tmp;
> pop();
> }
> if(tmp=peek()!='(')
> return false;
> pop();
> }else{
> char tmp;
> while(!isEmpty() && prec(t) <= prec(tmp=peek())){
> exp[++k] = tmp;
> pop();
> }
> push(t);
> }
> }
> while(!isEmpty()){
> exp[++k] = peek();
> pop();
> }
> exp[++k] = '\0';
> return true;
> }
> ```
> [name=張聖岳][time=Sat, Nov 2, 2019 6:06 PM]
### 8. Transform this expression from postfix to infix and evaluate it.
#### (1) $abc − d + /ea − ∗c∗$(Set a = 2, b = 3, c = 4, d = 5, e = 6)
> $a/(b-c+d)*(e-a)*c = 2/(3-4+5)\times(6-2)\times4=8$
>
> _Ans._$8$
> [name=張聖岳][time=Sat, Nov 2, 2019 5:14 PM]
#### (2) $+ ∗ +ABC ∗ + ∗ D ∗ E + DE ∗ ABC$(Set A = 1, B = 2, C = 3, D = 4, E = 5)
> $(A+B)*C+(D*E*(D+E)+A*B)*C \\=(1+2)\times3+(4\times5\times(4+5)+1\times2)\times3=555$
>
> _Ans._$555$
> [name=張聖岳][time=Sat, Nov 2, 2019 5:21 PM]
## Chapter 4
### 1. Write a function that inverts a single link list.
> ```c=
> typedef struct list *listptr;
> struct list{
> int key;
> listptr nxt;
> };
> listptr invert(listptr *lead)
> {
> listptr mid=NULL, tail;
> while(*lead)
> {
> tail = mid;
> mid = *lead;
> *lead = *lead->nxt;
> mid->nxt = tail
> }
> return *lead;
> }
> ```
> [name=張聖岳][time=Sat, Nov 2, 2019 9:24 PM]
### 2. Write a function that concatenate two circular link list A and B to one circular link list C.
> ```c=
> typedef list *listptr;
> struct list{
> int key;
> listptr link;
> }
> listptr concatenate(listptr A, listptr B)
> {
> listptr C, lastA, lastB;
> if(!A) return B;
> if(!B) return A;
> for(lastA = A; lastA->link!=A; lastA=lastA->link);
> for(lastB = B; lastB->link!=B; lastB=lastB->link);
> C = A;
> lastA->link=B;
> lastB->link=C;
> return C;
> }
> ```
> [name=張聖岳][time=Sat, Nov 2, 2019 9:43 PM]
### 3. Rewrite $delete$ so that it uses only two pointers, $first$ and $trail$.
```c=
void delete(listPointer *first, listPointer trail, listPointer x)
{/* delete x from the list, trail is the preceding node
and *first is the front of the list */
if (trail)
trail-->link = x-->link;
else
*first = (*first)-->link;
free(x);
}
```
> ```c=
> void delete(listPointer *first, listPointer trail, listPointer x)
> {/* delete x from the list, trail is the preceding node
> and *first is the front of the list */
> if (trail)
> trail-->link = trail->link->link;
> else
> *first = (*first)-->link;
> free(x);
> }
> ```
> [name=張聖岳][time=Sat, Nov 2, 2019 9:58 PM]
### 4. Assume that we have a list of integers as in figure1. Create a function that searches for an integer, $num$. If $num$ is in the list, the function should return a pointer to the node that contains $num$. Otherwise it should return $NULL$.
<div style="text-align:center;">
:arrow_up_small: Figure 1:
</div>
> ```c=
> listptr search(listptr first, int num){
> if(first==NULL) return NULL
> listptr tmp;
> for(tmp=first; tmp!=NULL; tmp=tmp->link)
> if(tmp->data==num) return tmp;
> return NULL;
> }
> ```
> [name=張聖岳][time=Sat, Nov 2, 2019 10:04 PM]
### 5. Write a function, $length$, that returns the number of nodes in a list.
> ```c=
> int length(listptr first){
> int len;
> listptr tmp = first;
> for(tmp = first; tmp!=NULL; tmp=tmp->link)
> len++;
> return len;
> }
> ```
> [name=張聖岳][time=Sat, Nov 2, 2019 10:07 PM]
### 6. Write a function, $pread$, that reads in $n$ pairs of coefficients and exponents, $(coef_i , expon_i), 0 \leq i < n$ of a polynomial, $x$. Assume that $expon_{i+1} > expon_i , 0 \leq i < n−2$, and that $coef_i \neq 0, 0 \leq i < n$. Show that this operation can be performed in $O(n)$ time.
> ```c=
> typedef struct poly *polyptr
> struct poly{
> int exp;
> double cof;
> polyptr link;
> };
> void pread(polyptr p){
> polyptr iter;
> for(iter=p; iter!=NULL; iter=iter->link)
> printf("(%f,%d)\n", iter->cof, iter->exp);
> }
> ```
> [name=張聖岳][time=Sat, Nov 2, 2019 10:16 PM]
### 7. Let $a$ be a pointer to a polynomial. Write a function, $peval$, to evaluate the polynomial $a$ at point $x$, where $x$ is some floating point number.
> ```c=
> typedef struct poly *polyptr
> struct poly{
> int exp;
> double cof;
> polyptr link;
> };
> #include <math.h>
> double peval(polyptr a, double x){
> polyptr tmp;
> double re=0;
> for(tmp=a; tmp!=NULL; tmp=tmp->link)
> re+=tmp->cof*pow(x, tmp->exp);
> return re;
> }
> ```
> [name=張聖岳][time=Sat, Nov 2, 2019 10:20 PM]
### 8. Rewrite Exercise 6 using a circular representation for the polynomial.
> ```c=
> typedef struct poly *polyptr
> struct poly{
> int exp;
> double cof;
> polyptr link;
> };
> void pread(polyptr p){
> polyptr iter;
> for(iter=p; iter!=p; iter=iter->link)
> printf("(%f,%d)\n", iter->cof, iter->exp);
> }
> ```
> [name=張聖岳][time=Sat, Nov 2, 2019 10:22 PM]
### 9. Write a function that deletes a node containing a number, $num$, from a circularly linked list. Your function should first search for $num$.
> ```c=
> typedef struct list *listptr
> struct list{
> int data;
> listptr link;
> };
> void delete(listptr first, int num)
> {
> if(first==NULL) return;
> listptr tmp = first;
> while(tmp->link!=first && tmp->link->data!=num);
> if(tmp->link->data==num) tmp->link=tmp->link->link;
> }
> ```
> [name=張聖岳][time=Sat, Nov 2, 2019 10:29 PM]
## Chapter 5
### 1. For the binary tree of Figure 1, list the leaf nodes,the nonleaf nodes, and the level of each node.
> leaf $=\{D, E\}$
> nonleaf $=\{A, B, C\}$
> level $=\{A:1, B:2, C:3, D:3,E:4\}$
>
> [name=張聖岳][time=Sun, Nov 3, 2019 10:43 AM]
### 2. Write out the inorder, preorder, and level-order traversals for the binary tree of Figure 2.
> (a)
> inorder $=(D,E,C,B,A)$
> preoder $=(A,B,C,D,E)$
> level_order $=(A,B,C,D,E)$
> (b)
> inoder $=(H,D,I,B,E,A,F,C,G)$
> preoder $=(A,B,D,H,I,E,C,F,G)$
> level_order $=(A,B,C,D,E,F,G,H,I)$
>
> [name=張聖岳][time=Sun, Nov 3, 2019 10:55 AM]
### 3. Do Exercise 2 for the binary tree of Figure 1.
> inoder $=(E,C,B,D,A)$
> preorder $=(A,B,C,E,D)$
> level_order $=(A,B,C,D,E)$
>
> [name=張聖岳][time=Sun, Nov 3, 2019 10:58 AM]
### 4. Suppose that we have the following key values:$7, 16, 49, 82, 5, 31, 6, 2, 44$.
#### (a) Write out the max heap after each value is insert into the heap.
> ```graphviz
> digraph G{
> subgraph r{
> node[label="" style=invis height=0 width=0]
> edge[style=invis]
> rank1->rank2->rank3->rank4
> }
> node[shape=circle]
> subgraph a{
> edge[style=invis]
> {rank=same; rank1->82}
> {rank=same; rank2->49->31}
> {rank=same; rank3->44->5->16->6}
> {rank=same; rank4->2->7}
> }
> edge[arrowhead=none]
> 82->{49,31}
> 49->{44,5}
> 31->{16,6}
> 44->{2,7}
> }
> ```
> [name=張聖岳][time=Sun, Nov 3, 2019 11:28 AM]
#### (b) Write out the min heap after each value is insert into the heap.
> ```graphviz
> digraph G{
> subgraph r{
> node[label="" style=invis height=0 width=0]
> edge[style=invis]
> rank1->rank2->rank3->rank4
> }
> node[shape=circle]
> subgraph a{
> edge[style=invis]
> {rank=same; rank1->2}
> {rank=same; rank2->7->5}
> {rank=same; rank3->44->16->49->6}
> {rank=same; rank4->82}
> }
> edge[arrowhead=none]
> 2->{7,5}
> 7->{44,16}
> 5->{49,6}
> 44->82
> }
> ```
> [name=張聖岳][time=Sun, Nov 3, 2019 11:28 AM]
### 5. Write a C function that searches for an arbitrary element in a max heap . What is the computing time of your function?
> ```c=
> typedef struct element{
> int key
> }element;
> element heap[MAX_SIZ];
> int n;
> int search(int i, int x)
> {
> if(heap[i].key==x) return i;
> if(heap[i].key < x) return 0;
> int re;
> if(re=search(i*2, x)) return re;
> if(re=search(i*2+1,x)) return re;
> return 0;
> }
> search(1, x);
> ```
> $O(n)$
> [name=張聖岳][time=Sun, Nov 3, 2019 11:38 AM]
### 6. Define the inverse transformation of the one that creats the associated binary tree from a forest. Are these transformations unique?
> _Ans._ Yes.
> [name=張聖岳][time=Sun, Nov 3, 2019 11:52 AM]
### 7. Prove that the preorder traversal of a forest and the preorder traversal of its associated binary tree give the same result.
> In a forest, we will traverse child from left to right by preorder.
> Each child will be traversed before there parents right slibing.
> Respond to its associated binary tree, the child in left subtree will be trace first which is correspond to the child in forest, so is slibing in right subtree.
>
> [name=張聖岳][time=Sun, Nov 3, 2019 12:07 PM]
### 8. Prove that every binary tree is unique defined by its preorder and inorder sequences.
> Without doubt, preorder ordered by each vertice it traverse.
> Inorder with binary tree, a vertice can have at most two children which mean that it can only be order between of its left subtree and right subtree.
>
> [name=張聖岳][time=Sun, Nov 3, 2019 12:13 PM]
## 重點整理
### 1. 時間複雜度的分析: time complexity analysis, big O, ...
### 2. 數學歸納法的證明: proof by induction
### 3. 稀疏矩陣(sparse matrix): how to maintain the non-zero elements and transpose the matrix
> Use a struct array. In each element,there are three member value, row, col, and n. The first element record the max row, the max col, and the number of element. The other elements are ordered by row and col.
>
> ```c=
> #include <string.h>
> typedef struct term{
> int row, col, n;
> }block;
> void transpose(block *A, block *B){
> B[0].row = A[0].col;
> B[0].col = A[0].row;
> int numElement = B[0].n = A[0].n;
> int start[MAX_SIZ], rowCnt[MAX_SIZ];
> int i;
> memset(rowCnt, 0, sizeof(int)*n);
> for(i=1; i<=n; i++){
> rowCnt[A[i].col]++;
> }
> start[0]=0;
> for(i=1; i<=n; i++){
> start[i] = start[i-1]+rowCnt[i-1];
> }
> for(i=1; i<=n; i++){
> int s = start[A[i].col]++;
> B[s].row = A[i].col;
> B[s].col = A[i].row;
> B[s].n = A[i].n;
> }
> }
> ```
> [name=張聖岳][time=Mon, Nov 4, 2019 10:08 PM]
### 4. 字串比對(pattern matching): how to build the failure table and use it to match the pattern
> ```c=
> int fail[MAX_LEN];
> void failure(char *pat){
> int i,j, n=strlen(pat);
> fail[0] = -1;
> for(j=1; j<n; j++){
> i=fail[j-1];
> while(pat[i+1]!=pat[j] && i>=0)
> i = fail[i];
> if(pat[i+1] == pat[j]) fail[j] = fail[i]+1;
> else fail[j] = -1;
> }
> }
> int pmatch(char *str, char *pat){
> int lens = strlen(str), lenp = strlen(pat);
> int i, j;
> i=j=0;
> while(i<lens && j<lenq){
> if(str[i]==pat[j])
> i++;j++;
> else if(j==0) i++;
> else j=fail[j-1]+1;
> }
> return (j==lenp)? i-lenp:-1;
> }
> ```
> [name=張聖岳][time=Mon, Nov 4, 2019 9:36 PM]
### 5. 堆疊和佇列(stack & queue): principle
> stack
> : last-in-first-out list
>
> queue
> : first-in-first-out list
>
> [name=張聖岳][time=Mon, Nov 4, 2019 9:39 PM]
### 6. 中敘轉後敘(infix -> postfix): use stack
> (exercise chapter3-7)
> [name=張聖岳][time=Mon, Nov 4, 2019 9:40 PM]
### 7. 鏈結清單(linked list): insertion and deletion
> ```c=
> typedef struct list *listptr;
> struct list{
> int key;
> listptr link;
> };
> void insertion(listptr *first, listptr x, int data){
> listptr tmp;
> tmp->key = data;
> MALLOC(tmp, sizeof(tmp));
> if(*first){
> tmp->link = x->link;
> x->link = tmp;
> }else {
> *first = tmp;
> tmp->link = NULL;
> }
> }
> void deletion(listptr *first, listptr trail, listptr x){
> if(trail){
> trail->link = x->link;
> }else{
> *(first) = *(first)->link;
> }
> free(x);
> }
> ```
> [name=張聖岳][time=Mon, Nov 4, 2019 9:50 PM]
### 8. 邏輯上刪除節點並儲存於可用清單(available list for polynomials)
> ```c=
> polyPointer getNode(void)
> {
> /* provide a node for use */
>
> polyPointer node;
>
> if (avail) {
> node = avail;
> avail = avail->link:
> }
> else
> MALLOC(node, sizeof(*node));
>
> return node;
> }
> void retNode(polyPointer ptr)
> {
> ptr->link = avail;
> avail = ptr;
> }
> void cerase(polyPointer *ptr)
> {
> polyPointer temp;
> if (*ptr) {
> temp = (*ptr)->link;
> (*ptr)->link = avail;
> avail = temp;
> *ptr = NULL;
> }
> }
> ```
> [name=張聖岳][time=Mon, Nov 4, 2019 10:24 PM]
### 9. 樹的所有名詞定義: tree terminology
> Tree
> : A unordered graph $G$
> : 1. $\forall u, v \in V(G)\rightarrow u,v$ is connective
> : imply that there are no nontrival vertice
> : 2. $|E(G)|=|V(G)|-1$
>
> root
> : the vertice that its parent is itself
>
> leaf
> : the vertice that has only a neighber, its parent
>
> height
> : the maxium distance from root to leaf
>
> level
> : the #nodes of the path to root.
>
> parent
> : $u$ is a neighber of $v$, $u$'s level is lower than $v$'s
> : $\rightarrow u$ is $v$'s parent.
>
> child
> : $u$ is a neighber of $v$, $u$'s level is higher than $v$'s
> : $\rightarrow u$ is $v$'s parent.
>
> slibing
> : the vertice which shared the parent with another
> : then, they are slibing
>
> Acestor
> : All node included from the path to root.
>
> Degree of a node
> : the number of subtrees of the node
>
> Degree of a tree
> : the maximum degree of the tree’s nodes
>
> [name=張聖岳][time=Mon, Nov 4, 2019 10:42 PM]
### 10. 沒有交集的集合: disjoint set, union function, find function, ...
> ```c=
> #include <string.h>
> #include <stdlib.h>
> int parent[MAX_SIZ];
>
> void Make_Set(int x){
> if(!parent[x])
> parent[x]=x;
> }
>
> int Find(int x){
> if(parent[x]!=x)
> parent[x] = Find(x);
> return parent[x];
> }
>
> void Union(int u, int v){
> int uRoot = Find(u);
> int vRoot = Find(v);
>
> if(uRoot == vRoot) return;
> int randnum = rand_r(&randnum);
> if(random%2) swap(xRoot, yRoot);
>
> parent[xRoot] = yRoot;
> }
> ```
> [name=張聖岳][time=Mon, Nov 4, 2019 10:55 PM]
### 11. heap: insertion and deletion
> ```c=
> typedef struct {
> int key;
> } element;
> element heap[MAX_SIZ];
> int current_size;
> void insertion(element x){
> if(current_size == MAX_SIZ-1) return;
> heap[++current_size]=x;
> int i=current_size;
> while(heap[i/2]<heap[i] && i>=1)
> swap(heap+(i/2), heap+i);i/=2;
> }
> element deletion(){
> element item = heap[1];
> int parent=1, child=2;
> element tmp = heap[current_size--];
> while(child <= current_size){
> if(child<current_size && heap[child].key < heap[child+1].key)
> child+1;
> if(heap[child].key < tmp.key) break;
> heap[parent] = heap[child];
> parent = child;
> child *= 2;
> }
> heap[parent] = tmp;
> return item;
> }
> ```
> [name=張聖岳][time=Mon, Nov 4, 2019 11:20 PM]
### 12. 樹上的拜訪: traverse in a tree, in-order, pre-order, ...
> ```=
> inorder(x){
> inorder(first child)
> print x
> for y in all remaining children:
> inorder(y)
> }
> pre-order(x){
> print x
> for y in all children:
> pre-order(x)
> }
> ```
> [name=張聖岳][time=Mon, Nov 4, 2019 11:26 PM]
### 13. 二元樹的特性: number of unused links, number of nodes, ..., use induction
> 1. The maximum number of nodes on level i of a binary tree is 2^i-1^ , i ≥ 1.
> 2. The maximum nubmer of nodes in a binary tree of depth k is 2 ^k^ -1, k ≥ 1.
> $$\sum_{i=1}^k2^{i-1}=2^k-1$$
> 3. For any nonempty binary tree, T, if n~0~ is the number of leaf nodes and n~2~ the number of nodes of degree 2, then n~0~ =n~2~ +1 (proof by #edge)
>
> [name=張聖岳][time=Mon, Nov 4, 2019 11:57 PM]
### 14. 二元樹上找第 k 個大的元素: use leftSize, maintain leftSize
> ```c=
> int binary_tree[MAX_SIZ];
> int search(int cur, int k){
> if(rightsize[cur]==k-1) return binary[cur];
> if(rightsize[cur]>k) return search(cur*2+1, k);
> else return search(cur*2, k-rightsize[cur]);
> }
> ```
> [name=張聖岳][time=Tue, Nov 5, 2019 12:01 AM]
### 15. 二元樹的可能種類: number of distinct binary trees
> The number of distinct binary trees with n node is equal to the
number of distinct inorder permutations with the same preorder
> [name=張聖岳][time=Mon, Nov 4, 2019 11:29 PM]
Sign in with Wallet
Connect another wallet