FSc Part 1 Computer Science Chapter 3 Complete Guide Book — Algorithms and Problem Solving

Look at an ordinary day and you will see problems everywhere: finding the highest marks in a class list, deciding whether a number is even, or working out the shortest way home. A computational problem is simply a problem of this kind that can be handed to a computer — a challenge that can be solved through a computational process, using an algorithm, which is a set of step-by-step instructions a computer can actually carry out.

Every computational problem has the same three parts, and naming them before you start is half the work. The input is the data given at the beginning. The process is the set of steps or rules — the algorithm itself — applied to that input. The output is the result produced after processing. Take the class-marks problem: input, the list of marks; process, compare the marks one by one and keep the biggest seen so far; output, the highest mark. If any one of these three is unclear, the computer cannot be told what to do, and that is usually where a student gets stuck — not in the coding, but in the thinking before it.

📌 Book note: the chapter opens with this input–process–output idea because everything that follows — sorting, searching, even the hardest problems in the chapter — is just this same pattern dressed up in different clothes.

To solve a problem computationally, the book says, you first have to characterise it: identify its inputs, its desired outputs, and the process that turns one into the other. Once that is clear, problems fall into four handy families. A decision problem answers with a simple “yes” or “no” — is this number even? A search problem asks you to find an item or a solution that meets certain criteria — find the student named Ahmed in this list. An optimization problem asks for the best solution by some measure — the shortest route, the cheapest ticket. And a counting problem asks how many ways certain conditions can be met — in how many ways can these books be arranged?

Problems can also be sorted by how clearly they are defined. A well-defined problem has a clear goal, clear inputs, a clear process and a clear output. The book's own example is deciding whether a number is even: goal, decide even or odd; input, one integer; process, check whether it is divisible by 2; output, “even” or “odd”. An ill-defined problem lacks clear definitions and has vague or ambiguous goals. The book's example is a project aimed at “how to reduce poverty in Pakistan” — a huge, vague goal with no single input, no single process and no single answer to check. The lesson is practical: if your problem reads like the second kind, your first job is not to code, but to sharpen it until it reads like the first.

⚠️ Book slip (numbering): the book prints “3.1.1” twice — once for “Characterizing” and again for “Classifying”. The second one is really subsection 3.1.1.1; nothing in the content changes, only the number is repeated.

An algorithm is a step-by-step procedure for solving a problem — the book compares it to a recipe, which gives steps for cooking a dish. Understanding algorithms matters because they supply the logic behind software: they let us solve complex problems, improve performance, and be sure of accuracy in all kinds of applications. A recipe that says “cook until done” without saying how long or at what heat is a bad recipe; an algorithm with a missing or vague step is a bad algorithm in exactly the same way. As a bit of colour, the book notes that Google's search engine uses a complex algorithm called PageRank, which weighs the number of links to a page and the quality of those links to rank search results.

One very general way of solving a problem is the Generate-and-Test method: generate a possible solution, test whether it meets the required conditions, and keep going until a satisfactory solution is found or every possibility has been exhausted. It is especially useful when the problem space is small enough to try everything, when there is no clear strategy for finding a solution directly, or when heuristics — rough rules of thumb — can cut down the number of candidates so the search stays feasible. Watch it work on a tiny problem: find a number between 10 and 20 that is divisible by both 3 and 4. Generate 10 — test: divisible by 3? No. Generate 11 — no. Generate 12 — divisible by 3 (12 ÷ 3 = 4) and by 4 (12 ÷ 4 = 3), so it passes, and we stop. The book also notes that this method is common in artificial-intelligence applications such as game playing, where trying out possibilities until one works is often the only sensible approach.

Before asking how fast a problem can be solved, ask whether it can be solved at all. A problem is solvable if an algorithm can solve it within a finite amount of time: it has clearly defined inputs and outputs, and there is a step-by-step procedure that reaches the solution. The book's classic example is the greatest common divisor (GCD) of two integers, solved by the Euclidean algorithm. Work it out for 48 and 18, step by step: 48 = 2 × 18 + 12, so the remainder is 12. Then 18 = 1 × 12 + 6, remainder 6. Then 12 = 2 × 6 + 0, remainder 0 — and the moment the remainder hits 0, the last non-zero remainder, 6, is the GCD. Finite steps, definite answer, no guessing: that is what solvable looks like.

An unsolvable problem is one for which no algorithm can provide a solution in all cases — there is no general procedure that guarantees an answer for every possible input. The famous example is the Halting Problem: deciding whether a given program will eventually halt (finish running) or run forever. Alan Turing proved that no general algorithm can solve it for all program–input pairs. The book states this result without the proof, so here is the idea in simple words (an elaboration, not a book passage): suppose a checker program H could always tell us “this program halts” or “this program loops forever”. Now build a mischievous program that asks H about itself and then does the opposite — if H says “it halts”, it loops forever; if H says “it loops”, it stops at once. Whatever H says about this program is wrong, so H cannot exist. The book's practical tip is worth remembering: before throwing time and resources at a hard problem, first check that it is solvable at all.

Once a problem is known to be solvable, the next question is how efficiently it can be solved — and here problems split into tractable and intractable ones, depending on the resources (time and space) they need. A problem is tractable if it can be solved in polynomial time, written as P: the time grows at a manageable rate, like a polynomial function, as the input grows. The book calls these “efficiently solvable”, and gives sorting a list with Merge Sort or Quick Sort, at O(n log n), as the example — double the list and the work grows, but only by a sane amount.

Intractable problems need super-polynomial time, often growing exponentially with the input, so they become impractical for large inputs even though they are solvable in principle. The book's example is the Travelling Salesman Problem (TSP): find the shortest route that visits a set of cities and returns to the start. The number of possible routes grows factorially with the number of cities. Count it yourself: with 5 cities there are (5 − 1)! ÷ 2 = 12 different tours; with 10 cities, 181,440; with 20 cities, about 60,000,000,000,000,000 tours. No computer can try them all for a big city list, which is why TSP is called intractable — and, as the book adds, NP-hard. The practical point is not to give up, but to change the goal: for such problems we usually accept a very good route found quickly instead of demanding the perfect one.

Complexity classes are boxes into which problems are sorted by how hard they are to solve and to check. Class P holds problems a computer can solve efficiently, quickly even as the problem grows. The book's example is sorting: take [4, 1, 3, 2, 5] and arrange it in ascending order to get [1, 2, 3, 4, 5]. Going from 5 numbers to 10 numbers takes more time, but it stays within a reasonable limit — that manageable growth is the whole idea of P.

Class NP is subtler, and students often misread it: NP does not mean “non-polynomial”. It means that if a solution is given to you, a computer can check it quickly, even though finding it might be difficult and time-consuming. The book's example is Sudoku: filling a 9 × 9 grid so every row, column and 3 × 3 box contains the digits 1 to 9 exactly once can take a long search, but once someone hands you a completed grid, checking each row, column and box is quick, mechanical work. NP-hard problems are at least as difficult as the hardest problems in NP, and no efficient algorithm is known for them — the Travelling Salesman Problem from the last section is the book's example. NP-complete problems are the special subset that sit inside NP and are as hard as the hardest NP problems, so solving one of them efficiently would let you solve all NP problems efficiently. The book's classic example is the Knapsack Problem: a bag with a maximum weight capacity, and items each with a weight and a value — choose the most valuable combination without exceeding the capacity. Try it: capacity 10 kg, items A (5 kg, value 10), B (4 kg, value 9), C (6 kg, value 12), D (3 kg, value 5). Check the promising pairs: A + B = 9 kg, value 19; B + C = 10 kg, value 21; A + C = 11 kg, over capacity; C + D = 9 kg, value 17. The winner is B + C at value 21. With four items you can check by hand; with forty, the checking explodes — and that is exactly the NP-complete feeling. Finally, the book notes that whether P equals NP is one of the most important unsolved problems in computer science, with big implications for cryptography and algorithm design.

Algorithm analysis means working out the computational complexity of an algorithm — its time and space complexity — so you can predict its performance and pick the best algorithm for a particular task. Time complexity measures how the running time grows as the size of the input data grows. Sorting five numbers is quick whatever you do; sorting five million is a different story, and time complexity is what lets you predict that story before you run anything.

