Computer Science Fundamentals

Cheatsheet Content

Fundamentals of Computers Components of a Computer Hardware: Physical parts (CPU, Memory, Storage, I/O devices). Software: Programs and data (Operating System, Applications). CPU (Central Processing Unit): The "brain" – executes instructions. Memory (RAM): Volatile storage for active programs/data. Storage (HDD/SSD): Non-volatile for long-term data. Input Devices: Keyboard, mouse, microphone. Output Devices: Monitor, printer, speakers. Problems, Flowcharts, Memory, Variables, Values, Instructions, Programs Problem: A task to be solved, often requiring computation. Flowchart: A visual representation of an algorithm using symbols. Start/End: Oval Process: Rectangle Input/Output: Parallelogram Decision: Diamond Connector: Circle Flow Lines: Arrows Memory: Stores data and instructions. Each location has a unique address . Variables: Named storage locations in memory that hold values. Can change during program execution. Example: int count = 0; Values: The actual data stored in variables (e.g., numbers, text). Instructions: Basic commands a computer understands (e.g., add, move data). Program: A sequence of instructions to perform a specific task. Problem Solving Techniques Algorithmic Approach Algorithm: A step-by-step procedure to solve a problem. Characteristics of an Algorithm: Unambiguous: Clear and precise steps. Input: Zero or more well-defined inputs. Output: One or more well-defined outputs. Finiteness: Must terminate after a finite number of steps. Feasibility: Should be executable with available resources. Independence: Steps should be independent of specific programming languages. Problem Solving Strategies Top-Down Approach: Break a large problem into smaller, manageable sub-problems. Solve each sub-problem independently. Combine solutions to solve the original problem. Focuses on overall structure first, then details. Bottom-Up Approach: Start by solving the most basic or atomic parts of the problem. Combine these basic solutions to build larger components. Eventually, build the complete solution. Focuses on details first, then integrates them. Number Systems and Data Representation Decimal (Base-10): Digits 0-9. (e.g., $123_{10}$) Binary (Base-2): Digits 0, 1. Used by computers. (e.g., $1111011_2$) Octal (Base-8): Digits 0-7. (e.g., $173_8$) Hexadecimal (Base-16): Digits 0-9, A-F. (e.g., $7B_{16}$) Data Representation: Integers: Stored using binary (e.g., Two's Complement for negative numbers). Floating-Point Numbers: Stored using IEEE 754 standard (sign, exponent, mantissa). Characters: Stored using encoding schemes like ASCII or Unicode. Elements of C++ Programming Language Data Types, Constants, Variables Data Types: Define the type of data a variable can hold. Primitive: int , char , float , double , bool . Derived: Arrays, Pointers, Structures. Constants: Values that cannot be changed during program execution. Literal constants: 10 , 3.14 , 'A' . Defined constants: const int PI = 3.14159; Variables: Named memory locations to store data. Declaration: int age; Initialization: age = 30; or int age = 30; Expressions and Assignment Statements Expression: A combination of operators, operands, and function calls that evaluates to a single value. Arithmetic: a + b * 2 Relational: x > y Logical: (a && b) || c Assignment Statement: Assigns the value of an expression to a variable. variable = expression; (e.g., sum = a + b; ) Input and Output Statements Input: Reading data from the user or a file. std::cin >> variable; (requires #include ) Output: Displaying data to the console or writing to a file. std::cout Conditional and Branch Statements if-else : Executes different code blocks based on a condition. if (condition) { // code if true } else { // code if false } switch-case : Selects one of many code blocks to execute based on the value of an expression. switch (expression) { case value1: // code block 1 break; case value2: // code block 2 break; default: // default code } Iteration Statements (Loops) while loop: Repeats a block of code as long as a condition is true. while (condition) { // code to repeat } do-while loop: Executes the block once, then repeats as long as the condition is true. (Guaranteed at least one execution). do { // code to repeat } while (condition); for loop: Used for iterating a specific number of times. for (initialization; condition; update) { // code to repeat } Arrays, Strings, Bit-wise Operations Arrays: A collection of elements of the same data type stored in contiguous memory locations. Single-Dimensional: int arr[5]; Multi-Dimensional: int matrix[3][3]; Accessed using an index (e.g., arr[0] ). Strings: A sequence of characters. In C++, often represented as a character array (C-style string) or using std::string . C-style: char name[] = "John"; (null-terminated) C++: std::string name = "John"; (more features) Bit-wise Operations: Operations performed on individual bits of an integer. & (AND), | (OR), ^ (XOR), ~ (NOT) (Left Shift), >> (Right Shift) Functions and Recursion Modular Approach & User-Defined Functions Modular Approach: Breaking a program into smaller, independent functions/modules. Improves readability, reusability, and maintainability. User-Defined Functions: Blocks of code designed to perform a specific task. return_type function_name(parameters) { // function body return value; // if return_type is not void } Library Functions: Pre-defined functions available in C++ libraries (e.g., sqrt() , pow() from ). Parameter Passing & Return Values Call by Value: A copy of the argument's value is passed to the function. Changes inside the function do not affect the original variable. Call by Reference: The memory address of the argument is passed. Changes inside the function directly affect the original variable. (Uses & symbol). void swap(int &a, int &b) { int temp = a; a = b; b = temp; } Return Values: A function can return a single value using the return statement. The type must match the function's return_type . Passing Arrays as Parameters: Arrays are always passed by reference (their base address is passed). void printArray(int arr[], int size) { // ... } Recursion A function that calls itself to solve a problem. Requires a base case to stop the recursion and prevent infinite loops. Example: Factorial $n! = n \times (n-1)!$ int factorial(int n) { if (n == 0) // Base case return 1; else return n * factorial(n - 1); // Recursive call } Structures and Classes Declaration, Members, Access Modifiers Structures ( struct ): A user-defined data type that groups related variables (of different types) under a single name. struct Point { int x; int y; }; Point p1; p1.x = 10; Classes ( class ): Blueprint for creating objects. Encapsulates data (member variables) and functions (member functions) that operate on that data. class Circle { public: // Access modifier double radius; double getArea() { return 3.14 * radius * radius; } }; Circle c1; c1.radius = 5; Member Variables: Data associated with a class/structure. Member Functions: Functions that operate on the data of a class/structure. Access Modifiers: Control visibility of members. public: Accessible from anywhere. private: Accessible only from within the class itself. (Default for classes) protected: Accessible within the class and derived classes. Function Overloading Defining multiple functions with the same name but different parameters (different number or types of arguments). The compiler decides which function to call based on the arguments provided. int add(int a, int b) { return a + b; } double add(double a, double b) { return a + b; } // add(5, 3) calls first; add(3.5, 2.1) calls second Problems on Complex Numbers, Date, Time, Large Numbers These are common examples where struct or class are used to represent custom data types. Complex Number: struct Complex { double real; double imag; }; Date: struct Date { int day, month, year; }; Time: struct Time { int hour, minute, second; }; Large Numbers: Can be represented as arrays of digits or strings, with custom member functions for arithmetic operations. Pointers and Files Pointers and Dynamic Allocation Pointer: A variable that stores the memory address of another variable. Declaration: int *ptr; Address-of operator: & (e.g., ptr = &variable; ) Dereference operator: * (e.g., *ptr = 10; ) Dynamic Memory Allocation: Allocating memory during program runtime. new operator: Allocates memory for a single object or an array. int *p = new int; int *arr = new int[10]; delete operator: Frees dynamically allocated memory to prevent memory leaks. delete p; delete[] arr; String Processing Using C-style strings ( char[] ) and functions from : strlen() : length strcpy() : copy strcat() : concatenate strcmp() : compare Using std::string (from ): Easier to use, handles memory automatically. Methods: length() , append() , find() , substr() . Operators: + for concatenation, == for comparison. File Operations Requires #include . File Streams: std::ofstream : Output file stream (for writing). std::ifstream : Input file stream (for reading). std::fstream : General file stream (for read/write). Steps: Open: file.open("filename.txt", std::ios::out); Check: if (file.is_open()) Read/Write: Use for writing, >> for reading. Close: file.close(); Searching and Sorting Searching Algorithms Linear Search: Sequentially checks each element until a match is found or end of list reached. Time Complexity: O($n$) (worst case). Works on unsorted lists. Binary Search: Requires a sorted list. Repeatedly divides the search interval in half. Time Complexity: O($\log n$). Sorting Algorithms Selection Sort: Finds the minimum element from the unsorted part and puts it at the beginning. Time Complexity: O($n^2$). Bubble Sort: Repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. Time Complexity: O($n^2$). Insertion Sort: Builds the final sorted array (or list) one item at a time. Time Complexity: O($n^2$) (worst case), O($n$) (best case, almost sorted). Merge Sort: A divide-and-conquer algorithm. Divides list into halves, sorts each half, then merges sorted halves. Time Complexity: O($n \log n$). Stable sort. Quick Sort: A divide-and-conquer algorithm. Picks an element as a pivot and partitions the array around the pivot. Time Complexity: O($n \log n$) (average), O($n^2$) (worst case). In-place sort (mostly). Data Structures Abstract Data Types (ADTs) A mathematical model for data types. Defines the behavior (what it does) rather than the implementation (how it does it). Specifies a set of data values and a set of operations on those values. Examples: Stack, Queue, List, Tree, Graph. Stack ADT LIFO (Last In, First Out): The last element added is the first one to be removed. Operations: push(element) : Adds an element to the top. pop() : Removes and returns the top element. peek()/top() : Returns the top element without removing it. isEmpty() : Checks if the stack is empty. size() : Returns the number of elements. Array-Based Implementation: Use a fixed-size array and a top index to track the top of the stack. push : Increment top , then add element. Check for overflow. pop : Return element at top , then decrement top . Check for underflow. Applications: Function call stack (recursion). Expression evaluation (infix to postfix). Undo/Redo mechanisms. Browser history. Queue ADT FIFO (First In, First Out): The first element added is the first one to be removed. Operations: enqueue(element) : Adds an element to the rear. dequeue() : Removes and returns the front element. front()/peek() : Returns the front element without removing it. isEmpty() : Checks if the queue is empty. size() : Returns the number of elements. Array-Based Implementation: Use a fixed-size array and two pointers: front and rear . Linear Queue: front moves, leading to wasted space. Circular Queue: Uses modulo operator to wrap around the array, utilizing space efficiently. Applications: Print spooling. CPU scheduling. Data buffering. Breadth-First Search (BFS).