CP 264 Midterm Review PDF - Laurier Computing Society

```markdown # CP 264 MIDTERM REVIEW LAURIER COMPUTING SOCIETY – REMEMBER TO SIGN IN – LAURIER COMPUTING SOCIETY – REMEMBER TO SIGN IN # TABLE OF CONTENTS * Compiling, data types, key words, functions...10-15 minutes * Char, pointers, arrays and strings, file 10...20-25 minutes * Principles of...

```markdown # CP 264 MIDTERM REVIEW LAURIER COMPUTING SOCIETY – REMEMBER TO SIGN IN – LAURIER COMPUTING SOCIETY – REMEMBER TO SIGN IN # TABLE OF CONTENTS * Compiling, data types, key words, functions...10-15 minutes * Char, pointers, arrays and strings, file 10...20-25 minutes * Principles of data structures, struct, union, enum ...20-25 minutes * Introduction to design and analysis, recurrences... 10-15 minutes * Samples and tips... 5-10 minutes # MIDTERM FORMAT **Format** * 40 minutes exam through lockdown browser * In person, closed book at class time * **Mark breakdown:** * Multiple choice (25) – 33% * Short answer questions (4) – 27% * Coding questions (4) – 40% **Expectations** * Covering weeks 1-4, including assignments * Multiple choice based on end of lecture quizzes * Review labs and assignments for coding help * Understand concepts for short answer # COMPILING AND C BACKGROUND BACK 2 BASICS # QUICK START – REVIEW: C BACKGROUND (I) * What compiling step eliminates all comments from code? * Is it necessary for a C program to contain a main function? * Where does the flow of control for a C program start? * What is a directive and how does it affect your code? * When are directives resolved? * Describe the memory model used in C. * What are 2 errors that arise from memory? How can you prevent them * What are the sizes of the following: char, int, float, double * When declaring an array of size 5, how much memory is reserved for this statement? * When is this memory reserved? What if it is a part of a function? * Where is this memory reserved? What if it is a part of a function? * Describe one difference between pass by reference and pass by value # THE EXECUTION PIPELINE 1. Preprocessing - parses code, resolves comments and directives, replaces macros 2. Compilation – converts the parsed code into assembly code, resolves constant arithmetic 3. Assembling – converts assembly code to object code for the machine 4. Linking – Combines object files and libraries from different sources into an executable program. # DATA TYPES * 4 primitive types in C: * Char - I byte * Int (on 32-bit systems) – 4 bytes * Float - 4 bytes * Double – 4 * 2 = 8 bytes * Unsigned: only accounts for positive numbers by reserving LMB * Short: 2 bytes * Long: 4 bytes # TYPES OF LOOPS * For – define iteration as argument * While - iteration is condition based * Do while – iteration is condition based plus one * Go to – deep iteration or return quickly * If, else if, else – specific cases * Switch – matching many cases * Break - return out of current scope * Continue - skip current iteration to end of scope * Careful if break not used with switch # MEMORY MANAGEMENT * Text region * Holds compiled instructions for all processes, i.e., functions * Data Region * Holds global and static variables * Stack Region * Holds runtime functions and scoped variable data * Heap Region * Allocated memory throughout the program for arrays, * Memory leaks – heap region * When allocated memory is not freed after its use. Can exhaust all available memory if not accounted for. * When an attempt to access freed memory is made, a segfault can happen * Stack overflow (the error) – stack region * Excessively deep recursion or large arrays can cause overflow # FUNCTIONS – PASS BY **Pass by pointer (reference)** * Passes the pointer to the object * Access or modify original data * Beware of making changes to the pointed object * Uses the unary operator '*' to dereference the pointer and get the object pointed to **Pass by value** * Constructs a copy of the value in memory * Does not change the parameter passed * Can change performance overhead in some cases # POINTERS, CHAR, STRING, FILE I/O POINTERS AND FRIENDS # QUICK START – REVIEW: POINTERS, CHAR, FILE I/O * Describe an algorithm that reverses a given string. * Given an integer cipher, and a string, return the string after shifting each char's ASCII by integer cipher * Describe how to traverse a 2 dimensional array * Describe how to traverse an n-dimensional array * How can you get the address of an object? * How can you get the values at a memory address? * Describe an algorithm that reverses a given string in place * Describe an algorithm that replaces every occurrence of a character in a string with another string pattern # POINTERS AND REFERENCING * A variable that stores the memory address of an object, rather than the object itself. * Declare <T> x; * Declare <T> *pointer * Set pointer = &x * Remember two things: object, and memory – switch between when tracing short answer code. * Could be tricky! Think of the memory addresses * Pointer Arithmetic: * Incrementing pointers is the same as incrementing the memory addresses it points to. * Useful for traversing arrays * Can perform relational arithmetic on pointers as well * Null Pointers point to nothing, generic pointers can point to anything Image of code example: ```c #include <stdio.h> int main() { int a=5; int *p=&a; int **pp = &p; printf("%d\n", a); // Line A printf("%d\n", *p); // Line B printf("%d\n", **pp); // Line C **pp = 10; printf("%d\n", a); // Line D return 0; } ``` Image of code example: ```c #include <stdio.h> void swap(int *a, int *b) { int *temp; temp = a; a = b; b = temp; } int main() { int x = 10, y = 20; swap(&x, &y); printf("%d %d\n", x, y); // Line A return 0; } ``` Image of code example: ```c #include <stdio.h> struct Point { int x, y; }; int main() { struct Point p1 = {10, 20}; struct Point *ptr = &p1; ptr->x += 5; ptr->y = 5; Printf("%d %d\n", p1.x, p1.y); // L return 0; } ``` # I/O FUNCTIONS **PRINTF** * Use replacement formatting: * % + flag + width align + precision + size + conversion * Flags: * "d" – integer * “f” – floating point decimal * "x" - hex value **SCANF/SSCANF** * Uses replacement formatting to assign variables to input * Place one-off delimiters to format the input accordingly * Makes a formula to follow when scanning # STRING OPERATIONS **Functions** * "strcpy” – copies source string into target location * “memcpy” – соpies the memory contents to the target location * Writing functions: * Can iterate until hitting the end character "\0” * Iterate over the length of the string **Patterns** * String Matching: * Determine if a string is a subsequence of another, or follows a certain pattern * String conversions: * Upper to lower case and vice versa, * Shifting by a # ARRAYS * Declared with type and size, and placed contiguously in memory for efficient random access * Can declare multidimensional arrays by directly appending the size at declaration, i.e. * <T> arr[1][2]; * Can iterate with index, or with pointer arithmetic * With multidimensional arrays, must declare pointer of type array with I less dimension * Iterate over the array for that dimension * Alternatively, can access index \*(x,y) with formula: * \*(p + y \* columns + x) Snippet of C code: ```c #include <stdio.h> int main() { int arr[2][3] = {{1, 2, 3}, {4, 5, 6}}; int *p = &arr[0][0]; printf("%d ", *(p + 2)); // Line A printf("%d ", *(p + 4)); // Line B printf("%d\n", *(*(arr +1) + 1)); // return 0; } ``` # FILE OPERATIONS * Keywords: fopen(), fclose() * "r" - reading * "w" - writing * “a” – appending * "r+" - updating * "w+” – create/wipe file for update * "a+" – create file for update and append * Read: * Fgets() for string of length ? * fgetc() for character * Fscanf() for formatted input * Write: * Fputs() for strings * fputc() for character * Fprintf() for formatted output # STRUCT, UNION, ENUM, AND SOME PRINCIPLES THE MEAT OF THE COURSE # STRUCTURE * A composite data type using none or more than one nested entries * Defined using struct and declared in the header * Supports assignment operations like init function or constructor method * Inner members accessible via arrow notation struct -> parameter * Pass by value to function # PRINCIPLES OF DATA STRUCTURES * Describes how an associated collection is: * Represented * Organized * Stored * Operated on * Common Operations: * Accessing, modifying, * Other Operations: * Traversal (lists, arrays) * Membership testing (sets, sorted sets) * Insertion and deletion (sets, trees) * Statistics (segment tree, hash table) * Sorting (AVL tree, self balancing) # PITFALLS: STRUCT * Using the arrow operator to access inner members is reserved with use of pointers * Using the dot operator to access members is reserved for the use with values # ENUM AND UNION **Enum** * Usually used to enumerate constants and to assign integer values * Allows for more readable code (days of the week, Boolean, etc.) **Union** * Conserves memory by allowing multiple different data types to share the same block. * However, all entries share the same block * Can accidentally overwrite the storage. * Wildcard data type that can be different things sequentially. # COMPLEXITY ANALYSIS NOT SO COMPLEX NOW... # QUICK START – REVIEW: COMPLEXITY ANALYSIS * What is the time complexity of a linear search? * What is the time complexity of generating all possible pairs from an array? * What is the lower bound for comparison-based sorting algorithms? * Describe the algorithm for a sorting algorithm, and guess the running time. # BIG O NOTATION * Measures the number of operations an algorithm will perform relative to input size. * O(1) means constant, or irrelevant to input size * O(log n) means log-proportional to input size * O(n) means linearly proportional to input size * O(2^n) means exponentially proportional to input size * O(n!) means factorially proportional to input size * Given 1-10 seconds, the recommended input sizes are: * > 10^9 for subsets of O(log n) or better * ~10^7 for subsets of O(n) or better * ~ 10^5 for subsets of O(n log n) or better * ~ 10^3 for subsets of O(n^2) or better # ASYMPTOTIC BEHAVIOR **What it is** * An approximation for how an algorithm will perform with relatively large input size * A guideline for the families of algorithms you should write given an input * A measure for efficiency on large scale inputs **What it isn't** * Exact runtime for the algorithm * The exact number of operations an algorithm has # THINGS HBF LIKES TO SAY, BUT I DON'T THINK WILL BE ON THE EXAM **Algorithms** * HBF likes to prove his algorithm correctness a lot using induction and solving recurrence relations. * "Assume T(n) is in O(n log n) ..." * Upper and lower bound time complexities * Proof of correctness **Algorithm Paradigms** * Dynamic Programming * Using known solutions to solve larger problems * Memorisation (top down) and Tabulated (bottom up) * Divide and Conquer * Breaking larger problems down into smaller problems * NON overlapping problems as opposed to dynamic programming * Complete Search: * Very slow, requires small search space # FINAL EXAMPLES THE FINALE... # INTERACTIVE EXAMPLE – STRINGS AND MEMORY * Describe an algorithm that reverses a string in place * Describe an algorithm that checks if two strings are reversed from one another. * Using these two algorithms, describe a third algorithm that determines if a string is a palindrome. * 1. Given a) constant string, b) these 3 function declarations, trace the memory of the program. # INTERACTIVE EXAMPLE – GRADE CALCULATOR Define a struct GRADES: containing two members: float percentage, and char grade. 1. Under which conditions can binary search be used? a. Describe a recursive binary search algorithm: binary\_search(int: left, int: right, GRADES: array) 2. Where does the function definition for the recursive function reside in memory? 3. At a memory level, what happens at a function call? 4. Given a list of number grades and their ranges, describe an efficient algorithm that finds the grade of a student. 5. What is the running time of this algorithm? 6. What is the space complexity of this algorithm? Beware of the parameters ```