Class 12 Computer Unit 2 Computer Thinking and Algorithm | FBISE Federal Board | Read and Download

Class 12 Computer Science – Unit 2: Computational Thinking & Algorithms (FBISE)

Welcome to the comprehensive study resource for Class 12 Computer Science Unit 2, aligned with the latest Federal Board (FBISE) curriculum. This unit is the foundation of efficient programming and software development.

Our notes cover critical concepts including Algorithm Design, Big O Notation, Linear and Binary Search, and Advanced Data Structures like Linked Lists, Stacks, Queues, and Trees. We focus on both theoretical understanding and practical problem-solving to help you ace your board exams.

Enhance your learning with our solved MCQs, step-by-step algorithm traces, and complexity analysis. Join our community for live sessions and exam updates.

▶ Watch Video Lectures 💬 Join WhatsApp Community

The Four Core Pillars of CT

• Decomposition: Dividing a large problem into smaller, simpler parts.
• Pattern Recognition: Finding trends or similarities to make tasks easier to manage.
• Abstraction: Focusing only on necessary information while ignoring unimportant details.
• Algorithm Design: Creating a step-by-step set of instructions to solve the problem.

Advanced Application of CT

• Design: Creating effective and efficient solutions.
• Analysis: Evaluating solutions based on their clarity, correctness, and efficiency.
• Integration: Combining CT with data structures to build optimized and scalable results.

---

Data Structures

A data structure is a specific way of organizing and storing data so it can be accessed and changed efficiently. They provide the framework for how computer programs manage information.

Key Characteristics and Impacts

• Memory Arrangement: They determine how data is placed in a computer's memory.
• Performance: The choice of structure directly affects the speed of operations like inserting, deleting, and retrieving data.
• Solution Quality: Understanding data structures is essential for determining how well a computational solution performs.

Common Examples and Use Cases

• Arrays: Used for quick access to elements via an index.
• Linked Lists: Used for flexible, dynamic data manipulation.
• Other Structures: Stacks, queues, trees, and graphs are chosen based on the specific needs of an application.

---

Deep Dive: Arrays

Definition and Core Concept

• Arrays: The simplest data structure in programming used to store elements of the same size.
• Memory Storage: Elements are stored in contiguous memory locations (side-by-side).
• Identification: Each memory location is identified by a unique index (note: usually treated as a string or integer depending on implementation).

Efficiency and Advantages

• No Metadata: Arrays are efficient because they do not require additional data to store elements.
• Fast Access: Because memory locations are contiguous, accessing specific elements is very fast.

Limitations and Disadvantages

• Fixed Size: The size of an array must be declared at the start and cannot be easily changed.
• Costly Resizing: Changing the size requires creating a new, larger array and shifting all elements.
• Homogeneous Data: Arrays are not suitable for storing elements of different types.

Types of Arrays

1. One-Dimensional (1-D) Array

Elements of the same type are stored in a single list. Accessed using a single index.

2. Two-Dimensional (2-D) Array

Also known as a matrix, where elements are stored in a table format. Accessed using two indexes: the row and the column.

2.1.2. Linked Lists

Linked lists are basic data structures where elements, called nodes, are connected via pointers.

Node Components

• Data: The actual value stored in the node.
• Next Node: A reference or memory address for the next node in the sequence.

Key Advantages

• Efficient Operations: Insertion and deletion are easier compared to arrays and can be done at any position.
• Dynamic Size: They do not require a pre-specified size; they can grow and shrink as needed.

---

Singly Linked List

The most basic type of linked list where each node maintains two specific parts: Data and Next.

• The "Head" Node: The first node in the sequence.
• The "NULL" Pointer: The last node contains NULL because it does not refer to any subsequent node.

Doubly Linked List

A more complex version that allows traversal in both directions (forward and backward).

• Prev: Reference to the previous node.
• Data: The value to be stored.
• Next: Reference to the next node.
• Note on Nulls: Both the first node (prev) and the last node (next) contain NULL.