Big O notation is the mathematical way of describing time complexity. It gives an upper bound on the time an algorithm will take as the input size grows — roughly, how bad things can get — and it lets you compare algorithms at a glance. Four cases carry the whole chapter. O(1), constant time: the runtime stays the same whatever the input size — for example, reading the first element of a list. O(n), linear time: the runtime grows in step with the input size. The book's example: n students, each with a unique ID, and you search through the list for one student — the time depends on how many students there are. O(n²), quadratic time: the runtime grows with the square of the input size. The book's example is comparing every student with every other student to pick the best team. ⚠️ Book slip, corrected here: the book says the number of comparisons “can be approximated as n(n − 1)”; the exact number of pairs is n(n − 1) ÷ 2. The order is still quadratic, so the Big O conclusion is unchanged, but the count itself is off by a factor of 2. O(log n), logarithmic time: the runtime grows very slowly — the book's guessing game: think of a number between 1 and 100, and I may only ask yes/no questions. Guess 50 — too high. Guess 25 — too low. Guess 37 — correct, in just 3 questions, because every question halves the range. That halving is exactly what binary search does, and it is why O(log n) beats O(n) so dramatically on large inputs.

Time is only half the bill; the other half is memory. Space complexity measures how the amount of memory or space an algorithm uses changes as the size of the input data increases. The book's example is plain: if an algorithm has to store a list of numbers, its space complexity tells you how much memory will be needed as the volume of numbers increases. A list of n numbers needs roughly n slots, so that is O(n) space — double the list, double the memory.

The trick students miss is that two algorithms can do the same job with very different memory footprints. Suppose you want the sum of n numbers. One approach copies the whole list into a second list and then adds it up — that second list alone costs O(n) extra space. The other approach walks through the original list once, keeping a single running total in one variable — that extra space stays constant no matter how long the list is, which is O(1) extra space. Same answer, same time in spirit, wildly different memory. That is why a good algorithm choice weighs both: a blazingly fast algorithm that needs far more memory than the machine has is not a good choice at all.

Divide and Conquer is a design technique that works by breaking a large problem into smaller, more manageable parts, solving each smaller part independently, and then combining their solutions to solve the original problem. It is particularly effective for problems that can be divided into similar smaller problems, because then the same method can be applied again and again until the pieces are trivially small. Think of it as the opposite of panicking at a huge task: instead of staring at the whole mountain, you split it into hills, climb each hill, and put the results together.

The book's illustration is Merge Sort on [14, 7, 3, 12]. Divide: split the list into [14, 7] and [3, 12]. Divide again: [14, 7] becomes [14] and [7]; [3, 12] becomes [3] and [12]. Conquer: sort each tiny piece — [14] and [7] sort into [7, 14], and [3] and [12] sort into [3, 12]. Combine: merge the two sorted halves by repeatedly taking the smaller front element — 3, then 7, then 12, then 14 — giving [3, 7, 12, 14]. The book also notes, in a “Do You Know?” box, that Big O notation helps computer scientists understand an algorithm's efficiency in the worst case, so they can predict how well it will perform as the input data increases — and Merge Sort's steady O(n log n) is exactly why it is trusted for large data.

A greedy algorithm works by making a sequence of choices, each of which is locally optimal — the best-looking move right now — in the hope that these choices will lead to a globally optimal solution, the best overall answer. It is often used when a problem has optimal substructure, meaning that the optimal solution to the whole problem can be built from optimal solutions to its subproblems. The book's classic example is the Coin Change problem: you have coins of different denominations and you want to make a specific amount with the fewest coins possible. The greedy rule is to choose the largest denomination coin that does not exceed the remaining amount, subtract it, and repeat until the amount is reached.

Work it with coins of 50, 20, 10, 5 and 1, making 87. Largest coin not exceeding 87 is 50; remaining 37. Largest not exceeding 37 is 20; remaining 17. Largest not exceeding 17 is 10; remaining 7. Largest not exceeding 7 is 5; remaining 2. Then 1, remaining 1; then 1, remaining 0. Answer: 50 + 20 + 10 + 5 + 1 + 1 = 87, in 6 coins. But — and the book's “Tidbits” box insists on this — greedy algorithms are often faster and easier to implement than other techniques, yet they do not always guarantee the optimal solution for every problem, so always analyse whether a greedy approach is appropriate. Here is a counter-example (derived, not from the book): with coins of 4, 3 and 1, making 6, greedy picks 4 first, then 1, then 1 — three coins — while 3 + 3 uses only two. The greedy choice looked best at the time and still lost. That is the whole danger and the whole charm of being greedy: it never looks back.

