Unit I — Complete Solutions to All Practice Questions

(a) Data: Raw facts, figures, or values that have no meaning by themselves. Example: 42, "hello", 3.14.

(b) Data Object: A collection of data items (instances) that share a common set of properties. Example: All integers form a data object; all characters form a data object.

(c) Data Type: A classification that specifies:

• The set of values a variable can hold
• The set of operations that can be performed on those values

Example: int in C — values: integers in range $[-2^{31}, 2^{31}-1]$; operations: +, -, *, /, %.

(d) Data Structure: A particular way of organizing and storing data in a computer so that it can be accessed and modified efficiently. It defines the relationship between data elements and the operations allowed on them.

Example: Array (contiguous memory, indexed access), Linked List (nodes with pointers).

(e) ADT (Abstract Data Type): A mathematical model for a data type where the behavior is defined by:

1. A set of values (domain)
2. A set of operations on those values
3. A set of axioms/constraints (rules the operations must follow)

The ADT specifies WHAT operations do, not HOW they are implemented. Example: Stack ADT defines push, pop, peek, isEmpty — without specifying whether an array or linked list is used internally.

Example:

• Data Type int: You know it uses 4 bytes, stores values $-2^{31}$ to $2^{31}-1$, supports +, -, *, /.
• ADT Stack: You know it supports push(), pop(), peek(), isEmpty(). You do NOT know (or care) if it uses an array or linked list internally.

                    Data Structures
                    /             \
               Primitive       Non-Primitive
              /  |  |  \        /          \
           int float char bool  Linear    Non-Linear
                               / | | \      /    \
                         Array LL Stack Queue Tree Graph

Alternatively classified as:

When to prefer:

• Static: When the size is known in advance, and you need fast random access. Example: storing 100 student scores.
• Dynamic: When the size is unpredictable or frequently changing. Example: a playlist where songs are added/removed often.

Three Linear Examples:

1. Array — indexed, contiguous memory
2. Stack — LIFO access
3. Queue — FIFO access

Three Non-Linear Examples:

1. Binary Tree — hierarchical parent-child relationship
2. Graph — network of interconnected nodes
3. Heap — complete binary tree with heap property

This forms a hierarchy of increasing abstraction:

1. Data — Raw values with no structure. Example: 5, "hello", true.

2. Data Type — Gives meaning to data by defining allowed values and operations. Example: int means 5 is an integer that supports +, -, *, /.

3. Data Structure — Organizes multiple data items with defined relationships and efficient access patterns. Example: An array of integers with indexed access, or a linked list with pointer-based traversal.

4. ADT — The highest abstraction — defines WHAT operations exist without specifying HOW they are implemented. Example: Stack ADT says “push adds on top, pop removes from top” — doesn’t specify array or linked list.

Progression: Each level adds more abstraction. Data has no structure → Data Type adds meaning → Data Structure adds organization → ADT hides implementation details entirely.

Choosing the right data structure is critical because it determines the efficiency of all operations performed on the data.

Example — Contacts App (Search by Name):

If you store 1 million contacts in an unsorted linked list, finding a contact requires scanning up to 1 million entries. Using a hash table, the same lookup takes constant time.

Another example — Undo feature: Using a Queue (FIFO) would undo the oldest action first — completely wrong! A Stack (LIFO) correctly undoes the most recent action.

Definition: An algorithm is a finite, well-defined sequence of computational steps that transforms input into output to solve a specific problem.

Five Essential Characteristics:

1. Input — Zero or more well-defined inputs are provided. Example: A sorting algorithm takes an array as input.

2. Output — At least one well-defined output is produced. Example: The sorted array is the output.

3. Finiteness — The algorithm must terminate after a finite number of steps. A procedure that runs forever is NOT an algorithm (it’s a “computational procedure”).

4. Definiteness — Each step must be precisely defined with no ambiguity. “Sort the array somehow” is NOT definite. “Compare adjacent elements and swap if out of order” IS definite.

5. Effectiveness — Each operation must be basic enough that it can, in principle, be carried out by a person with pencil and paper in finite time. Example: arithmetic operations, comparisons, assignments are effective. “Find the meaning of life” is not.

Algorithm: EuclideanGCD(a, b)
Purpose: Find the Greatest Common Divisor of two positive integers
Input: Two positive integers a, b
Output: GCD of a and b

1. while b ≠ 0 do
2.     temp ← b
3.     b ← a mod b
4.     a ← temp
5. end while
6. return a

Trace for GCD(48, 18):

GCD(48, 18) = 6 ✓

