CS 137 Fall 2012 Course Notes

15 Pages
101 Views

Department
Computer Science
Course Code
CS 137
Professor
Andrew Morton

This preview shows pages 1,2,3. Sign up to view the full 15 pages of the document.
Description
CS 137 - Programming Principles Kevin Carruthers Fall 2012 Outline We will be covering 1. Basic C programming concepts ▯ Variables ▯ Integers, chars, expression evaluation ▯ Conditionals ▯ Loops (do, do while, for) 2. Functions, parameters, recursion 3. Arrays and pointers 4. Structures 5. Sorting, searching, time and space complexity Absolute Basics // import standard input/output library #include // main function returns and integer and takes no (void) parameters int main(void) { // print formatted "Hello, World!" printf("Hello, World!"); // returns 0, ie successful completion 1 return 0; } Inputs #include int main(void) { // declare variables int a,b,r; // take two integers as input, assign them to a and b. %d is for integers scanf("%d,%d",&a,&b); // so long as b is non-zero... while(b) { // r is the remainder of a divided by b r = a % b; a = b; b = r; } printf("%d\n",a); return 0; } Integer Data Types Table 1: Types of integers and their sizes and ranges. Type Size Range 8 unsigned char 1 byte [0;2 ▯ 1] char 1 byte [▯28▯1;28▯1] unsigned short 2 bytes [0;216▯ 1] 16▯1 16 short 2 bytes [▯2 ;2 ] unsigned int 4 bytes [0;232▯ 1] int 4 bytes [▯232▯1;232▯1] 64▯1 64▯1 long 4/8 bytes [▯2 ;2 2 Logic False is denoted by zero, true is denoted by non-zero (traditionally one). The logical operators are ▯ NOT ( ! ) ▯ OR ( jj ) ▯ AND ( && ) DeMorgan’s Identities ▯ !(P && Q) == !P || !Q ▯ !(P || Q) == !P && !Q Loops ▯ while(expression) statement // executes at least 0 times ▯ do statement while(expression); // executes at least 1 time Functions // create function gcd which can be called with gcd(x,y) and returns an integer answer int gcd(int a, int b) { int r = a % b; while(r) { a = b; b = r; r = a % b; } return b; } int main() { // print the result of a function call with arguments 806 and 338 printf("%d\n",gcd(806,338)); 3 return 0; } // include boolean library (defines boolean type with true and false) #include #include bool isLeap(int year) { if(year%400 == 0) return true; else if(year%100 == 0) return false; else if(year%4 == 0) return true; else return false; } bool isPrime(int num) { int divisor = 2; if(num <= 1) return false; // expressions can be evaluated within loop tests while(num/divisor >= divisor) { if(num % divisor == 0) { return false; divisor++ } return true; } Asserts // include assert library #include bool leap(int year) { // if year <= 1582, terminates with error assert(year > 1582); ... } 4 Seperate Compilation If you have multiple ▯les (ie functions in one ▯le, main program in another), declare the function in the main ▯le as void func(int number); and compile as % gcc -o output functions.c main.c Header Files You can also declare the functions in a header ▯le as #ifndef HEADER_H #define HEADER_H void func(int number); #endif and in your main ▯le #include Recursion int gcd(int a, int b) { if(!b) return a; // call itself with updated/new arguments else return gcd(b,a%b); } Locality void func(int a) { // changes the value of a... within func a = 42; } int main() { int a = 3; func(a); // a has not been changed in this scope 5 printf("%d\n",a); return 0; } Arrays int a[3] = {10,30,50}; creates an array, we can access the elements by a[2]; which returns 50. Very useful is // beginning with i = 0, iterate n times // n is the number of elements in a // i is a count of how many times we’ve gone through the loop for(int i = 0; i < sizeof(a)/sizeof(a[0]); i++) { // add the current element to the sum sum += a[i]; } Note that a for loop is de▯ned as for(initialization; condition; increment) { statement } where any one or more parameters may be removed. Floating-Point Numbers double x = 4/5; // 0.0 double x = 4.0/5; // 0.8 double x = (double)4/5; // 0.8 Polynomials Polynomials are often represented as arrays, ie 3 + 4x ▯ x is represented as double f[] = {3,4,-1}; and must be evaluated with double eval(double f, int n, double x); 6 Example (Horner’s Method) #include double horner(double f[], int n, double x) { double h = f[n-1]; // declaring a variable within a loop statement requires compilation with c99 standards for(int i = n-2; i >= 0; i--) { h = h * x + f[i]; } return h; } int main() { double f[] = {2,9,4,3}; // we could replace the 4 by the sizeof() stuff we did earlier printf("%g\n", horner (f,4,0)); printf("%g\n", horner (f,4,1)); printf("%g\n", horner (f,4,2)); return 0; } Math #include has stu▯ like sin, cos, tan, exp, log, Mpi as a constant)... #include #include // let’s find the root of this function (if it’s continuous on [a,b]) double f(double x) { return x-cos(x); } double bisect(double a, double b, double epsilon, int maxIters) { double m; for(int i = 0; i < maxIters; i++) { // find the mindpoint 7 m = (a+b)/2; // fabs is from the math library, it return the absolute value of a variable if(fabs(f(m)) <= epsilon) return m; // figure out which half has the answer within it if(f(m) > 0) { b = m; } else { a = m; } } return m; } int main() { printf("%g\n", bisect(-10,10,0.001,1000000); return 0; } Structs // defines a variable containing two other variables struct tod { int hours; int minutes; }; int main() { // declare a struct like this struct tod now = {13,46}; struct tod later; // access member variables later.hours = now.hours + 3; later.minutes = now.minutes; return 0; } Structs can be pass
More Less
Unlock Document

Only pages 1,2,3 are available for preview. Some parts have been intentionally blurred.

Unlock Document
You're Reading a Preview

Unlock to view full version

Unlock Document

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit