Aere 3610 Exam 2 review

GDB, pointers, complexity (BIG O notation), makefiles, and more.

This is the declaration of a struct with two members of integer type.

struct structname {
	int a;
	int b;
};

The output of this code:

#include <stdio.h>

int main () {
 int A = 43;
 int * ptr = &A;

 printf("%p\n", ptr);
 printf("%d\n", *ptr);
return 0;
}

ptr will print the memory address and *ptr will print 43

There are 2 things a makefile can be named.

Makefile and makefile

This gcc flag is used to compile position independent code (for when you don’t know where your code will be when it runs, like making a library).

-fPIC

This gcc flag is used to compile .o files and is not compatible with the -o flag.

-c

What does the first line do and how is it used?

OBJS = main.o util.o helper.o
program : $(OBJS)
	gcc -o program $(OBJS)

Defines a variable named “OBJS” and uses it as dependencies for program/in the compile command to link all objects into the executable

This is the format of a function pointer

<output type> (*NAME) <input type>

What is the complexity of the following code?

int count = 0;
for (int i = 0; i < n; i++) {
	for( int j = n; j > 0; j /= 2) {
		count++;
		if( j % 3 == 0)
			count +=1;
		}
	}
	count +=10;
}

O(n logn)

This is the standard that controls how decimal numbers are stored in all computers since 1985 and your favorite and least favorite part of the standard

IEEE 754, cant do equivalence check

int *p[3]; 
int(*p)([3];

are different in this way

1. declaration of an array of 3 pointers to integers

2. A pointer to an array of 3 integers

These are the 4 stages of compilation

1. Preprocessing

2. Compiling

3. Assembly

4. Linking

What is the complexity?

int count = 0;
for (int i =0; i <n; i++){
	int j =i;
	while (j<n){
		count++;
		if( j %2 == 0){
			j +=3;
		} else {
			j +=1;
		}
	}
}

O(n²)

These 3 components make up a floating point number

sign bit, exponent, and mantissa (fraction)

a[i], *(a+i), *(i+a), i[a]

are all valid methods to access this part of an array.

the ith element

int * p1,p2;

produces these variables of these types

pointer TO int (p1) AND int (p2)

Is this line that does illegal operation:

1. char * cp
2. const char *ccp;
3. ccp = cp;
4. cp = ccp;

“cp = ccp”

(ccp is a constant)

This is the formula used to estimate machine epsilon

| 3 * ( ( 4/3 ) - 1 ) - 1 |

it is the smallest # the machine can represent

Interpret why BDG is showing a seg fault:

#include <stdio.h>

int main () {
	int arr[3] = {1, 2, 3};
	int i = 5;
	printf("%d\n", arr [i]);
	return 0;
}

Accessing arr[5] is out of bounds

What is the complexity?

int count = 0;
for ( int i = 0; i < n ; i++){
	for ( int j = 0; j <= i: j++){
		int k = n;
		while (k>0){
			k/=2;
			count ++;
		}
		if (i%2 ==0){
			for (int m = 0; m<n-i; m++)[
				count++;
			}
		}
	}
	int t = i+1;
	while (t >2){
		t=/2;
		count ++;
	}
}
for (int x = 0; x<n; x++){
	for(int y = 0; y<n; y++){
		count ++;
	}
}

O(n² logn)

1111111111111011 is the 16-bit 2’s complement of this decimal number

-5

this binary number is expressed as 5 in decimal

101

the action of the following GDB command

(gdb) break main

creates a breakpoint before main function, causing the program to pause execution when main is reached.

this is the way to dereference the pointer to a struct and access a member without syntactic sugar

(*ptr).member

what is the complexity?

#include <stdio.h>

int task1(int n){
	int count = 0;
	for (int j = 0; j < n; j++){
		count = count +j;
	}
	return count;
}

int task2 (int n) {
	int total_sum = 0;
	for (int i=0; i < n; i++){
		total_sum = total_sum + task1(n);
	}
	return total_sum;
}

int main(){
	int n_value = 100;
	int result = task2(n_value);
	printf("Result for n = %d: %lld\n", n_value, result);
	return 0;
}

O(n²)

this condition arises when memory allocated on the heap is not free by your program

memory leak

this utility in this tool is used to detect many memory-related errors that are common in c and c++ programs and that can lead to crashes and unpredictable behavior

memcheck in valgrind

this data structure is used to collect members of different types that can be accessed by their names

struct

What is the complexity?

int sum=0;
for(int i=0; i <n; i++){
	sum += arr[i];

	if (i % 2 ==0) {
		sum +=5;
	} else {
		sum -=3;
	}
}

O(n)

this is the syntactic sugar for dereferencing the pointer to a structure and accessing a member

->

these are the steps for how to write code

0. Take a deep breath

1. requirements and test cases

2. write test cases

3. write algorithm

4. review algorithm and test cases

5. write comments of algorithm

6. executable c statements (line by line)

7. iterate the process

8. run all test cases

a successful compile after including the right header does not prove the program is complete, because the actual function body is stil missing until this stage succeeds

linking

This is the use of ccflags in the following makefile:

program: main.o util.o
	gcc $(CCFLAGS) -o program main.o util.o

CCFLAGS (warnings, optimizations, debug) will apply when building the program

the output of this code:

int main(void){
	int mason = 5;
	int numbers = 3;
	printf("The numbers Mason! What do they mean?! %d\n", mason + numbers);
	return 0;
}

The numbers Mason! What do they mean?! 8

void (*(*f[]) () ) ();

Declares this

array of unspecified size of pointers to functions that return pointers to functions of return type void

What is the complexity?

\begin{lstlisting}
int n = 0; /*loop variable*/
for (n = 0; n <argc; n++){ /*loop through all command-line arguments*/
	/*print each argument to the screen*/
	printf("Argument %d: %s\n", n, argv[n]);
}/*end for*/

O(n)

The output of this code:

int c = 6;
int *p = &x;
int **q = &p;
*p = *p+4;
**q = **q + 1;

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

x = 11

what is the complexity?

void bar(int n) {
	int limit = (int) exp(n);

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

O(eⁿ)

Interpret why gdb is showing a seg fault

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

int main(){
	int *ptr = NULL;
	*ptr = 10;
	printf("%d\n", *ptr);
	return 0;
}

ptr is a NULL pointer (0×0), attempting to dereference it with *ptr=10 is illegal memory access

this special target is executed when you type make without specifying a target

all

This complement standard can represent more numbers in negative binary and is used the most in industry

2’s complement

What is the complexity of this code?

#include <stdio.h>

#define SIZE 5

int stack [SIZE};
int top = -1;

void push(int value) {
	if (top < SIZE -1){
		stack[++top] = value;
	}
}

int main(){
	push(10);
	push(20);
	printf("%d\n", stack[top]);
	return 0;
}

O(1)

The output of this code:

int arr[5] = {1, 2, 3, 4, 5};
int *p = arr;
printf("%d %d\n", *(p+3), p[1]);

4 2

This gdb command allows you to pause the execution whenever a specified variable is modified

watch

the following code does this:

#define FUNC(x) ((*func)(x))
float trapzd(func, a, b)
float a, b;
float (*func)(float);
{
	return (s = 0.5*(b-a)*(FUNC(a) + FUNC(b)));
}

integrates the input function with the trapezoid rule on the given bounds

in C, #include gives the compile declarations from this kinds of file, but it does not itself provide the compiled code later resolved by the linker

header file

these are what represent 00000000 AND 11111111 in 1’s compliment.

+0 and -0

Address the comment:

for(int i =0; i <strlen(argv[1]); i++) { /* (2) What does this loop do? */
	if (isdigit(argv[1][i]) == 0) {
		fprintf(stderr, "Wrong type for input.\n");
		exit(1);
	} /*end if*/
} /*end for*/

loop checks every character in argv 1 to make sure it is a digit, and exits with an error and print statement if any character is not numeric

the output of this code:

int a =5, b =9, c;
int *p = &a;
int *q = &b;
*p = *q;
printf("%d %d %d\n", a, b, c);

9 9 <garbage value>

this is the largest decimal number you can express in a signed 8-bit binary

127

This gdb command prints the call stack (all functions that led to the current point), showing functions names, arguments, and line numbers

backtrace

What is the complexity?

int count = 0;
for (int i =0; i < n; i++){
	for (int j =1; j < n; j *=2){

		int k = j;

		while (k>0) {
			count ++;
			k/=2;
		}
	}
}

O(n (logn)²)

interpret the line of code:

if (argc <2) { /* (1) what does this if-statement do? */

checks if the number of input arguments is less than 2

(NOTE: this is not checks if argc is less than 2)

the output of this code:

int x = 7;
int *p = &x;
*p = `10;
printf("X  is the following: %d\n", x);

X is the following: 10

this command executes the next line of code, If the next line is a function call, it does not step into the function, it executes it entirely and moves to the following line.

next

What is the complexity?

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

O(1)

this is the largest decimal number you can express in 8-bit binary

255

this decimal number is expressed as 1000000 (6 zeros) in binary

64

the output of this code:

int x = 10;
int *p = &x;
printf("%d %d\n", x, *p);

10 10

this is the standard make command to remove all generated files produced by other rules in the makefile.

make clean

this command starts the program from beginning under gdb’s control. Execution will stop at any breakpoints.

run