C Implementation:

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

        [Start]
           ↓
      [Read n]
           ↓
      ┌─ n ≤ 1? ──Yes──→ [Print "Not Prime"] → [End]
      │   No
      ↓
   [i = 2]
      ↓
   ┌─ i * i ≤ n? ──No──→ [Print "Prime"] → [End]
   │   Yes
   ↓
   ┌─ n % i == 0? ──Yes──→ [Print "Not Prime"] → [End]
   │   No
   ↓
   [i = i + 1]
      ↓
   └──→ (back to "i * i ≤ n?")

Pseudo code equivalent:

Algorithm: IsPrime(n)
1. if n ≤ 1 then return "Not Prime"
2. for i ← 2 to √n do
3.     if n mod i == 0 then return "Not Prime"
4. end for
5. return "Prime"

Algorithm: ReverseArray(A, n)
Purpose: Reverse array A of n elements in-place
Input: Array A[0..n-1], integer n
Output: Array A reversed

1. left ← 0
2. right ← n - 1
3. while left < right do
4.     swap(A[left], A[right])
5.     left ← left + 1
6.     right ← right - 1
7. end while

Trace for A = [1, 2, 3, 4, 5]:

Time: $O(n)$, Space: $O(1)$

When to prefer Flowchart:

• Simple algorithms with clear branching
• Explaining logic to non-technical stakeholders
• Understanding control flow visually

When to prefer Pseudo Code:

• Complex algorithms with many steps
• Translating directly to code
• Documenting algorithms in papers/textbooks

Algorithm: SecondLargest(A, n)
Purpose: Find the second largest element in array A
Input: Array A[0..n-1], integer n (n ≥ 2)
Output: Second largest element

1. if n < 2 then
2.     return "Error: Need at least 2 elements"
3. end if
4. largest ← max(A[0], A[1])
5. second ← min(A[0], A[1])
6. for i ← 2 to n-1 do
7.     if A[i] > largest then
8.         second ← largest
9.         largest ← A[i]
10.    else if A[i] > second then
11.        second ← A[i]
12.    end if
13. end for
14. return second

Trace for A = [12, 35, 1, 10, 34, 1]:

Result: 34 ✓

Time: $O(n)$ — single pass, Space: $O(1)$

(a) “Keep printing 1 forever” — ❌ NOT a valid algorithm

• Violates the Finiteness property. An algorithm must terminate after a finite number of steps. This runs infinitely.

(b) “Take two numbers, add them, print the result” — ✅ Valid algorithm

• Has input (two numbers), output (the sum), is finite (3 steps), definite (each step is clear), and effective (addition is a basic operation).

(c) “Sort the array somehow” — ❌ NOT a valid algorithm

• Violates the Definiteness property. “Somehow” is ambiguous — it doesn’t specify HOW to sort. A valid algorithm must have precisely defined steps.

Algorithm: TowerOfHanoi(n, source, auxiliary, destination)
Purpose: Move n disks from source peg to destination peg
Input: n disks, three pegs (source, auxiliary, destination)
Output: Sequence of moves

1. if n == 1 then
2.     print "Move disk 1 from " + source + " to " + destination
3.     return
4. end if
5. TowerOfHanoi(n-1, source, destination, auxiliary)
6. print "Move disk " + n + " from " + source + " to " + destination
7. TowerOfHanoi(n-1, auxiliary, source, destination)

Trace for n = 3 (A→C, using B as auxiliary):

Total moves = $2^n - 1 = 2^3 - 1 = 7$

Time Complexity: $T(n) = 2T(n-1) + 1 = O(2^n)$

        [Start]
           ↓
    [Read A[], n, key]
           ↓
    [low = 0, high = n-1]
           ↓
    ┌── low ≤ high? ──No──→ [Print "Not Found"] → [End]
    │     Yes
    ↓
    [mid = (low + high) / 2]
           ↓
    ┌── A[mid] == key? ──Yes──→ [Print "Found at mid"] → [End]
    │     No
    ↓
    ┌── A[mid] < key? ──Yes──→ [low = mid + 1] ──┐
    │     No                                       │
    ↓                                              │
    [high = mid - 1] ─────────────────────────────┘
           ↓
    └──→ (back to "low ≤ high?")

Key idea: Repeatedly halve the search space by comparing the middle element with the key.

Algorithm: FindEvenNumbers
Purpose: Find and display all even numbers in an array
Input: Array A[0..n-1] of integers, integer n
Output: All even numbers in the array
Pre-condition: n ≥ 1