Dynamic Programming (DP) is an optimization technique that solves problems by breaking them down into simpler subproblems and storing the results of those subproblems, so the same work is never done twice. It is particularly useful for problems with overlapping subproblems — the same small problem cropping up again and again — and optimal substructure, where the best answer to the whole problem is built from the best answers to its parts. If Divide and Conquer is about splitting a problem up, DP is about splitting it up and remembering.

The book's example is the Fibonacci sequence, where each number is the sum of the two before it: F(0) = 0, F(1) = 1, and F(n) = F(n − 1) + F(n − 2). Work it with DP, filling a table once from the bottom up: F(0) = 0, F(1) = 1, F(2) = 1 + 0 = 1, F(3) = 1 + 1 = 2, F(4) = 2 + 1 = 3, F(5) = 3 + 2 = 5, F(6) = 5 + 3 = 8. Every value is computed exactly once and then simply read back whenever it is needed again. Without that table, a naive recursive program recomputes F(3), F(2) and F(1) over and over, like a student who solves the same sum fresh every time instead of writing the answer in the margin. Storing results is a small idea with an enormous payoff, and it is the entire difference between an exponential program and a linear one for this problem.

Backtracking is a method for problems where you build a solution step by step, and if you find that a particular path does not lead to a solution, you simply go back and try a different path. The book's own comparison is trying out different routes on a map and turning back when you find you are going the wrong way. It is often used for problems where you need to look at all possible options, like puzzles or problems that involve different combinations.

Picture a small maze with one junction. You enter, reach the junction, and try the left passage first. It ends in a dead end — a wall, no exit. A backtracking solver does not panic and does not start the whole maze again: it steps back to the last junction, marks the left passage as tried and failed, and takes the right passage instead, which leads to the exit. That is the whole method in one image: try, fail, step back, try differently, and never waste time re-trying a path you already know is dead. It is the same spirit you will meet again in Depth-First Search, which explores one branch to its end before backtracking to the next — and it is also how a human solves a Sudoku square by pencil: try a digit, and if it breaks a row, erase it and try the next one.

Bubble Sort is one of the simplest sorting algorithms. It works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order. This process is repeated until the list is sorted. The book's process, in order: start from the beginning of the list; compare each pair of adjacent elements; swap them if they are in the wrong order; continue the process until no more swaps are needed. The name comes from the picture: big values “bubble” up to the end of the list, one pass at a time, like bubbles rising in water.

Now trace the book's example completely — [5, 3, 8, 4, 2] — and do not skip a pass, because the exam loves exactly this. Pass 1: compare 5 and 3, swap → [3, 5, 8, 4, 2]; compare 5 and 8, no swap; compare 8 and 4, swap → [3, 5, 4, 8, 2]; compare 8 and 2, swap → [3, 5, 4, 2, 8]. The 8 has bubbled to the end. Pass 2: 3 and 5, no swap; 5 and 4, swap → [3, 4, 5, 2, 8]; 5 and 2, swap → [3, 4, 2, 5, 8]; 5 and 8, no swap. Pass 3: 3 and 4, no swap; 4 and 2, swap → [3, 2, 4, 5, 8]; the rest need no swaps. Pass 4: 3 and 2, swap → [2, 3, 4, 5, 8]; nothing else moves. Sorted: [2, 3, 4, 5, 8], matching the book's answer. The time complexity is O(n²), making it inefficient for large datasets, but it is easy to understand and implement, which is why it survives in teaching — and why the book's tip is to reach for Quick Sort or Merge Sort once the data gets large.

Selection Sort is another simple sorting algorithm, and its idea is almost the opposite of Bubble Sort's neighbour-swapping. It works by selecting the smallest (or largest, depending on the desired order) element from the unsorted part of the list and swapping it with the first element of the unsorted part. The book's process: find the minimum element in the unsorted part; swap it with the first unsorted element; move the boundary between the sorted and unsorted sections by one element; repeat for the remaining elements. The sorted part grows from the left, one element at a time, like filling seats in a row from the front.

