Comprehensive Study Guide for Data Structures and Algorithms

Introduction to Data Structures and Algorithms

• Data Structures: This refers to the arrangement of data so that they can be used efficiently in memory. It deals specifically with the organization of data items.
• Algorithms: This is a sequence of steps performed on data using efficient data structures to solve a given problem.
• Database: A collection of information stored in permanent storage used for faster retrieval and updation.
• Data Warehousing: The management of huge amounts of legacy data for the purpose of better analysis.
• Big Data: The analysis of data sets that are too large or complex to be dealt with by traditional data processing applications.
• Programming Context: Data structures and algorithms are fundamental to programming. For example, in languages like C, a programmer uses Arrays (a data structure) and a sequence of processing steps to solve a problem (an algorithm).

Memory Layout of C Programs

When a program starts, its code is copied to the main memory (RAM). The layout consists of several segments:

• Code Segment: This section contains the literal program code.
• Initialized Data Segment: This holds global and static variables that have been initialized by the programmer.
• Uninitialized Data Segment: This holds global and static variables that are not explicitly initialized (often called the BSS segment).
• Stack: This area of memory holds the memory occupied by functions, including local variables and function call frames.
• Heap: This contains data that is requested by the program as dynamic memory during runtime.

Time Complexity and Big O Notation

• Definition: Time Complexity is the study of the efficiency of algorithms. It determines how the time taken to execute an algorithm grows relative to the size of the input.
• The Scaling Problem (Pizza Example):
  • If a brother needs to get 2 pizzas from Dominos ($3\,km$ away) on his bike, he can do it easily.
  • If he needs to get pizzas for 29 friends, the input size ($n=29$) becomes too huge for him to handle in the same amount of time/way on a bike.
• Developer Comparison Example: Consider Shubham and Rohan, who developed sorting algorithms. Records of their runtimes for different input sizes ($n$) show how efficiency changes:
  • For $n = 10\text{ elements}$: Shubham ($90\,ms$), Rohan ($122\,ms$).
  • For $n = 70\text{ elements}$: Shubham ($110\,ms$), Rohan ($124\,ms$).
  • For $n = 110\text{ elements}$: Shubham ($180\,ms$), Rohan ($131\,ms$).
  • For $n = 1000\text{ elements}$: Shubham ($800\,ms$), Rohan ($200\,ms$).
  • Conclusion: While Shubham’s algorithm is faster for small inputs, Rohan's algorithm is superior as the input size increases.
• Data Transfer Example (GTA V):
  • Sending a $60\,GB$ file (GTA V) to a friend $5\,km$ away using a $4G$ connection with a $1\,Gb/day$ limit is inefficient.
  • Online/Linear Sending: As the file size grows, the time taken for online sending increases linearly, represented as $O(n)$.
  • Physical Sending: If you copy the game to a Hard Disk and deliver it physically, the time remains constant regardless of the file size (within reason), represented as $O(1)$ or $O(n^0)$.
  • Comparison: Small files like Minesweeper (in KBs) are better sent via internet, but massive files are more efficient to send physically.

Calculating and Visualizing Big O

• Order Calculation: To calculate the order of growth, only the most impactful term containing $n$ (input size) is considered, and lower-order terms and constants are ignored.
  • Example 1: $k_1 n^2 + k_2 n + 36 \rightarrow O(n^2)$.
  • Example 2: $k_1 k_2 n + k_3 k_4 + 8 \rightarrow O(n)$.
  • Example 3: If the formula is just constants ($k_1 k_2 + k_3 k_4 + 8$), it results in $O(1)$.
• Visualizing Growth:
  • $O(1)$ (Constant) appears as a flat horizontal line on a time vs. input size graph.
  • $O(n)$ (Linear) appears as a straight diagonal line.
• Big O Complexity Chart (Better to Worse):
  • Amazing: $O(1)$ and $O(\log(n))$
  • Good: $O(n)$
  • Fair: $O(n \log(n))$
  • Bad: $O(n^2)$, $O(n^3)$, and $O(2^n)$
  • Terrible: $O(n!)$
• Common Runtime Hierarchy: $1 < \log(n) < n < n \log(n) < n^2 < n^3 < 2^n < n^n$

Asymptotic Notations

• Big Oh Notation ($O$): Used to describe the asymptotic upper bound. It defines that for a given function $f(n)$, $f(n)$ is $O(g(n))$ if and only if there exist positive constants $C$ and $n_0$ such that $0 \le f(n) \le C \times g(n)$ for all $n > n_0$. Note: if a function is $O(n)$, it is technically also $O(n^2)$.
• Big Omega Notation ($\Omega$): Used to describe the asymptotic lower bound. $f(n)$ is $\Omega(g(n))$ if there exist positive constants $C$ and $n_0$ such that $0 \le C \times g(n) \le f(n)$ for all $n > n_0$. Note: if a function is $\Omega(n^2)$, it is automatically $\Omega(n)$.
• Big Theta Notation ($\Theta$): This provides a tight bound by combining the upper and lower bounds. It means the function is "sandwiched". Mathematically, $0 \le C_2 \times g(n) \le f(n) \le C_1 \times g(n)$ for all $n \ge n_0$. This is the notation most developers mean when they say "Order of".

