DS Midterm Summary PDF

Data Structure Summery Intro Any program consists of code + data. RAM consists of Heap, stack, global variables, code. Heap: This is the area of memory used for dynamic memory allocation. Variables allocated here persist until they are explicitly deallocated (e.g., with free in C o...

Data Structure Summery Intro Any program consists of code + data. RAM consists of Heap, stack, global variables, code. Heap: This is the area of memory used for dynamic memory allocation. Variables allocated here persist until they are explicitly deallocated (e.g., with free in C or delete in C++). Stack: The stack is used for function calls and local variables. Each time a function is called, a new stack frame is created, which holds function parameters, return addresses, and local variables. The stack automatically cleans up when the function returns. Global/Static Variables: This section holds variables that are declared outside of functions, such as global variables and static variables. These variables have a lifetime that spans the entire duration of the program. Code (Text Segment): This section contains the actual machine code that the CPU executes, typically read-only. What is a data strucure? A data structure is a scheme (‫ )مخطط‬for organizing data in the memory of a computer for efficient storage and efficient manipulation. Time Complexity Time complexity refers to the amount of time an algorithm takes to complete as a function of the size of its input. ‫يعني مقدار الوقت اللي كود معين بيحتاجه عشان يتنفذ والوقت ده مبني على حجم الداتا أو االنبوت اللي داخله‬ It helps to estimate the performance of an algorithm, especially when working with large inputs. Time complexity is usually expressed using Big-O notation, which describes the upper bound or worst case of an algorithm's runtime as the input size grows. Types of complexity 1. Best Case or lowerbound Ω (Omega) 2. Average case or upper & lower bound Θ (Theta). 3. Worst case or upper bound O (Big-O). Methods of Calculating Time Complexity 1. Frequency Count The frequency count method involves counting how many times each statement or operation in an algorithm is executed. Ramez Medhat  Example: 2. Asymptotic Analysis it focuses on describing the behavior of an algorithm as the input size grows towards infinity. It eliminates constant factors and lower-order terms, providing a general classification of the algorithm's efficiency. The Frequency count method gives you the Exact time, but we care more about the Order or Asymptomatic time ‫الوقت‬ ‫التقريبي‬, so we must follow these two rules: 1. Statements: Order of 1 2. Conditions: choose the max 3. Loops: Order of body × number of iterations 4. constants are removed. O(6n + n 2 2 + 5) = O(n + n ) 5. the biggest order is the dominant O(n + n 2 2 ) = O(n ) Common Orders O(1): Constant time, the algorithm takes the same time regardless of input size. int n = 5; O(log n): Logarithmic time, the algorithm's time grows logarithmically as the input size increases. (‫كل مره بقلل عدد‬ ‫)العمليات للنص‬ for(int i = 0; i < n; i *= 2) {} O(n): Linear time, the time increases proportionally with the input size. for(int i = 0; i < n; i++) {} O(n log n): Quasi-linear time, common in algorithms like merge sort and quicksort. for(int i = 0; i < n; i++) { for(int i = 0; i < n; i *= 2) {} } O(n²): Quadratic time, time grows with the square of the input size, often found in algorithms that use nested loops. Ramez Medhat  for(int i = 0; i < n; i++) { for(int i = 0; i < n; i++) {} } O(2^n): Exponential time, the time doubles with each additional input size. int fibonacci(int n) { if (n next = newNode; tail = newNode; } size++; } Insert at void insert_at(T val, int index) { if (index > size || index < 0) { throw out_of_range("Index out of range"); } if (index == 0) { insert_at_begin(val); } else if (index == size) { insert_at_end(val); } else { Node* newNode = new Node(val); Node* current = head; for (int i = 0; i < index; i++) { current = current->next; } newNode->next = current; newNode->prev = current->prev; current->prev->next = newNode; current->prev = newNode; Ramez Medhat  size++; } } And the rest of the deteting function is the same, we put into consideration that there's a tail that must be updated with a new value. 3. Circular linked list The last node points back to the first node instead of null , creating a loop. Can be singly or doubly linked ): ‫ الدكتور مشرحهاش ولكن ممكن تفكر فيها مع نفسك‬،‫ تاني‬head‫ ال انت هتوصل لل‬null ‫وانت بتلف مش هتوصل ل‬ Stack It is a linear-squential-logical data structure, It follows the Last In, First Out (LIFO) principle. This means that the most recently added element is the first one to be removed. Stack are used in function calls for almost all programming evnironments. Stack operations 1. Push: adds an element to the top of the stack, this element is the most accessible and will be the first to be removed. 2. Pop: Removes the top element from the stack, which was the item that was most recently added. 3. Peek/Top: retrives the top element without removing it. (‫)بترجع أخر قيمة اتضافت‬ Implementation Stack can be built with both dynamic array or linked list. ‫ (اللي‬head ‫ هترجع العنصر اللي عند ال‬peek ‫ تمسح عنصر من االول وفال‬pop ‫ تضيف عنصر فاالول وفال‬push ‫ كل اللي عليك فال‬linked list ‫االسهل تستخدم‬ )‫فاالول‬ Ramez Medhat  Push void push(t val){ // allocation Node *newNode = new Node(val); if(head == nullptr) { head = newNode; } else { newNode->next = head; head = newNode; } } Pop void pop(){ if(head == nullptr){ cout next; delete temp; } } top/peak void top(){ if(head == nullptr){ cout