Steps:
1. [Initialize] count ← 0
2. [Traverse array]
   Repeat for i ← 0 to n-1:
       2.1 [Check even]
           if A[i] mod 2 == 0 then
               print A[i]
               count ← count + 1
           end if
   [End of loop]
3. [Output count]
   print "Total even numbers: " + count
4. [Finished]
   return

C Implementation:

void findEven(int A[], int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (A[i] % 2 == 0) {
            printf("%d ", A[i]);
            count++;
        }
    }
    printf("\nTotal even numbers: %d\n", count);
}

Time: $O(n)$, Space: $O(1)$

Time Complexity: A function that describes the amount of time (number of basic operations) an algorithm takes as a function of the input size $n$.

Space Complexity: A function that describes the amount of extra memory (beyond the input itself) an algorithm uses as a function of $n$.

Why time is more commonly discussed:

1. Memory is reusable — space can be freed and reused, but time once spent is gone forever.
2. Time is the main bottleneck — most algorithms run out of time before running out of memory.
3. Memory is cheap — modern systems have abundant RAM, but users won’t wait for slow algorithms.
4. Time is more variable — space usage is often straightforward ($O(1)$ or $O(n)$), while time complexity varies widely ($O(\log n)$ to $O(n!)$).

Big O — $O(g(n))$ — Upper Bound (Worst Case)

$f(n) = O(g(n))$ if there exist constants $c > 0$ and $n_0 > 0$ such that:

“$f(n)$ grows at most as fast as $g(n)$.”

Example: $3n + 5 = O(n)$ — choose $c = 4, n_0 = 5$: $3n + 5 \leq 4n$ for $n \geq 5$. ✓

Big Omega — $\Omega(g(n))$ — Lower Bound (Best Case)

$f(n) = \Omega(g(n))$ if there exist constants $c > 0$ and $n_0 > 0$ such that:

“$f(n)$ grows at least as fast as $g(n)$.”

Example: $3n + 5 = \Omega(n)$ — choose $c = 1, n_0 = 1$: $3n + 5 \geq n$ for $n \geq 1$. ✓

Big Theta — $\Theta(g(n))$ — Tight Bound (Exact Growth Rate)

$f(n) = \Theta(g(n))$ if there exist constants $c_1, c_2 > 0$ and $n_0 > 0$ such that:

“$f(n)$ grows exactly as fast as $g(n)$.”

Example: $3n + 5 = \Theta(n)$ — choose $c_1 = 1, c_2 = 4, n_0 = 5$. ✓

To prove: Find constants $c > 0$ and $n_0 > 0$ such that $5n^2 + 3n + 100 \leq c \cdot n^2$ for all $n \geq n_0$.

Proof:

For $n \geq 1$:

• $3n \leq 3n^2$ (since $n \leq n^2$ for $n \geq 1$)
• $100 \leq 100n^2$ (since $1 \leq n^2$ for $n \geq 1$)

Therefore: $5n^2 + 3n + 100 \leq 5n^2 + 3n^2 + 100n^2 = 108n^2$

So with $c = 108$ and $n_0 = 1$:

Tighter bound: For $n \geq 10$: $3n \leq 0.03n^2$ and $100 \leq n^2$. So $c = 6.03, n_0 = 10$ also works.

Therefore $5n^2 + 3n + 100 = O(n^2)$. $\blacksquare$

Proof by contradiction:

Assume $n^2 = O(n)$. Then there exist constants $c > 0$ and $n_0 > 0$ such that:

Dividing both sides by $n$ (valid since $n > 0$):

But this is a contradiction — $n$ grows without bound, so for any fixed constant $c$, we can always find $n > c$ (simply choose $n = \lceil c \rceil + 1$).

Therefore, no such $c$ and $n_0$ exist, and $n^2 \neq O(n)$. $\blacksquare$

Growth comparison at $n = 100$:

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j += i) {
        printf("*");
    }
}

The inner loop runs $\lceil n/i \rceil$ times for each value of i.

Total operations = $\sum_{i=1}^{n} \frac{n}{i} = n \cdot \sum_{i=1}^{n} \frac{1}{i} = n \cdot H_n$

where $H_n = 1 + \frac{1}{2} + \frac{1}{3} + … + \frac{1}{n}$ is the Harmonic series.

Since $H_n = \Theta(\ln n)$:

Answer: $O(n \log n)$

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        for (int k = 0; k < n; k++)
            // O(1) work

Each loop independently runs $n$ times. By the multiplication rule:

Answer: $O(n^3)$

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

Time Complexity: $O(2^n)$