Case Analysis and Searching

• Best Case: When the algorithm performs optimally due to ideal input (e.g., finding the search item at the first position).
• Worst Case: When the input is as difficult as possible for the algorithm.
• Expected Case: The average of all possible case runtimes.
• Searching in a Sorted Array:
  • Linear Search: Starts from the first element and moves sequentially until the element is found or a larger element is reached.
    • Best Case: $O(1)$
    • Worst Case: $O(n)$
  • Binary Search: Continually halves the search range by checking the center element.
    • Best Case: $O(1)$
    • Worst Case: $O(\log(n))$
• Understanding $\log(n)$: This represents the number of times you need to half an array of size $n$ before it is exhausted. For example, $\log_2(8) = 3$ because $8 \rightarrow 4 \rightarrow 2 \rightarrow 1$.

Space Complexity and Practical Rules

• Space Complexity: Measures how the memory requirements of an algorithm grow with input size.
  • Creating an array of size $n$ results in $O(n)$ space complexity.
  • If a function calls itself recursively $n$ times, its space complexity is $O(n)$.
• Prohibiting Time in Seconds: Complexity cannot be calculated in seconds because hardware power varies between computers. Asymptotic analysis focuses on growth relative to input.
• Simplification Rules:
  1. Drop Constants: $O(3n)$ becomes $O(n)$.
  2. Drop Non-Dominant Terms: $O(n^2 + n)$ becomes $O(n^2)$.
  3. Consider All Variables: Use all input variables provided, e.g., painting a park of dimension $m \times n$ results in $O(m \times n)$.

Questions & Discussion

• Problem 1: Find the complexity of func1 which contains two separate loops, each running from $0$ to length.
  • Answer: $O(n) + O(n) = O(n)$.
• Problem 2: Find the complexity of func with a nested loop where both i and j go from $0$ to n.
  • Answer: $O(n \times n) = O(n^2)$.
• Problem 3: For a recursive algorithm where i = random(n - 1) and the return is function(i) + function(n - 1 - i), what is the value of $T(6)$?
• Problem 4: Which are equivalent to $O(N)$?
  • a) $O(N + P)$ where $P < N/9$.
  • b) $O(9N - k)$.
  • c) $O(N + 8 \log(N))$.
  • d) $O(N + M^2)$.
• Problem 5: Summing values in a balanced binary search tree.
  • Answer: $O(n)$ because every node is visited once.
• Problem 6: Complexity of primality test for (int i = 2; i * i < n; i++).
  • Answer: $O(\sqrt{n})$.
• Problem 7: Complexity of for (int i = 2; i * i < 10000; i++).
  • Answer: $O(1)$ as the loop runs a constant number of times.

Array Operations

• Traversal: Visiting every element of an array exactly once (e.g., printing or storing data using loops).
• Insertion: Adding an element at a specific position. Requires shifting elements to the right to maintain order. Requires checking array capacity.
• Deletion: Removing an element at a position. Creates a void that must be fixed by shifting subsequent elements to the left. Alternatively, the last element can fill the void if order is unimportant.
• Searching: Finding the index of a value. Faster in sorted arrays ($O(\log(n))$) than unsorted ($O(n)$).
• Sorting: Arranging elements in ascending or descending order.

Linked Lists

• Description: Linear data structures where elements are stored in non-contiguous memory locations. Each node contains data and a pointer to the next node.
• Pros vs. Cons:
  • Pros: Dynamic capacity (no fixed size), easy insertion/deletion.
  • Cons: Requires extra memory for pointers, no random access (must traverse sequentially).
• C Implementation: c struct Node { int data; struct Node *next; };     
• Deletion Cases:
  1. Deleting the first node (Update head pointer).
  2. Deleting at an index (Rewire previous node's pointer).
  3. Deleting the last node.
  4. Deleting a node with a specific value.
  • Note: Memory must be freed using free().
• Circular Linked List: The last element points back to the head node, forming a chain.
• Doubly Linked List: Each node contains pointers to both the previous and next nodes. Requires adjusting two pointers during insertion/deletion.

Stack Data Structure

• Definition: A linear data structure following the LIFO (Last In First Out) principle.
• Applications:
  1. Function calls.
  2. Infix to Postfix conversion.
  3. Parenthesis matching.
• Stack ADT Operations:
  • push(): Add an element to the top.
  • pop(): Remove the topmost element.
  • peek(index): Return value at a specific position.
  • isEmpty() / isFull(): Check the status of the stack.
• Implementation: Can be achieved using either an Array or a Linked List.