VariablesEdit
NamingEdit
 Can a variable name start with a number?
 Can a variable name start with a typographical symbol(e.g. #, *, _)?
 Give an example of a C variable name that would not work. Why doesn't it work?
 No, the name of a variable must begin with a letter (lowercase or uppercase), or an underscore.
 Only the underscore can be used.
 for example, #nm*rt is not allowed because # and * are not the valid characters for the name of a variable.
#include<stdio.h> main() { int a,b,c,max; clrscr(); printf("\nenter three numbers "); scanf("%d %d %d",&a,&b,&c); max=a; if(max<b) max=b; if(max<c) max=c; printf("\nlargest=%d \n",max); getch(); }
Data TypesEdit
 List at least three data types in C
 On your computer, how much memory does each require?
 Which ones can be used in place of another? Why?
 Are there any limitations on these uses?
 If so, what are they?
 Is it necessary to do anything special to use the alternative?
 Can the name we use for a data type (e.g. 'int', 'float') be used as a variable?
 3 data types : long int, short int,float.
 On my computer :
 long int : 4 byte
 short int : 2 bytes
 float : 4 bytes
 we can not use 'int' or 'float' as a variable's name.
AssignmentEdit
 How would you assign the value 3.14 to a variable called pi?
 Is it possible to assign an int to a double?
 Is the reverse possible?
 The standard way of assigning 3.14 to pi is:
double pi; pi=3.14;

 Since pi is a constant, good programming convention dictates to make it unchangeable during runtime. Extra credit if you use one of the following two lines:
const float pi = 3.14; #define pi 3.14
 Yes, for example :
int a=67; double b; b=a;
 Yes, but a cast is necessary and the double is truncated:
double a=89; int b; b=(int) a;
ReferencingEdit
 A common mistake for new students is reversing the assignment statement. Suppose you want to assign the value stored in the variable "pi" to another variable, say "pi2":
 What is the correct statement?
 What is the reverse? Is this a valid C statement (even if it gives incorrect results)?
 What if you wanted to assign a constant value (like 3.1415) to "pi2":
 a. What would the correct statement look like?
 b. Would the reverse be a valid or invalid C statement?
pi2 = pi;
 The reverse,
pi = pi2;
is a valid C statement ifpi
is not a constant.  a.
pi2 = 3.1415;
b. The reverse:3.1415 = pi2;
is not valid since it is impossible to assign a value to a literal.
Simple I/OEdit
InputEdit
 scanf() is a very powerful function. Describe some features that make it so versatile.
 Write the scanf() function call that will read into the variable "var":
 a float
 an int
 a double
scanf("%f",&var); //read float into var scanf("%d",&var); //read int into var scanf("%lf", &var); //read double into var
String manipulationEdit
1. Write a program that prompts the user for a string, and prints its reverse.
One possible solution could be:
#include <stdio.h> #include <string.h> int main(void) { char s[81]; // A string of upto 80 chars + '\0' int i; puts("Please write a string: "); fgets(s, 81, stdin); puts("Your sentence in reverse: "); for (i= strlen(s)1; i >= 0; i) { if (s[i] == '\n') continue; // don't write newline else putchar(s[i]); } putchar('\n'); return 0; }
2. Write a program that prompts the user for a sentence, and prints each word on its own line.
One possible solution could be:
#include <stdio.h> int main(void) { char s[81], word[81]; int n= 0, idx= 0; puts("Please write a sentence:"); fgets(s, 81, stdin); /* %s matches a sequence of nonwhitespace character, which is a * fair definition of "word" in this context. * %n matches nothing, but stores the number of characters that have * been processed. i.e. if s is "Hello, World!", then word and n * will be "Hello," and 6 respectively in the first iteration. In * the second iteration they will be "World!" and 7 (6 chars + * the space in front of the word). */ while ( sscanf(&s[idx], "%s%n", word, &n) > 0 ) { idx += n; puts(word); } return 0; }
LoopsEdit
1. Write a function that outputs a right isosceles triangle of height and width n, so n = 3 would look like
* ** ***
One possible solution:
void isosceles(int n) { int x,y; for (y= 0; y < n; y++) { for (x= 0; x <= y; x++) putchar('*'); putchar('\n'); } }
2. Write a function that outputs a sideways triangle of height 2n1 and width n, so the output for n = 4 would be:
* ** *** **** *** ** *
One possible solution:
void sideways(int n) { int x,y; for (y= 0; y < n; y++) { for (x= 0; x <= y; x++) putchar('*'); putchar('\n'); } for (y= n1; y > 0; y) { for (x= 0; x < y; x++) putchar('*'); putchar('\n'); } }
or like this (all math)
void sideways(int n) { int i=0,j=0; for(i=1;i<2*n;i++){ for(j=1;j<=(n(abs(ni)));j++){ printf("*"); } printf("\n"); } }
3. Write a function that outputs a rightsideup triangle of height n and width 2n1; the output for n = 6 would be:
* *** ***** ******* ********* ***********
One possible solution:
void right_side_up(int n) { int x,y; for (y= 1; y <= n; y++) { for (x= 0; x < ny; x++) putchar(' '); for (x= (ny); x < (ny)+(2*y1); x++) putchar('*'); putchar('\n'); } }
Program FlowEdit
1. Build a program where control passes from main to four different functions with 4 calls.
2. Now make a while loop in main with the function calls inside it. Ask for input at the beginning of the loop. End the while loop if the user hits Q
3. Next add conditionals to call the functions when the user enters numbers, so 1 goes to function1, 2 goes to function 2, etc.
4. Have function 1 call function a, which calls function b, which calls function c
5. Draw out a diagram of program flow, with arrows to indicate where control goes
FunctionsEdit
1. Write a function to check if an integer is negative; the declaration should look like bool is_positive(int i);
2. Write a function to raise a floating point number to an integer power, so for example to when you use it
float a = raise_to_power(2, 3); //a gets 8
float b = raise_to_power(9, 2); //b gets 81
float raise_to_power(float f, int power); //make this your declaration
MathEdit
1. Write a function to calculate if a number is prime. Return 1 if it is prime and 0 if it is not a prime.
One possible solution using a naïve primality test:
// to compile: gcc Wall prime.c lm o prime #include <math.h> // for the square root function sqrt() #include <stdio.h> int is_prime(int n); int main() { printf("Write an integer: "); int var; scanf("%d", &var); if (is_prime(var)==1) { printf("A prime\n"); } else { printf("Not a prime\n"); } return 1; } int is_prime(int n) { int x; int sq= sqrt(n)+1; // Checking the trivial cases first if ( n < 2 ) return 0; if ( n == 2  n == 3 ) return 1; // Checking if n is divisible by 2 or odd numbers between 3 and the // square root of n. if ( n % 2 == 0 ) return 0; for (x= 3; x <= sq; x += 2) { if ( n % x == 0 ) return 0; } return 1; }
2. Write a function to determine the number of prime numbers below n.
3. Write a function to find the square root by using Newton's method.
4. Write functions to evaluate the trigonometric functions:
5. Try to write a random number generator.
6. Write a function to determine the prime number between 2 and 100:
RecursionEdit
Merge sortEdit
1. Write a C program to generate a random integer array with a given length n , and sort it recursively using the Merge sort algorithm.
 The merge sort algorithm is a recursive algorithm .
 sorting a one element array is easy.
 sorting two oneelement arrays, requires the merge operation. The merge operation looks at two sorted arrays as lists, and compares the head of the list , and which ever head is smaller, this element is put on the sorted list and the head of that list is ticked off, so the next element becomes the head of that list. This is done until one of the lists is exhausted, and the other list is then copied onto the end of the sorted list.
 the recursion occurs, because merging two oneelement arrays produces one twoelement sorted array, which can be merged with another twoelement sorted array produced the same way. This produces a sorted 4 element array, and the same applies for another 4 element sorted array.
 so the basic merge sort, is to check the size of list to be sorted, and if it is greater than one, divide the array into two, and call merge sort again on the two halves. After wards, merge the two halves in a temporary space of equal size, and then copy back the final sorted array onto the original array.
One possible solution , after reading online descriptions of recursive merge sort, e.g. Dasgupta :
// to compile: gcc Wall rmergesort.c lm o rmergesort /* ============================================================================ Name : rmergesort.c Author : Anon Version : 0.1 Copyright : (C)2013 under CCBySA 3.0 License Description : Recursive Merge Sort, Ansistyle ============================================================================ */ #include <stdio.h> #include <stdlib.h> #include <string.h> //const int MAX = 200; const int MAX = 20000000; int *b; int printOff = 0; // this debugging print out of the array helps to show // what is going on. void printArray(char* label, int* a, int sz) { int h = sz/ 2; int i; if (printOff) return; printf("\n%s:\n", label); for (i = 0; i < h; ++i ) { printf("%d%c", a[i], // add in a newline every 20 numbers ( ( i != 0 && i % 20 == 0 )? '\n': ' ' ) ); } printf("  "); for (;i < sz; ++i) { printf("%d%c", a[i], ( ( i != 0 && i % 20 == 0 )? '\n': ' ' ) ); } putchar('\n'); } void mergesort(int* a, int m ) { printArray("BEFORE", a, m); if (m > 2) { // if greater than 2 elements, then recursive mergesort(a, m / 2); mergesort(a + m / 2, m  m / 2); } else if (m == 2 && a[0] > a[1]) { // if exactly 2 elements and need swapping, swap int t = a[1]; a[1] = a[0]; a[0] = t; goto end; } // 1 or greater than 2 elements which have been recursively sorted // divide the array into a left and right array // merge into the array b with index l. int n = m/2; int o = m  n; int i = 0, j = n; int l = 0; // i is left, j is right ; // l should equal m the size of the array while (i < n) { if ( j >= m) { // the right array has finished, so copy the remaining left array for(; i < n; ++i) { b[l++] = a[i]; } // the merge operation is to copy the smaller current element and // increment the index of the parent subarray. } else if( a[i] < a[j] ) { b[l++] = a[i++]; } else { b[l++] = a[j++]; } } while ( j < m) { // copy the remaining right array , if any b[l++] = a[j++]; } memcpy(a, b, sizeof(int) * l ); end: printArray("AFTER", a, m); return; } void rand_init(int* a, int n) { int i; for (i = 0; i < n; ++i ) { a[i] = rand() % MAX; } } int main(void) { puts("!!!Hello World!!!"); /* prints !!!Hello World!!! */ // int N = 20; // int N = 1000; // int N = 1000000; int N = 100000000; // still can't make a stack overflow on ubuntu,4GB, phenom printOff = 1; int *a; b = calloc( N, sizeof(int)); a = calloc( N, sizeof(int)); rand_init(a, N); mergesort(a, N); printOff = 0; printArray("LAST", a, N); free(a); free(b); return EXIT_SUCCESS; } /* Having failed to translate my concept of nonrecursive merge sort, * I tackled the easier case of recursive merge sort. * The next task is to translate the recursive version to a nonrecursive * version. This could be done by replacing calls to mergesort, with * pushes onto a stack of * tuples of ( <array start address>, <number of elements to process> ) */ /* The central idea of merging, is that two sorted lists can be * merged into one sorted list, by comparing the top of each list and * moving the lowest valued element onto the end of the new list. * The other list which has the higher valued element keeps its top * element unchanged. When a list is exhausted, copy the remaining other list * onto the end of the new list. */ /* The recursive part, is to defer any work in sorting an unsorted list, * by dividing it into two lists until there is only 1 or two elements, * and if there are two elements, sort them directly by swapping if * the first element is larger than the second element. * * After returning from a recursive call, merge the lists, which will * begin with one or two element sorted lists. The result is a sorted list * which will be returned to the parent of the recursive call, and can * be used for merging. */ /* The following is an imaginary discussion about what a programmer * might be thinking about when programming: * * Visualising recursion in terms of a Z80 assembly language, which * is similiar to most assembly languages, there is a data stack (DS) and * a call stack (CS) pointer, and each recursive call to mergesort * pushes the return address , which is the program address of the instruction * after the call , onto the stack pointed to by CS and CS is incremented, * and the address of the array start and integer which is the subarray length * onto the data stack pointed to by DS, which will be incremented twice. * * If the number of recursive , active calls exceed the allowable space for either the call stack * or the data stack, then the program will crash , or a process space protection * violation interrupt signal will be sent by the CPU, and the interrupt vector * for that signal will jump the processor's current instruction pointer to the * interrupt handling routine. */
Binary heapsEdit
2. Binary heaps :
 A binary maxheap or minheap, is an ordered structure where some nodes are guaranteed greater than other nodes, e.g. the parent vs two children. A binary heap can be stored in an array , where ,
 given a position i (the parent) , i*2 is the left child, and i*2+1 is the right child.
 ( C arrays begin at position 0, but 0 * 2 = 0, and 0 *2 + 1= 1, which is incorrect , so start the heap at position 1, or add 1 for parenttochild calculations, and subtract 1 for childtoparent calculations ).
 try to model this using with a pencil and paper, using 10 random unsorted numbers, and inserting each of them into a "heapsort" array of 10 elements.
 To insert into a heap, endadd and swapparent if higher, until parent higher.
 To delete the top of a heap, move endtotop, and deferhigherchild or siftdown , until no child is higher.
 try it on a pen and paper the numbers 10, 4, 6 ,3 ,5 , 11.
 10, 4, 6, 3, 5, 11 > 10
 4, 6,3, 5, 11 > 10, 4 : 4 is endadded, no swapparent because 4 < 10.
 6, 3, 5, 11 > 10, 4, 6 : 6 is endadded, no swapparent because 6 < 10.
 3, 5, 11 > 10, 4, 6, 3 : 3 is endadded, 3 is position 4 , divide by 2 = 2, 4 at position 2, no swapparent because 4 > 3.
 5 , 11 > 10, 4, 6, 3 , 5 : 5 is endadded , 5 is position 5, divided by 2 = 2, 4 at position 2, swapparent as 4 < 5; 5 at position 2, no swapparent because 5 < 10 at position 1.
 10 , 5, 6, 3, 4
 11 > 10, 5, 6, 3, 4, 11 : 11 is endadded, 11 is position 6, divide by 2 = 3, swap 6 with 11, 11 is position 3, swap 11 with 10, stop as no parent.
 11, 5, 10, 3, 4, 6
 11 has children 5, 10 ; 5 has children 3 and 4 ; 10 has child 6. Parent always > child.
 the answer was 11, 5, 10, 3, 4 , 6.
 EXERCISE: Now try removing each top element of 11, 5, 10, 3, 4, 6 , using endtotop and siftdown ( or swaphigherchild) to get the numbers
in descending order.
 11 leaves * , 5, 10, 3, 4, 6 > 6 , 5, 10, 3, 4 > siftdown > choose greater child 5 (2*n+0) or 10 ( 2*n+1) > is 6 > 10 ? no > swap 10 and 6 >
 10, 5, *6, 3, 4 > 4 is greatest child as no +1 child. is 6 > 4 ? yes, stop.
 10 leaves * , 5 , 6 , 3, 4 > *4, 5, 6, 3 > is left(0) or right(+1) child greater > +1 is greater; is 4 > +1 child ? no , swap
 6,5, *4, 3 > *4 has no children so stop.
 6 leaves *, 5, 4, 3 > *3, 5, 4 > +0 child is greater > is 3 > 5 ? no , so swap > 5, *3, 4 , *3 has no child so stop.
is
 5 leaves so 3, 4 > *4, 3 > +0 child greatest as no right child > is 4 > 3 ? no , so exit
 4 leaves 3 .
 3 leaves *.
 numbers extracted in descending order 11, 10, 6, 5, 4, 3.
 a priority queue allows elements to be inserted with a priority , and extracted according to priority. ( This can happen usefully, if the element has a paired structure, one part is the key, and the other part the data. Otherwise, it is just a mechanism for sorting ).
 EXERCISE: Using the above technique of insertback/challengeparent, and deletefront/lasttofront/deferhigherchild, implement either heap sort or a priority queue.
Dijsktra's algorithmEdit
Dijsktra's algorithm is a searching algorithm using a priority queue. It begins with inserting the start node with a priority value of 0. All other nodes are inserted with priority values of large N. Each node has an adjacency list of other nodes, a current distance to start node, and previous pointer to previous node used to calculate current node. Alternative to an adjacency list, is an adjacency matrix, which needs n x n boolean adjacencies.
The agorithm basically iterates over the priority queue, removing the front node, examining the adjacent nodes, and updating with a distance equal to the sum of the front nodes distance for each adjacent node , and the distance given by the adjacency information for an adjacent node.
After each node's update, the extra operation "update priority" is used on that node :
while the node's distance is less than it's parents node ( for this priority queue, parents have lesser distances than the children), the node is swapped with the parent.
After this, while the node is greater distance than one or more of its children, it is swapped with the least distant child, so the least distant child becomes parent of its greater distant sibling, and parent to the greater distant current node.
With updating the priority, the adjacent node to the current node has a back pointer changed to the current node.
The algorithm ends when the target node becomes the current node removed, and the path to the start node can be recorded in an array by following back pointers, and then doing something like a quick sort partition to reverse the order of the array , to give the shortest path to target node from the start node.
Quick sortEdit
3. Write a C program to recursively sort using the Quick sort partition exchange algorithm.
 you can use the "driver", or the random number test data from Q1. on mergesort. This is "reuse", which is encouraged in general.
 an advantage of reuse is less writing time, debugging time, testing time.
 the concept of partition exchange is that a partition element is (randomly) selected, and every thing that needs sorted is put into 3 equivalance
classes : those elements less than the partition value, the partition element, and everything above (and equal to ) the partition element.
 this can be done without allocating more space than one temporary element space for swapping two elements. e.g a temporary integer for integer data.
 However, where the partition element should be using the original array space is not known.
 This is usually implemented with putting the partition on the end of the array to be sorted, and then putting two pointers , one at the start of the array,
and one at the element next to the partition element , and repeatedly scanning the left pointer right, and the right pointer left.
 the left scan stops when an element equal to or greater than the partition is found, and the right scan stops for a smaller element than the partition value,
and these are swapped, which uses the temporary extra space.
 the left scan will always stop if it reaches the partition element , which is the last element; this means the entire array is less than partition value.
 the right scan could reach the first element, if the entire array is greater than the partition , and this needs to be tested for, else the scan doesn't stop.
 the outer loop exits when then left and right pointers cross. Testing for pointer crossing and outer loop exit
should occur before swapping, otherwise the right pointer may be swapping a lessthanpartition element previously scanned by the left pointer.
 finally, the partition element needs to be put between the left and right partitions, once the pointers cross.
 At pointer crossing, the left pointer may be stopped at the partition element's last position in the array, and the right pointer not progressed past the
element just before the last element. This happens when all the elements are less than the partition.
 if the right pointer is chosen to swap with the partition, then an incorrect state results where the last element of the left array becomes less than the partition element value.
 if the left pointer is chosen to swap with the partition, then the left array will be less than the partition, and partition will have swapped with an element with value greater than the partition or the partition itself.
 The corner case of quicksorting a 2 element outoforder array has to be examined.
 The left pointer stops on the first out of order element. The right pointer begins on the first outoforder element, but the outer loop exits because this is the leftmost element. The partition element is then swapped with the left pointer's first element, and the two elements are now in order.
 In the case of a 2 element in order array, the leftmost pointer skips the first element which is less than the partition, and stops on the partition. The right pointer begins on the first element and exits because it is the first position. The pointers have crossed so the outer loop exits. The partition swaps with itself, so the inordering is preserved.
 After doing a swap, the left pointer should be incremented and right pointer decremented, so the same positions aren't scanned again, because an endless loop can result ( possibly when the left pointer exits when the element is equal to or greater than the partition, and the right element is equal to the partition value). One implementation, Sedgewick, starts the pointers with the left pointer minus one and right pointer
the plus one the intended initial scan positions, and use the preincrement and predecrement operators e.g. ( ++i, i) .
One possible solution , can be to adapt this word sorting use of quicksort to sort integers. Otherwise , an exercise would be to rewrite nongeneric qsort functions of qsortsimp, partition, and swap for integers.
/* * qsortsimp.h * * Created on: 17/03/2013 * Author: anonymous */ #ifndef QSORTSIMP_H_ #define QSORTSIMP_H_ #include <stdlib.h> void qsortsimp( void* a, size_t elem_sz, int len, int(*cmp) (void*,void*) ); void shutdown_qsortsimp(); #endif /* QSORTSIMP_H_ */ // /* qsortsimp.c * author : anonymous */ #include "qsortsimp.h" #include<stdlib.h> #include<string.h> static void * swap_buf =0; static int bufsz = 0; void swap( void* a, int i, int j, size_t elem_sz) { if (i==j)return; if (bufsz == 0  bufsz < elem_sz) { swap_buf = realloc(swap_buf, elem_sz); bufsz=elem_sz; } memcpy( swap_buf, a+i*elem_sz, elem_sz); memcpy( a+i*elem_sz, a+j*elem_sz, elem_sz); memcpy( a+j*elem_sz, swap_buf, elem_sz); } void shutdown_qsortsimp() { if (swap_buf) { free(swap_buf); } } int partition( void* a, size_t elem_sz, int len, int (*cmp)(void*,void*) ) { int i = 1; int j = len1; void* v = a + j * elem_sz; for(;;) { while( (*cmp)(a + ++i * elem_sz , v ) < 0); while ( (*cmp)(v, a + j * elem_sz) < 0 ) if (j==0) break ; if( i>=j)break; swap(a, i, j, elem_sz); } swap( a, i, len1, elem_sz); return i; } void qsortsimp( void* a, size_t elem_sz, int len, int(*cmp) (void*,void*) ) { if ( len > 2) { int p = partition(a, elem_sz, len, cmp); qsortsimp( a, elem_sz, p, cmp); qsortsimp( a+(p+1)*elem_sz, elem_sz, len  p 1, cmp ); } } // /* Name : words_quicksort.c Author : anonymous Version : Copyright : Description : quick sort the words in moby dick in C, Ansistyle ============================================================================ */ #include <stdio.h> #include <stdlib.h> #include <ctype.h> #include <string.h> #include "qsortsimp.h" void printArray(const char* a[], int n) { int i; for(i=0; i < n; ++i) { if(i!=0 && i% 5 == 0) { printf("\n"); } if (i%1000000 ==0) { fprintf(stderr,"printed %d words\n", i); } printf("%s ", a[i]); } printf("\n"); } const int MAXCHARS=250; char ** wordlist=0; int nwords=0; int remaining_block; const size_t NWORDS_PER_BLOCK = 1000; //const char* spaces=" \t\n\r"; //inline isspace(const char ch) { // int i=0; // while(spaces[i]!='\0') { // if(spaces[i++] == ch) // return 1; // } // return 0; //} void freeMem() { int i = nwords; while(i > 0 ) { free(wordlist[i]); } free(wordlist); } static char * fname="~/Downloads/books/pg2701mobydick.txt"; void getWords() { char buffer[MAXCHARS]; FILE* f = fopen(fname,"r"); int state=0; int ch; int i; while ((ch=fgetc(f))!=EOF) { if (isalnum(ch) && state==0) { state=1; i=0; buffer[i++]=ch; } else if (isalnum(ch) && i < MAXCHARS1) { buffer[i++]=ch; } else if (state == 1) { state =0; buffer[i++]= '\0'; char* dynbuf = malloc(i); int j; for(j=0; j < i; ++j) { dynbuf[j] = buffer[j]; } i=0; if (wordlist == 0 ) { wordlist = calloc(NWORDS_PER_BLOCK, sizeof(char*)); remaining_block = NWORDS_PER_BLOCK; } else if ( remaining_block == 0) { wordlist = realloc(wordlist, (NWORDS_PER_BLOCK + nwords)* sizeof(char*)); remaining_block = NWORDS_PER_BLOCK; fprintf(stderr,"allocated block %d , nwords = %d\n", remaining_block, nwords); } wordlist[nwords++]= dynbuf; remaining_block; } } fclose(f); } void testPrintArray() { int i; for(i=0; i < nwords;++i) { printf("%s  ", wordlist[i]); } putchar('\n'); printf("stored %d words. \n",nwords); } int cmp_str_1( void* a, void *b) { int r = strcasecmp( *((char**)a),*((char**)b)); return r; } int main(int argc, char* argv[]) { if (argc > 1) { fname = argv[1]; } getWords(); testPrintArray(); qsortsimp(wordlist, sizeof(char*), nwords, &cmp_str_1); testPrintArray(); shutdown_qsortsimp(); freeMem(); puts("!!!Hello World!!!"); /* prints !!!Hello World!!! */ return EXIT_SUCCESS; }