The recurrence is $T(n) = T(n-1) + T(n-2) + O(1)$.

The recursion tree is a binary tree where each call spawns two more. At depth $k$, there are up to $2^k$ calls. The tree has depth $n$, giving roughly $2^n$ total calls.

More precisely, $T(n) = O(\phi^n)$ where $\phi = \frac{1+\sqrt{5}}{2} \approx 1.618$ (golden ratio), but $O(2^n)$ is the standard upper bound.

Space Complexity: $O(n)$

At any point, only ONE branch of the recursion tree is active on the call stack. The maximum depth is $n$ (following the leftmost path: $fib(n) \to fib(n-1) \to … \to fib(1)$). So the stack holds at most $n$ frames.

Linear Search Example (searching for key in array of $n$ elements):

Bubble Sort Example:

Yes, $O(100n) = O(n)$.

Why constants are dropped:

1. Big O describes growth rate, not actual time. We care about how the function behaves as $n \to \infty$, not specific values.

2. Constants depend on hardware. An algorithm taking $100n$ operations on a slow machine may be faster than $n$ operations on an even slower machine. Constants are machine-dependent.

3. Mathematical definition allows it. If $f(n) = 100n$, then $f(n) \leq 100 \cdot n$ for all $n \geq 1$. With $c = 100$, this satisfies the Big O definition for $O(n)$.

4. Asymptotic dominance matters. For large $n$: $100n$ vs $n^2$ — eventually $n^2$ overtakes $100n$ (at $n = 100$). The growth rate of $n^2$ is fundamentally different from $n$, regardless of constants.

Key insight: $O(100n) = O(n)$ but $O(n) \neq O(n^2)$. Constants don’t change the complexity class.

int i = n;
while (i > 0) {
    i = i / 3;
}

After $k$ iterations: $i = \frac{n}{3^k}$

The loop stops when $i = 0$ (integer division), which happens when $3^k > n$:

Since $\log_3 n = \frac{\log_2 n}{\log_2 3}$, and base changes are just constant factors:

Answer: $O(\log n)$

Note: Dividing by ANY constant $> 1$ gives logarithmic complexity.

The dominant term is $3n^2$ (since $n^2$ grows faster than $n \log n$).

Big O (upper bound): $T(n) = O(n^2)$

For $n \geq 1$: $3n^2 + 7n\log n + 100 \leq 3n^2 + 7n^2 + 100n^2 = 110n^2$. So $c = 110$, $n_0 = 1$.

Big Omega (lower bound): $T(n) = \Omega(n^2)$

$3n^2 + 7n\log n + 100 \geq 3n^2$ for all $n \geq 1$. So $c = 3$, $n_0 = 1$.

Big Theta (tight bound): $T(n) = \Theta(n^2)$

Since $T(n) = O(n^2)$ AND $T(n) = \Omega(n^2)$, we have $T(n) = \Theta(n^2)$.

Data → Processing → Information

(a) Data Type: A classification that specifies the domain of values and the set of operations for a variable. Examples: int, float, char.

(b) Abstract Data Type (ADT): A mathematical model defining a data type purely by its behavior (operations and constraints), independent of implementation. It specifies WHAT, not HOW. Examples: Stack, Queue, List.

(c) Data Structure: A concrete way of organizing, storing, and managing data in memory to enable efficient access and modification. It implements an ADT. Examples: Array, Linked List, Hash Table.

Linear:

1. Queue at a movie theater — people wait in a line (FIFO order)
2. Stack of plates — you take from the top (LIFO order)

Non-Linear:

1. Company organizational chart — hierarchical (tree structure)
2. Road network between cities — interconnected (graph structure)

ADT Bag:
    Data:
        An unordered collection of elements that ALLOWS DUPLICATES

    Operations:
        create()           → Initialize an empty bag
        add(element)       → Add an element to the bag
        remove(element)    → Remove one occurrence of element (if exists)
        contains(element)  → Return true if element is in the bag
        count(element)     → Return number of occurrences of element
        size()             → Return total number of elements
        isEmpty()          → Return true if bag has no elements
        clear()            → Remove all elements

    Error Conditions:
        remove(element) where element ∉ Bag → "Element not found"

    Axioms:
        1. isEmpty(create()) = true
        2. size(add(B, x)) = size(B) + 1
        3. contains(add(B, x), x) = true
        4. count(add(B, x), x) = count(B, x) + 1

Key difference from Set: A Bag allows duplicates. add(B, 5) twice means count(B, 5) = 2.

