# Data Structure (I) - 01 Basic Concepts
> PART (I) - 01
> Other parts in this series $\rightarrow$ [Data Structure - Syllabus ](/bU7575BKTwmwkvmJ5742xA)
# Introduction to data structures
A data structure is a way to store and organize data in a computer, so that it can be used efficiently.

We will research them in their :
> 1. logical view
> 2. operations
> 3. cost of operations
> 4. implementation
# Data Type
## Native Data Type
It is hardware implementation, for example:
> * int
> * float
> * char...
>
Each of them are collections of values (objects) and there are sets of operations on those values.

We know that all of our data store in bit ( 8bits = 1 byte ), which only store 0 and 1. We can say that the data type is interpretation of a bit pattern.

e.g.

flowchart LR
0([0100 0001])-->|integer|1((65))
0([0100 0001])-->|ASCII code|2(('A'))
0([0100 0001])-->|BCD\nbinary coded decimal|3((41))

### 1’s and 2’s Complements
**range of 1’s complement in 8 bits**
$-(2^7-1) \sim 2^7-1 \Rightarrow -127\sim127$
e.g.
> * 0000 0000 = 0
> * 0000 0001 = 1
> * 0111 1110 = 126 
> * 1111 1110 = −1 
> * 1111 1111 = −0

**range of 2’s complement in 8 bits**
01111111 = 127
10000000 = -128
$-(2^7) \sim 2^7-1 \Rightarrow -128\sim127$
e.g.
> * 0000 0000 = 0
> * 0000 0001 = 1
> * 0111 1110 = 126 
> * 1111 1110 = −2 
> * 1111 1111 = −1
## Absrtact Data Type (ADT)
* defined by existing data types.
* internal object representation and operation implementation are hidden by software implementation. $\rightarrow$define data and operations, but no implementation.

examples:
> * stack
> * queue
> * set
> * list...

## Concrete Implementation
Which is correponded to the ADT, how we use them in the real computer. for example: In C++, we can implement list in to array `int arr[3]`.

# Algorithm
In the beginning, I said we will dive into the logical view, operations and cost of operations, and these are what algorithm talk about. And there are some practice for you to review what we learnt in the first year in college.

There are few points we need to consider:
> The Criteria to Judge a Program
> • Does it do what we want it to do?
> • Does it work correctly according to the original specification of the task?
> • Is there documentation that describes how to use it and how it works?
> • Do we effectively use functions to create logical units?
> • Is the code readable?
> • Do we effectively use primary and secondary storage?
> • Is running time acceptable?

## Asymptotic O Notation
> $f(n)$ is $O(g(n))$ if there exist positive integers $a$ and $b$ such that
> $f(n) ≦ a．g(n) \quad\forall\quad n ≧b$ .

* $f(n)= c_1 n^k + c_2 n^{k-1} +...+ c_k n + c_{k+1} = O(n^{k+j})$, for any j ≧0
* $f(n)= c = O(1)$ , c is a constant.
* $log_m(n) = log_m(k)． log_k(n)$ , for some constants m and k.
* $log_m(n) = O(log_k(n)) = O(log n)$

Values of Functions

|$log(n)$|$n$|$nlog(n)$| $n^2$ |$n^3$|$2^n$|
| -------- | -------- | -------- | -------- | -------- | -------- |
0|1| 0| 1| 1 |2
1|2| 2| 4| 8| 4
2|4| 8| 16| 64| 16
3|8| 24| 64| 512| 256
4|16| 64 |256 |4,096 |65,536
5|32| 160 |1,024| 32,768| 4,294,967,296


## Time Complexity and Space Compexity
### Time Complexity
The amount of computation time required by a program.
* **Polynomial order** : $O(n^k )$, for some constant k.
* **Exponential order** : $O(d^n )$, for some d >1.
* **NP-complete(intractable) problem** : require exponential time algorithms today.
* **Best sorting algorithm with comparisons** : $O(nlog(n))$

### Space complexity
The amount of memory required by a program.
### Time Performance in C Code

#include <time.h>
time_t start, stop;
start = time(NULL); // start of sec since 00:00 hours, Jan 1, 1970 UTC (current unix timestamp)

... //the program to be evaluated
    
