Problem Solving

Topic 1: Problem Solving

Problem solving is the cornerstone of computer science. It involves systematically breaking down a challenge into manageable parts and developing a clear, logical solution that a computer can execute. This process is guided by the principles of computational thinking.

#### Computational Thinking

Computational thinking is a set of problem-solving methods that involve expressing problems and their solutions in ways that a computer could execute. The key pillars for this syllabus are:

* Decomposition: This is the process of breaking down a large, complex problem into smaller, more manageable sub-problems. Each sub-problem can then be solved individually. For example, creating a school management system can be decomposed into modules for student registration, fee collection, exam reporting, and timetable management. Solving each module is much simpler than tackling the entire system at once.

* Abstraction: This involves removing unnecessary detail and focusing only on the essential characteristics of a problem. It's about hiding complexity to make things easier to think about. When you use a ride-hailing app like Careem or Uber, you abstract away the complexity of GPS tracking, driver allocation algorithms, and payment processing. You simply provide a pickup and drop-off location and the app handles the rest.

#### Representing Algorithms

An algorithm is a finite sequence of well-defined, step-by-step instructions designed to perform a specific task or solve a problem. We use two main tools to design and represent them:

1. Flowcharts

A flowchart is a visual representation of an algorithm's logic. It uses standard symbols to show the sequence of operations and the flow of control.

* Oval (Terminator): Represents the Start or End point of the algorithm.

* Parallelogram (Input/Output): Used for any operation that involves inputting data (e.g., from a keyboard) or outputting information (e.g., to a screen).

* Rectangle (Process): Denotes any processing step, such as a calculation (`total = price * quantity`) or assigning a value to a variable.

* Diamond (Decision): Represents a point where a decision must be made, typically a yes/no or true/false question (e.g., `Is age > 18?`). It will have at least two arrows leading out of it.

* Arrow (Flow Line): Connects the symbols and indicates the direction of flow.

2. Pseudocode

Pseudocode is a way of describing an algorithm using structured English-like statements. It is not a real programming language, so it has no strict syntax rules, but we use common keywords for clarity and consistency.

* INPUT/READ: Get data from the user.

* OUTPUT/PRINT: Display information.

* SET/STORE: Assign a value to a variable (e.g., `SET score TO 0`).

* IF...THEN...ELSE...ENDIF: Conditional statements for making decisions.

* WHILE...ENDWHILE: A loop that continues as long as a condition is true.

* FOR...ENDFOR / FOR...NEXT: A loop that repeats a set number of times.

#### Standard Algorithms

Searching Algorithms

* Linear Search: This is the simplest search method. It sequentially checks each element in a list until a match is found or the entire list has been checked. It works on unsorted data. Its efficiency is O(n), meaning in the worst case, it has to check every single item.

* Binary Search: A much more efficient method, but it has a critical requirement: the data must be sorted. It works by repeatedly dividing the search interval in half.

1. Compare the target value with the middle element of the list.
2. If they match, the search is over.
3. If the target is less than the middle element, discard the upper half of the list.
4. If the target is greater, discard the lower half.
5. Repeat until the value is found or the interval is empty.

This 'divide and conquer' approach gives it a very efficient time complexity of O(log n).

Sorting Algorithms

* Bubble Sort: This algorithm repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. Passes through the list are repeated until no swaps are needed, indicating the list is sorted. It is very simple to understand but highly inefficient for large datasets, with a time complexity of O(n²).

* Merge Sort: Another 'divide and conquer' algorithm. It is significantly more efficient than Bubble Sort.

1. Divide: Recursively split the list into two halves until you are left with sub-lists containing only one element (which are inherently sorted).
2. Conquer: Merge the sub-lists back together in the correct order. Pairs of single-element lists are merged to form sorted two-element lists, which are then merged, and so on, until the entire list is sorted.

Its efficiency is O(n log n), making it suitable for large datasets, such as sorting the final exam results for a BISE (Board of Intermediate and Secondary Education) to determine merit positions.

#### Testing and Verification

Trace Tables

A trace table is a tool used to manually test the logic of an algorithm step-by-step. It consists of a table where each column represents a variable (or a condition), and each row represents a step in the algorithm's execution. By tracking the state of each variable, you can find logical errors and verify that the algorithm behaves as expected. This is a very common exam task.

*Exam Trap: * A common mistake with binary search is forgetting the pre-condition that the data must be sorted. If an exam question asks you to perform a binary search on an unsorted list, the correct first step is to state that the list must be sorted first, or that the algorithm cannot be applied as is.