false

Study Guides
(248,605)

Canada
(121,634)

University of Waterloo
(5,732)

Computer Science
(334)

CS 137
(4)

Andrew Morton
(3)

School

University of Waterloo
Department

Computer Science

Course Code

CS 137

Professor

Andrew Morton

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

Related notes for CS 137

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

Unlock DocumentJoin OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

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.