datduyng/csce155e-c-note.md

## csce155e-c-note.md

      
    Raw
  

              csce155e-c-note.md
            
          
    /*csce155e
Cbourke
C introduction

1/11/17


Programming, compiling and running process
Source files are plain text
Have to be compile into an excutable program
Source – assembly – machine code(binary)

Demonstration


edit a source code file, helo.c
assemble: gcc –S hello .c s

Product a file hello.


Compile: gcc –c hello.c

Produce an object file, hello.o
View: hexdump –C hello.c


you need to also link an external library or all in one shot :

gcc hello.c
gcc -o hello hello.c to produce an executable file name hello


Example CS account (g++) commands for compilation and linking:

gcc -c frac.c               // translates frac.c into object code, frac.o 
gcc -c main.c                // translates main.c into object code, main.o 
gcc frac.o main.o -o sample    // links object code files into an executable called "sample" 
or 
gcc -c frac.c 
gcc frac.o main.c -lm or gcc -o OUTPUT_FILE_NAME frac.o main.c -lm

Example of makefile


Large projects require even more abstraction and tools to manage source code and specify how it gets built. One tool to facilitate this is a program called Make which uses makeﬁles–speciﬁcations for which pieces of code depend on other pieces and how all pieces get built and combined to build an executable program (or collection of executables). The use of modern IDEs has made the build process much more manageable, but make is still widely used. Several useful tutorials exist describing how makeﬁles can be deﬁned and used.
• http://www.opussoftware.com/tutorial/TutMakefile.htm
• http://mrbook.org/tutorials/make/


basically make allow you to link all file and compile in a short way.


with a file structure

integrate.c, intergrate.h,integrateMain.c


CC = gcc
CFLAGS=-I.

tester: integrateMain.c integrate.o
        $(CC) -o tester integrate.o integrateMain.c -lm

integrate.o: integrate.o integrate.c
        $(CC) -c -o integrate.o integrate.c

Program in C

* Comment —  are design to tell the why and the how not that what.
* Preprocessor directive: these are tdirective to the copiler that are executed before it start compiling

* include external library using #include
* define “Macro” using #define
* A macro is essentially a cut and paste operation
* The main function is always starting point for any executable program.
* for now, ignore int args, char **args

Other syntax,

* Semicolons end excutable statements
* quotation marks delimit(Static) String
* commas delimit
* Reserved keyword( that have a predefined meaning): double, printf, etc.

Variable


* C is a statically typed language.
* a variable must be defined before you can use it.
* A declaration must include a type and an identifier.
* The scope of a variable  is the section(s) of code in which it exist.
* built in types of variable
	- int - represent from (-2147483648 -2147483648)( since it is only a 				- 32-but signed 2s complement intereger).
		- double - a floating point number that gives you about 16-17 digits of 			accuracy.
	- char - a single ASCII text character
		+ASCII : American standard code for information interchange. - 			defined table of common characters that are lexicographically 				ordered.(Asciitable.com)


Additional:
https://en.wikibooks.org/wiki/C_Programming/Simple_input_and_output'

EX:

printf("19+31 is '''%d'''", 19+31);

The placeholder %d literally "holds the place" for the actual number that is the result of adding 19 to 31.
These placeholders are called format specifiers. Many other format specifiers work with printf(). If we have a floating-point number, we can use %f to print out a floating-point number, decimal point and all. Other format specifiers are:
•	%d - int (same as %i)
•	%ld - long int (same as %li)
•	%f - float
•	%lf - double[1]
•	%c - char
•	%s - string
•	%x - hexadecimal

Scanf funtion


The `scanf()`` function is the input method equivalent to the printf() output function - simple yet powerful. In its simplest invocation, the scanf format string holds a single placeholder representing the type of value that will be entered by the user. These placeholders are mostly the same as the printf() function - %d for ints, %f for floats, and %lf for doubles.

EX:
#include "stdio.h"

int main(void)
{
    int a;

    printf("Please input an integer value: ");
    scanf("%d", &a);
    printf("You entered: %d\n", a);

    return 0;
}

// declare an interger and set it to 10
int x =10;

//declare a double variable and set ti to 3.14
double pi = 3.14;

// declare but do not assign a character variable:
char firstInitial; //  no default value

// later on you can assign and reassign variable values
pi = 3.14159
// assign firstInitial
firstInitial = ‘C’;
Operator

* Assignment operator(single equal sign): variable stay on the left hand side.
* Arithmetic:+,-,*,/.
* interger division: % represent modulus - remainder.
	* EX: 5%2(“5 mod 2) -> return 1;
	       - 10%3 -> return 1
* Truncation is an issue
* when an integer is divided by an integer, the result is an integer.

		int a= 10;
		int b = 20;

		double c= a/b; //  result in 0.0
		// explicit typecast: force( temporily) one fo the variables
		// to become a double
		double c =(double)a/b;   // result is 0.5

		int x =3.14; // x will have the value 3.
Other pitfalls

	int x = 10 ;
	int y = 0;

	int z = x/y;
* There are undefined result. It may result in Inf or -Inf or NaN(not a number)

Basic I/O

* scanf Scanning the  standard input in a formatted way.
*  standard input == keyboard.
* to specify the format, you use placeholder:
	* for double use `%lf` ( long floating point )
	* for int use 	`%d` ( (digit))
	* for char use 	`%c`
* you place the placeholder into a string( double quote) and specify which  variable you want the value stored in.

	int x ;
	scanf(“%d” ,&x);

	double pi;
	scanf(“%lf”,&pi);

	char firstInitial;
	scanf(“%c”,&firstInitial);

	There is no ampersand with printf

	int x = 10;
	double pi =3.14;
	char firstInitial = ‘C’;

	printf(“The variable x is equal to %d\n”);
	printf(“my intial is %c, and pi is %f\n”);

	by default, printf prints 6 decimals of accuracy
	you can change this using modifier to you place holder.

	double pi= 3.1415;
	printf(‘%f”,pi);        //  3.141500
	printf(“%.10f”,pi); // 3.1415000000
	printf(“%.2f”,pi); //3.14
	printf(“%.3f”,pi);   // 3.142 note printf rounds!
* you can also “pad” a formatted number spaces using two modifers:
* `%m.nf`, m is the minimum number of columns to print, n is the number of
	decimal to print

	double pi = 3.1415  ;
	printf(“%20.4f”, pi); //  20 total columns including the period
				// with 4 decimals of accuracy
				// 14 spaces then 3.1415( 14 spaces + 6 spaces);
	printf(“%2.4”, pi); // minimum of 2 columns, 4 decimals of accuracy
			       // 3.14 ( no leading spaces, since we hit the minimum of 2);
### Ecerxise:


write a program that promt the user for 2 right

triangle.c


/*
*Author: Not me
* Date: not today
* This program computes the hypotenuse of a right triangle
*given its two other sides, read in interactively from the user
*
*/
#include<stdio.h>
#incldue<stdlib.h>
#include<math.h>

int main( int argc, char **argv){

	double a,b ,h;

	// promt the user for input:
	printf(“Please enter the length of the first side:”);
	// read in the first input
	scanf(“%lf”,&a);

	printf(“Please enter the length of teh second side:”);
	scanf(“%lf”,&b);

	// compute the value of teh hypotenuse
	h  = sqrt(a*a + pow(b,2));

	printf(“The value of the hypotenuse is %f\n”);
	return 0;
}// end main ()

1- 18 - 18

Conditional


normally, program have sequential control flow.


Basis If/esle - if-else if statement.


	if(<condition>){
		// this is the code that will execute the condition
	}

	if(condition>){
		// block A, if condition is true
	}else if ( <condition2>){
		// block B
	}else{
		// block C , if condition is false
	}
* The first condition that evaluate to true is the one that is execute
* You may omit else bliacj if there is no code to execute

Numeric comparison Operators
* <,>,<=,>=,==,!=
* All numerical comparison can operate literals.
EX;
	int a;
	double b,c;

	// comparing a variable to a literal/
	if(a==0){
	printf(“a is a zero!\n”);
	}

	// comparing 2 variable
	if(a =b){
	printf(“the 2 value are equal”);
	}

	// you can do but should never do this
	if(10 == a){
	….
	}
Negation operator.