Circular Linked List

A special type of list where all nodes form a continuous loop.

• Core Characteristic: The last node points back to the first node instead of NULL.
• Traversal: A traversal never naturally reaches an end.

---

2.1.3. Stacks

Stacks follow the LIFO (Last-In, First-Out) principle. The most recently added element is the first one to be removed.

Key Operations

Operation	Description
Push	Adds a new element to the top.
Pop	Removes the element from the top.
Top	Returns the top element without removing it.
IsEmpty / IsFull	Checks the capacity status of the stack.

---

2.1.4. Queues

Queues follow the FIFO (First-In, First-Out) principle. The first element added is the first one to be removed.

Key Operations

• Enqueue: Adds a new element to the end (back/tail/rear).
• Dequeue: Removes the element at the start (front/head).
• Front: Returns the start element without removing it.

---

2.1.5. Graphs

A data structure consisting of nodes (vertices) connected by edges. Used to model networks like social media and routing.

Primary Types

• Connected Graph: A path exists between every pair of nodes.
• Directed Graph: Edges have a specific direction (arrows) associated with them.

2.1.6. Trees

A hierarchical data structure where each node contains a value and references (pointers) to its children.

Key Terminology

• Root: The top-most node of the tree.
• Parent/Child: Directly connected nodes where the higher node is the parent.
• Leaf Node: A node with no children (the "ends" of the branches).
• Subtree: A portion of the tree that can be viewed as a complete tree itself.

Common Examples: OS directory structures (folders) and HTML DOM tag structures.

Basic Operations

• Insertion: Adding a node at a specific location.
• Deletion: Removing a node.
• Search: Finding a specific node within the hierarchy.
• Traversal: Visiting all nodes in a systematic order.

---

Tree Traversal Methods

Used to visit all nodes in a tree for different purposes, such as searching, deleting, or sorting.

Method	Sequence	Primary Usage
In-Order	Left $\rightarrow$ Root $\rightarrow$ Right	Used with Binary Search Trees to visit nodes in ascending order.
Pre-Order	Root $\rightarrow$ Left $\rightarrow$ Right	Useful when you need to process the root before its children (e.g., cloning a tree).
Post-Order	Left $\rightarrow$ Right $\rightarrow$ Root	Used for deleting nodes or freeing memory (processing children before parents).

---

2.1.7. Data Structures & Computational Thinking

Mastering these structures is essential for efficient algorithm design and involves three core principles:

• Problem Decomposition: Breaking down complex problems into manageable parts.
• Efficiency: Balancing trade-offs (e.g., access time vs. insertion time) to choose the right tool for a task.
• Algorithmic Thinking: Using structures to improve problem-solving and analyze performance.

---

3.1. Algorithm Evaluation

1. Correctness

An algorithm is correct if it produces the expected output for all valid inputs. Developers verify this through:

• Multiple Scenarios: Testing with various search keys or arrays of different sizes.
• Edge Cases: Testing extreme scenarios, such as an empty array or an array with only one element.

Examples:

• Sorting: Bubble Sort is correct if it consistently turns [5, 2, 9, 1] into [1, 2, 5, 9].
• Searching: Binary Search is correct if it returns the exact index of the target key.

2. Clarity

Clarity refers to how logically structured and understandable an algorithm is to humans.

• Descriptive Naming: Using names like factorial instead of fct.
• Logical Ordering: Ensuring steps follow a clear, predictable sequence.
• Documentation: Using comments to explain the code's purpose.

3. Efficiency

Efficiency measures how well an algorithm utilizes computer resources, specifically Time and Memory. It is usually expressed using Big O notation, which describes the "worst-case scenario" or the upper bound of resource usage.

Types of Complexity

• Time Complexity: Estimating execution time relative to the input size ($n$).
• Space Complexity: Measuring the amount of memory used relative to the input size ($n$).

Common Big O Notations