stop = time(NULL);
duration = ((double) difftime(stop,start);

#include <time.h>
clock_t start, stop;
start = clock(); // start of clock ticks since the program begins

... //the program to be evaluated
    
stop = clock();
duration = ((double) (stop - start) ) / CLOCKS_PER_SEC;

## Practices
### Factorial
#### Iterative definition of n factorial:
$\begin{cases}
n! = 1\quad \textrm{if}\quad n = 0\\
n! = n(n-1)(n-2)...(1) \quad \textrm{if} \quad n>0
\end{cases}$

int f = 1;
for (int x = n; x > 0; x--)
    f *= x;
return f;

#### recursive definition of n nactorial
$\begin{cases}
n! = 1\quad \textrm{if}\quad n = 0\\
n! = n(n-1)! \quad \textrm{if} \quad n>0
\end{cases}$

int fact(int n){
    if ( n == 0) //boundary condition
        return (1);
    else 
        return n*fact(n-1);
} 

### Binary Search
sorted sequence : (search 9)

||01| 04| 05| 07| 09| 10|12|15|
| -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |
step 1 ||||↑|||||
step 2 ||||||↑|||
step 3 |||||↑||||

• used only if the table is sorted and stored in an array.
• Time complexity: $O (log(n))$

#### Iterative C Code for Binary Search

// Search a[0], ..., a[n-1] for x
int BinarySearch (int *a, int x, const int n){
    int left = 0, right = n - 1;
    while (left <= right;) {
        int middle = (left + right)/2;
        if(x < a[middle]) right = middle - 1;
        else if(x > a[middle]){left = middle + 1;}
        else{return middle};
    } // end of while
    return -1; // not found
} 

#### Recursion for Binary Search

//Search a[left], ..., a[right] for x
int BinarySearch (int *a, int x, const int left, const int right){
    if (left <= right) {
        int middle = (left + right)/2;
        if (x < a[middle])
            return BinarySearch(a, x, left, middle-1);
        else if (x > a[middle])
            return BinarySearch(a, x, middle+1, right);
        else return middle;
    } // end of if
    return -1;// not found
}

### Permutation

void permutation(int *arr, int pos, int size){
    if(pos==size-1){
        for(int i=0;i<size;i++){
            printf("%d ",arr[i]);
        }
        printf("\n");
    }else{
        // set the pos-th number
        for(int i=pos;i<size;i++){
            //swap
            int temp = arr[i];
            arr[i] = arr[pos];
            arr[pos] = temp;
            //to set next position
            permutation(arr, pos+1, size);
            //swap
            temp = arr[i];
            arr[i] = arr[pos];
            arr[pos] = temp;
        }
    }
}

main function

int main() {
    int arr[4]={1,2,3,4};
    permutation(arr,0,4);

    return 0;
}

### Fibonacci Sequence
#### Recursive code

int fib(int n){
    if(n<=1){
        return 1;
    }else{
        return fab(n-1)+fab(n-2);
    }
}

#### Iterative code

int fib(int n){
    int i, x, logib, hifib;
    if (n <= 1)
        return(n);
    lofib = 0;
    hifib = 1;
    for (i = 2; i <= n; i++){
        x = lofib; /* hifib, lofib */
        lofib = hifib;
        hifib = x + lofib; /* hifib = lofib + x */
    } /* end for */
    return(hifib);
}

### The Towers of Hanoi Problem

int towers(int n, char A, char B, char C){
    if ( n == 1){
        // If only one disk, make the move and return.
        printf("move disk 1 from %c to %c\n", A, C);
        return 0;
    }
    //Move top n-1 disks from A to B, using C as auxiliary
    towers(n-1, A, C, B);
    //move remaining disk from A to C
    printf("move disk %d from %c to %c\n", n, A, C);
    //Move n-1 disk from B to C, using A as auxiliary
    towers(n-1, B, A, C);
} // end towers 

### Selection sort

void sort (int *a, int n){
    for ( int i = 0; i < n; i++){
        int j = i; 
        for (int k = i+1; k < n; k++)
            if (a[k] < a[j]) j = k;
        int temp = a[i]; 
        a[i] = a[j]; 
        a[j] = temp;
    }
}

### Quick sort

void quick_sort(int arr[], int size) {
    if (size > 1) {
        int small[size];
        int big[size];
        int small_size = 0, big_size = 0, temp = arr[0];
        for (int i = 1; i < size; i++) {
            if (arr[i] <= arr[0]) {
                small[small_size] = arr[i];
                small_size++;
            } else {
                big[big_size] = arr[i];
                big_size++;
            }
        }
        quick_sort(small, small_size);
        quick_sort(big, big_size);
        for (int i = 0; i < small_size; i++) {
            arr[i] = small[i];
        }
        arr[small_size] = temp;
        for (int i = 0; i < big_size; i++) {
            arr[i + small_size + 1] = big[i];
        }
    }
}

### 8 queens problem

#include <iostream>
using namespace std;
int storages[92][8];
int total=0;
void put_queen(const int* pos,int count){
    if(count==8){
    	for(int i=0;i<8;i++){
    	    storages[total][i]=pos[i];
    	}
    	total++;
    	return;
    }
    bool avoid_area[8]={true,true,true,true,true,true,true,true};
    for(int i=0;i<8;i++){
    	if(pos[i]!=-1){
    	    avoid_area[i]=false;
    	    int avoid_left=i+pos[i]-count,avoid_right=i-pos[i]+count;
    	    if(avoid_left>=0){
    	    	avoid_area[avoid_left]=false;
    	    }
    	    if(avoid_right<=7){
    	    	avoid_area[avoid_right]=false;
    	    }
    	}
    }
    for(int i=0;i<8;i++){
    	if(avoid_area[i]){
            int new_pos[8]={pos[0],pos[1],pos[2],pos[3],pos[4],pos[5],pos[6],pos[7]};
	    new_pos[i]=count;
            put_queen(new_pos,count+1);
        }
    }
}
int main() {
    int pos[8]={-1,-1,-1,-1,-1,-1,-1,-1};
    put_queen(pos,0);
    for(int k=0;k<total;k++){
    	cout<<endl<<k+1<<endl;
    	for(int i=0;i<8;i++){
    	    for(int j=0;j<8;j++){
    	        if(storages[k][i]==j)
	            cout<<"Q ";
		cout<<"- ";
	    }
	    cout<<endl;
        }
    }
    return 0;
}

### Sierpiński triangle

#include <iostream>
using namespace std;
char Sierpinski_Triangle(int layer, int pos) {
	if(pos<0||layer<0||pos>(layer+1)*2-2){
		return ' ';
	}
	if(pos==0 || pos==(layer+1)*2-2 || Sierpinski_Triangle(layer-1,pos-2)=='^' ^ Sierpinski_Triangle(layer-1,pos)=='^'){
    	return '^';
	}
	return ' ';
}
int main() {
	int n;
	cout<<"Input the height of triangle: ";
	cin>>n;
    for(int i=0;i<n;i++){
    	for(int j=0;j<n-i;j++){
    		cout<<" ";
		}
		for(int j=0;j<2*n-1;j++){
    		cout<<Sierpinski_Triangle(i,j);
		}
		cout<<endl;
	}
}