1. Input — Zero or more well-defined inputs
2. Output — At least one well-defined output
3. Finiteness — Must terminate after a finite number of steps
4. Definiteness — Each step must be precisely and unambiguously defined
5. Effectiveness — Each step must be basic enough to be carried out mechanically

(a) Inner loop runs $i^2$ times: \(\text{Total} = \sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6} = O(n^3)\)

(b) Outer loop halves $i$: $\log n$ iterations. Inner loop always runs $n$ times: \(\text{Total} = n \cdot \log n = O(n \log n)\)

(c) Trick question! Variable j is NOT reset inside the outer loop.

• First outer iteration: inner loop runs $n$ times ($j$ goes 0 to $n$)
• All subsequent iterations: $j$ is already $n$, inner loop runs 0 times.
• Total: $O(n)$, NOT $O(n^2)$!

Let $f(n) = O(n^2)$ and $g(n) = O(n)$. Then:

• $f(n) \leq c_1 \cdot n^2$ for $n \geq n_1$
• $g(n) \leq c_2 \cdot n$ for $n \geq n_2$

For $n \geq \max(n_1, n_2)$:

With $c = c_1 + c_2$ and $n_0 = \max(n_1, n_2, 1)$:

Therefore $f(n) + g(n) = O(n^2)$. $\blacksquare$

General rule: $O(n^a) + O(n^b) = O(n^{\max(a,b)})$ — the higher-order term dominates.

A is better when $100n < n^2$:

A is better for $n > 100$. B is better for $n < 100$. They tie at $n = 100$.

This illustrates why Big O drops constants — for large inputs, $O(n)$ always beats $O(n^2)$ regardless of the constant factor.

(a) Sum of Digits:

Algorithm: SumOfDigits(n)
Input: Positive integer n
Output: Sum of all digits of n

1. sum ← 0
2. while n > 0 do
3.     sum ← sum + (n mod 10)
4.     n ← n / 10  (integer division)
5. end while
6. return sum

Example: $n = 1234$: $4 + 3 + 2 + 1 = 10$. Time: $O(\log_{10} n)$

(b) Palindrome Check:

Algorithm: IsPalindrome(S, n)
Input: String S of length n
Output: true if S is a palindrome, false otherwise

1. left ← 0
2. right ← n - 1
3. while left < right do
4.     if S[left] ≠ S[right] then return false
5.     left ← left + 1
6.     right ← right - 1
7. end while
8. return true

Example: “madam” → m=m, a=a, d=d → true. Time: $O(n)$

(c) Sieve of Eratosthenes:

Algorithm: SieveOfEratosthenes(n)
Input: Integer n ≥ 2
Output: All prime numbers from 2 to n

1. Create boolean array isPrime[0..n], initialize all to true
2. isPrime[0] ← false, isPrime[1] ← false
3. for i ← 2 to √n do
4.     if isPrime[i] = true then
5.         for j ← i*i to n step i do
6.             isPrime[j] ← false
7.         end for
8.     end if
9. end for
10. for i ← 2 to n do
11.     if isPrime[i] then print i
12. end for

Time: $O(n \log \log n)$, Space: $O(n)$

Example with $f(n) = 3n^2 + 5n$:

• $f(n) = O(n^2)$ ✓ and also $O(n^3)$ ✓ (upper bound can be loose)
• $f(n) = \Omega(n^2)$ ✓ and also $\Omega(n)$ ✓ (lower bound can be loose)
• $f(n) = \Theta(n^2)$ ✓ — this is the tightest and most informative

Relationship: $f(n) = \Theta(g(n))$ if and only if $f(n) = O(g(n))$ AND $f(n) = \Omega(g(n))$.

Insertion Sort Algorithm: For each element, insert it into its correct position in the already-sorted portion.

Best Case — Already Sorted Array $[1, 2, 3, 4, 5]$:

• Each element is already in the right position
• Inner loop comparison: $A[j] > key$ is false immediately
• Comparisons per element: 1
• Total: $(n-1) \times 1 = n - 1$
• Time: $O(n)$

Worst Case — Reverse Sorted Array $[5, 4, 3, 2, 1]$:

• Each element must be moved to the very beginning
• Element at position $i$ requires $i$ comparisons and shifts
• Total comparisons: $1 + 2 + 3 + … + (n-1) = \frac{n(n-1)}{2}$
• Time: $O(n^2)$

Average Case — Random Array:

• On average, each element is compared with half the sorted portion
• Total: $\frac{1}{2}(1 + 2 + … + (n-1)) = \frac{n(n-1)}{4}$
• Time: $O(n^2)$