Unit 2: Computational Thinking & Algorithms
wn big problems into smaller parts and come up with step-by-step solutions that a computer or a person can follow.
CT isn’t just about coding; it’s a basic skill useful in any area. It involves mental tools and strategies to think more clearly, logically, and creatively.
Key concepts often associated with CT: Decomposition, Pattern Recognition, Abstraction, Algorithm Design (see Fig.2.1: Computational Thinking).
A computing problem in computer science is one that is solved step-by-step through computation. It usually has:
a well-defined input, and
an output that must satisfy certain properties.
Examples of computing problems include:
Finding the largest number in a list.
Checking if a number is even or odd.
Simulating a scientific phenomenon.
Major problem domains in CT:
Decision Problems (yes/no questions, e.g., is n even?)
Search Problems
Counting Problems
Example of a decision problem: “is n prime?” (requires more work than parity checks).
Example of a search problem: finding a route on a map from one site to another (e.g., Islamabad to Lahore).
Example of a counting problem: determining how many routes exist between two sites given a set of possible roads.
2.2 Basics of Counting Problems
Counting problems often use tree-based structural approaches to represent options as branches.
The foundation of counting is to consider the options available to select items for a given selection.
Tree representations help visualize choices and their combinations.
2.3 Basic Counting Principles
Addition Principle (sum rule): used when you have mutually exclusive events.
Total Possibilities = Number of Possibilities for Event A + Number of Possibilities for Event B + … + Number of Possibilities for Event N
Symbolically: ext{Total} =
\sum{i=1}^{N} Ni.Example: A student has 3 desktop computers and 4 laptops. Total options = 3 + 4 = 7.
Multiplication Principle (product rule): used when you select one option from each of several events.
If Event A has A options, Event B has B options, Event C has C options, then total options = A \times B \times C.
Example: If Bilal has 3 apples, 3 bananas, and 3 cherries, the number of different fruit baskets is 3 \times 3 \times 3 = 27.
Permutations: number of ways to arrange objects in order.
Example: 4 paintings and 3 places on a wall to display, choosing 3 paintings in order yields:
Total permutations = 4 \times 3 \times 2 = 24. (In general, P(n,r) = \frac{n!}{(n-r)!}.)
Combinations: number of ways to choose items where order does not matter.
Example continuation from permutations: choosing 3 out of 4 paintings without regard to order yields:
C(4,3) = \frac{4!}{3!(4-3)!} = \frac{24}{6} = 4.
Pigeonhole Principle: if n boxes and n+1 objects are placed into these n boxes, at least one box contains more than one object.
Example: If you have 13 apples and 12 baskets, at least one basket contains more than one apple.
Inclusion and Exclusion Principle: to count the size of the union of overlapping sets by adding sizes of sets and subtracting overlaps.
General form: |A \cup B| = |A| + |B| - |A \cap B|. For three sets: add sizes of all sets, subtract pairwise intersections, then add back triple intersection.
Example: How many binary strings of length 8 have either the last two bits "00" or begin with a "1"?
|A| (end with 00) = 2^{6} = 64.
|B| (begin with 1) = 2^{7} = 128.
Intersection (begin with 1 and end with 00) = 2^{5} = 32.
Total = 64 + 128 - 32 = 160.$$
2.4 Algorithms and their Characteristics
An algorithm is a well-defined, step-by-step procedure or set of rules for solving a specific problem or performing a task.
Algorithms in computer science are expressed in various forms: programming languages, flowcharts, pseudocode, or natural language.
Properties of algorithms:
Input: An algorithm can have one or more externally supplied inputs.
Output: The result of the computation; at least one output is produced.
Definiteness: Every step must be clearly and unambiguously stated.
Finiteness: There must be a finite number of steps; the algorithm must terminate.
Effectiveness: Each operation must be simple enough for a human to perform with paper and pencil in a reasonable time.
Generality: The algorithm should handle a family of problems, not just a single instance.
Critical roles of algorithms in computational problem solving:
They provide a clear, repeatable set of instructions to follow before coding.
They are designed to be efficient in time and space.
They automate repetitive and tedious tasks.
They help analyze and decompose complex problems into manageable steps.
Once designed and tested, they can be reused for similar problems.
They provide precise and accurate solutions and form the foundation of programming and software development.
Algorithm applications include:
Sorting and Searching (e.g., quicksort, mergesort, binary search).
Graph Algorithms (e.g., shortest paths like Dijkstra’s algorithm).
Cryptography (encryption/decryption for privacy and security).
Machine Learning (decision trees, neural networks).
Image Processing (enhancement, compression, analysis in medical imaging, computer vision, multimedia).
2.5 Logical Reasoning
Logical reasoning is central to algorithm development and CT:
Problem Decomposition: break large problems into smaller parts.
Pattern Recognition: identify patterns and similarities to form general solutions.
Abstraction: focus on pertinent information, ignore extraneous details.
Algorithm Design: create step-by-step procedures to ensure accuracy and effectiveness.
Boolean Logic: statements can evaluate to true or false.
Operators: AND, OR, NOT, etc.
Truth values commonly represented as 1 (true) and 0 (false).
Example visualization (truth tables) for AND, OR, NOT (A, B, A AND B, A OR B, NOT A).
Logical Reasoning Types:
Verbal reasoning questions (solutions stated in language).
Non-verbal reasoning questions (solutions presented via figures, pictures, or diagrams).
Example problems:
Color logic puzzle: Aiza, Uzair, and Luqman have different favorite colors; use clues to deduce each color.
Pattern sequencing: determine the next shape in a repeating sequence (Square, Triangle, Circle, Square, Triangle, Circle, …); the next shape is Circle.
2.6 Standard Algorithms
Standard algorithms are fundamental methods used to solve common problems.
Sorting Algorithms:
Bubble Sort: repeatedly traverse the list, compare adjacent elements, and swap if out of order.
Selection Sort: repeatedly select the smallest (or largest) element from the unsorted portion and move to the sorted portion.
Merge Sort: divide the list into halves, recursively sort each half, then merge.
Insertion Sort: build the sorted array one element at a time by inserting each new element into its correct position.
Searching Algorithms:
Linear Search: check each element sequentially until found or end.
Binary Search: on sorted arrays; repeatedly divide the search interval in half.
2.7 Steps in algorithm to A, B, C, D
The material presents a visual set of steps (A, B, C, D) for illustrating algorithm flow. No explicit textual content is provided here beyond the visual cue.
2.8 Abstraction
Abstraction is focusing on the core idea and ignoring non-essential details to simplify problem-solving.
Common abstractions:
Maps: focus on roads and landmarks, ignore minor details like trees or houses.
Symbols: treat apps as icons rather than their underlying code.
Models: use architectural models to communicate design without detailing every component.
Abstraction in computing contexts:
Programming Variables: represent data abstractly rather than using concrete constants.
Functions: reusable built-in or user-defined units with a name; the internal steps are abstracted away.
Object-Oriented Programming (OOP): represent real entities as objects to hide internal implementation details.
Example: Steps to Make a Cup of Tea (abstracted process):
Boil water.
Put tea bag into the cup.
Fill the cup with boiled water.
Remove tea bag.
Add sugar (optional).
Add milk (optional).
Stir for a moment; tea is ready.
2.9 Creating Generalized Solutions
Generalized solutions aim to handle a broad class of problems, not just a specific instance.
Steps to create generalized solutions:
Identify the Core Problem: extract essential common components across specific cases.
Extract Common Patterns: find recurring elements across cases.
Develop a Generic Solution: use variables instead of constants to test various inputs.
Test with Different Scenarios: validate the solution with a range of inputs and refine as needed.
Examples:
Sorting Algorithms: Specific case – Bubble Sort; Generalized solution – Quick Sort, Merge Sort, Heap Sort; end results are sorting the list.
Area calculations: Specific case – rectangle area = length × width; Generalized solution – compute area for various shapes (rectangle, circle, triangle) via a function that handles different shapes and parameters.
2.10 Modular Design
Modular design breaks a system into smaller, interchangeable parts (modules).
In programming, modules are often functions or methods that perform specific tasks. In OOP, classes and objects implement modular design.
Examples:
Python: a function to calculate the area of a rectangle.
Web development: modular design via components and services.
Steps to implement modular design:
Define Modules: divide the problem into subproblems with core problems to be handled.
Design Interfaces: define how modules interact, including input/output specifications.
Implement Modules: implement each module according to its algorithmic steps and interfaces.
Integrate Modules: combine modules to form the complete solution; ensure proper interaction via interfaces.
Test Modules: perform module testing and complete system testing.
2.11 Algorithm Dry Run
An algorithm dry run is a manual execution with a specific input to verify correctness and understand behavior.
Steps for a dry run:
Choose an Input: select a specific set of input values.
Simulate Execution: perform each step manually, track variable states.
Observe Output: note the final output after all steps.
Compare with Expected Result: if it matches, the algorithm is correct; otherwise, review steps.
Example: Dry run of an algorithm to find the largest number in a list [3, 1, 4, 1, 5, 9, 2, 6].
Algorithm steps (illustrative):
max = 3 (initial)
Compare 1 with 3 → max remains 3
Compare 4 with 3 → max becomes 4
Compare 1 with 4 → max remains 4
Compare 5 with 4 → max becomes 5
Compare 9 with 5 → max becomes 9
Compare 2 with 9 → max remains 9
Compare 6 with 9 → max remains 9
Final result: max = 9.
Trace Table concept: records values of variables at each step; an example trace shows the evolution of max from 3 up to 9 as iterations proceed.
2.12 Errors
Types of errors in problem solving and programming:
Syntax Errors: mistakes in the structure of an expression or statement (like grammatical errors in writing).
Logical Errors: mistakes in reasoning or planning that lead to incorrect conclusions or results.
Example: A search engine query like "Best smartphones for college students under 500" may return irrelevant results due to logical and/or syntax issues in specifying the criteria (e.g., including used phones or omitting currency).
Remedies: refine the query to be clear and precise (e.g., "Best new smartphones for college students under PKR 500").
2.13 Unit Summary
Computational Thinking is a problem-solving approach using computer science ideas.
A computing problem is solved step-by-step through computation.
Decision problems typically have yes/no outcomes; search problems involve satisfying a set of criteria; counting problems involve counting the number of solutions.
The Addition Principle and Multiplication Principle are foundational counting rules.
A permutation is an ordered arrangement of items; a combination is a selection where order does not matter.
The Pigeonhole Principle states that if more items than containers exist, some container must contain more than one item.
Inclusion–Exclusion helps count the size of unions of overlapping sets.
An algorithm is a well-defined, step-by-step procedure for solving a problem, with properties such as input, output, definiteness, finiteness, effectiveness, and generality.
Sorting and Searching are core algorithmic tasks; examples include Bubble Sort, Selection Sort, Merge Sort, Insertion Sort, Linear Search, and Binary Search.
Boolean Logic uses true/false values with operators like AND, OR, NOT.
Logical reasoning underpins algorithm design, including decomposition, pattern recognition, abstraction, and algorithm design.
Abstraction helps simplify problems by focusing on essential ideas and ignoring details.
Generalized solutions enhance efficiency, scalability, and reusability by using core problem understanding and pattern extraction.
Modular design promotes breaking a system into reusable modules with well-defined interfaces and integrated testing.
Dry runs and trace tables are essential tools to validate algorithms before implementation.