Midterm Review CP264

• CP 264 Midterm Review provided by Laurier Computing Society

Table of Contents

• Review includes: compiling, data types, keywords, functions, characters, pointers, arrays, strings, file input/output, data structure principles, struct, union, enum, design & analysis introduction, recurrences, samples and tips.
• Estimated review time for compiling data types, keywords, functions: 10-15 minutes.
• Estimated review time for characters, pointers, arrays, strings, file input/output: 20-25 minutes.
• Estimated review time for data structure principles, struct, union, enum: 20-25 minutes.
• Estimated review time for introduction to design, analysis, recurrences: 10-15 minutes.
• Estimated review time for samples and tips: 5-10 minutes.

Midterm Format & Expectations

• The midterm exam is 40 minutes long and will be administered through a lockdown browser.
• The exam is in person and closed book, conducted during class time.
• The mark breakdown: 33% multiple choice (25 questions), 27% short answer (4 questions), and 40% coding questions (4 questions).
• Covers weeks 1-4 content including assignments.
• Multiple-choice questions will be based on end-of-lecture quizzes.
• Review labs and assignments for coding help.
• Understand concepts for short answers.

Compiling and C Background

• Compilation eliminates all comments from code.
• A C program must contain a main function.
• The flow of control for a C program starts at the main function.
• A directive affects your code.
• Directives are resolved during preprocessing.
• When declaring an array of size 5, the amount of memory reserved depends on the data type
• The memory is reserved when the function is called
• One difference between pass by reference and pass by value is that pass by reference can modify the original data, while pass by value works on a copy

Execution Pipeline

• Preprocessing parses code, resolves comments and directives, and replaces macros.
• Compilation converts the parsed code into assembly code and resolves constant arithmetic.
• Assembling converts assembly code to object code for the machine.
• Linking combines object files and libraries from different sources into an executable program.

Data Types

• Four primitive data types in C include:
  • char which is 1 byte,
  • int (on 32-bit systems) which is 4 bytes,
  • float which is 4 bytes,
  • double which is 8 bytes.
• Unsigned accounts for positive numbers and reserves the leftmost bit
• Int is 4 bytes long
• Short is 2 bytes
• Long is 4 bytes

Types of Loops

• "For" loops define iteration as an argument.
• "While" loops iteration is condition-based.
• "Do while" loops iteration is condition-based plus one.
• "Go to" allows for deep interation or for a quicker return
• "If, else if, else" are specific cases.
• "Switch" is used if matching many cases.
• Break returns execution out of the current scope
• Continue will skip the current iteration and continue at the end of the current scope
• It's important to be careful if break is not used with switch statements.

Memory Management

• Text region holds compiled instructions for all processes.
• Data Region holds global and static variables.
• Stack Region holds runtime functions and scoped variable data.
• Heap Region is for allocated memory throughout the program for arrays.
• Memory leaks come from the heap region
• Allocated memory is not freed after its use.
• All available memory can be exhausted.
• An attempt to excess freed memory will cause a segmentation fault
• Stack overflow impacts the stack region
• Excessively deep recursion or large arrays can cause stack overflow

Functions - Pass by

• Pass by pointer (reference): It passes the pointer to the object; allowing access or modification to original data, caution must be applied
• Uses the unary operator * to dereference the pointer to get the object pointed to.
• Pass by value: It constructs a copy of the value in memory, so there's no change to the parameter passed; may cause performance overhead.

Pointers, CharString, File I/O

• Given string operations and file I/O practice questions

Pointers and Referencing

• Pointers: A variable stores the memory address of an object rather than the object itself.
• Declare a pointer using <T> *pointer.
• Assign the address of a variable x to a pointer using pointer = &x.
• Pointer Arithmetic: Incrementing pointers increments the memory addresses it points to, useful in traversing arrays.
• Relational arithmetic can be performed on pointers
• Null Pointers point to nothing, while generic pointers can point to anything.

Arrays

• Arrays are declared with type and size, and elements are placed contiguously in memory.
• Multidimensional arrays can be declared by appending sizes, e.g., <T> arr[1][2].
• Arrays can be iterated over using index or pointer arithmetic.
• With multidimensional arrays, a pointer type array must be declared with 1 less dimension.
• Arrays can be accessed via index *(x,y) using the formula *(p + y * columns + x).

I/O Functions

• printf: Uses replacement formatting such as % + flag + width align + precision + size + conversion.
• printf Flags include: "d" for integer, “f” for floating point decimal, and "x" for hex value.
• scanf/sscanf uses replacement formatting to assign variables to input.
• Place one-off delimiters to format the input accordingly.
• scanf/sscanf Makes a formula to follow when scanning

String Operations

• String functions:
  • "strcpy” copies source string into target location,
  • "memcpy” copies the memory contents to the target location.
• String writing functions: iterate until hitting the end character "\0” or iterate over the length of the string.
• String Matching: Determine if a string is a subsequence of another, or follows a certain pattern
• String conversions: Can convert strings to upper or lower case and vice versa, and Shifting by a character

File Operations

• Keywords include: fopen() and fclose().
• File modes:
  • "r" for reading,
  • "w" for writing,
  • “a” for appending,
  • "r+" for updating,
  • "w+” creates/wipes file for update,
  • "a+" creates file for update and append.
• File reading functions: fgets() for string of length ? , fgetc() for character, fscanf() for formatted input.
• File writing functions: fputs() for strings, fputc() for character, fprintf() for formatted output.

Struct, Union, Enum, and Some Principles

• Struct is a composite data type using zero or more nested entries; is defined using struct and declared in the header; can use init function/constructor method; accessible via arrow notation struct -> parameter; and passed by value to function.
• Principles of Data Structures describe how an associated collection is represented, organized, stored, and operated on, with common operations being accessing and modifying, as well as other traversal, membership testing, insertion/deletion, statistics and sorting.
• Arrow notation is used to access inner members and is reserved for the use of pointers
• Dot notation is used to access members and is reserved for the use of values

Enum and Union

• Enum is typically used to enumerate constants and assign integer values; allows for more readable code for days of the week, Boolean, etc.
• Union conserves memory by allowing multiple different data types to share the same block; all entries share the same block, which can accidentally overwrite storage; acts as Wildcard that can sequentially hold different data types.

Complexity Analysis

• Big O Notation measures the number of operations an algorithm will perform relative to input size.
  • O(1) means constant,
  • O(log n) means log-proportional,
  • O(n) means linearly proportional,
  • O(2^n) means exponentially proportional,
  • 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, and ~ 10^3 for subsets of O(n^2) or better.
• Asymptotic complexity analysis is an approximation for how an algorithm will perform with relatively large input size; serves as a guideline and a measure for efficiency on large scale inputs; however, it isn't an exact runtime, or number of operations an algorithm has.
• HBF likes algorithm correctness, time complexities, and proof of correctness.
• Algorithm Paradigms include: Dynamic Programming, Divide and Conquer, and Complete Search.
• Dynamic Programming uses known solutions to solve larger problems with Memorisation (top down) and Tabulated (bottom up) approaches.
• Divide and Conquer breaks larger problems down into smaller NON-overlapping problems.
• Complete Search can be very slow.

Interactive Examples

• General questions about strings, memory and grade calculator