Trace the book's example — [29, 10, 14, 37, 13] — all the way. Step 1: the unsorted part is the whole list; its minimum is 10, so swap 10 with the first element, 29 → [10, 29, 14, 37, 13]. Sorted part: [10]. Step 2: the unsorted part is [29, 14, 37, 13]; its minimum is 13, so swap 13 with 29 → [10, 13, 14, 37, 29]. Step 3: the unsorted part is [14, 37, 29]; its minimum is 14, which is already first, so no swap → [10, 13, 14, 37, 29]. Step 4: the unsorted part is [37, 29]; its minimum is 29, so swap 29 with 37 → [10, 13, 14, 29, 37]. Sorted, and it matches the book's description that the process continues until the list is fully sorted. The time complexity is O(n²), like Bubble Sort, so it is not efficient for large datasets, but it is straightforward to implement — and it has one quiet advantage students should notice: it performs far fewer swaps than Bubble Sort, at most one per step, which matters when swapping is expensive.

Search algorithms are designed to find specific elements within a dataset, and they matter for information retrieval, database queries and decision-making. Linear search is the straightforward one: check each item one by one until you find what you are looking for. The book's steps: start at the beginning and look at the first item; compare the item you are looking for with the current item; if they do not match, move to the next item; repeat until you find the item or reach the end of the list. Its own example uses cities: [Karachi, Lahore, Islamabad, Faisalabad], searching for Islamabad. Start with Karachi — not Islamabad, move on. Next is Lahore — not Islamabad, move on. Next is Islamabad — that is the city you are looking for, found on the third check. If Islamabad were not in the list, you would check all four cities one by one and then conclude it is not there. It is called linear because you check in a straight line, start to finish, and it works on unsorted data — but in the worst case it costs O(n) checks.

Binary search is the efficient alternative, but it comes with a condition: the list must be sorted. It works by repeatedly dividing the search interval in half and discarding the half the item cannot be in, until the item is found or the interval is empty. The book's steps: start with the middle element of the sorted list; if it is the target, return its position; if the target is smaller, repeat on the left half; if larger, repeat on the right half. ⚠️ Book gap, filled here: the book's first binary-search example gives the sorted list [1, 3, 5, 7, 9, 11, 13] and says binary search “will start at the middle element (7) and find the target immediately”, without naming the target. The only reading that fits is that the target is 7, the middle element itself, so it is found in one check — and that is how it is presented here. The book's fuller worked figure searches for 78 in [21, 34, 43, 57, 66, 78]: first mid is 43; 78 is larger, so look in the right half; new mid is 66; 78 is larger, so look in the right half; new mid is 78 — element found at mid. Three checks instead of six. The time complexity is O(log n), much faster than linear search for large datasets, and the book's warning is blunt: binary search is only effective on sorted lists; if your data is not sorted, sort it first, for example with Merge Sort, before applying binary search.

Graph algorithms explore and analyse graphs — data structures made up of nodes (vertices) connected by edges. They are essential for network analysis, route planning and social network analysis, and the chapter closes with the two classic ways of walking through a graph. Breadth-First Search (BFS) explores all the nodes of a graph level by level, starting from a given node, often called the root, and it uses a queue to keep track of the nodes that need to be explored. The book's process: start from the root node and enqueue it; dequeue a node, process it, and enqueue all its unvisited neighbours; repeat until the queue is empty. Its example is a social network, where each node is a person and each edge is a friendship: BFS can find the shortest path between two people, for instance the degree of separation between two users. The time complexity is O(V + E), where V is the number of vertices and E the number of edges, which makes it efficient for exploring large graphs.

Depth-First Search (DFS) is the other temperament entirely: it explores as far down a branch as possible before backtracking to explore other branches, and it uses a stack to manage the nodes to be explored. The book's process: start from the root node and push it onto the stack; pop a node, process it, and push all its unvisited neighbours onto the stack; repeat until the stack is empty. The book's figure compares the two on the same graph, and the outputs are worth memorising: BFS gives 0, 1, 2, 3, 4, 5, 6, 7 — level by level, in order — while DFS gives 0, 1, 4, 5, 2, 6, 3, 7 — plunging down one branch before returning. DFS suits puzzles like mazes, the book says, where the algorithm explores one possible path to the end and, if it hits a dead end, backtracks and tries another path. Its time complexity is also O(V + E), similar to BFS, but the book adds that DFS is more memory-efficient for deep graphs, while BFS is more suited for shallow graphs. Queue for breadth, stack for depth: if you remember nothing else from this section, remember that pairing and the two output orders.