* Any logical expression can be negated with a single !
* (a ==b) has a negation of  !(a ==b), but it is better to use (a != b)
* (a <= b) has a negation of !(a <= b), but it is better to use (a >= b)
* Usually a negatio is used on a “flag” variable; a variable that simply holds a 		truth value( true or false)
* in C, any numerical value can be treated as a boolean value( something that 	 	is true or false)
* in C, false is 0 ( zero)
* true is any non zero value( 3,3.5,3.14,-10, etc)
* by convention, it is usually use the value 1 as the true

	// flag variabele to indicate if someone is a student( true) or false

	int isStudent =1 ;

	// they are not a student;
	isStudent = 0;

	if(isStudent){
		printf(“congratulation, you get a student discount”);
	}

	if(!isStudent ){  // ( isStudent =0)
		printf(“ you will pay full price”);
	}
Ternary if-then-else operator


int min = ( (a < b) ? a : b );
The syntax, X ? Y:Z is as follow :X is any conditional statement; if it statement is true; then the expression take the value Y;else it take Z

Complex Logical Operator

* You can combine logical statement to form more complex logical statements
* “connectives” or logical operators
* The logical AND is true if and only if both of its operands are true*
	-Syntax: &&
	-Example: a && b is true if and only if “a” evaluate to true and “b: 			evaluate to true
* The logical OR operator. is true at least one of the operand is true
* 	syntax: ||

	if( 0 <= a  <= 10){
	….
	}

* In C, the above code will compule will execute but will not work for certian 		value,
* What happen when a ==  20 ;
		- The first comparison evaluated. 0 <= 20( true)
		- then 1 <= 10 evaluated and gives you true
		- Solution: break up condition using a &&

* Consider the following code.

	// C
	int a =5 ;
	if( a =10){…}
* The abve will compile and run, but will give incorrect value.
* `a =10` results in an assignment of the value 10 to the vairable a , which now has a value of 10( which is true)

* COnsider the following code.

	if(a ==10);{printf(“a is 10\n” }

* the semicolon only goes after after executable statements.

## Short Circuit( DARK AGES OF COMPUTER)
	* WHEN COMPUTER OPERATE A KILO HZ

	* Consider a logical and : a && b
  * if a evaluate false, does it matter what the value of b?
	*	NO; since the first one is false, then whenever or not the second is true does not matter, the entire expression evaluate to false.
	* consider a logical: `a|| b`
			- if “a “ evalueate to true, does it matter what the value of b is ?
			- No, the first being true, make the entire  statement true. so the second is irrelevenant
  * In C, if one of the two situation above occurs, the second expression is 		not evaluated.

Non numerical operation

`if(char firstInitial = ‘C’ || initial == ‘B’ || initial =‘c’){}``

* You cannot ever using equality and inequality operator on strings( sequences	of characetrs)

	// this is not valid
	if(name == “Chris”){
	printf(“Hello! Christ”);
	}		// because string store in difference address.
			// compare memories address store at difference location
Loops

An introduction to loop control structures.

We need a way to repeatedly execute blocks of code
There are three basic elements to a loop control structure:

An initialization (where the loop starts)
A continuation condition (how long should the loop continue or when should it stop)
An increment or "update" (how you make progress toward that ending condition)


For Loops


A for loop uses the keyword for
All three elements appear on teh same line:
for(<initialization>; <continuation>; <increment>)
Each loop is attached to a loop body: a block of code after the for statement that is executed on every "iteration" of the loop

int i;
for(i = 1; i <= 10; i = i + 1) {
  printf("%d\n", i);
}


The above example prints 1 through 10 in increments of 1, one number per line


Initialization condition: i = 1; (assigning the value 1 to i


Continuation: we continue executing the loop until the value stored in i exceeds 10


Incrmeent: i = i + 1 we count up by one on each iteration


Loop Body: print out the value of i on each iteration


Pitfall: if you do not assign an initial value to a variable in C, then it may hold ANY value! Sometimes 0xDEADBEEF is used to indicate uninitialized memory


Increment Operators


continually writing i = i + 1 is a lot!
Many languages define shorthand syntax ("syntactic sugar") for doing these common operations
Example: i++ (this adds one to the variable i) (increment operator)
Example: i-- (this subtracts one from the variable i) (decrement operator)
You can also increment or decrement by values other than one

a += 10; adds 10 to the variable a
a -= 5; subtracts 5 from the variable a
a *= 2; doubles the value of a
a /= 3; divides a by three and places the value back into a


//print numbers 10, 20, 30, ... 100 one to a line
int i;
for(i = 10; i <= 100; i += 10) {
  printf("%d\n", i);
}

While Loops


While loops use a different syntax an the keyword while
But the three elements are located on different lines

<initialization>
while(<continuation>) {
  //loop body

  <increment>
}
int i = 1;
while(i <= 10) {
  printf("%d\n", i);
  i++;
}

Fact: any for loop can be rewritten as a while loop and vice versa
Why multiple loop control structures?
For loops ar generally used in situations where the number of iterations is known before hand (though it may be variable);
Ex: you are going to execute the loop for 10 iterations or 20 iterations or n iterations

int n = 10;
int i;
for(i = 1; i <= n; i = i + 1) {
  printf("%d\n", i);
}

In contrast, while loops are generally used when the number of iterations is not known up front; instead some condition is modified on each iteration that can affect the number of iterations

int n = 234897324;
while(n > 1) {
 printf("n = %d\n", n);
  //n = n / 2;
  n /= 2; //divide n by two on each iteration
}
Pitfalls

Off By One Errors


Zune Bug

Infinite Loops


Consider the following code:

int i = 0;
while(i < 10) {
  printf("%d\n", i);
}

results in an infinite loop
Hint: to break out of an infinite loop via putty you can hit control-C

Missin Brackets

Consider the following code
int i = 0;
while(i < 10)
  printf("%d\n", i);
  i++;

Curly brackets are actually optional: if there are none, then the loop only binds the the immediate next line
Above prints zero forever because the loop only binds to the print statement
General rule: even if they are not necessary, always include your curly brackets!

Unnecessary (wrong) semicolons

int i = 0;
while(i < 10); {
  printf("%d\n", i);
  i++;
}

The above loop binds to an empty executable statement and gets stuck in an infinite loop, doing nothing

Nested Loops


Often you may need to do more than one iteration or an interation within an iteration

int i, j;
for(i=0; i<10; i++) {
  for(j=0; j<10; j++) {
    printf("%d\n", (i+j));
  }
}

The above loop makes 10 * 10 = 100 total iterations

Exercises


Do the following

A list of even integers 0 to n, one to a line
The same list, but delimited by commas
A list of integers divisible by 3 between 10 and 100 (print a total as well)
Prints all positive powers of two, 1, 2, 4, 8, …, up to 2^30
Prints all even integers 2 thru 200 on 10 different lines (10 numbers per line) in reverse order
Prints the following pattern of numbers (hint: use some value of i+10j):


11, 21, 31, 41, ..., 91, 101
12, 22, 32, 42, ..., 92, 102

20, 30, 40, 50, ..., 100, 110


Write a FizzBuzz program (see here for more information)


Write a program to project the total earnings in a savings account with a fixed APR, initial balance, and monthly deposit over a specified number of years.


Implement a program to use the Babylonian method to compute a square root of a number a using the series,


Solutions:

#include "stdio.h"

int main(void) {

  int n = 60;
  int i, j;
  //A list of even integers 0 to n, one to a line
  for(i=0; i<=n; i+=2) {
    printf("%d\n", i);
  }

  //The same list, but delimited by commas
  for(i=0; i<=n; i+=2) {
    printf("%d", i);
    if(i+2<=n) {
      printf(", ");
    }
  }
  printf("\n\n\n");
  //A list of integers divisible by 3 between 10 and 100 (print a total as well)
  int sum = 0;
  for(i=12; i<=99; i+=3) {
    printf("%d\n", i);
    sum += i;
  }
  printf("total is %d\n", sum);

  //Prints all positive powers of two, 1, 2, 4, 8, …, up to 230
  int result = 1;
  for(i=0; i<=30; i++) {
    //int power = pow(2, i);
    printf("2^%d = %d\n", i, result);
    result *= 2;
  }
  //Prints all even integers 2 thru 200 on 10 different lines (10 numbers per line) in reverse order
  for(i=200; i>=2; i-=2) {
    printf("%d ", i);
    if(i % 20 == 2) {
      printf("\n");
    }
  }

  for(i=1; i<=10; i++) {
    for(j=10; j<100; j+=10) {
      printf("%d, ", i+j);
    }
    printf("%d\n", i+j);
  }
}
FizzBuzz:
  int i;
  for(i=1; i<=100; i++) {
    if(i % 15 == 0) {
      printf("FizzBuzz\n");
    } else if(i % 3 == 0) {
      printf("Fizz\n");
    } else if(i % 5 == 0) {
      printf("Buzz\n");
    } else {
      printf("%d\n", i);
    }
  }
Square root:
#include "stdio.h"

int main(void) {

  double epsilon = 0.01;
  double a = 2.0;

  double x_curr = 1;
  double x_prev = 0; //previous value in the sequence

  while(fabs(x_curr-x_prev) >= epsilon) {
    double x_next = .5 * (x_curr + a / x_curr);
    printf("DEBUG: x_next = %f\n", x_next);
    x_prev = x_curr;
    x_curr = x_next;
  }

  printf("sqrt of %f is %f\n", a, x_curr);
  printf("the math library says %f\n", sqrt(a));

}
Date feb 13th,2018

Error Handling


Reconsider the quadratic roots program
Error can either be completelt unexpected or they can be anticipated but not normal
Error hanlding can be done by differenct appoached:

defensive programing: we can check for illegal or invalid operation before doing them and it would result error
communicate the tpe of error back to the calling function
you can use "exception" ( in other mordern programming language): go ahead and leap w/o looking,b/c we will catch you if you fall.


in C, we will follow the second strategy.
In C, you write defensive code( check for error conditions) and report an error to the calling function.
In the standard library, there is an errno.h library

C defines three error "codes"

EDOM indicate an error in the domain of a function
ERANGE indicatedan error in the range fo the function
EILSEQ indicated illlegal byte sequence


extended POSIX stanard defines defines 130 some other error


usually you use error term instead of raw error number,

ENumerated type in C


Many pieces of date have a limited number of possible value
Example: days of week, month in a year, error codes
In C uou can define an enumerated type and give it predefine human readable values
SyntaxL typedef (type definition) and enum(enumeration)
You can use openning/closing curly bracket to defune a comma -delimited list of possible values
Modern convention: use ALL_CAPS_UNDERSCORE_CASSING for enumeration calues
you can guve your enumerated type a nam that can then be used in your code; convenion: UpperCammelCasing

  typedef enum{
    SUNDAY,
    MONDAY,
    TUESDAY,
    WEDNESDAY,
    THURSDAY,
    FRIDAY,
    SATURDAY
  } dayOfWeek;


typically, enumerated types are declared in a header file
After declaration, you can use your type like any other vairable types

syntaxtix sugar.
  dayOfWeek today;
  today = TUESDAY;

  if(today == FRIDAY){
    printf("Have a good weekend");
  }

In C, enumerated types are actually just integer.
they always start(byde default) at zero and increment by 1
SUNDAY is associateed with zero, MONDAY  = 1, SATURDAY = 6

  dayOfWeek today = SATURDAY;
  today = today + 1;
EX:
  typedef enum{
    ERROR1,
    ERROR2,
    ERROR3,
    DIVISION_BY_ZERO_ERROR,
    NULL_ERROR
  }QuadraticErrorCode;

if(root1 = NULL || root2 == NULL){
  return NULL_ERROR;
}else if (a = 0){
  return DIVISION_BY_ZERO_ERROR;
}

// usage
int error code = ;

if(errorCode = NULL_ERROR){
  printf("some thing really srewing up\n");
}else if( errorCode = DIVISION_BY_ZERO_ERROR){
  printf("division by zero error");
}

Date : Feb 15th, 2018

Arrays


In general:

array have a single name( identify )
You can access individual element in an array using index
first is 0-index, second is at index 1
If there is n elements in an array, the last element is located at index n-1


Static array


static arrays are arrays of a fix size that allocated on top of the program call stack
Syntax:

// create an array that can hold 10 integer :
int arr[10];

// create an array of 20 double values:
double numbers[20];

// indexing :
arr[0] = 42; // set the first element to 42
arr[1] = 12; // set the second element to 12
arr[2] = 1;

arr[9] = 3.75;

Question: what value is stored in arr[3]?
answer: who knows? it does not have a default value.
Question: what happen if you try arr[11] = 4; // likely a segmentation fault. or "Undefine behavior"
Alternative, syntax:

  int n = 7;
  int prime[] = {2,3,5,7,11,13,17}; //set array of size 7

  // in the example above, the compiler take care of the size for us.
  // recommend to "book keep" your self
Sizing and iteration


In C, there is ABSOLUTELY NO WAY to(consistenly) determine the size of an array.
If we pass an array to a function, we also need to pass its size.
Of course, the size of an array is always an integer.

Variable length arrays(VLAs) around 20 yrs after c created


Int C 99( and in GNU C89) VLAs are support"

  int n = ....; // read from the user.
  int arr[n] ;
Just because you can( or more accurately might) use
int n = 10000000 ;
int arr[n] ; an array of size 10 million

above alnmost certainly be a segmentation fault: stack frame are not meant for such a large data
instead: to use Dynamic array

Dynamic arrays


Dynamics array are allocated not on the stack, but on the "heap" wich is much larger though more ineffiecient than the stack
The memory heap space is generally larger but less effiecient
You can dynamically allocate memory in the heap using a function in the standard lubrary called malloc (memory allocation )
you give it only one argumentL the number of bytes you want it to allocate and "give" to you
It return a pointer that points to the "beginning" of the memory location that it successfully allocated for you
It unsuccessful, it return NULL to indicate that memory could not be allocaed
malloc actually returns a "generic void pointer", void*

  int *arr = NULL;
  // want to allocate an array of 1 million integer

  int n = 1000000 ;
  arr = (int *) malloc(n * sizeof(int));

  // code above allocate 4 * size of int( 4bytes normally)
  // this code work on any system with a c compiler

  //create an array of 40 double values;
  int m = 40 ;
  int *number = (double *) malloc(sizeof(double) * m);

sizeof can be used to determine the number of bytes each type of variable takes
In general: malloc return a generic void pointer
A void pointer can point to anything

Memory management


once you have a dymaiccally alocated array, you can use it like any static array


Once you are done using your memory, you must clean up after yourself.


Memory is a resource, obce you are done with it, you need to return it back.So that it can be reused


if you don't, and hold on to memory, you will run out


This is known as a "memory leak"


So to give it back, you "free it up"


Use free function


it is most natural to use a for loop to iterate over elemtn in an array


  int n = 500 ;
  double *number = (double *) malloc(n * sizeof(double)) ;
  number[0] = 3.14;
  number[1] = 42.5;

  number[n-1]] = 3.5;
  number[n] = -1.5; // segmentation fault

  // use it yaya

  // done with it, so We need to free it up
  free(numbers);
    // example firefox keep requesting memory,
    //then it will crash. so you need to not request a lot of memory.

  // if you try to use you free memory, it is an undefine behavior
  number[0] =42;

  // iterate over the array, print each element one to a line;

  int i;
  for( i = 0;i< n;i++){
    printf("%f",number[i]);
  }

  // error checking reminder

  if(number == NULL){
    printf("allocation fail");
  }
Exercise

ptrArr.c

write a program to allocate n integer, fill it with values go from 1,2,3,4,n then iterate over them, print them, then sum them up.

Date feb 20th, 2018

Using array with function

  /** this function takes an int array and return
   * the sum of it element
   * array is NULL or if it sizes is <= 0 ;
   */

  int sum(const int *arr, int n){

    // declare variable
    int total = 0;
    int i = 0;
    for(i = 0; i < n - 1; i++){
      total += arr [i];
    }
    return total;
  }

  void printArray(int *arr, int n){

    int i;
    for(i = 0; i < n; i++){
      printf("%d",arr[i]);
    }
    return;

  }

  int main(){
    int prime[] = {2,3,5,7,11,13,17};
    int s = sum (prime, sizeof(prime));
    printArray(prime,);
    //arr[0] = 42;
    return 0;
  }

  // an array is a memory address.

Since array are passed by reference, no ampersands are needed.
using square brackets automatically dereferences the elements in the array.
Problem: since the array is passed by reference, changed can be made to its elements.
You can use the keyword const to prevent any change to the array element during the program.
You can also write a function to "return" an array .

Exercise


write a function that takes an int and creates and array of that size filled with one

/**
 * // return array
 * This function creates a new integer array
 * of the given size and fills it with ones, and return its.
 */

int* createOneArray(int size){
  int *result = (int *) malloc(size * sizeof(int));
  int i ;
  for(i = 0; i <size; i ++){
    result[i] = 1;
  }
  return result;
}
Multidimensional array s


YOu can have arrays with more than one "dimension"
2-D arrays: rows and column. table or matrix
3-D arrays: rows columns and "lane" or "aisles"
4+ D array.
In C, a pointer int *arr point to a 1-D array
a "double" pointer, int **mat points to a "2D array"
Using a pointer to pointers means that you need a loop of call to malloc
Exercise: write a function to create an n x n identity matrix

/**
 * This function creates an n x n identity matrix, returning
 * /

  int** identityMatrix(int n){

    int **result = (int**) malloc(n * sizeof(int*));

    int row;
    int col;
    for(row = 0; row < n ; row++){
      result[row] = (int *) malloc(n * sizeof(int));
    }
    for(row = 0 ; row < n; row++){
      for(col = 0;col < j; col ++){
        if(row == col){
          result[row][col] = 1;
        }else{
          result[row][col] = 0;
        }
      }
    }
    return result ;
  }
Shallow and deep copy

  int i, n = 10;
  ine *a = (int*) malloc(n * sizeof(int));
  for()

The above is a "shallow cope" , that is both ref point to the same memory location. changeing cvalue with respect to one, changes it for the
alternatively, you can make " a deep copy", a complete different opy sotred somewhere else in memory with the same value.
Exercise: write a deeo compy function for int array

/**
 * This function takes an int array and creates a deep copy
 * of it, returning the new deep compy
 * /

int* deepCopy(const int *arr, int size){
  // TODO: ERROR checking
  if(arr == NULL){
    return NULL;
  }
  int *copy = (int *) malloc(size * sizeof(int))l
  int i;
  for(i = 0; i < size; i ++){
      copy[i] = arr[i];
  }
  return copy;
}
Date feb 22nd, 2018

Deugging


Using printf statements to view the value(s) of variables if reffered to as "poor man's" debugging
A debugger is a program that simulate/run another program and allow you to: pause the execution
view vairable values
"step" thourgh the program line by line
set break points in a program and continue execution up to that point
GDP (gnu's debugger) is a command line debugger
Usage:

compile with -g flag to preserve variable and function names

gcc -g arrayProgram.c


with Multiple file

use ` gcc -g -o programName file1.c file2.c
then gbb programName


start GDB with your program:

*** gdb a.out***


Run your program:

run    - set a break point
break main


layout next // see the code. .// 2 layout next command will lead to the system processorn
layout source
break 16 // break at line 16
break main// break at main
break sum// break at sum // break FUNCTION_NAME
print VARIABLE_NAME
*print array@7 // print the whole array
watch iteration // watch a increment value of a varibale in a loop.
continue
break FILE.c:5 // break file.c @ line 5
type ***n *** to execute the program line by line


String


String are ordered of character (may be ASCII or unicode )
C only support ASCII
Different languages represent strings
Most language also provide a standatd library of function to process string

In String


In C, string are simplify an array of char elements
BIG ISSUE: in C all string must end with a special null-terminating character, \0( slash- zero)
this is not the same thing as NULL, it is not the same thing as 0, it is not the same thing as \n
You can declare static string

  char message[] = "Hello World!";
  // message is automatically null-terminated
  //and has a "size" of 13 characters including "/0"

  // once created, you can also change the contents of a string:
  message[0] = 'H';


String in C are "mutable"(Their content can be change)
message[5] = '/0'


The above "truncate" the string, @ position 5, so that its content now are only Hello


The size of the array and the remaining character are unchanged


It still technically contains ***Hello\0World!\


You can also restore the entire string:
message[5] = '';


printing string:


char name [] = "chris";
printf("Hello, %s", name);
What happen when a string is not properly null-terminated?
char message [] = " Hello World";
message[12] = '~' ;

possibly a segmentation fault, memory corruption
you can also create a dynamic string

int n = 100
char name = (char) malloc((n + 1) * sizeof(char));
// the plus one is oto accomodate the null terminating character
// probelm: we have a string, but how do we get: charcter into it ?
  name[0] = 'C';
  name[1] = 'h';
  name[2] = 'r';
String assignment


You can place the contents of once string into another using strcpy ( string copy)
// "copy" a stirng
strcpy(name,"Chris Bourke");
// now name contain "Chris Bourke"


strcpy copies the second string( called the "src") into the first string, called the " destination "


Exercise

* strcy only copues one string into another
* what if we want to create a brand new, entirely different copy( contaitning the same content of the strin g)

      /**
       * This function taks a string s and creates a new deep copy
       * *of it, returning the new copy.
       */

       char* deepStringCopy(char * s){

         / get the size of the string
          int n = strlen(s);
          // create a new string array +1 to aommodate the null terminator /0
          char *copy = (char*) malloc(n * sizeof(char));
          // copy the actual content
          strcpy(copy,s);
          return copy;

       }
Other convention function


strcpy copies entire string
strncopy part of a string
the extra *** n*** is reference to a third character, taht specifies a mac number of bytes to copy

    char fullName[] = "Chrisopher";
    cahr name [6] ;

    // this would be dangerous:
    strcp(name,fullName);

    strncpy(name, fullName,5);// copy "Chris"
    name[5] = "/0";
    // now name is properly null-terminated string
String Concatenation
strcpy copy a string, you can also " concatenate a string using strcat"
concatenation L appending one string to the end of another string
cahr fullName[100]; // big enough
char firstName ="Christopher";
char middle Init =
"M."

similarly, you have strncat

String processing


String represrnt data that mauy need to be processed
common to deal with CSV(comma separate value) or similar formatted data
std lib fiunction can help, but processing require designing algorithm

more convention function


ctype.h lib provide several other "check" funciton L isalpha(char c), isdigit(char c), islower(), isupper(), isspace()

String formatted


IN c : format string using printf using %c as a place holder
you can also print a result to a string
use sprintf to "print" to a string
usage: same as printf, but there is a new 1st argument

  chars[100]; // this can be a waste of unsage space . use strlen to determine the size of char to save data
  int x = 10;
  double pi = 3.1414;
  char name[] = "Chris";

  //to print to a std output
  printf("Hello, %s, You have a value of %d, and pi is %3f\n");

  // to print to the string s instead:
  sprintf(s,"Hello,%s, You have a value of %d, and pi is %.3f\n",name,s,pi);
tokenization


string may cintain formatted data: CSVm TSV( Tab separate value)
we may want to split a string up along delimier (psace, tab,etc called tokenizationL splitting it up into individual tokens
C provides a function called strtok- 2 argumentsL the string you want to tokenize and a list of delimiter to use( generally you use one)
The first call to strtok specifies the string and delimiter, but each subsequent call ONLY specifies the delimiter( the string is left as NULL) otherwise it start over
strtok change the content of your string

  # include <string.h>

  char s[] = "chris,Bourke,UNL,Omaha,UNL";
  // strtok return a pointer to the "next" token
  char *token = strtok(s, ",");
  while(token != NULL){
    printf("token: %s \n", token);
    token = strtok(NULL, ",");
  }
  //printf("First token is %s\n",token);
  // printf("The original string is now ")

  token = strtok(NULL, "")
String comparation


In c , cannot use eqaulity operator for string
you cannot use *** == *** to compare string, using == compare memory addresses.
Instead, use a function: strcmp

Argument: a, b and @ return an interger:
something neagtive if a < b
zero if a == b
something positive if a > b


  int r = strcmp("apple", "apple"); // >> r = 0
  int r = strcmp("apple", "banana"); // >> r = -1// indorder
  int r = strcmp("banana", "apple"); // >> r = 1
  int r = strcmp("Apple", "apple"); // >> r = -1// in order
  int r = strcmp("banana", "Apple"); // >> r = OUTOF order
Exercises


Write a string function to create a deep copy of a string
Write a string function to change the string's characters to uppercase letters
Write a string function that returns a new copy of a string with all characters converted to uppercase

/**
 * This function modifies the input string to make all the
 * lower case letters to upper case.
 * It returns an error code if s is NULL
 */
int capitalization(char *s) {

  if(s == NULL) {
    return 1; //yes, there was an error
  }

  int i;
  for(i=0; i<strlen(s); i++) {
    if(islower(s[i])) {
      //its a lower case character, so change it to an upper case
      s[i] = toupper(s[i]]);
    }
  }


  return 0; //no error
}


char * newCapitalizationCopy(const char *s) {

  if(s == NULL) {
    return NULL;
  }

  char *copy = (char *) malloc(sizeof(char) * (strlen(s)+1));
  strcpy(copy, s);

  int i;
  for(i=0; i<strlen(copy); i++) {
    if(islower(copy[i])) {
      //its a lower case character, so change it to an upper case
      copy[i] = toupper(copy[i]]);
    }
  }


  return copy;
}