Notation	Name	Description
$O(1)$	Constant Time	Execution time stays the same regardless of input size.
$O(\log n)$	Logarithmic Time	Execution time increases slowly; search space is halved each step.
$O(n)$	Linear Time	Execution time grows at the same rate as the input.
$O(n \log n)$	Linearithmic Time	Common in efficient sorting algorithms like Merge Sort.
$O(n^2)$	Quadratic Time	Time increases dramatically (doubling input quadruples time).

---

Binary Search Algorithm

A highly efficient search algorithm for sorted lists that repeatedly divides the search interval in half.

Algorithm Steps

1. Examine the Center: Look at the number in the middle of the list.
2. Check for Match: Determine if this middle number is the target value.
3. Identify Success: If the numbers match, the search is complete.
4. Search Left/Right: If the target is smaller, repeat on the left half; if larger, repeat on the right half.
5. Repeat: Continue until the number is found or the list is exhausted.

Complexity Analysis

• Time Complexity: $O(\log n)$ – The search space is divided in half at every step.
  • Step 1: $n/2$ remaining
  • Step 2: $n/4$ remaining
  • Step $k$: $n/2^k$ remaining. Total steps $\approx \log_2(n)$.
• Space Complexity: $O(\log n)$ (Recursive) – Each recursive step adds a new frame to the stack, proportional to the number of times the problem is halved.

---

Linear Search Algorithm

A method used to find a target value within an array by examining each element sequentially from start to finish.

Process

• Start at the beginning of the array.
• Examine and compare each element one by one.
• Completion: Ends when the target matches an element.
• Failure: Ends when the array is exhausted without a match.

Complexity Analysis

• Time Complexity: $O(n)$ – Operations increase linearly; in the worst case, every element must be checked.
• Space Complexity: $O(1)$ – Uses a constant amount of extra space regardless of array size.

Case Study 1: Greatest Common Divisor (GCD)

Problem: Find the greatest common divisor of two integers using the Euclidean Algorithm.

Process

1. Take two integers $a$ and $b$ (where $a \ge b$).
2. While $b$ is not zero:
   • Set $a$ to $b$.
   • Set $b$ to $a \pmod b$ (the remainder).
3. When $b$ reaches zero, $a$ is the GCD.

Evaluation

• Efficiency: Time Complexity is $O(\log \min(a, b))$; Space Complexity is $O(1)$.
• Clarity: A simple, elegant iterative process.
• Correctness: Based on the mathematical properties of division and remainders.

---

Case Study 2: Count Vowels in a String

Problem: Count the number of vowels ('a', 'e', 'i', 'o', 'u') in a given string using Simple Iteration.

Process

1. Initialize a counter to zero.
2. Iterate through every character in the string.
3. Check if the character is a vowel.
4. If yes, increment the counter.
5. The final counter value is the total number of vowels.

Evaluation

• Efficiency: Time Complexity is $O(n)$; Space Complexity is $O(1)$ (uses one variable).
• Clarity: Involves basic iteration and conditional checks.
• Correctness: Accurately counts vowels by evaluating every character.

---

Quiz Dashboard: Practice MCQs

Question	Answer	Explanation
What defines a data structure?	b. Storing/organizing data	Formats for organizing, processing, and retrieving data.
Structure for dynamic memory and easy insertion?	c. Linked List	Can grow/shrink during execution without shifting elements.
What does a singly linked list node contain?	c. Data and address of next node	Consists of a data value and a pointer to the next node.
Advantage of a doubly linked list?	c. Traversal in both directions	Nodes have pointers to both "next" and "previous" nodes.
List that connects last node to first?	b. Circular linked list	The tail node's next pointer points back to the head.
Operation to remove top element of a stack?	c. Pop	"Push" adds, "Pop" removes from the top.
Which tree node has no children?	b. Leaf node	The terminal node at the end of a branch.
Which structure follows LIFO?	b. Stack	Last-In, First-Out (like a pile of plates).
Which algorithm is used for sorting?	a. Quick Sort	A popular divide-and-conquer sorting algorithm.
Example of a Greedy Algorithm?	b. Huffman Coding	Repeatedly chooses smallest frequencies to build a tree.
Space complexity of (Iterative) Binary Search?	a. $O(1)$	Uses constant extra space regardless of input size.
Allows random access by index?	c. Array	Uses contiguous memory for direct indexing.
Separating marks and assigning grades step?	d. Algorithm Design	Developing step-by-step instructions to solve a problem.
Time complexity of Linear Search?	c. $O(n)$	In the worst case, every single item must be checked.
Best use of CT for traffic signals?	b. Flowchart of signal timing	Systematic logic represented via flowcharts.

Short Question Answers: Problem Solving & Evaluation

Problem 1: Finding the Sum of Digits

Solution: Digit Extraction and Summation

• Algorithm:
  1. Initialize sum = 0.
  2. While the number $n > 0$:
     • Get the last digit using n % 10 and add it to sum.
     • Remove the last digit using integer division n = n // 10.
  3. Return sum.
• Efficiency:
  • Time Complexity: $O(d)$, where $d$ is the number of digits in the integer (logarithmic relative to the value of $n$).
  • Space Complexity: $O(1)$, as it only requires a few variables regardless of input size.
• Clarity: High. The logic follows a standard mathematical decomposition of numbers.
• Correctness: Correct for all non-negative integers. For negative integers, the absolute value should be taken first.

---

Problem 2: Finding the Factorial of a Number

Solution: Iterative Approach

• Algorithm:
  1. Initialize result = 1.
  2. If $n$ is 0 or 1, return 1.
  3. Loop from $i = 2$ to $n$: Update result = result * i.
  4. Return result.
• Efficiency:
  • Time Complexity: $O(n)$, as the loop runs exactly $n$ times.
  • Space Complexity: $O(1)$, uses a single variable to accumulate the product.
• Clarity: Very High. Straightforward and avoids stack overflow risks associated with recursion.
• Correctness: Mathematically sound for all non-negative integers; handles the base case ($0! = 1$) correctly.

---

Problem 3: Finding the Largest Number in a List

Solution: Linear Scan

• Algorithm:
  1. Assume the first element is the max.
  2. Iterate through the remaining elements of the list.
  3. If the current element is greater than max, update max.
  4. Return max after checking all elements.
• Efficiency:
  • Time Complexity: $O(n)$, where $n$ is the number of elements.
  • Space Complexity: $O(1)$, as it only stores one "current maximum" value.
• Clarity: Excellent. Mimics how a human naturally scans a list for the highest value.
• Correctness: Correct for any non-empty list.

---

Problem 4: Checking for Prime Numbers

Solution: Simple Divisibility Test

• Algorithm:
  1. If $n \leq 1$, return False.
  2. Loop from $i = 2$ to $\sqrt{n}$ (the square root of $n$).
  3. If $n$ is divisible by $i$ (n % i == 0), return False.
  4. If the loop finishes, return True.
• Efficiency:
  • Time Complexity: $O(\sqrt{n})$, significantly more efficient than checking up to $n$.
  • Space Complexity: $O(1)$.
• Clarity: High. Directly applies the fundamental definition of primality.
• Correctness: Correct. Accurately identifies primes by confirming no divisors exist.

---

Problem 5: Finding the Average of a List

Solution: Summation and Division

• Algorithm:
  1. Initialize total_sum = 0.
  2. Iterate through each number in the list and add it to total_sum.
  3. Count the total number of elements (count).
  4. Divide total_sum by count.
• Efficiency:
  • Time Complexity: $O(n)$, as each element must be visited once.
  • Space Complexity: $O(1)$, only stores sum and count.
• Clarity: Very High. Follows the standard mathematical formula for arithmetic mean.
• Correctness: Correct for non-empty lists (requires a check for count > 0 to avoid division by zero).