char * newCapitalizationCopy(const char *s) {

  if(s == NULL) {
    return NULL;
  }

  char *copy = deepStringCopy(s);
  capitalization(copy);

  return copy;
}

/**
 * This function creates a new copy of the given string where
 * every hyphen - is replaced with a with a double hyphen --
 *
 * Ex: "hello-how are you-?" => "hello--how are you--?"
 */
char * doubleHyphen(const char *s) {

  //count up the number of hyphens in the string:
  int numberOfHyphens = 0;
  int i;
  for(i=0; i<strlen(s); i++) {
    if(s[i] == '-') {
      numberOfHyphens++;
    }
  }

  char *copy = (char *)
    malloc(sizeof(char) * (strlen(s) + numberOfHyphens + 1));

  int i, j; //j will be the copy's index variable

  for(i=0; i<strlen(s); i++) {
    if(s[i] != '-') {
      copy[j] = s[i];
      j++;
    } else {
      copy[j] = '-';
      copy[j+1] = '-';
      j = j + 2;
    }
  }
  copy[j] = '\0';
  return copy;
}


Date: march 8th, 2018

File I/O


A file is unit of stored memory, usually on disk
A file can also be.. directories, buffers(std/input) are files, a "socket"
You can read r write to a file
Files may be plaintext or buneary(or plain text but not intended for human comsumption(XML,JSON,base-64 encoding, CSB files
File I/O has the following three basic steps

open the file
process the file
Close the file


File I/O in C


There is a special FILE * type(pointer) built into the std lib
you open a file using fopen()
It takes 2 arguments

Name/path of the file to open
Second: "mode" to open it in : "r" (reading, input) or "w" (writing output)


  // open afule data.txt in the current directory for reading
  FILE *f = fopen("data.txt","r");

  // open a file data.txt for writing
  FILE *f = fopen("data.txt", "w");

  // you can also use relative path
  FILE *f = fopen("../../data.txt", "r");
  // 2 file up

  // absolyte path
  FILE *f = fopen("/etc/shadow", "r");

If fopen fails, it return NULL
if you open a file for writing and it deos not exist. it will create one for you . if you have permission to create that file
if you open an existing file it will overwrite it
once you are down with a file, you should close it. file to do so will lead to file corruption
fclose() close a file; @ one argument, the file pointer that you want to close.

File output


there are many way to fo file output
simplest, use fprintf() - same formatting and behavior as printf - take one addition argument

int fprintf(FILE *stream, const char *format, ...)
FILE *stream is the file name( can be get assign to a vairble
ex:
fp = fopen ("file.txt", "w+");
fprintf(fp, "%s %s %s %d", "We", "are", "in", 2012);


File input


there are many(dangerous) ways of reading from a file
we need to limit the amount of data that is read, so that er don't overflow any "buffers" ( string where we store the data)
fgetc() this give you the file character by character
fgets() gets uop to an entire line from a file but you can limit the numebr of bytes(characters) that it read.
fgets reads an enture string from a size, *fgets(char *s, int size, FILE, *stream);

side

  // write on a file
  FILE *f = fopen("data.txt","w");

  fprintf("f,"Hello how are you");
  int i = 10;
  fprintf(f, " i as a value of %d\n",i);
  fprintf(f, "the pi in the math lib is %lf\n",M_PI);

  fclose(f);

  // read char by char in a file
  char c;
  c = fgetc(f);
  printf("the first character is %c",c);
  //>>> OUTPUT: H
  printf("the second
   character is %c",c);
  //>>> OUTPUT: e

// read letter
c = fgetc(f);
while(c != EOF){ // end of file
  printf("

}
FILE *f = fopen("data.txt","r");

//buffer to conatin a single line of data
char buffer[1000]; // should not be a static'
char *s = fgets(buffer,1000,f);

printf(" the first line is %s\n",buffer);
Binary data in C


C povide both fread for reading binary data and fwrite
size_t
fwrite(const void *restrict ptr, size_t size, size_t nitems,
FILE *restrict stream);

    int x  = 2147 billions
    printf("%d\n",x);

  FILE *f = fopen("example.txt", "r");
  fprintf("%d",x);
  fclose(f);

  FILE *g = fopen("ex.bin");

    fwrite(&x, sizeof(int),1,g);

open passwd file on csce terminal

UNIX


finger command pointing at someine

  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>

  int main( int argc, char **argv){

      // open the /etc/passwd file and
      // 2. process it line by lin e
      // 3. find the lind that starts with the login you are searching for
      // 4. once found, process the line, tokenize along colon, print each token

    char login[] = "cbourke";

    FILE *f = fopen("/etc/passwd", "r");

    //create a buffer to read each lne intoL
    char buff[1000];

    // rad each line form /etc/passwd file :
    char *s = fgets(buffer, 1000,f );
    int isFound = 0 ;

    while(s != NULL){

      // while we have notreached the ned og the file
      // compare the login to the buffer to see if the buffer
      // begin with the login you are searching for
      if(strncmp(login, buffer, strlen(login) == 0){

        //chomp out the endline character
        buffer[strlen(buffer) - 1] = '/0';
        // You have found me
        // statr processing the string

        printf("line = ");

        cahr *token = strtok(buffer, ":,");// tokenize : also ,

        while(token != NULL){
          printf("token = %s\n",token);
          token
        }
        isFound = 1;
      }
      // get next line

        s = fgets(buffer, 1000,f );
    }

    if(!isFound){
      printf("Users with login is not found ");
    }

    return 0;


  telnet
  talk
  curl
Encapsulation

Date: march 15th, 2018

Structures & object


Built in primitive type( int, double, char ) are limitting: not everything is a number or character
real world enties are made up of multiple pieces of data( number and char together )
Ex: lab10 - sorting "teams"

kept a lot of diffferent related pieces of data in different array
Every "swap" when sorting had to swap every value in every array
Its hard to "bookkeeping"'


Encapsulation:

The grouping of data
Protection of data
The gruoping of functionality that acts on that data


Encapsulation in C


C provide for : grouping of data" weak encapsulation"
C provide weak encapsulation through structure  or "struct" for short
Syntax:

/**
 * create a structure to represent a student*/
   typedef struct{
    int nuid; //better design: to set nuid to a string
              // when comparing nuid from different
              // system.
    double gpa;
    char *major;
    Date birthday;// resuse "Date" struct /
    char *firstName;
    char *lastName;
  }Student;

  typedef struct{
    int year;
    int month;
    int day;
  }Date;

typically, structure are decalred in a header file .h where all the function prototype involve/
modern COnvention: You name your structure UpperCamelCasing
use lowerCamelCasing for member vairabel
Structure can contain other structure.
Structure contain other structure: this mechanism is reffered to as "composition"

Using structure


once declared, you can use a structure like any other variable

  //decalre a student structure
  Student s;

  //once declared, you can access individual pieces
  // of data using the "dot" operator"

  s.nuid = 20185273;

  //set my first name to "Chris"
  //s.firstName = "Chris"; // this will not work
  s.firstName = (char*) malloc(6 * sizeof(char ) );
  strcpy(s.firstName,"Chris");

  s.lastName = (char*) malloc(7 * sizeof(char ) );
  strcpy(s.lastName,"Bourke");

  s.gpa = 4.0;
  s.birthday.year = 1988;
  s.birthday.month = 7;
  s.birthday.day = 9;

Factory Function


A "factory" function allows you to easily create new structure

  Student * createStudent(int nuid, char *firstName, char *lastName, double gpa, Date dateOfBirth){
    Student  *s = NULL;
    s = (Student *) malloc(sizeof(Student) * 1);

    //s.nuid = nuid;// this will not work

    *s.nuid = nuid;// this dot operator will take president
    // it has high president

    // you have to put "()"
    (*s).nuid = nuid;// this does work


    // but there is a better way
    s->nuid = nuid;// "->" this is a pointer
    s->firstName = (char *) malloc(() strlen(firstName) +1) * sizeof(char));
    strcpy(s->firstName, firstName);

    s->lastName = (char *) malloc(() strlen(lastName) +1) * sizeof(char));
    strcpy(s->lastName, lastName);
    s->gpa = gpa;
    s->birthDay.day = dateOfbirth.day;


    // we dont want to return by value
              // it is best to return by ref
              // take less memory
    return s;
  }

  main(){

    Date myBday ;
    myBDay.year = 1995;
    myBDay.day = 5;
    mybDay.month = 4;
    student *me = createStudent(20175278,"Chris","bourke", 4.0, myBDay);

    }
Summary


if you have regular old structure, use dot operator


if you have a pointer to as tructure, use the arrow operator


Structure should be pass by value and return by reference


look at figure 1a for more detail about memory allocation on structure.


void printStudent(){

	char *str = studentToString(s);
	printf("%s\n",str);
	// c up after your self
	free(str);
	return;
	//printf("%s, %s (%.08d), %.02f\n", s->lastName, s->firstName,s->nuid,s->gpa);
}


char * studentToString(const Student *s){
	char buffer[1000];

	sprintf(buffer,"%s, %s (%.08d), %.02f\n", s->lastName, s->firstName,s->nuid,s->gpa);
	//return buffer;// cannot return the buffer like this
	// when buffer run in the stack it get deleted .
	// solution : got to take advantage of the heap

	char *result = (char *) malloc( (strlen(buffer)+1) * sizeof(char) );
	strcpy(result,buffer);
	return result;
}
Arrays of structures.

Date march, 27th , 2018

int n = 10;
//if you wanted 10 integers:
int *arr = (int *) malloc(n * sizeof(int));

//if you want a roster of 10 students:
Student *roster = (Student *) malloc(n * sizeof(Student));

roster[0] = *createStudent(12345678, "Chris",
  "Bourke", 3.9, dayOfBirth);

void printRoster(const Student *roster, int size) {

  int i;
  for(i=0; i<size; i++) {
    printStudent(&roster[i]); //roster[i] is a regular structure
    //so we need to reference it to change it to a pointer
  }

}


Recursion

#include<stdio.h>
#include<stdlib.h>

int choose(int n, int k);
int chooseWithMemoization(int n, int k);
int chooseWithMemoizationRecursive(int n, int k, int **values, int **flags, int N, int K);

void printTableau(int **table, int n, int k);

int numCalls = 0;

int main(int argc, char **argv) {

  int choice = 1; //1 = slow, 2 = memoization

  if(argc > 1) {
    choice = atoi(argv[1]);
  }

  /*
    C(37, 12) = 1852482996 which can be used with an int...
    Recursive version:
      -correct answer,
      -took about 20 seconds
      -took 1,709,984,303 recursive calls
    Recursive version with memoization:
      -correct answer
      -took less than 1 microsecond
      -took 573 recursive calls
   */

  int n = 37;
  int k = 12;
  int c;
  if(choice == 1) {
    c = choose(n, k);
  } else {
    c = chooseWithMemoization(n, k);
  }
  printf("choose(%d, %d) = %d\n", n, k, c);
  printf("number of calls: %d\n", numCalls);

}

int chooseWithMemoization(int n, int k) {

  if(k < 0 || n < 0) {
    printf("invalid inputs: choose(%d, %d), quitting on you...\n", n, k);
    exit(1);
  }

  int i, j;

  /*
     setup a tableau to told values along with a tableau
     of flags to indicate if the values has been set or
     not
  */
  int **binomialValues = malloc(sizeof(int *) * (n+1));
  int **isSet = malloc(sizeof(int *) * (n+1));
  for(i=0; i<=n; i++) {
    binomialValues[i] = malloc(sizeof(int) * (k+1));
    isSet[i] = malloc(sizeof(int) * (k+1));
  }
  for(i=0; i<=n; i++) {
    for(j=0; j<=k; j++) {
      //initialize values to zero, flags to false
      binomialValues[i][j] = 0;
      isSet[i][j] = 0;
    }
  }

  //with a table, we can pre-compute our base cases in the tableau:
  for(i=0; i<=n; i++) {
    //for k = 1, C(n,k) = 1
    binomialValues[i][0] = 1;
    isSet[i][0] = 1;
    //for k = 1, C(n,k) = n
    binomialValues[i][1] = i;
    isSet[i][1] = 1;
  }

  for(i=0; i<=n; i++) {
    for(j=0; j<=k; j++) {
      //for k > n, C(n,k) = 0
      if(j > i) {
	binomialValues[i][j] = 0;
	isSet[i][j] = 1;
      }
    }
  }

  //DEBUGGIN: printTableau(binomialValues, n+1, k+1);

  //now make the recursive call...
  int val = chooseWithMemoizationRecursive(n, k, binomialValues, isSet, n, k);

  //TODO: free up memory here...

  return val;

}

chooseWithMemoizationRecursive(int n, int k, int **values, int **flags, int N, int K) {

  numCalls++;

  //if the value has already been computed, return it...
  if(flags[n][k]) {
    return values[n][k];
  } else {
    //otherwise, we're forced to compute it via recursion...
    int value = chooseWithMemoizationRecursive(n-1, k, values, flags, N, K) + chooseWithMemoizationRecursive(n-1, k-1, values, flags, N, K);
    values[n][k] = value;
    flags[n][k] = 1;
    return value;
  }

}

int choose(int n, int k) {

  numCalls++;

  if(k < 0 || n < 0) {
    printf("invalid inputs: choose(%d, %d), quitting on you...\n", n, k);
    exit(1);
  }

  if(k == 0) {
    return 1;
  } else if(k > n) {
    return 0;
  } else if (k == 1) {
    return n;
  } else {
    return (choose(n-1, k) + choose(n-1, k-1));
  }

}


void printTableau(int **table, int n, int k) {
  int i,j;
  for(i=0; i<n; i++) {
    printf("[ ");
    for(j=0; j<k; j++) {
      printf("%8d ", table[i][j]);
    }
    printf("]\n");
  }

}


	void countDown( int n){
		if(n < 0){
			printf("Error! cannot count down from a negative\n");
		}else if(n == 0){
			printf("blast off\");
		}else{
			printf("%d\n",n);
			n--;
			countDown(n-1);
		}
		return;
	}


What is recursion?// google joke on recursion // search recursion on google to see the joke


In genral, recursion is something that reference itself.


recursve function: fibonacci, gractal// divide in fraction a equilateral .


Recursion funciton: function that can call themselves


Challege: print a count down from 10 to 1with out using a loop.


Recersive Function must have:

At least one" base case"( a condition after which the recursion stop)
Each recursion call must make progress toward the base case
Corner case: must need to be handle.


Recursion is NOT a replacement for loop

because the stack does not ahve enough memory for big data:


deep an infinite recursion may result in stack overflow

test. input big number for countDown Fucntion ``


Recursion can be a good and useful thing:

divide and conquer problem approach generally use recursion
many programing language - pascal , use recursion a as control flow.


Recursive function "abuse"" the program stack by creating and destroying many stack frame
Some organiz(NASA) explitcitly forbid the use of recursion in htier system.
recurssion also �s recomputing the same values over and over .


EXMAPL: FIBONACCI.


int fibonazzi(int ){
		if(n ==0 || n==1){
			return 1;

		}
	}

compromise/ better solution
“Memoization”


We make recurisive calls if we need to
each time we compute a value, we store it in a “cache”
If the value we want is stored in the cache, we use it and avoid the recursion compromise/ better solution
Memoization means recording the results of earlier calculations so that we don’t have to repeat the calculations later. If our code depends on the results of earlier calculations, and if the same calculations are performed over-and-over again, then it makes sense to store interim results
http://rayhightower.com/blog/2014/04/12/recursion-and-memoization/


Searching and sorting

Date: 3/4/18


Processing data is a fundamental in CS
2 fundamental operation in processing data are searching and sorting
form the basis or proprocessing step of many algorithm
Large variety of algorithm have been developed.

LInear search

* given a collection of int or more, obj and a key element k we want to search through the collection to find any element that "matches" k
* Collection: hayStack, key :needle
* basic idea: simply iterate through each element in an array. and test if it match

	/**
	*This function take an arr of ints
	* and search for a given key, returning the
	* index at which it is found in, otherwise return -1; //
	* if not foudn
	*/
	void linearSearch(int *arr,int n, int key){
		int i = 0;//iteration
		for(i = 0;i <0;i++){
			if(arr[i] == key){
				//you found you needle
				// return at which the index at which it was found.
				return i;
			}
		}
		//needle was not found.
		return -1;


	}
* The above function is only good for arrs of int
* If we wanted to search `double` or `char` or anything else.
* Ultimate goal: goal is tobe lazy.

Binary search

* Suppose that the input array is sorted, how could we exploit this structure?
* Work if the array is sorted.
* EX:"Searching might be slow in non-indexed location" serch in window 7.
* You can explitof the sorted structure by checking the middle
	- cut half. check the middle. determine which half is it in.
* >> Much better than linear search.

Analysis.

* Suppose we have an arr of `n` elements
* How many comparisons does linear search require?
	- Best Case: you get lucky. making one single comparisons
	- worst Case:make `n` comparison. all don't find it at all
* Binary Search:
	- result: only take log_2(n) comparison in average and worst case.
	- log_2(n) ---> n ( exponential difference between the 2)

Perspective.

* Supppose, We have database 10^12( 1 trillion element)
	- if unsorted, we have to use linear searching: 5 * 10^11, 5 billion comparison are needed to sarch for particular element.
	- if it is sorted, then we only need. approx log_2 10^12 <= 40
* Another perspective, suppose that we "double the size" of an array to be searched
	- Linear search:
		- doubling the input size double the number of comparison. ( because it is linear)
	- Binary searching:n -> 2n : log_2(n) comp -> log(2n) = log_2(n) + log_2(2)
		- Doubling the input size only requires one more comparison. log_2(2) = 1


Sorting

Selection sort

* Basic idea: Search through the arr and find the minimal element. and swap with the first element.
	- repeat the next smallest then swap with the 2nd smallest.
	- In genral, the 1st
* Analysis: How bad is selection?
	- How many comparison does selection sort make?  n^2^ sorting algorithm
	- Quadratic sorting algorithm
* bad.

void selectionSort(int *a, int size) {
  int i, j, min_index;
  for(i=0; i<size-1; i++) {
  	min_index = i;
  for(j=i+1; j<size; j++) {
  	if(a[min_index] > a[j]) {
    	min_index = j;
 	}
  }
  //swap
    int t = a[i];
    a[i] = a[min_index];
    a[min_index] = t;
  }
}
Quick sort

* Basic idea:
	- Divide and conquer strategy
	- choose a `pivot` element.
	- Quick sort is an alog_2(n) sorting algorithm in general.
* cut in half in each time. choose a pivot. go through an array select an min and max.
* Consider: doubling the unput size.
	- selection sort: n^2
	- Quick sort: n -> 2n ; 2nlog(2n)= 2n[log(n) + log(2)] = 2n[log(n) + 1]
		- Roughly double the run time.

Searching & sorting in practice

* In practice, you don't "roll your own" searching/sorting algorithm.
* Instead, you use the standard library function.
* ***BUT***: We Don't want to implement different function for each type of vairable
* We want only one function that can sort any type of array.
	- Generic sorting algorithm. input  r -> sorted arr. It will go through a comparator .
* A `comparator` is a function that takes 2 generic elements, a and b and return
	- something negative if `a<b`
	- zero if `a==b`
	- something positive if `a>b`

Comparator fnction

* In C, `comparator` function has the following signatature.
	- `int cmp(const void *a, const void *b)`
		- const mean we don't change it
		- `void *` is a generic void pointer that can point to anytype of variable
* Standard patern for implementing comparators:
	1. Cast the pointer(s) to particular type of data
	2. Use the state of the element/ obj or struture to det the proper order
	3. return a valid int value that express the ordered
* Best Pratice:
	- Use Descriptive function name!
	- Be explicit in your comparision
	- Avoid "trick"
	- Reuse.

* Example:
	* Write a comparator to order int in non-decreasring ordered
	* Write a comparator to order int in non-increasring ordered
	* Write a comparator to order `Student` structure by NUID,GPA, by lastname and first name

/*
 *THe comparator functon orders int in
 * non-decreasing orders*
 */

 int cmpIntAsc(const void *a, const void *b){
		const int *x = (const int*) a;
		const int *y = (const int*) b;

		if(*x < *y){
			return -1;
		}else if(*x > *y){
			return 1;
		}else{
			return 0;
		}
 }

 /*
  * This comparator function orders int in
  * non-increasing orders(
	*/

	int cmpIntDesc(const void *a, const void *b){

		// any of these line would work the same way.
		 //return cmpIntAsc(a,b) * -1;
		 //return -cmpIntAsc(a,b);
		 return cmpIntAsc(b,a);
	}

/*
 * This comparator function compares Student Structures
 * by name: last name then first name.
 */

 int cmpStudentByName(const void *a, const void *b){
	 const Student *x = (const Student *)a;
	 const Student *y = (const Student *)b;
	 int r = strcmp(x->lastname,y->lastname)

	 if (r == 0){// if last name match Ex: Nguyen and Nguyen then check first name
		 return strcmp(x->firstName, y->firstName);
	 }else{
		 return r;
	 }
 }

 /*
  * This comparator function compares Student Structures
  * by GPA.
  */

  int cmpStudentByGPA(const void *a, const void *b){
 	 const Student *x = (const Student *)a;
 	 const Student *y = (const Student *)b;

	 if(x->gpa < y->gpa){
		 return -1;
	 }else if(x->gpa > y->gpa){
		 return 1;// out of order. then it will swap.
	 }else{
		 return 0;
	 }
  }

	/*
	 * This comparator function compares Student Structures
	 * by NUID.
	 */

	 int cmpStudentByNUID(const void *a, const void *b){
		const Student *x = (const Student *)a;
		const Student *y = (const Student *)b;

		if(x->nuid < y->nuid){
			return -1;
		}else if(x->nuid > y->nuid){
			return 1;// out of order. then it will swap.
		}else{
			return 0;
		}
	 }


Searching & Sorting


Processing data is a fundamental operation in Computer Science
Two fundamental operations in processing data are searching and sorting
Form the basis or preprocessing step of many algorithms
Large variety of algorithms have been developed

Linear Search


Given a collection of integers or more generally, objects and a key element $k$ we want to search through the collection to find any element that "matches" $k$

Collection: haystack, key: needle
Collection: an array, key: an element that "equals" an element in the array
Basic Idea: simply iterate through each element in the array and test if it matches the key if so, we stop and say "we found it", otherwise if we get to the end and do not find an element, "not found"

/**
 * This function takes an array of integers
 * and searches it for the given key, returning
 * the index at which it found it, or -1 if no
 * such element exists.
 */
int linearSearch(int *arr, int n, int key) {

  int i;
  for(i=0; i<n; i++) {
    if(arr[i] == key) {
      //you found your needle...
      //return the index at which it was found
      return i;
    }
  }
  //the needle was not found
  return -1;

}

The above function is only good for arrays of integers
If we wanted to search double or char or anything else, Student etc. then we would cut-paste-adapt
Ultimately: goal is to be lazy; we'll want one "generic" solution to solve this problem that will work with any type of variable

Binary Search


Suppose that the input array is sorted, how could we exploit this structure?
You can exploit the sorted structure by checking the middle element:

Either you've found it (end the search)
Or you know that it lies in the left half
Or you know it lies in the right half


Each iteration cuts the array size roughly in half
You can do this recursively (or better yet) using a while loop
Much better than linear search

Analysis


Suppose we have an array of $n$ elements
How many comparisons does linear search require?

Best case scenario: you get lucky and immediately find the element, making one single comparison
Worst Case: you make $n$ comparisons (you get unlucky and find the element at the last place, or you don't find it at all)
Average case scenario: $\approx \frac{n}{2}$


Binary Search:

Derivation: white board
Result: only takes $\log_2{(n)}$ comparisons in the average and worst case


Perspective


Suppose we have a database of $10^{12}$ (1 trillion elements)

If unsorted, we have to use linear search:
$$\approx 5 \times 10^{11}$$
500 billion comparisons are needed to search for a particular element
If it is sorted, then we only need
$$\approx \log_2{10^{12}} \leq 40$$


Another perspective: suppose that we "double" the size of an array to be searched

Linear Search: how many more comparisons are we going to do?
Doubling the input size, doubles the number of comparisons
Binary Search: doubling the input size only requires one more comparison


Sorting

Selection Sort


Basic Idea: search through the array and find the minimal element and swap it with the first element

Repeat finding the next smallest element and swap it with the second, third, fourth, etc.
In general, in the $i$ -th iteration the first $i-1$ elements are sorted; we'll find the smallest element among the elements $a_i$ through $a_{n-1}$ and swap it with $a_i$


Analysis: How bad is selection sort?

How many comparisons does selection sort make on an array of size $n$?
Selection is an $n^2$ sorting algorithm
Quadratic sorting algorithm
In practice: how bad is $n^2$

Doubling the input size means that it quadruples in the number of operations; 4 times slower
Even for "moderately large" data sets, $n^2$ is not feasible


Quick Sort


Basic Idea:


Divide and conquer strategy


Choose a pivot element


Quick Sort is an $n\log_2{(n)}$, it makes about that many comparisons to sort an array of size $n$


Consider doubling the input size:

Selection sort: $n^2$ quadruples the running time (four times as slow)
Quick Sort: $n \rightarrow 2n$
Roughly, it doubles the run time


Consider sorting large arrays $10^{12}$
* $10^{12}\times 10^{12}$ (1 septillion) operations for selection sort
* $10^{12} \log{(10^{12})} &lt; 40 * 10^{12}$ for quicksort


Searching & Sorting in Practice


In practice, you don't "roll your own" searching/sorting algorithms
Instead, you use the standard library functions
BUT: we don't want dozens of different functions one for each type of variable or criteria that we want to sort with respect to
Instead: we want ONE generic solution that can sort any type of variable by any criteria
We want one sorting function to sort them all
Solution: we're write a generic sorting function that takes a comparator

A Comparator is a function that takes two generic elements, $a, b$ and returns

something negative if $a &lt; b$

zero if $a = b$

something positive if $a &gt; b$


Comparator Functions


In C, a comparator function has the following signature:
int cmp(const void *a, const void *b)

const means we don't change it
void * is a generic void pointer that can point to any type of variable


Standard pattern for implementing comparators:

Cast the pointer(s) to a particular type of data
Use the state of the elements/objects or structure to determine the proper order
Return a valid integer value that expresses the order


Best practices:

Use descriptive function names!
Be explicit in your comparisons
Avoid "tricks"
Reuse comparator functionality when possible


Examples:
* Write a comparator to order integers in non-decreasing order
* Write a comparator to order integers in non-increasing order
* Write a comparator to order Student structures by NUID
* Write a comparator to order Student structures by GPA
* Write a comparator to order Student structures by last name/first name


/**
 * This comparator function orders integers in
 * non-decreasing order
 */
int cmpIntAsc(const void *a, const void *b) {
  const int *x = (const int *)a;
  const int *y = (const int *)b;
  if(*x < *y) {
    return -1;
  } else if(*x > *y) {
    return 1;
  } else {
    return 0;
  }
}

/**
 * This comparator function orders integers in
 * non-increasing order
 */
int cmpIntDesc(const void *a, const void *b) {

  return cmpIntAsc(b, a);

}

/**
 * This comparator compares student structures
 * by name: last name then first name
 */
int cmpStudentByName(const void *a, const void *b) {

  const Student *x = (const Student *)a;
  const Student *y = (const Student *)b;

  int r = strcmp(x->lastName, y->lastName);
  if(r == 0) {
    return strcmp(x->firstName, y->firstName);
  } else {
    return r;
  }


}


/**
 * This comparator compares student structures
 * by gpa
 */
int cmpStudentByGPA(const void *a, const void *b) {

  const Student *x = (const Student *)a;
  const Student *y = (const Student *)b;

  if(x->gpa < y->gpa) {
    return -1;
  } else if(x->gpa > y->gpa) {
    return 1;
  } else {
    return 0;
  }

}

/**
 * This comparator compares student structures
 * by nuid
 */
int cmpStudentByNUID(const void *a, const void *b) {

  const Student *x = (const Student *)a;
  const Student *y = (const Student *)b;

  if(x->nuid < y->nuid) {
    return -1;
  } else if(x->nuid > y->nuid) {
    return 1;
  } else {
    return 0;
  }

}
Searching & Sorting


The standard C library provides a function:

void qsort(void *base,
           size_t nel,
           size_t size,
           int (*compar)(const void *, const void *));

base is the array of elements to be sorted (also note: it is not const)
nel is the number of elements in the array
size is the number of bytes each element takes
compar - the comparator function you want to use to order elements

Function Pointers


A pointer refers to a memory location
Guess what is stored in memory? variables, arrays, data,
Program and a program's code are stored in memory
It makes sense that we can create pointers to memory locations that contain functions!
Function pointers
Function pointers allow us to "pass" a function to another function
These are known as "callback" functions

//create a pointer called ptrToFunc that can point to a
//function that returns an integer and takes three arguments:
//(int, double, char)

int (*ptrToFunc)(int, double, char) = NULL;

//declare a pointer that can point to math's sqrt function
double (*ptrToSqrt)(double) = NULL;

//let's make ptrToSqrt point to the sqrt function
ptrToSqrt = sqrt;

//you can call a function via its pointer:
double x = ptrToSqrt(2.0);

//careful: you can reassign standard library functions:
sqrt = sin;
double y = sqrt(3.14159); //0
//don't do this
Using function poiners with qsort

int i;
int n = 10;
int arr[] = {5, 9, 3, 1, 0, 10, 2, 4, 3, 12};

qsort(arr, n, sizeof(int), cmpIntAsc);

for(i=0; i<n; i++) {
  printf("%d ", arr[i]);
}
printf("\n");

//decending order instead:

qsort(arr, 10, sizeof(int), cmpIntDesc);

for(i=0; i<n; i++) {
  printf("%d ", arr[i]);
}
printf("\n");


int n = 10; //10 students
Student *roster = ...
qsort(roster, n, sizeof(Student), cmpStudentByNUID);

Searching: search.h contains linear search functions, lfind, lsearch
Standard library:

void * bsearch(const void *key,
               const void *base,
               size_t nel,
               size_t size,
               int (*compar) (const void *, const void *));

returns a pointer to the element that "matches" the key (an element such that the comparator returns 0)
returns NULL if no such element
It assumes that the array is sorted in the same order as defined by compar


Graphic user interface and Event-based programing


up to now: sequencial programming , CLI(Command line interface_
Most (mordern) HCI(Human Computer Interaction) is done  thourgh a GUI
Thin client: browserm cross-platform.
Thick client: Full program compiled for a particular system.
Basically, what happen when an event occur.(Ex: mouse-click)

brief history


1973 XEROx
1983 apple's lisa
1985 Window 1.0
1986 Macintosh

Frame work

* C: GTK
* C++:GTK++,Qt,wxWidget,..
* Java: AWT,swing
* Swift( create to replace objective C)

** GNU is not unix ( recursive)
** PHP ; PHP: hypertext preprocessor
GUI component

1. Windowing system. ( not mifcrosoft window)
	* handle low-level functionality: hardware interaction(keyboard, mouse)
	* graphic rendering
2. WIndowing manager.
	* handle interation of app, window and widget.
	* control the flow of app.
	* an event is an action that init out side the scope of program.
3. Widgets.( generiv GUI element)
	* EX:
		* Buttons, slider, header, label, text box, drop down menus
		* check box, window, pop-up prompt.

Event-base programing

* User-centric: many way to accomplish same thing
*	UX: User Experiece: good user interface will provide good feedback,good/instruction/direction to human.
* modal behavior: at any point in the program, some subset of actions may be prevent or the user mnay be a  ble to see a small set of them
* Asuynchronicity: User interface should not "block" a program, with a  Asuynchronicity program, you have the capability of continuing your interaction

Event

*	Event are asynchronous: there maybe thousand per Second
	* Click, Hover, Drag and drop, keyboard event.

* Event registration: with a particular event add a particuylar widget you can register.
	* usually done via a call back.

implementing GUIs

1. You need a way to create Widgets
2. specify a layout a Widgets
3. register event.

	ssh -Y datduyn@cse.unl.edu
	run program
	./gtk_keypad.
Function pointer

funcPtr.c

void runFunction(double (*f)(double) ){
    double result = 2.0;
    printf("That 's %lf",result);
}
int main(){

    double (*ptr)(double) = NULL;

    //make it point to sqrt
    ptr = sqrt;
    ptr = sin;
    ptr pow;// compiler warning

    double (*ptrB)(double)(double) = NULL;
    ptrB = pow;

    double x =2.0;
    ptr = sqrt;
    double y = ptr(x);// y is sqrt(2.0)

    prt = sin;
    y = ptr(x);

    // point main
    int (*ptrMain)(int );
    ptr = main;

    runFunction(sprt);
    runFunction(sin);
    return 0;
}
Databases


Data representation:

CSV:
XML
JSON
each one has each stength and weaknesses
They still represent file. and fiel I/O is bad for file Processing
only one program can access the file at a time.


Solution: RDBMS(Relation databas management system)

- Data stored in table
- table have row and reccord
- table have column( individual each pieces of data for each record)
- RDBSes provides structure, means to enforce data integrity(constraint), multi-user capability
	- Databases system:
	- maria DB(FOSS)
	- mysql(free beer)
	- MSsql(few thousand)

ACID

- RDBMS provide data manipulation through transactions
- Atomiccity: data modification are an all or nothing process
- ConsistencyL a database will alwas remain in a consistent state before and after any transcction
- Isolation: no transaction interfere with another.

CRUD

- Create, Retrieve, Update, AND destroy
- SQL = structured Query Language


API ( Application program interface)

Databases Structure.

- Tables have rows and columns
- tables may(should) have primary keysl promarykey uniquely identify
-
No results found