Week 1

Foundations of Problem Solving in Computing

1.1. Introduction to the Core Concepts of Computing

Welcome to COS 102. Before we dive into problem solving itself, let us establish what computing is and why
problem solving lies at its heart. Computing, in the broadest sense, is the activity of using computers to manage,
process, and communicate information. However, from the perspective of a computer scientist, computing is
fundamentally about solving problems through systematic, automatable processes.
At the centre of computing are a few core concepts:
 Data: raw facts, figures, or symbols that have no meaning by themselves. For example, the numbers 23, 05,
1998 are data.
 Information: data that has been processed, organised, or structured to make it meaningful. If I tell you those
numbers represent a date, 23rd May 1998, they become information.
 Algorithm: a finite sequence of well-defined, unambiguous steps that solves a specific problem or
accomplishes a task. We will formalise this later, but for now think of a recipe.
 Program: an algorithm expressed in a language that a computer can execute.
Every time we use a computer – to send a message, play a video, or calculate a budget – a program is executing one
or more algorithms to transform data into the information we need.

The essence of computer science is not just the machine, but the problem solving that instructs the machine. The
computer is a tool; our minds are the problem solvers.

1.2 What Is a Problem?

In everyday language, a "problem" is something difficult or unpleasant that we want to get rid of. In a more precise,
academic sense – especially in the context of computing and cognitive science – a problem is defined by three
components:
A problem exists when an individual (or system) has a clear initial state and a desired goal state, but the path
from the initial state to the goal state is not immediately obvious, and some form of deliberate thinking or
action is required to bridge the gap.

There are three things to note in the definition:

 Initial state: The beginning of the state. It can refer to where you are now, what you know or what you have.
 Goal state: The final stage of a state. That refer to where you want to be, what you want to achieve or the
solution of the expected state.
 Obstacles Challenge: it means the constraints and available actions that can change the state.

Table 1.1: Different state of a Problem Solving

Context Initial State Goal State Obstacle / Challenge
Everyday You are in your room. The You want to be on the other You cannot simply walk through; you
door is locked from the side of the door. must find a key or a different exit.
outside.
 Computing A list of 10,000 unsorted The same list sorted Doing it by hand would take hours;
student names. alphabetically. you need an efficient method
(algorithm).
Mathematics Given a quadratic equation: Find the values of *x* that You must apply algebraic methods
*x² – 5x + 6 = 0*. satisfy the equation. (factoring, formula).
Notice that in each case there is a gap that requires thought and a series of actions.

1.3 Problem Identification and Problem Statement Formulation

A problem cannot to be solved except it is known and clearly articulated. This step is often undervalued, but it is
the foundation upon which all successful solutions are built.

1.3.1 Problem Identification

Problems are identified through some processes. They are as follows:
 Observation of symptoms: This happens when something is not working as expected. For example, when
a report takes too long to generate or a program crash without any previous error messages.
 Needs analysis: Sometimes a stakeholder may express a desire for a new capability, such as a need a need
to track inventory in real time, then it can propel needs analysis of the system.
 Opportunities: It occurs when recognising that a task could be done better, faster, or cheaper with a
computational solution.

In computing, we often talk about "requirement elicitation”, that is, the process of understanding what the user really
needs, which may be different from what they initially ask for.

1.3.2 Problem Statement Formulation

A well-formed problem statement is a concise, unambiguous description of the issue to be addressed. A good
problem statement typically includes:
a. The current state: What is the existing situation, and why is it unsatisfactory?
b. The goal state: What would a successful solution look like? What are the measurable criteria for success?
c. The context and constraints: What resources are available? What limitations exist? The resources might be
time, budget, hardware, legal, ethical and so on. What are the necessary things not available?
d. The stakeholders: Who is affected by the problem and its solution?

Example of a weak problem statement:

"Our university registration system is bad."

Example of a strong problem statement:

"During the peak registration period, over 2,000 students are forced to queue physically for an average of 4 hours
because the online registration portal can only handle 200 concurrent sessions. The goal is to provide a system that
allows all students to complete course registration online within 15 minutes, without system crashes, using the
existing network infrastructure, and with a budget not exceeding ₦5,000,000."

The strong statement clarifies what the "bad" system means, sets a measurable target, and acknowledges constraints.
Thus, this clarity will guide the subsequent search for a solution.

1.4 Types of Problems

Not all problems are alike. A fundamental distinction in problem-solving theory is between routine, that is, well-
defined and non-routine or ill-defined problems. Understanding this difference tells us what kind of solution
strategy is appropriate.
1.4.1 Routine Problems (Well-Defined)
 Characteristics:
o All the necessary information is given; the initial state, goal state, and permissible operators are
clearly specified.
o There is a known, systematic procedure, that is, an algorithm that guarantees a correct solution.
o They are often repetitive and can be solved by following a fixed set of rules.

The typical examples of this characteristics are: computing the average of a list of numbers; converting
temperatures from Celsius to Fahrenheit; finding the shortest path in a known network using Dijkstra’s
algorithm; and sorting a set of records by a specific field.

 Solution approach: The primary challenge is choosing the most efficient algorithm. The solution may
involve choosing the best among the existing algorithms and not inventing a new one to solve the problem.

1.4.2 Non-Routine Problems (Ill-Defined)

 Characteristics:
o The problem may be ambiguous; the goal, initial state, or allowable operations are not fully specified.
o There is often no single "correct" answer; solutions are evaluated on how well they satisfy multiple,
sometimes conflicting, criteria.
o They require creativity, judgment, and often the use of heuristics (rules of thumb) rather than
algorithmic procedures.
o They may be unique or novel.

The examples might be among these:

o Designing a user-friendly interface for a mobile banking app, what does "user-friendly" mean
exactly?
o Choosing the best data structure for a complex, evolving software project.

 Solution approach to this problem is that it must be structured and clarified. Solution methods can be
heuristics, experimentation, iterative refinement, and multidisciplinary insight. In this type of problem there
is no step-by-step procedure.

The reason why this distinction matters in computing is that a computer can only execute algorithms. To make a
computer solve a non-routine problem, we must first transform the whole problem or a manageable part of it, into
well-defined, routine problem. Thus, the creativity happens in the human mind while the execution is delegated to
the machine which is the computer.

1.5. The Role of Problem Solving in Computer Science

Computer science is frequently misunderstood as merely "programming" or "learning languages." In truth,
programming is just the final step in a much larger intellectual process. The heart of computer science is
computational thinking, that is, a way of approaching problems that draws on concepts fundamental to computing.

Problem solving in computer science involves:

 Formulating problems in a way that enables us to use a computer to help solve them.
 Logically organising and analysing data.
 Representing data and processes through abstractions such as models and simulations.
 Automating solutions via algorithmic thinking – creating a series of ordered steps.
  Identifying, analysing, and implementing possible solutions with the goal of achieving the most efficient
and effective combination of steps and resources.
 Generalising and transferring this problem-solving process to a wide variety of situations.

In industry, when a new software product is built, developers may spend weeks or months understanding the
problem, modelling the domain, and designing algorithms before a single line of code is written. Code that is written
without thorough problem analysis is often buggy, inefficient, and fails to meet the users’ needs.

1.6. Overview of the General Problem-Solving Process

To navigate both routine and non-routine problems systematically, we need a structured framework. One of the most
enduring models comes from the mathematician George Pólya, who outlined four essential steps in his book How
to Solve It (1945). Although Pólya’s context was mathematics, the steps are universal and form the backbone of
problem solving in computing.

1.5.1 Pólya’s Four Steps

Step 1: Understand the Problem
 Read the problem carefully. What are you asked to find or do?
 Identify the given data, the unknowns, and the conditions.
 Draw a diagram or restate the problem in your own words.
 Ask yourself: Is there enough information? Is there redundant information? Do I need to make assumptions
explicit?
Step 2: Devise a Plan
 This is the “how” step. What strategies could lead to a solution?
 Think about similar problems you have solved in the past (analogy).
 Consider drawing a flowchart or writing pseudocode (tools we will learn).
 Select an appropriate solution technique (abstraction, divide and conquer, etc. – topics for Weeks 3 and 4).
 For routine problems, this often means selecting the correct algorithm.
 For non-routine problems, you may need to break the problem into smaller, better-defined subproblems.

Step 3: Carry Out the Plan

 Execute the chosen strategy with care and patience.
 If you are writing an algorithm, code it, or manually trace it.
 Check each step as you proceed. Is each step correct? Does it logically follow from the previous one?
 Keep a clear record of your work so it can be reviewed.

Step 4: Look Back (Evaluate and Reflect)

 Examine the solution obtained. Does it satisfy all conditions of the problem? Is it reasonable?
 Could there be a simpler or more efficient solution?
 What did you learn from this problem that could help you solve future problems?
 In computing, this step corresponds to testing, debugging, and optimisation.

You can apply these steps to this example that states “Find the Largest of Three Numbers”
1. Understand: We are given three numbers, say a, b, c. We need to find which one is the largest. All numbers
are distinct (assumption).
2. Devise a plan: Compare a with b; keep the larger of the two. Then compare that result with c. The final larger
value is the overall maximum.
3. Carry out: If a = 15, b = 22, c = 9: compare 15 and 22 → 22 is larger; compare 22 and 9 → 22 is larger. So
answer is 22.
 4. Look back: Does the method work if some numbers are equal? Yes, it still works because “larger” can be
interpreted as “greater than or equal to”. Could we do it with a different plan? Yes, sort them and pick the
last one, but that is less efficient. Our solution is simple and fast.

This four-step process will be the scaffolding upon which we build all subsequent techniques. As the course
progresses, you will see that algorithm, flowcharts, pseudocode, and programming languages are simply tools that
help us formalise and automate the Devise a Plan and Carry Out the Plan stages.
Week 2

Solvability and the Nature of Solutions

2.1. Introduction
In Week 1, we established that problem solving in computing involves moving from an initial state to a goal state.
But before we even begin devising a plan, we must ask two fundamental questions:
 Can this problem be solved at all by a computer? (Solvability)
 If it can be solved, can it be solved within a reasonable amount of time and resources? (Tractability)
Furthermore, the nature of the solution can vary widely. Some solutions are fully guaranteed and exact – we call
these algorithms. Others are clever shortcuts that give us a "good enough" answer most of the time – these are
heuristics. Understanding these concepts is foundational to choosing the right approach for any problem you will
encounter.

2.2. Solvable and Unsolvable Problems

2.2.1 What Does “Solvable” Mean in Computing?
A problem is said to be solvable (or decidable) if there exists an algorithm that, given any valid input, will produce
the correct output and always terminate after a finite number of steps. If no such algorithm can possibly exist, the
problem is unsolvable (or undecidable).
This is not about our current knowledge or technology; it is a mathematical statement about the very nature of the
problem itself. An unsolvable problem will remain unsolvable forever, regardless of advances in processor speed,
memory, or artificial intelligence.

2.2.2 The Limits of Computation: A Brief Historical Perspective

The discovery that some problems are unsolvable is one of the most profound intellectual achievements of the 20th
century. It emerged from a quest by the mathematician David Hilbert, who in 1928 posed the Entscheidungsproblem
(German for “decision problem”). He asked whether there could exist a mechanical procedure – an algorithm – that
could determine the truth or falsehood of any mathematical statement. In other words, could mathematics be
completely automated?

In 1936, a 24-year-old British mathematician named Alan Turing answered this question with a resounding no. To
do so, he invented a theoretical model of computation we now call the Turing machine. A Turing machine is a
simple abstract device consisting of:
 An infinite tape divided into cells, each containing a symbol (or blank).
 A head that can read and write symbols and move left or right.
 A finite set of states and a transition table that tells the machine what to do based on the current state and
symbol read.

Despite its simplicity, a Turing machine can simulate the logic of any computer algorithm. Turing argued that
anything that can be computed, can be computed by a Turing machine. This is now known as the Church-Turing
thesis. Turing then showed that there exist well-defined problems that no Turing machine can solve, and therefore
no computer program can solve them. The most famous of these is the Halting Problem.
2.2.3 The Halting Problem
Halting Problem: Given a description of an arbitrary program and its input, determine whether the program will
eventually stop (halt) when run with that input, or whether it will run forever.
Turing proved that no general algorithm can solve the Halting Problem for all possible program–input pairs.

Intuitive Proof (by contradiction):

Suppose there were a magical program H(P, I) that returns true if program P halts on input I, and false if it runs
forever. Now consider another program G(X) defined as follows:

Program G(X):
if H(X, X) is true:
loop forever
else:
halt

In plain language, G takes a program X, asks the halting oracle H what X would do when given its own description
as input. If H says X halts, G deliberately loops forever; if H says X runs forever, G halts.

Now ask: What does G(G) do?

 If H(G, G) returns true (meaning G halts on itself), then G enters the infinite loop – so it does not halt.
Contradiction.
 If H(G, G) returns false (meaning G does not halt on itself), then G halts. Contradiction.

Therefore, the assumed program H cannot exist. No algorithm can decide the halting behaviour of all programs. This
is not a practical limitation; it is a logical impossibility.

Why does this matter?

The Halting Problem demonstrates that there are inherent boundaries to what computation can achieve. Many other
questions in computer science – such as determining whether two programs are equivalent, or whether a program
contains a certain type of bug – can be shown to be reducible to the Halting Problem, and are therefore also
undecidable. As computer scientists, we must recognise these limits and work within them, for example by using
heuristics or by restricting ourselves to solvable subclasses of problems.

2.3. Tractable vs. Intractable Problems

2.3.1 When “Solvable” Is Not Enough
Knowing that a problem is solvable in principle is reassuring, but in practice we also need to solve it with the time
and memory available to us. A problem is tractable if it can be solved by an algorithm whose running time grows
as a polynomial function of the size of the input. A problem is intractable if the best known (or any possible)
algorithm requires exponential or worse time growth, making the solution computationally infeasible for even
moderately sized inputs.

The algorithmic efficiency is measured using Big O notation, which describes how the time or space required scales
with input size *n*:
 Polynomial time (tractable): O(nᵏ) for some constant *k*. Examples:
o Linear: O(*n*) – scanning a list once.
o Linearithmic: O(*n* log *n*) – many efficient sorting algorithms.
 o Quadratic: O(n²) – simple sorting (bubble sort), still manageable for small to medium *n*.
 Exponential time (intractable): O(kⁿ) for *k* > 1. Even for *n* = 100, 2¹⁰⁰ operations is astronomically
large – far beyond the age of the universe.
 Factorial time: O(n!) – worst-case brute-force for Traveling Salesman Problem (TSP).

Table 2.1: Solvable Problem approaches

Problem Best Exact Algorithm Tractability
Searching a sorted list Binary search: O(log *n*) Tractable
Sorting a list Merge sort: O(*n* log *n*) Tractable
Shortest path in a graph Dijkstra’s: O(n²) or better Tractable
Traveling Salesman (TSP): shortest route Dynamic programming: O(n² 2ⁿ) Intractable for large *n*
visiting *n* cities exactly once
Integer factorization (large semiprime) General number field sieve: sub- Edge of tractability; basis
exponential but not polynomial of RSA security

2.3.2 The P vs. NP Question

A vast class of important optimization and decision problems – such as the TSP, Boolean satisfiability, and protein
folding – belong to a class called NP (Non-deterministic Polynomial time). They share a curious property: if a
solution is proposed, its correctness can be verified in polynomial time, even though finding the solution seems to
require exponential time for all known algorithms.

Whether P = NP – that is, whether every problem whose solution can be verified quickly can also be solved quickly
– is the most famous unsolved question in computer science. Most experts believe P ≠ NP, which means that for
many practical problems, exact algorithmic solutions will remain out of reach for large inputs. Consequently, we
must resort to heuristics that find good, though not necessarily optimal, solutions in reasonable time.

2.4. Introduction to Solution Methods: Algorithms and Heuristics

2.4.1 Algorithms: Formal Definition and Examples
An algorithm is a finite sequence of well-defined instructions for solving a class of problems. When given an input
from a specified set, the algorithm produces the corresponding output and terminates in a finite number of steps.
Think of an algorithm as a precise procedure that is guaranteed to work. Let’s examine some common examples
and computing examples:

Example 1: A Recipe for Baking a Cake

 Inputs: ingredients are flour, eggs, sugar, and so. on
 Steps: preheat oven to 180°C, mix dry ingredients, cream butter and sugar, add eggs, combine, pour into pan,
bake for 30 minutes.
 Output: a baked cake.

This qualifies as an algorithm if the steps are definite and the process always finishes it is in assuming correct
proportions and no cataclysms. However, if the recipe says “add some sugar until it tastes right”, it fails on
definiteness, therefore, we need a precise quantity.

Example 2: Long Division

Given two integers, the long division procedure teaches us a set of unambiguous steps - divide, multiply, subtract,
bring down - that always yields a quotient and remainder, as well, always terminates.

Computing Example 1: Euclid’s Algorithm for Greatest Common Divisor (GCD)

Input: two positive integers *a* and *b*.
Steps:
1. If *b* = 0, return *a* as the GCD.
2. Otherwise, set *a* to *b*, and *b* to (*a* mod *b*).
3. Repeat from step 1.
Output: the GCD of the original numbers.

This algorithm is elegant, provably correct, and terminates because the numbers decrease at each step.

Computing Example 2: Binary Search

Input: a sorted array A and a target value T.
Steps: Set low = 0, high = length-1. While low ≤ high: compute mid = (low + high) // 2. If A[mid] = T, return mid. If
A[mid] < T, set low = mid + 1. Else set high = mid - 1. If the loop ends, return “not found”.

Binary search is guaranteed to find the target if it exists, and it does so in O(log *n*) steps – a tractable, exact
algorithm.

2.4.2 Heuristics: Definition and Usage

A heuristic (from Greek heuriskein, “to find” or “to discover”) is an experience-based technique that helps find
satisfactory solutions to problems when:
 An exact algorithm does not exist (the problem is unsolvable or poorly defined).
 An exact algorithm exists but is computationally intractable (too slow or memory-hungry) for the input
size at hand.
 The problem environment is dynamic, uncertain, or requires real-time response.

Heuristics are rules of thumb, educated guesses, mental shortcuts. They do not guarantee an optimal solution; they
may even fail to find any solution in some cases. Their value lies in providing good enough answers with much less
effort, time, and resources than an exhaustive search.

Example: Finding a Parking Space

There is no algorithm that guarantees you the closest spot to the mall entrance in minimum time, because traffic,
pedestrian movements, and unknown availability are unpredictable. Your heuristic might be: “Drive up the row
nearest the entrance; if no spot appears after two aisles, go to the next level, repeat.” This doesn’t guarantee the
optimal spot, but it works well in practice.

Computing Example 1: Chess-Playing Programs

The game tree for chess is astronomically large (more possible moves than atoms in the observable universe). No
algorithm can search all possible moves to the end. Instead, programs like Deep Blue use heuristics: a board
evaluation function that approximates the strength of a position (material count, piece activity, king safety), and a
search that prunes unpromising lines (alpha-beta pruning). The heuristic enables the program to play at grandmaster
level without examining every possibility.

Computing Example 2: Greedy Algorithms as Heuristics

A greedy algorithm makes the locally optimal choice at each step, hoping it leads to a global optimum. For some
problems (e.g., finding the minimum spanning tree with Prim’s or Kruskal’s algorithm), the greedy choice is
provably optimal, so the algorithm is exact. For many others (e.g., the 0/1 knapsack problem), a greedy “take the
highest value-to-weight ratio first” approach yields a feasible solution that is often close to optimal, but it is a
heuristic because it can fail to produce the true optimum.

Where heuristics are used.

  Intractable optimization: Transport State Problem (TSP), vehicle routing, scheduling.
 Ill-defined or wicked problems: Interface design, business strategy.
 Real-time systems: Autonomous driving, where decisions must be made in milliseconds.
 Unsolvable sub-problems: Using heuristics within a larger algorithmic framework, like heuristics for clause
selection in SAT solvers.

Table 2.2: Trade-offs of Heuristics

Advantages Disadvantages
Fast, computationally cheap No guarantee of optimality
Can handle large, complex instances May get stuck in local optima (not global best)
Often easy to understand and implement Hard to measure solution quality without benchmarks
Enable practical solutions where none existed Can be fragile; performance may degrade on different data

2.5. The Five Essential Properties of an Algorithm

For a procedure to be considered a true algorithm, it must satisfy all of the following properties, as articulated by
computer science pioneer Donald Knuth:
a. Finiteness
An algorithm must always terminate after a finite number of steps. Each step must be finite, and the total number
of steps must be finite for all inputs. A program that goes into an infinite loop does not satisfy this property and
is therefore not an algorithm for solving a problem (though it may be a reactive system, like an operating system,
that runs indefinitely but is not a terminating algorithm).
b. Definiteness
Each step of the algorithm must be precisely and unambiguously defined. There can be no room for subjective
interpretation. Statements like “choose a large number” or “do the right thing” are not allowed. In programming,
this means that the operations must be exactly specified so that a computer can execute them without additional
human judgment.
c. Input
An algorithm has zero or more inputs. These are quantities that are given before the algorithm begins and are
taken from specified sets of objects. For example, the GCD algorithm has two integer inputs. An algorithm that
generates a random number might have zero inputs (though it might rely on an implicit system time).
d. Output
An algorithm has one or more outputs. The output is any quantity that has a specified relation to the inputs. An
algorithm must produce a result; otherwise it is not useful as a problem solver. The output is what the algorithm
was designed to compute.
e. Effectiveness
All operations in the algorithm must be sufficiently basic that they can, in principle, be carried out by a human
using only pencil and paper in a finite amount of time. Furthermore, the algorithm as a whole must be practically
feasible. For example, an algorithm containing the step “if the Goldbach conjecture is true, then do X” is not
effective, because no one knows how to determine that condition. Likewise, an algorithm requiring infinite
precision real arithmetic is not effective on a digital computer.

Example:
Consider a set of instructions: “To sort a list, look at it and arrange the elements in order.”
 Definiteness? No, “look at it and arrange” is not a precise step.
 Effectiveness? The mental process is not broken down into basic operations.
Thus, this is not an algorithm. However, “Selection sort: find the smallest element, swap it with the first position,
then repeat for the rest of the list” meets all five properties.

2.6. Distinguishing Algorithmic Solutions from Heuristic Solutions

We now have two distinct categories of solution approaches. The choice between them depends on the nature of the
problem and the requirements of the solution.

Table 2.3: Difference between Algorithmic Solutions from Heuristic Solutions

Feature Algorithmic Solution Heuristic Solution
Guarantee Always produces a correct/optimal solution if No guarantee of correctness or optimality; may
it terminates. produce a “good enough” solution or
sometimes fail entirely.
Completeness Solves all instances of the problem class. Usually solves most practical instances, but
might fail on some (e.g., stuck in local
optimum).
Process A deterministic sequence of defined steps; can Often based on rules of thumb, trial and error,
be formally analyzed and proven. or probabilistic methods; difficult to prove
formally.
When to use Well-defined, routine problems with known Ill-defined, non-routine, or intractable
efficient algorithms. problems; problems where time is critical and
an approximation is acceptable.
Examples Computing square root using Newton’s method Face recognition using a convolutional neural
(exact within tolerance), string matching with network (heuristic feature extraction),
Knuth-Morris-Pratt. simulated annealing for TSP.
Analysis Complexity can be rigorously analyzed (Big Performance often evaluated empirically via
O). benchmarks and heuristics-specific metrics.

A concrete comparison:
Problem: Schedule final exams for 500 courses across 20 time slots so that no student has two exams at the same
time, and the number of conflicts is minimized.
 Algorithmic approach: Model as a graph colouring problem. A backtracking algorithm can find an exact
conflict-free schedule, but for large, densely connected graphs the runtime may be exponential and
completely impractical.
 Heuristic approach: Use a greedy colouring heuristic: assign the most constrained course first (largest
number of conflicting courses), iteratively pick the first available slot. This runs in O(*n* log *n*) and
produces a schedule with very few conflicts, although it might not be the absolute minimum possible.

In real life, the heuristic is often chosen because it is fast and sufficient, and the cost of an extra conflict is negligible
compared to the cost of waiting centuries for the exact solution.

2.7. Summary
This week we explored the very boundaries of what computation can achieve:
 Solvability: Some problems, like the Halting Problem, are mathematically unsolvable by any computer.
Knowing these limits prevents us from chasing impossible solutions.
 Tractability: Even solvable problems may require more time or memory than the universe can provide.
Problems with only exponential-time algorithms are considered intractable for large inputs.
 Algorithms are precise, finite, unambiguous step-by-step procedures that guarantee a correct result and
possess the five properties of finiteness, definiteness, input, output, and effectiveness.
 Heuristics are intelligent shortcuts that trade guaranteed optimality for speed and practicality. They are
essential for tackling the vast number of real-world problems that are intractable or ill-defined.
 Choosing the right tool means recognizing whether your problem demands an exact solution and can
feasibly obtain it, or whether a heuristic approach will provide an acceptable answer within constraints.
Week 3

Solution Techniques – Part I

3.1. Introduction: Why Study Solution Techniques?

In Week 1, we established that problems can be routine or non-routine, and that Pólya’s four-step process provides
a universal framework for tackling them. In Week 2, we explored the boundaries of what computers can solve
(solvability and tractability) and introduced the twin concepts of algorithms (exact, guaranteed solutions) and
heuristics (practical, approximate solutions). Now we turn our attention to the strategies that fill the gap between
recognising a problem and devising a concrete plan. When faced with a new problem – especially one that is not
trivial – you do not simply stare at it until a solution emerges. You draw upon a repertoire of solution techniques:
mental tools that help you structure your thinking, generate possibilities, and transform the unfamiliar into the
familiar.

The six techniques we cover this week – abstraction, analogy, brainstorming, trial and error, hypothesis testing,
and reduction – are among the most powerful and widely applicable. Some are precise and systematic; others are
creative and divergent. A skilled problem solver knows them all and can select the right tool for the task at hand.
Let us examine each technique in detail.

3.2. Abstraction
3.2.1 Definition and Core Idea
Abstraction is the process of filtering out unnecessary details to focus on the essential features of a problem. It
involves creating a simplified, high-level model of a complex reality, retaining only those aspects that are relevant
to the problem at hand and deliberately suppressing the rest.
The word comes from the Latin abstrahere, meaning “to draw away.” In problem solving, we draw away the
incidental noise to reveal the underlying structure.
Abstraction is one of the four cornerstones of computational thinking, alongside decomposition, pattern
recognition, and algorithm design. Without abstraction, every problem would have to be solved in its full,
overwhelming detail, which is cognitively impossible and computationally wasteful.

3.2.2 The Process of Abstraction

When you abstract a problem, you typically follow these steps:
1. Identify the core goal. What are you ultimately trying to achieve?
2. Determine the critical entities, their attributes, and their relationships. What are the minimum pieces of
information required to describe the problem?
3. Suppress irrelevant details. Which colours, sizes, physical locations, emotional states, or transient
conditions do not affect the solution?
4. Build a representation (model). Express the essential elements in a clean, manageable form – often as a
diagram, mathematical structure, or set of variables.

Common Examples:
 Underground metro map: The famous schematic map of the London Underground, designed by Harry
Beck in 1931, is a masterpiece of abstraction. It discards accurate geographical distances and the winding
 paths of the tracks. It retains only the stations (nodes), their sequence along each line, and the transfer points.
This stripped-down representation is far more useful for a traveller planning a route than a detailed street
map would be.
 Floor plan of a building: An architect’s floor plan abstracts away the colour of the walls, the texture of the
carpets, the brand of furniture, and the occupants inside. It preserves the spatial layout: walls, doors,
windows, and rooms. This abstraction is exactly what a builder needs to understand the structure.
 A recipe: “Cream together 200g of butter and 200g of sugar” abstracts away the brand of butter, the exact
temperature of the ingredients (assuming room temperature), and the type of mixing bowl. The essential
action – combining fat and sugar until light and fluffy – is captured.

Computing Examples
 Object-oriented programming classes: When you design a Student class for a university information
system, you do not include attributes for the student’s favourite colour, shoe size, or childhood pet’s name –
unless those are relevant to the system’s purpose. Instead, you abstract the attributes that matter: studentID,
name, dateOfBirth, enrolledCourses. The class is an abstraction of a real student.
 Data structures as abstractions: A stack is an abstraction of a physical pile of plates. We ignore the material
of the plates and focus only on the operations that matter: push (place on top), pop (remove from top), and
peek (view top). This abstract model is then applied to solve problems like expression evaluation, undo/redo
functionality, and backtracking.
 Layered network models (TCP/IP, OSI): The Internet protocol suite is built on layers of abstraction. The
application layer (HTTP, SMTP) does not need to know how the transport layer (TCP) guarantees reliable
delivery, nor how the physical layer encodes bits as electrical signals. Each layer provides a service to the
layer above while hiding its internal complexity. This allows developers at one level to solve problems
without understanding the entire stack.
 User interfaces as abstractions: When you drag a file to the recycle bin on your desktop, you are interacting
with an abstraction. You do not see the disk sectors being marked as free, the file allocation table being
updated, or the electronic signals traveling across the motherboard. The graphical icon and the drag-and-
drop gesture are abstractions that make the operation intuitive.

3.2.3 Abstraction in the Problem-Solving Process

When you encounter a complex problem description, your first step should often be to abstract it into a simpler
model. For example:
Problem: A delivery company needs to plan routes for its fleet of 50 trucks, making 500 stops across a city,
minimising total fuel consumption.
 Abstraction: Ignore the colour of the trucks, the names of the drivers, and the specific contents of the
packages. Represent the city as a graph: intersections are nodes, road segments are edges weighted by
distance or travel time. The problem becomes a Vehicle Routing Problem (VRP) – a well-known
combinatorial optimisation problem. Once abstracted, you can draw upon a vast body of research and
algorithms.

3.2.6 Pitfalls and Limitations

 Over-abstraction: Removing details that are actually essential. If the delivery trucks have different
capacities and the packages have different sizes, abstracting away capacity constraints would yield a solution
that cannot be executed in reality.
 Under-abstraction: Failing to remove enough clutter, leaving the problem too complex to analyse. The art
lies in finding the right level of detail for the task at hand.
 Multiple abstractions: The same reality may be abstracted in different ways depending on the problem. A
road network can be abstracted as a graph for route planning, but as a heatmap of congestion for traffic
analysis. Choose the abstraction that serves your goal.
3.3. Analogy
3.3.1 Definition and Core Idea
Analogy is the technique of solving a new problem by recognising its similarity to a previously solved problem and
transferring the solution – or the principles behind it – from the familiar domain to the unfamiliar one. In essence,
you ask: “What does this problem remind me of?” The power of analogy lies in its ability to make the novel
accessible by harnessing the brain’s pattern-recognition capabilities.

3.3.2 The Process of Analogical Reasoning

Psychologists and AI researchers have identified a structured process underlying analogical problem solving:
1. Representation: Build a mental model of the target problem (the one you are trying to solve).
2. Retrieval: Search your memory – or a knowledge base – for a source problem that has a similar deep
structure. Superficial similarity is not enough; the relationships between entities must align.
3. Mapping: Draw correspondences between the elements of the source and the target. “The source’s X
corresponds to the target’s Y.”
4. Transfer: Adapt the solution method from the source to the target, adjusting for any differences.
5. Evaluation: Test whether the adapted solution works for the new problem.

Common Examples
 The Wright brothers and the bicycle: In their quest for controlled flight, Wilbur and Orville Wright drew
a crucial analogy to riding a bicycle. A bicycle is inherently unstable, but a skilled rider maintains balance
through continuous, subtle adjustments. The brothers reasoned that a flying machine could similarly be
unstable if the pilot had a means to constantly adjust the lifting surfaces. This led to their breakthrough
concept of wing-warping for roll control – the precursor to modern ailerons.
 Heart as a pump: William Harvey, in the 17th century, described the circulation of blood by analogy to a
mechanical pump. The heart’s chambers, valves, and rhythmic contractions were mapped to the components
of a water pump, an invention familiar to the engineers of his time. This analogy transformed medicine.
 Learning to drive a new vehicle: If you have learned to drive a sedan, driving a minivan or a small truck is
easier because you apply analogical reasoning. The steering wheel, pedals, gear shift, and mirrors all work
on the same principles. You map the known controls to the new vehicle and adjust for its larger dimensions.

Computing Examples
 The tortoise and hare algorithm (Floyd’s cycle detection): The problem is to determine whether a linked
list contains a cycle, and if so, to find the start of the cycle. The brilliant solution uses two pointers moving
at different speeds – a “tortoise” (one step at a time) and a “hare” (two steps). This is a direct analogy to a
race on a circular track: a faster runner will eventually lap a slower one. By mapping the athletic race to
pointer manipulation, the algorithm becomes intuitive and provably correct.
 Quicksort’s partition and the binary search tree: When you partition an array around a pivot – all elements
smaller to the left, all larger to the right – you are creating a structure analogous to the root node of a binary
search tree, where left children are smaller and right children are larger. Understanding one illuminates the
other.
 Ant colony optimisation: When faced with the intractable Travelling Salesman Problem, researchers drew
an analogy to how ants find the shortest path between their nest and a food source. Ants deposit pheromone
trails; shorter paths are traversed more frequently and thus accumulate stronger pheromone, attracting more
ants. This biological analogy gave birth to a whole family of heuristic optimisation algorithms.
 Email vs. postal mail: The designers of early email protocols explicitly used the analogy of physical postal
mail. An email has a sender address, a recipient address, a subject (like a memo line), and a body. Mail
 servers act as post offices. This analogy helped users and developers understand the new technology in terms
of something familiar.

3.3.3 The Value and Danger of Analogy

Value: Analogy accelerates problem solving by eliminating the need to invent a solution from scratch. It leverages
collective experience and enables cross-disciplinary innovation.
Danger: False analogy. Superficial similarities can seduce you into applying a solution that does not hold. The
Ptolemaic model of the solar system used an elaborate system of epicycles, which was an analogy to gears and
circles but ultimately incorrect. In computing, blindly treating a file system as a physical filing cabinet can lead to
inefficient search strategies when the underlying data structures (B-trees, hashing) behave very differently.
Guideline: Always verify that the structural relationships match. In a good analogy, the causal and functional
dependencies are preserved, not just the appearances.

3.4. Brainstorming
3.4.1 Definition and Core Idea
Brainstorming is a creative technique for generating a large number of diverse ideas in a short period, with the
explicit rule that judgment is suspended during the generation phase. The goal is quantity and variety, not
immediate quality. The technique was popularised by advertising executive Alex Osborn in the 1940s. He observed
that critical, evaluative thinking tends to inhibit the free flow of imaginative ideas. By separating the processes of
divergent thinking (generating ideas) and convergent thinking (evaluating and selecting), brainstorming
maximises creative output.

3.4.2 The Four Fundamental Principles

Osborn’s original rules are still the gold standard:
1. Aim for quantity: The more ideas, the higher the probability that one will be a winner. Quantity breeds
quality.
2. Withhold criticism: No idea is too silly, too expensive, or too impossible. Evaluation and judgment are
reserved for a later stage.
3. Welcome wild and unusual ideas: These push the boundaries of the solution space and may trigger practical
ideas from others.
4. Combine and improve ideas: Build on suggestions made by others. “Hitchhiking” on an idea is encouraged:
“What if we took Alice’s idea and combined it with Bob’s?”

3.4.3 How to Conduct a Brainstorming Session

Individual brainstorming:
 Define the problem as a clear, focused question.
 Set a timer (e.g., 10–15 minutes).
 Write down every idea that comes to mind, without self-censorship.
 After the session, review, cluster related ideas, and then evaluate.
Group brainstorming:
 A facilitator states the problem and enforces the rules.
 Participants call out ideas; all are recorded on a whiteboard or sticky notes.
 After the designated time, the group organises ideas into themes and begins the critical evaluation phase,
applying feasibility, cost, and impact criteria.

3.4.4 Brainstorming in the Problem-Solving Framework

Brainstorming is most valuable in the Devise a Plan stage, especially for non-routine, ill-defined problems where
the solution space is wide open. It is a heuristic for generating candidate approaches, not for solving the problem
directly. Once ideas are generated, you can switch to analytical techniques (hypothesis testing, reduction, algorithmic
thinking) to develop and validate the chosen direction.

3.4.5 Pitfalls and Mitigations

 Social loafing: In groups, some individuals may coast. Mitigation: write ideas individually first, then share
(brainwriting).
 Evaluation apprehension: People hold back for fear of looking foolish. A skilled facilitator can create
psychological safety.
 Production blocking: Only one person can speak at a time, slowing idea flow. Brainwriting or digital
brainstorming tools help.
 Lack of follow-through: Brainstorming without a subsequent evaluation and action plan is wasted time.
Always schedule a convergent phase.

Common Examples
 Planning a surprise birthday party: A group of friends brainstorms possible party themes: “pirate ship,”
“Hollywood red carpet,” “escape room,” “retro arcade,” “virtual reality party.” No idea is rejected at this
stage. Later, they narrow down based on budget, the birthday person’s preferences, and logistical feasibility.
 Family vacation ideas: Members throw out destinations: “beach resort,” “mountain cabin,” “cross-country
road trip,” “space camp,” “volunteering abroad.” The wild ideas (space camp) may spark a compromise like
visiting a science museum with a space exhibit.

Computing Examples
 Designing a mobile app feature: The product team brainstorms ways to improve user engagement. Ideas
include: “daily streaks,” “leaderboard,” “personalised daily tips,” “augmented reality mascot,” “random acts
of kindness challenges,” “integration with smart fridge.” Later, these are evaluated against user research,
technical feasibility, and business goals.
 Choosing a software architecture: A technical team brainstorms architectures for a real-time chat
application: “client-server with polling,” “WebSockets,” “peer-to-peer WebRTC,” “MQTT broker,”
“serverless with AWS AppSync.” The brainstorming surface options that might not have been considered if
the team jumped straight to their default choice.

Debugging a mysterious system crash: Developers brainstorm potential causes: “memory leak,” “race condition,”
“disk full,” “third-party API timeout,” “cosmic ray bit flip.” The last one is whimsical, but it keeps the team open to
looking at unlikely but real hardware faults

3.5 Trial and Error

3.5.1 Definition and Core Idea
Trial and error are the most fundamental empirical problem-solving method. It consists of making successive
attempts (trials), observing the outcome of each attempt, and using the resulting feedback to adjust the next attempt
until a satisfactory solution is found or the problem space is exhausted. Trial and error are the method of last resort
when no theory, algorithm, or heuristic is readily available. It is also the first method employed by infants exploring
the world, and by scientists in the earliest stages of investigating an unknown phenomenon.

3.5.2 Variants of Trial and Error

 Random trial and error: Attempts are made haphazardly, with no memory of past failures. This is the least
efficient and often fails to converge, but requires no planning.
 Systematic trial and error: Attempts are varied in a structured way. Each failure eliminates a class of
possibilities. This is the basis of search algorithms in artificial intelligence.
  Informed trial and error: Feedback from each trial is used intelligently to steer subsequent attempts toward
more promising regions of the search space. This shades into heuristic search.

3.5.3 The Process

1. Make an initial attempt. Based on whatever knowledge you have, try a candidate solution.
2. Observe the result. Did it succeed? Did it fail? How far was it from the goal? What kind of error occurred?
3. Learn from failure. Analyse why the attempt failed. Formulate a hypothesis (even informally) about what
went wrong.
4. Adjust and retry. Modify your attempt to correct the error, or try a completely different approach if the
current one seems hopeless.
5. Repeat until success or until resources (time, money, patience) are exhausted.

3.5.4 Advantages and Disadvantages of Trial and Error

Advantages Disadvantages
Universally applicable; requires no prior Can be extremely slow; may not scale.
theory.
Simple to implement and automate. No guarantee of finding a solution within resource constraints.
Can discover unexpected solutions Random trial and error can be inefficient and miss the solution
(serendipity). entirely if the search space is vast.
Forms the basis of powerful machine Systematic exploration often still requires an exponential number of
learning techniques. trials for hard problems.

3.5.5 When to Use Trial and Error

 When you have no better method and the search space is small enough to explore.
 As a component of a larger heuristic or learning system.
 For diagnostic problems where you can test potential causes rapidly.

However, in most computing problems, pure trial and error is a starting point, not the final solution. The goal of
learning algorithms is to replace exhaustive trial and error with intelligent, directed search.

Common Examples
 Fitting a jigsaw puzzle piece: You pick up a piece and try it in a spot. If it does not fit, you try another
orientation or another spot. Over time, you learn the shapes and colours, making future trials more informed.
 Finding the right key on a keyring: You try each key sequentially until the lock turns. If you label or mark
keys based on past experience, you improve the process.
 Cooking without a recipe: You add a pinch of salt, taste; not enough, add more; too much, add a potato (a
classic fix). Each taste-test is a trial.

Computing Examples
 Brute-force password cracking: An attacker tries every possible combination of characters until the correct
password is found. This is a pure trial-and-error method, and its only virtue is guaranteed success – if enough
time is available. The exponential growth of the search space with password length makes it impractical
beyond a certain length, which is why we need cryptographic strength.
 Genetic algorithms: These are a sophisticated computational instantiation of trial and error. A population of
candidate solutions is generated randomly. Each candidate is evaluated against a fitness function. The best
candidates are selected, combined (crossover), and mutated to produce a new generation. Over many
generations, the population evolves towards better solutions. This is massively parallel, automatically-
informed trial and error.
  Debugging with print statements: When a program behaves unexpectedly, a novice programmer often
inserts print statements at various points to see the values of variables. Each run is a trial. Seeing an
unexpected null might lead to a correction. The process is iterative: add prints, run, observe, adjust, run again.
 Reinforcement learning: An AI agent takes actions in an environment and receives rewards or penalties. It
learns a policy by trial and error. AlphaGo, which defeated the world champion in Go, learned by playing
millions of games against itself, trying moves and learning from wins and losses.

3.6 Hypothesis Testing

3.6.1 Definition and Core Idea
Hypothesis testing is a systematic, evidence-based technique for diagnosing problems and evaluating solution ideas.
It involves:
1. Formulating a hypothesis – a specific, testable conjecture about the cause of the problem or the effect of a
proposed solution.
2. Designing and executing an experiment to test the hypothesis.
3. Analysing the results to accept, reject, or refine the hypothesis.
Hypothesis testing adds rigour to trial and error. Instead of blindly trying things, you reason: “If my understanding
is correct, then doing X should produce result Y. If it does not, my understanding is wrong.” This is the scientific
method applied to everyday problem solving.

3.6.2 The Process in Detail

1. Observe and gather data: What are the symptoms? What patterns do you notice? Collect quantitative and
qualitative information.
2. Form a hypothesis: Propose a possible explanation. A good hypothesis is:
o Specific: “The server crashes due to a memory leak in the image processing module.”
o Falsifiable: It must be possible to imagine an experiment whose outcome would contradict the
hypothesis.
3. Derive a prediction: “If the hypothesis is true, then when I monitor memory usage while repeatedly
processing images, I should see a monotonic increase in memory consumption that is never reclaimed,
eventually leading to a crash.”
4. Design a controlled test: Minimise confounding variables. Have a baseline for comparison if possible.
5. Execute the test and collect results.
6. Interpret the results:
o If the prediction matches observation, the hypothesis is supported (not proven, but strengthened).
o If the prediction fails, the hypothesis is falsified. You must discard or revise it and formulate a new
one.
7. Iterate: Use the new understanding to refine the diagnosis or solution.

3.6.3 Why Hypothesis Testing Is Powerful

 Efficiency: Instead of randomly changing things (pure trial and error), you systematically eliminate large
classes of causes with each experiment.
 Learning: Even a failed experiment teaches you something definitive about the system.
 Collaboration: Hypotheses and test results can be communicated clearly to team members.
3.6.4 Pitfalls and Cautions
 Confirmation bias: The human tendency to seek evidence that confirms our pet hypothesis while ignoring
disconfirming evidence. A good scientist actively tries to falsify their own hypothesis.
 Confounding variables: Your test might give a misleading result because you changed two things at once
and don’t know which one caused the effect. Always change one variable at a time if possible.
 Overgeneralisation: A hypothesis supported by a single experiment is not yet a proven fact. Replicate the
test under different conditions.
Common Examples
 Car won’t start.
o Symptom: Turning the key produces a clicking sound, engine does not crank.
o Hypothesis 1: The battery is dead.
o Prediction: If the battery is dead, the headlights should be very dim or not turn on at all.
o Test: Turn on the headlights.
o Result: Headlights are bright. Hypothesis 1 rejected.
o Hypothesis 2: The starter motor solenoid is faulty.
o Prediction: If the solenoid is faulty, the clicking sound should come from the starter area, and a
voltage test at the starter terminal while turning the key should show low or no voltage.
o Test: Use a multimeter at the starter terminal.
o The process continues until the true cause is identified.
 Medical diagnosis: A doctor observes symptoms (fever, sore throat). Hypothesis: strep throat. Test: rapid
strep test. Positive result → treat with antibiotics. Negative result → new hypothesis (viral pharyngitis).

Computing Examples
 Website performance slowdown.
o Observation: The homepage takes 8 seconds to load instead of the usual 1 second.
o Hypothesis 1: The database query that fetches featured products has become slow due to a missing
index after a recent migration.
o Prediction: If I run the query directly with EXPLAIN ANALYZE, it should show a sequential scan
and high execution time.
o Test: Execute the query profiler. Result: query uses index and runs in 20ms. Hypothesis rejected.
o Hypothesis 2: A third-party API call (e.g., currency converter) is timing out.
o Prediction: The network timeline in browser developer tools will show a long stalled request to the
API endpoint.
o Test: Inspect network waterfall. Result: the currency API request takes 7 seconds. Hypothesis
supported.
o Solution: Implement a cache or a circuit breaker.
 Algorithm correctness.
o Observation: Your new sorting algorithm works for small arrays but occasionally produces unsorted
output for large ones.
o Hypothesis: An off-by-one error in the merge step when the array length is odd.
o Prediction: If the error is caused by an odd length, running the algorithm on arrays of sizes 100, 101,
102, etc., should show failure only on certain lengths.
o Test: Write a test that runs the algorithm on thousands of random arrays of increasing size and checks
maybe it is sorted. The output of the test pinpoints the failing sizes. You examine the code and find
the bug. Hypothesis confirmed by the pattern.

3.7. Reduction
3.7.1 Definition and Core Idea
Reduction (also called problem reduction or transform-and-conquer) is the technique of solving a problem by
transforming it into another problem for which a solution is already known. You map the original problem onto a
target problem, solve the target problem using existing methods, and then map the solution back.
In computational complexity theory, reduction has a precise technical meaning: problem A is reducible to problem
B if an algorithm that solves B can be used as a subroutine to solve A, with only a polynomial amount of extra work.
But the practical spirit of reduction is broader: if I can express my problem in terms of a problem I already know
how to solve, I am done.

3.7.2 The Reduction Process

1. Analyse the original problem. What are its inputs, outputs, and constraints?
2. Identify a known problem (or a simpler variant) that shares the same deep structure. This is often the hardest
step and requires a good knowledge of standard computational problems (sorting, searching, graph problems,
linear programming, satisfiability, etc.).
3. Define a mapping (transformation) from instances of your problem to instances of the known problem.
4. Apply the known algorithm to the transformed instance.
5. Map the result back to the original problem’s domain, if necessary.

3.7.3 Reduction vs. Analogy

Reduction is a more formal, algorithmic cousin of analogy. Both involve mapping a new problem to a known one.
The difference lies in precision:
 Analogy is often qualitative and heuristic. It transfers insight and strategy, but the mapping may be loose
and require creative adaptation.
 Reduction aims for an exact, often mathematical mapping that guarantees that a solution to the known
problem is also a valid solution to the original problem, perhaps after transforming the instance and the
output.

3.7.4 Pitfalls
 Incorrect mapping: If the transformation is not faithful, the solution to the reduced problem may be invalid
for the original. Always verify that the mapping preserves all constraints and objectives.
 Transformation overhead: The reduction itself might be computationally expensive. If the reduction plus
the known algorithm takes longer than a direct solution, the approach is counterproductive. Always consider
the combined cost.
 The “hammer” syndrome: If you only know one problem (e.g., you just learned SAT solving), you might
force every problem into that mould even when a simpler, more efficient direct solution exists. Good problem
solvers maintain a broad toolkit.
3.7.5 Integrating the Six Techniques into the Problem-Solving Process
These six techniques are not mutually exclusive; they are often used in combination. Consider a typical workflow
for a complex, non-routine problem:
1. Brainstorming to generate a wide range of potential approaches and clarify the goal.
2. Abstraction to strip the problem down to its essentials and build a manageable model.
3. Analogy and Reduction to connect the abstracted problem to known solution classes.
4. Hypothesis testing to evaluate and compare the feasibility of candidate solutions or to diagnose the root
cause of an observed failure.
5. Trial and error as a fallback when the search space is small or when systematic knowledge is lacking.

In the “Devise a Plan” stage of Pólya’s model, you may cycle through several of these techniques before settling on
a concrete plan.

Common Examples
 Fitting furniture through a doorway: You have a large sofa and need to know if it will fit through a 90 cm
wide door. You could lift and try (trial and error), but you can reduce the problem to a geometric one: measure
the sofa’s narrowest cross-section in all orientations. The problem becomes a 2D shape fitting through a
rectangle – a problem of comparing dimensions. If the sofa’s cross-section can be inscribed in a 90 cm wide
rectangle at some angle, it will fit. This reduction saves your back and your walls.
  Finding a mutual friend: You want to know if you have a path of acquaintances to a certain influential
person. This reduces to the graph reachability problem: people are nodes, friendships are edges. You can
then apply breadth-first search (or simply visualise the social graph) to find a path.
 Cooking for a large group: You need to plan a menu that meets various dietary restrictions. This reduces to
a constraint satisfaction problem: assign dishes to courses such that all constraints (vegan, gluten-free, no
peanuts) are satisfied. You can use a logic grid or a simple backtracking approach in your head.
Computing Examples
 Finding the median of an array: This can be reduced to sorting the array and picking the middle element
(O(*n* log *n*)). But it can also be reduced to the selection problem (finding the *k*th smallest element),
which has a linear-time algorithm (Quickselect). Knowing these reductions allows you to choose the best
available tool.
 Scheduling as graph colouring: You need to schedule final exams so that no student has two exams at the
same time. Represent each course as a node; draw an edge between two courses if they share at least one
student. The problem reduces to graph colouring: assign each node a colour (time slot) such that no adjacent
nodes share the same colour. You can then use graph colouring heuristics to produce a conflict-free schedule.
 Boolean satisfiability (SAT) as a universal reduction target: Many hard problems – planning, hardware
verification, software testing, Sudoku solving – can be reduced to SAT. First, you encode your problem as a
set of Boolean variables and constraints in Conjunctive Normal Form (CNF). Then, you feed it to a state-of-
the-art SAT solver. If the solver finds a satisfying assignment, you decode it back to a solution for your
original problem. This approach is used extensively in industry because SAT solvers have become
remarkably efficient.
 Using library functions: When you use a built-in sort() function in Python or C++, you are practising
reduction. You have a problem: “arrange these records in order of date.” You reduce it to a standard sorting
problem by specifying a comparison key, and the library’s highly optimised algorithm does the rest. You did
not need to write Timsort or introsort yourself.
 The concept of NP-completeness: The theory of NP-completeness, which we touched on in Week 2, is built
on the idea of reduction. If problem A is NP-complete, every problem in NP can be reduced to A. Thus, if
you find a polynomial-time algorithm for A, you have effectively solved all problems in NP. The famous “P
= NP” question is fundamentally about whether such reductions can go both ways.

3.7.6 Summary
This week we armed ourselves with six fundamental problem-solving techniques:
 Abstraction teaches us to focus on what matters by building simplified models.
 Analogy lets us borrow solutions from familiar domains.
 Brainstorming unleashes creative, divergent thinking without premature judgment.
 Trial and error provide a fallback empirical method, from brute-force to sophisticated genetic algorithms.
 Hypothesis testing brings scientific rigour to diagnosis and evaluation.
 Reduction leverages the power of mapping a new problem to an already solved one.
Week 4

Solution Techniques – Part II

4.1. Introduction
Last week we began building your problem-solving toolkit with six powerful techniques: abstraction, analogy,
brainstorming, trial and error, hypothesis testing, and reduction. These methods help you to model problems,
generate ideas, and connect new challenges to known solutions. This week we would complete the toolkit by
exploring eight additional techniques. Some of these, like lateral thinking and the method of focal objects, stretch
your creativity. Others, such as means-end analysis and divide and conquer, provide rigorous, step-by-step
approaches to complex tasks. Still others – research, root cause analysis, and proof – ground your problem solving
in evidence, depth, and logical certainty. Collectively, these fourteen techniques form a comprehensive collection
for tackling the widest variety of problems you will encounter in computing and beyond.

4.2. Lateral Thinking

4.2.1 Definition and Origins
Lateral thinking is a term coined by the Maltese physician and psychologist Edward de Bono in 1967. It refers to
a deliberate, creative approach to problem solving that seeks to break free from conventional, linear (or “vertical”)
thinking. While vertical thinking follows logical steps along established paths, lateral thinking aims to restructure
patterns, escape dominant ideas, and generate novel insights by approaching the problem from unexpected
angles.
De Bono emphasised that lateral thinking is not a mystical talent; it is a set of teachable techniques that can be
practised. In computing, where algorithmic and logical thinking dominate, lateral thinking reminds us that
innovation often requires stepping outside the established framework.

4.2.2 Core Principles and Techniques

1. Challenging assumptions: Identify the unspoken assumptions that define the boundaries of the problem and
deliberately question them. Often, a “constraint” is self-imposed and can be removed.
2. Generating alternatives: Consciously produce multiple, diverse solution ideas – even if they seem absurd
– before evaluating any of them. This is closely related to brainstorming but with an emphasis on breaking
the patterns that first come to mind.
3. Provocation: Use provocative statements that are intentionally false or impossible to jolt the mind out of its
rut. For example, “Cars have square wheels.” Then explore the consequences: “If cars had square wheels,
what would roads look like?” This can lead to ideas about suspension systems or continuous track designs.
4. Random entry: Introduce a completely unrelated word, image, or object and force a connection to the
problem. This technique will be formalised in the “method of focal objects” later in this lecture.

Common and Classic Examples

 The hotel elevator problem: A hotel manager received complaints that the elevators were too slow.
Conventional solutions (faster motors, more elevators) were expensive. A lateral-thinking consultant
suggested placing full-length mirrors next to the elevator doors. People became distracted by looking at
themselves and stopped noticing the wait time. The problem was reframed from “reduce waiting time” to
“reduce perceived waiting time.”
 The nine-dot puzzle: Connect all nine dots of a 3×3 grid with four straight, continuous lines without lifting
the pen. Most people fail because they unconsciously assume the lines must stay within the “square” of the
 dots. The solution requires drawing lines that extend outside the perceived boundary – literally thinking
outside the box. (The phrase “thinking outside the box” is popularly derived from this puzzle.)

Computing Examples
 CAPTCHA: The problem of distinguishing humans from bots on websites was initially approached with
distorted text that humans could read but OCR software could not. A lateral shift was reCAPTCHA, which
asks users to transcribe two words, one known and one unknown, thus harnessing human effort to digitise
old books. The problem “keep bots out” was combined with a completely unrelated problem “digitise books.”
 The Web browser as an application platform: In the late 1990s, web browsers were seen as document
viewers. The idea of running full-fledged applications inside a browser – with technologies like AJAX, and
later SPAs – required lateral thinking. It broke the assumption that the desktop OS was the only viable
application host.
 Dropbox’s viral growth model: When Dropbox struggled to acquire users through paid advertising, they
applied a lateral-thinking provocation: “What if our product grew by not spending on advertising?” This led
to the famous referral programme that gave free storage to both referrer and referee, exploding their user
base.

4.2.3 Practical Application

When you are stuck on a problem, especially one that resists algorithmic formulation, take a lateral step:
 List your assumptions explicitly. Cross out the most fundamental one and see if the problem still makes sense
without it.
 Open a dictionary at a random page, pick a noun, and try to relate it to your problem.
 Ask “what if the opposite were true?”

4. 2.4 Limitations
Lateral thinking is inherently a divergent, creative process. It produces candidate ideas, not verified solutions. It
must be followed by convergent, analytical evaluation. Moreover, in safety-critical or formally specified computing
tasks, lateral thinking without rigour can lead to unsound designs. Use it where innovation and reframing are needed,
but ground the results with the other techniques in this course.4

4.3. Means-End Analysis

4.3.1 Definition and Historical Context
Means-end analysis is a problem-solving strategy that reduces the gap between the current state and the goal state
by systematically identifying differences and applying operators (actions) that reduce those differences. It was a
central mechanism of the General Problem Solver (GPS), an early AI program developed by Allen Newell and
Herbert A. Simon in the late 1950s. GPS was one of the first attempts to simulate human problem solving on a
computer.

4.3.2 The Process

1. Define the current state and the desired goal state precisely.
2. Compare the current state to the goal state. Identify the most important difference(s).
3. Find an operator (an allowed action or transformation) that reduces this difference. If the operator cannot
be applied directly (because its preconditions are not satisfied), a new subgoal is created: to make the
operator applicable.
4. Apply the operator once its preconditions are met, moving to a new current state.
5. Repeat recursively until no differences remain.
This recursive generation of subgoals is the essence of means-end analysis. The process can be visualised as a tree
of goals and subgoals.
4.3.3 The Tower of Hanoi
The classic puzzle that best illustrates means-end analysis is the Tower of Hanoi. The problem is as follows:
There are three pegs (A, B, C) and *n* disks of different sizes. Initially, all disks are stacked on peg A in decreasing
size from bottom to top. The goal is to move the entire stack to peg C, obeying the rules:
1. Only one disk can be moved at a time.
2. A larger disk may never be placed on top of a smaller disk.

Applying means-end analysis for n = 3 (or any n):

 Initial state: All disks on A. Goal state: All disks on C.
 Difference: The largest disk (disk *n*) is not on C. More precisely, disk *n* is on A and must be on C.
 Operator to reduce difference: Move disk *n* from A to C.
 Precondition for that operator: Disk *n* must be on top of a peg (i.e., no disk on top of it), and peg C must
have no disk smaller than *n* (i.e., it must be empty or have only larger disks, which is impossible since *n*
is the largest, so C must be empty).
 New subgoal: Move all *n-1* disks from the top of *n* on A to peg B. This will clear disk *n* so it can
move to C.
 We now recursively solve the subproblem: move *n-1* disks from A to B, using C as the spare.
 After achieving that, we can move disk *n* from A to C (the one step that reduces the main difference).
 Finally, a new difference: the *n-1* disks are on B, but they need to be on C on top of disk *n*. So we create
a new subgoal: move the *n-1* disks from B to C, using A as the spare.
 This yields the recursive algorithm, which can be implemented elegantly.
Means-end analysis thus transforms an initially bewildering puzzle into a clear, recursive plan. It is not just a toy:
the same reasoning underlies backward-chaining in expert systems and automated planning in robotics.

4.3.4 Other Applications

 Troubleshooting a network issue: Current state: network is down. Goal: all services reachable. Differences:
specific server unresponsive. Operator: restart the service. If restart precondition is that the host must be
reachable, subgoal: diagnose physical co
 nnectivity, and so on.
 Writing a compiler: The difference between source code and machine code is bridged by a series of
operators (lexical analysis, parsing, semantic analysis, code generation), each with preconditions that guide
the design.

4.3.5 Strengths and Limitations

Means-end analysis works well when the problem can be represented as a well-defined state space and the operators
are known. It can, however, be computationally expensive and may not find a solution if the necessary operators are
not available or if the problem requires temporarily increasing a difference to eventually reduce it (a limitation
known as the “non-monotonic” problem). Despite its age, the core idea remains fundamental in AI and software
design.

4.4. Method of Focal Objects

4.4.1 Definition
The method of focal objects is a creativity technique that forces a connection between a central problem (the “focal
object”) and one or more randomly chosen, unrelated objects. By examining the attributes of the random objects and
linking them to the focal object, novel ideas and solutions emerge that would not arise from focused, linear analysis
alone.
The technique was developed by Charles S. Whiting in the 1950s and has been used in product design, advertising,
and innovation management.
4.4.2 The Process
1. Select the focal object: Clearly define the product, system, or problem you want to improve or redesign.
2. Select random objects: Choose a few items arbitrarily – from a dictionary, a magazine, or your immediate
environment. Their only requirement is that they be unrelated to the problem.
3. List attributes or associations for each random object. What are its properties, functions, shapes, materials,
behaviours?
4. Force connections: For each attribute, ask: “How could this attribute be applied to the focal object?” or
“What if the focal object had this attribute?”
5. Generate ideas: Write down all resulting concepts, no matter how far-fetched. Later, evaluate and refine the
most promising ones.

Common Example
 Focal object: A new design for a chair.
 Random object: A cat.
 Attributes of a cat: Flexible, self-cleaning, retractable claws, purrs when comfortable, lands on its feet.
 Forced connections:
o Flexible: Chair that conforms to the sitter’s posture.
o Self-cleaning: Chair with a coating that repels stains.
o Retractable claws: Chair with fold-away armrests or cup holders.
o Purrs: Chair with built-in massage or gentle vibration when weight is detected.
o Lands on its feet: Chair with self-righting mechanism if tipped over (for children).
 Some of these ideas are impractical, but others could lead to innovative product features.

Computing Examples
 Focal object: A new mobile app for managing personal finances.
 Random object: A garden.
 Attributes: Grows over time, needs watering, has different seasons, attracts bees, composed of many small
plants.
 Ideas:
o Grows over time: App that shows your savings growing as a virtual tree; the healthier the finances,
the bigger the tree.
o Seasons: App adapts its interface and advice based on “financial seasons” (holiday spending, tax
season, bonus time).
o Attracts bees: Social features that encourage “pollination” of good financial habits among friends
(peer saving challenges).
 Focal object: Algorithm to detect spam emails.
 Random object: A library.
 Attributes: Catalogues items, uses Dewey Decimal system, librarians check authenticity, rare books section.
 Ideas: Treat emails as books; classify them using a “digital Dewey” system; a “librarian” AI agent that learns
to recognise trusted vs. suspicious content. (This mirrors real-world email classification using Bayesian
filtering and reputation systems.)

4.4.3 Strengths and Limitations

The method of focal objects is excellent for breaking mental fixations and generating truly original ideas. It is,
however, highly stochastic: the quality of output depends on the random objects chosen and the creativity of the
participants. It is best used in the early, divergent stages of problem solving, followed by rigorous filtering using the
more analytical techniques we have studied.

4.5. Morphological Analysis

4.5.1 Definition
Morphological analysis is a systematic, non-quantitative method for structuring and exploring the entire set of
possible solutions to a multi-dimensional, complex problem. It was developed by the Swiss astrophysicist Fritz
Zwicky in the 1940s to study jet propulsion and later applied to a wide range of engineering, design, and policy
problems.
The name comes from the Greek morphē (form, shape) and logos (study): it studies the forms or configurations that
a solution can take.

4.5.2 The Process of Building a Morphological Box

1. Identify the key dimensions or parameters of the problem. These are the independent axes along which
the solution can vary. For a product, parameters might be “material,” “power source,” “size,” “target user.”
2. List possible values or conditions for each parameter. The lists should be as exhaustive as possible.
3. Construct a matrix (often called a Zwicky box or morphological box) with one row per parameter, and the
values arranged along the row.
4. Generate combinations by selecting one value from each row. The total number of theoretical combinations
is the product of the number of values per parameter – which quickly becomes enormous. Many
combinations will be impossible or nonsensical; the value is in systematically considering combinations that
might otherwise be overlooked.
5. Evaluate and prune the combinations, identifying feasible and promising solutions.

Sample of the Problem: Design a new personal transportation device.

Parameter Possible Values

Propulsion Electric motor, petrol engine, human-powered (pedals), hydrogen fuel cell
Medium Road, water, air, rail, off-road
Numberof passengers 1, 2, 4, 8+
Body material Steel, aluminium, carbon fibre, plastic, bamboo
Control interface Steering wheel, handlebars, joystick, voice command

Exploring the combinations: (Electric motor, water, 1, plastic, joystick) → a personal electric watercraft; (Human-
powered, air, 1, carbon fibre, handlebars) → a human-powered aircraft (challenging but exists); (Hydrogen fuel cell,
road, 4, aluminium, voice command) → a hydrogen SUV with voice control.
Many combinations are impractical, but some spark genuine innovation. This method ensures that no stone is left
unturned.

4.5.3 Computing Applications

 Software testing: Each parameter can be an input variable or environmental condition. A morphological box
represents the full combinatorial test space. Pairwise or combinatorial testing tools systematically sample
this space.
 Algorithm design: Parameters: data structure (array, linked list, tree, hash table), traversal order, recursion
vs. iteration, in-place vs. extra memory. Exploring the matrix can suggest novel hybrid algorithms.
 User interface design: Parameters: input modality (touch, mouse, keyboard, voice), output (visual, audio,
haptic), navigation style (tabs, scroll, cards, wizard), colour scheme. Systematically combining these yields
a comprehensive set of design alternatives.
 Security threat modelling: Use morphological analysis to enumerate attack vectors: attacker location, skill
level, attack vector, target asset, etc.

4.5.4 Strengths and Limitations

Morphological analysis is exhaustive and structured, making it suitable for complex, multi-faceted problems.
However, it suffers from combinatorial explosion; a box with 8 parameters each having 5 values yields nearly
400,000 combinations. Pruning and judgment are essential. It works best when the problem can be decomposed into
clear dimensions.

4.6. Research
4.6.1 Definition and Importance
In problem solving, research is the systematic investigation and study of materials, sources, and data in order to
establish facts and reach new conclusions. It is not a single flash of insight but a sustained, disciplined process. In
computing, research means finding out what already exists before trying to build something new: algorithms,
libraries, frameworks, prior art, and empirical performance data.
Too often, novice problem solvers attempt to solve a problem from scratch, unaware that a solution already exists,
or that key information is available. Research bridges the gap between isolated ingenuity and collective human
knowledge.

4.6.2 The Research Process

1. Define the research question or information need. What exactly do you need to know? Be specific.
2. Identify sources: In computing, these include academic papers (via Google Scholar, IEEE Xplore, ACM
Digital Library), technical documentation, open-source repositories (GitHub), textbooks, and reputable
online communities (Stack Overflow with caution).
3. Collect and review information: Read broadly at first, then narrow. Distinguish between primary sources
(original algorithm paper) and secondary sources (tutorials). Take notes.
4. Synthesise and analyse: Compare approaches. What are the trade-offs? Under what conditions does each
work best? Is there a gap that your problem fills?
5. Apply the findings: Adapt existing knowledge to your specific problem context. Credit your sources.
6. Evaluate: Does the researched solution meet your requirements? If not, iterate.

Examples
 Choosing a sorting algorithm for an embedded system: Research reveals that quicksort has excellent
average-case performance but worst-case O(n²) and requires O(log *n*) stack space. IntroSort (used in C++
STL) switches to heapsort when recursion depth is high, guaranteeing O(*n* log *n*). For very small arrays,
insertion sort is fastest. This research leads you to implement a hybrid approach tailored to your memory-
constrained device.
 Building a real-time chat application: Before coding, you research existing protocols. You discover
WebSockets (full-duplex, low overhead), MQTT (publish-subscribe for IoT), and server-sent events (simpler
but unidirectional). You evaluate each against your latency and scalability needs.
 Understanding a bug: A cryptic error message “segmentation fault” in a C program. Research the error
leads you to understand that it indicates memory access violation. You then research tools like Valgrind and
AddressSanitizer to detect the exact line. Research transforms a mysterious crash into a solvable puzzle.

4. 6.3 The Role of Research in Algorithm Discovery

Many of the algorithms we use today were not invented in a single stroke. Newton’s method for root-finding built
on earlier iterative approximations; Dijkstra’s shortest path algorithm emerged from studying the mathematical
properties of graphs. Modern problem solvers stand on the shoulders of giants. Research ensures you do not waste
time reinventing a square wheel.

4.7. Root Cause Analysis

4.7.1 Definition
Root cause analysis (RCA) is a class of problem-solving methods aimed at identifying the fundamental, underlying
cause of a problem, rather than merely treating its symptoms. Removing a symptom may provide temporary relief,
but if the root cause remains, the problem will recur. RCA is widely used in software engineering, manufacturing,
healthcare, and business.

4.7.2 Techniques
a. The Five Whys.
Developed by Sakichi Toyoda and used within the Toyota Production System, the 5 Whys technique involves
repeatedly asking “Why?” to peel away layers of symptoms and reach the root cause. The number five is a
guideline, not a strict rule; the key is to continue until the answers become process-level rather than human-error-
level.

Example: A website is down.

 Why? The web server ran out of memory.
 Why? A new deployment increased the memory footprint of the application.
 Why? The development team did not profile memory usage before deploying.
 Why? There is no performance testing stage in the continuous integration pipeline.
 Why? The team was never trained on memory profiling tools, and management prioritised speed over
quality.

The root cause is not “the server ran out of memory” (that is a symptom). It is a process failure: lack of automated
performance testing and training. The corrective action is to implement profiling in CI, not just to restart the server.

b. Fishbone (Ishikawa) Diagram

A visual tool that categorises potential causes of a problem into major groups (e.g., Methods, Machines, Materials,
Manpower, Measurement, Environment – the 6 Ms). The team brainstorms possible causes within each category and
drills down to root causes. This is especially useful in collaborative settings.

c. Fault Tree Analysis (FTA)

A top-down, deductive approach that starts with the undesirable event and uses Boolean logic to combine a series
of lower-level events. It is common in safety-critical systems (aviation, nuclear power) to quantify failure
probabilities and identify single points of failure.

4.7.3 Computing Applications

 Recurring software bugs: A bug keeps reappearing after being “fixed.” Instead of another patch, RCA might
reveal that the underlying module has an anti-pattern (e.g., global state causing unpredictable interaction),
and the fix should be a refactor.
 System outages: After a major incident, a blameless post-mortem is conducted. RCA identifies that the
outage was caused by a cascading failure due to a missing circuit breaker, not by the developer who pushed
the config change. The solution is architectural, not punitive.
 Security incidents: A breach occurs. RCA traces the attack path back to an unpatched library, which in turn
was caused by a lack of automated dependency scanning. The root cause is the missing process, not the
vulnerability itself.

4.7.4 Mindset
RCA requires a culture that focuses on systems and processes, not on blaming individuals. The question is not “Who
caused this?” but “What in our system allowed this to happen, and how do we prevent it in the future?”

4.8. Proof
4.8.1 Proof as a Problem-Solving Technique
In mathematics and computer science, proof is the process of establishing the truth or validity of a statement beyond
doubt, using a sequence of logical deductions from accepted axioms, definitions, and previously established facts.
In problem solving, proof serves two primary functions:
 Verification: Once a solution is proposed, proof demonstrates that it is correct and meets all specifications.
 Derivation: Sometimes, constructing a proof leads directly to an algorithm or reveals the structure of the
solution. For example, proving a loop invariant leads to a correct iterative program.

4.8.2 Deductive Reasoning

Deduction moves from general principles to a specific conclusion. If the premises are true and the reasoning is valid,
the conclusion is guaranteed to be true.
Syllogism (classic example):
 Premise 1: All algorithms that terminate and use at most O(*n* log *n*) comparisons are comparison-based
sorting algorithms that are optimal in the comparison model. (A general theorem)
 Premise 2: Merge sort is an algorithm that terminates and uses O(*n* log *n*) comparisons.
 Conclusion: Merge sort is an optimal comparison-based sorting algorithm.

In computing: Deductive reasoning is used to prove algorithm correctness via invariants. A loop invariant is a
condition that is true before and after each iteration of a loop. By proving that the invariant holds upon entry, is
maintained by each iteration, and that it implies the desired output when the loop terminates, you prove the loop’s
correctness.
Example: Proving binary search.
 Invariant: If the target value T is in the array, it lies between indices low and high (inclusive).
 Base: Initially low=0, high=*n*-1, trivially true.
 Maintenance: The midpoint calculation and comparison eliminate the half that cannot contain T. The
invariant is preserved.
 Termination: The loop ends when low > high, meaning the subarray is empty. If T were present, it would
have been in a non-empty subarray. Combined with the invariant, T is not in the array. The algorithm returns
“not found.” If T was found earlier, the algorithm returned the index.
This proof eliminates doubt: binary search is correct, not just “it seems to work.”

4.8.3 Inductive Reasoning

Induction moves from specific observations to a general conclusion. The conclusion is probable, but not guaranteed,
and may be falsified by further evidence. In problem solving, induction helps us to discover patterns and formulate
conjectures.
Example: You observe that 1+2=3, 1+2+3=6, 1+2+3+4=10. You induce that the sum of the first *n* positive integers
is *n*(*n*+1)/2. You then prove it by mathematical induction, which is actually a deductive technique. Mathematical
induction is a formal proof method: prove a base case (e.g., *n*=1) and prove that if the statement holds for *n*, it
holds for *n*+1. This provides certainty.

In computing: When designing a recursive divide-and-conquer algorithm, you often hypothesize the recurrence
relation by induction on the input size. Empirical testing (e.g., running the algorithm on various inputs) provides
inductive evidence of efficiency, but a formal proof via recurrence relation analysis (Master Theorem) gives
asymptotic guarantees.

4.8.4 Proof and Algorithm Design

Many algorithms are born out of a proof of impossibility or optimality. For example, the proof that any comparison-
based sorting algorithm requires at least Ω(*n* log *n*) comparisons motivates the search for algorithms that
achieve this lower bound. The proof of correctness of Dijkstra’s algorithm relying on the greedy-choice property
and optimal substructure is essential to trusting its implementation.

4.8.5 Proof in Practice

In industry, full formal verification of entire software systems is rare and expensive. However, property-based
testing (e.g., with QuickCheck) uses proofs to guide testing: a developer specifies properties that should hold for all
inputs (e.g., “sorting a list yields a list where every adjacent pair is ordered”), and the framework tests them on
thousands of random inputs. While not a proof, it inculcates a proof-like discipline.
Proof as a technique reminds us that a solution is not complete until we have good reason to believe it is correct.

4.9. Divide and Conquer

4.9.1 Definition
Divide and conquer is a fundamental algorithm design paradigm. The strategy is:
1. Divide: Break the given problem into two or more smaller subproblems that are instances of the same type
of problem.
2. Conquer: Solve the subproblems recursively. If a subproblem is small enough, solve it directly (base case).
3. Combine: Merge the solutions of the subproblems into a solution for the original problem.
This technique is the algorithmic manifestation of the general problem-solving principle of decomposition. It is
responsible for some of the most efficient algorithms in computer science.

4.9.2 Classic Examples

a) Merge Sort
 Divide: Split the array of *n* elements into two halves of roughly equal size.
 Conquer: Sort each half recursively using merge sort.
 Combine: Merge the two sorted halves into a single sorted array.
 Base case: An array of size 1 is already sorted.
The merge step does the heavy lifting: it scans both sorted sub-arrays and picks the smaller head element, creating
a merged array in O(*n*) time. The recurrence relation T(*n*) = 2T(*n*/2) + O(*n*) solves to O(*n* log *n*) by
the Master Theorem.

b) Binary Search (already seen) – Divide by comparing with the middle element; conquer by recursively searching
only one half.
c) Quicksort
 Divide: Choose a pivot; partition the array so that elements less than pivot are on the left, greater on the
right.
 Conquer: Recursively sort the left and right subarrays.
 Combine: Trivial, as the array is sorted in-place after the recursive calls.
 Worst-case O(n²) if pivot selection is poor, but average O(*n* log *n*).

d) Strassen’s Matrix Multiplication

 Naive matrix multiplication takes O(n³) for n×n matrices. Strassen observed that by dividing each matrix
into four quadrants and using seven cleverly designed recursive multiplications instead of eight, the
recurrence T(*n*) = 7T(*n*/2) + O(n²) yields O(*n*^log₂7) ≈ O(*n*^2.807). This was a breakthrough in
theory.

e) Fast Fourier Transform (FFT)

 Divides a discrete Fourier transform of *n* samples into two transforms of *n*/2 samples, exploiting
symmetry, achieving O(*n* log *n*).
4.9.3 Divide and Conquer as a General Problem-Solving Strategy
Beyond formal algorithms, the divide and conquer mentality applies to complex, non-routine problems. Instead of
tackling the entire problem monolithically, you recursively decompose it:
 Project management: A large software project is divided into modules, then submodules, then individual
tasks.
 Debugging: When a program fails, narrow down the faulty component by dividing the codebase: does the
error occur in the frontend or backend? If backend, in the API layer or database layer? Binary search through
the code.
 Learning a new domain: Instead of trying to learn everything about machine learning at once, you divide
the field into supervised, unsupervised, and reinforcement learning, then further subdivide supervised into
regression and classification, and so on.

4.9.4 Activity: Merge Sort Intuition

We will walk through merge sort manually with a small list: [38, 27, 43, 3, 9, 82, 10].
1. Divide into [38, 27, 43, 3] and [9, 82, 10].
2. Further divide until base cases (single elements).
3. Merge step by step:
o Merge [38] and [27] → [27, 38]
o Merge [43] and [3] → [3, 43]
o Merge [27, 38] and [3, 43] → [3, 27, 38, 43]
o Similarly for right half, then merge the two sorted halves.
This is the essence: the problem is made trivial by breaking it down to atomic units and then rebuilding the solution
through a systematic combination step.

4.9.5 When to Use Divide and Conquer

 The problem can be broken into independent, smaller instances of the same problem.
 The subproblems can be combined efficiently.
 The problem size is reduced substantially at each step (usually by a constant factor).
 A direct iterative solution would be less efficient or more complex.
Note that divide and conquer often leads to elegant recursive implementations, which must be checked for stack
overflow and may be optimised with memoisation or dynamic programming if subproblems overlap (though
overlapping is more characteristic of dynamic programming; divide and conquer typically involves non-overlapping
subproblems).

4.10. Integration of All Fourteen Solution Techniques

We have now completed the full set of fourteen techniques outlined in the course contents:

# Technique Type Primary Use

1 Abstraction Analytical Simplifying problem models
2 Analogy Associative Transferring known solutions
3 Brainstorming Creative/Divergent Generating many ideas
4 Trial and Error Empirical Exploring small search spaces
5 Hypothesis Testing Empirical/Analytical Diagnosing causes
6 Reduction Analytical Transforming to a known problem
7 Lateral Thinking Creative Breaking patterns
8 Means-End Analysis Analytical/Strategic Planning step-by-step state transitions
9 Method of Focal Objects Creative Forcing novel associations
# Technique Type Primary Use
10 Morphological Analysis Structural/Systematic Enumerating combinations
11 Research Investigative Gathering existing knowledge
12 Root Cause Analysis Diagnostic Finding underlying causes
13 Proof Analytical/Verification Establishing correctness
14 Divide and Conquer Algorithmic/Structural Decomposing problems recursively

These techniques are not isolated silos. A master problem solver weaves them together. Consider a large-scale
software engineering challenge:
1. Research existing systems and academic papers.
2. Use brainstorming and lateral thinking to generate innovative feature ideas; use the method of focal
objects to create unique user interactions.
3. Abstract the core domain model.
4. Apply morphological analysis to explore architectural alternatives.
5. Use means-end analysis to plan the transformation from current legacy system to new system.
6. Divide and conquer the implementation into modules.
7. Hypothesis testing guides debugging when tests fail.
8. Root cause analysis prevents recurrence of bugs.
9. Proof (or at least rigorous invariant reasoning) ensures critical algorithms are correct.
10. Use trial and error for fine-tuning parameters.
This integrated approach transforms problem solving from an art to a reproducible discipline.

4.11. Summary
This week we completed the survey of solution techniques that every computer science student should master. We
began with lateral thinking, which challenges our assumptions and invites fresh perspectives. Means-end analysis
showed us how to systematically close the gap between a current state and a desired goal, most vividly illustrated
by the Tower of Hanoi. The method of focal objects and morphological analysis gave us structured creativity tools
for product and system design. Research emphasised the importance of building on existing knowledge. Root cause
analysis ensured that we solve problems permanently, not just cosmetically. Proof demanded that our solutions be
logically sound, and divide and conquer provided a powerful algorithm design paradigm that mirrors the way we
naturally decompose complex tasks.
Week 5
The General Problem-Solving Process and Algorithm Development

5.1. Introduction
In the first two weeks of this course, we established what problems are, what kinds of problems exist (routine vs.
non-routine, solvable vs. unsolvable, tractable vs. intractable), and what general classes of solutions we can apply
(algorithms and heuristics). Over the last two weeks we filled your problem-solving toolkit with fourteen specific
techniques, ranging from the creative – such as brainstorming and lateral thinking – to the rigorously analytical –
such as reduction, proof, and divide and conquer.

Now it is time to see how all of these pieces fit together. This week we will study the general problem-solving
process, that is, a universal framework that guides you from the moment you first encounter a problem to the moment
you have a verified, working solution. The framework is not a straitjacket; it is a scaffold that gives structure to your
thinking, ensuring that you do not skip crucial steps or rush to implementation prematurely.

We will base our study on the four-step model proposed by the mathematician George Pólya, and we will see how
each of the fourteen techniques finds its natural home within one or more of these steps. From this structured
thinking, we then move to the beginnings of algorithm design: stepwise refinement and top-down design. We shall
also revisit the formal properties that make a procedure a true algorithm, and practice expressing algorithms in clear,
unambiguous natural language.
Let us begin.

5.2. Pólya’s Four-Step Problem-Solving Process – In Depth

Though introduced briefly in Week 1, we now examine each step with the full benefit of the techniques we have
learned. Pólya’s model is often summarized as:
1. Understand the problem
2. Devise a plan
3. Carry out the plan
4. Look back (evaluate and reflect)
Each stage is essential. A mistake in the first stage will propagate through the entire solution. A neglected fourth
stage means you lose the opportunity to learn and to verify correctness.

Step 1: Understand the Problem

“It is foolish to answer a question that you do not understand.” – George Pólya
This stage is about building a complete, accurate, and precise mental model of the problem. You must be able to
state, in your own words, what is given, what is required, and under what conditions.
Key actions:
 Read or listen carefully. Restate the problem without looking at the original text.
 Identify the inputs, the outputs, and the processing required.
 Identify constraints and assumptions explicitly. Are there limits on time, memory, data type? Is the input
guaranteed to be sorted? Are there missing pieces of information that you must request?
 Draw a diagram, sketch a graph, construct a small instance. Visual representation often reveals hidden
patterns.
 Consider edge cases: what happens if the input is empty, zero, negative, or at the boundary?
 Distinguish between what is essential and what is incidental; this is where abstraction plays a major role.

Solution techniques that primarily serve this stage:

 Abstraction: Strip away irrelevant details to focus on the core problem.
  Research: Gather domain knowledge and clarify terminology. If you don’t know what “palindrome” means,
you cannot solve a palindrome-checking problem.
 Root cause analysis (5 Whys): When the problem is “the system is broken,” you may need to dig to
understand what the real problem is, not just the surface symptom.

Example:
Problem: “Write a program that determines whether a given year is a leap year.”
Understanding:
 Input: an integer representing a year (say, positive, perhaps Gregorian calendar).
 Output: true or false (or “Leap year” / “Not a leap year”).
 Rule: A year is a leap year if it is divisible by 4, except if it is divisible by 100, unless it is also divisible by
400.
 Edge cases: year 0? Year 1900 (not leap), year 2000 (leap). Negative years? We assume they are not in scope
unless stated.
 Abstraction: we do not care about the calendar system’s history, just the numeric rule.
Only after such clarification do we proceed.

Step 2: Devise a Plan

This is the bridge between the problem statement and its solution. Here you select the strategy, the method, the high-
level approach. You are not yet working out minute details; you are designing the blueprint.
Key actions:
 Ask: “Have I seen a problem like this before?” Use analogy to transfer a known solution.
 Can the problem be reduced to a known problem class (sorting, searching, graph problem, and so on)?
 Can the problem be divided into independent subproblems (divide and conquer)?
 Is it a routine problem with a known algorithm, or do you need to generate creative ideas via brainstorming
or lateral thinking?
 Draw a high-level flowchart or a rough pseudocode skeleton.
 Use means-end analysis to identify the main differences between current and goal state and the operators
that reduce them.
 If the problem is diagnostic (“Why does this crash?”), plan a hypothesis testing approach.

Solution techniques primarily serving this stage:

 Analogy, Reduction, Divide and Conquer: Connecting your problem to a solved one or decomposing it.
 Means-End Analysis: For transformation problems.
 Brainstorming, Lateral Thinking, Method of Focal Objects, Morphological Analysis: For generating
novel solution ideas when no standard algorithm exists.
 Proof (conceptually): Sometimes you can design an algorithm by constructing a proof of existence or
optimality.
 Research: Looking up existing algorithms, libraries, and best practices.

Example (Leap year problem continued):

Plan: The leap year condition can be expressed as a logical condition. Use a sequence of if statements or a single
Boolean expression. The plan is trivial because the problem is routine; the plan is simply to implement the rule
exactly. We can sketch:

text
if (year / 400 = 0) → leap
else if (year / 100 = 0) → not leap
else if (year / 4 = 0) → leap
else → not leap

This is an algorithmic solution.

Step 3: Carry Out the Plan

Here you execute the strategy, moving from the high-level plan to a concrete, step-by-step procedure. In computing,
this is where you write the algorithm in precise terms, be it pseudocode, a flowchart, or eventually code in a
programming language.

Key actions:
 Refine the plan step-by-step (stepwise refinement), adding more detail at each level.
 Translate the plan into a formal representation: pseudocode, flowchart, decision table, or decision tree
(topics of upcoming weeks).
 If coding, write clean, documented code that directly reflects the plan.
 Perform trial and error for fine-tuning parameters or small design choices (e.g., tuning a heuristic
threshold).
 Use divide and conquer recursively within the implementation.
 Test small pieces as you go, using hypothesis testing to verify that a sub-module works.

Solution techniques primarily serving this stage:

 Stepwise refinement / Top-down design: To transform the plan into detailed steps.
 Trial and Error: For empirical parameter selection.
 Divide and Conquer: Structuring the implementation itself.

Example (Leap year continued):

Carry out the plan by writing the algorithm in natural language, then pseudocode, then actual code (in later weeks).
At the natural language stage:

text
Step 1: Accept an integer year as input.
Step 2: If year is divisible by 400, then output "Leap year" and stop.
Step 3: If year is divisible by 100, then output "Not a leap year" and stop.
Step 4: If year is divisible by 4, then output "Leap year" and stop.
Step 5: Otherwise, output "Not a leap year".

Step 4: Look Back (Evaluate and Reflect)

This step is sadly the most neglected, yet it is the one that transforms a one-time solution into lasting learning and
guarantees quality.

Key actions:
 Test the solution with a variety of inputs: typical, edge, boundary, invalid, and random. Does it always
produce the expected output?
 Verify correctness more formally: can you construct an invariant or a proof that the algorithm is correct?
 Analyse efficiency: What is the time and space complexity? Is there a more efficient approach?
 Reflect on the process: What did you learn? Which techniques worked well? Where did you get stuck and
why?
 Consider generalisation: Can the solution be extended to a broader class of problems? Can it be made
reusable?
 Document the solution so that others (and your future self) can understand it.
Solution techniques primarily serving this stage:
 Proof: Formal verification of correctness.
 Hypothesis Testing / Root Cause Analysis: If the solution fails, diagnose why and correct it.
 Abstraction (for generalisation): To see the deeper pattern that can be reused.
 Research: To compare your solution with known optimal ones.

Example (Leap year continued):

 Testing: year 2000 → leap (correct). year 1900 → not leap (correct). year 2024 → leap (correct). year 2023
→ not leap (correct). year 0? If we allow year 0, our modulo logic still works, but is year 0 historically a leap
year? This is an assumption to document.
 Efficiency: O(1) – constant time, cannot improve.
 Reflection: The plan was directly the algorithm; the simple logic could be combined into one Boolean
expression: (year % 400 == 0) or (year % 4 == 0 and year % 100 != 0). Which is clearer? This is a design
choice.
 Generalisation: The same structure can be applied to any set of rules that follow an exception hierarchy.

5.3. Mapping Solution Techniques to Pólya’s Stages

To solidify the connection between your toolkit and the process, here is a comprehensive mapping of all fourteen
techniques to the stages in which they are most active. (A technique may appear in multiple stages.)

Table 5.1: Mapping Solution Techniques

Stage Primary Techniques
Understand the
Abstraction, Research, Root Cause Analysis, Problem Restatement, Diagramming
Problem
Analogy, Reduction, Divide and Conquer, Means-End Analysis, Brainstorming, Lateral
Devise a Plan
Thinking, Method of Focal Objects, Morphological Analysis, Proof (strategy), Research
Carry Out the Stepwise Refinement, Top-Down Design, Trial and Error, Hypothesis Testing, Divide and
Plan Conquer (implementation), Formal Notation
Proof (verification), Hypothesis Testing (debugging), Root Cause Analysis (for failures),
Look Back
Efficiency Analysis, Generalisation

This table is not rigid; it is a guide. A skilled problem solver moves fluidly among stages and techniques, sometimes
revisiting earlier stages when new insights emerge.

5.4. Introduction to Algorithm Design: Stepwise Refinement and Top-Down Design

Now we turn to the systematic creation of algorithms. An algorithm does not usually spring into the mind fully
formed. It must be designed. Two complementary strategies dominate the design process: stepwise refinement (also
known as incremental refinement) and top-down design.

5.4.1 Stepwise Refinement

Stepwise refinement is the process of starting with a high-level, coarse description of the solution and then repeatedly
breaking down each step into more detailed sub-steps until the level of detail is sufficient for direct implementation
(in code or formal pseudocode). It is the algorithmic analogue of zooming in on a fractal – each level reveals more
structure.
The approach:
1. Write the overall task as a single, abstract statement (the “top-level”).
2. Replace that statement with a sequence of slightly more concrete steps.
3. For each step that is still too abstract, repeat: decompose it into smaller steps.
4. Stop when every step is primitive enough to be directly translated into instructions.

Example: Searching a list for a target value (linear search)

Level 0 (most abstract):
 Search the list for the target.

Level 1:
 Go through each element of the list from the beginning.
 If you find an element equal to the target, indicate success and stop.
 If you reach the end without finding the target, indicate failure.

Level 2 (more refined, natural language):

text
1. Set a counter i to 0.
2. While i is less than the length of the list:
a. If list[i] equals target, return i (the position).
b. Increment i.
3. Return -1 (indicating not found).

Level 3 (in pseudocode – preview for Week 6):

text
Algorithm LinearSearch(A, target):
for i ← 0 to length(A)-1:
if A[i] = target then
return i
return -1

At each refinement stage, the description becomes more specific and closer to executable code. Notice how we did
not try to write the final pseudocode in one leap; we built it up.
Stepwise refinement naturally incorporates divide and conquer: each decomposition is a division of a complex task
into simpler ones.

5.4.2 Top-Down Design

Top-down design is a system-design methodology that works from the general to the specific. It is stepwise
refinement applied at the architecture level of a larger software system. You start with the main function or module
and progressively break it down into smaller functions or modules, each with a clear responsibility.

Principles:
 Main program first: Write a high-level main function that calls abstract helper functions.
 Decompose functions: Each function should do one thing well (single responsibility). If it does multiple
things, split it.
 Stubs: Initially, the helper functions can be stubs (dummy implementations that return fixed values) so you
can test the high-level flow.
 Iterate: Refine each stub into a working function, which may itself call further sub-functions.
Example: Top-down design of a simple calculator program
Main program (top level):
text
1. Display menu to user.
2. Get user's choice of operation (add, subtract, multiply, divide).
3. Get two numbers from user.
4. Perform the chosen operation on the two numbers.
5. Display the result.

Refinement – step 2 “Get user’s choice”: This can be a function get_operation_choice() that validates input.
Refinement – step 3 “Get two numbers”: A function get_two_numbers() that returns a tuple.
Refinement – step 4 “Perform operation”: A function compute(op, a, b) with a selection structure (if-else or
switch).
Refinement – step 5 “Display result”: display_result(value).

Each of these functions can be written, tested, and refined independently. This modular approach not only makes the
problem easier to solve but also promotes reusability and maintainability.

Connection to stepwise refinement: Top-down design is stepwise refinement applied across the structure of a
program, whereas stepwise refinement can also be applied within a single algorithm. Both encourage deferring
details until you have a clear high-level picture.

5.5. Detailed Properties of a Good Algorithm – Revisited with Computing Examples

In Week 2, we introduced the five essential properties of an algorithm: finiteness, definiteness, input, output,
effectiveness. Now we revisit them in the context of algorithm development, with more pointed computing
examples, and we add practical considerations that make an algorithm not just a valid algorithm, but a good one.

5.5.1 The Five Formal Properties (Recap)

1. Finiteness: The algorithm must always terminate after a finite number of steps for all valid inputs.
2. Definiteness: Each step must be precisely defined; no ambiguity.
3. Input: Zero or more externally supplied quantities.
4. Output: One or more results that have a specified relation to the inputs.
5. Effectiveness: Operations must be basic enough to be performed exactly and in finite time by a human or
machine.

5.5.2 Applying the Properties: Example Analysis

Consider an algorithm to compute the factorial of a non-negative integer *n*:

Naïve natural language description A:

“Multiply the numbers from 1 to n together and give the result.”
Analysis:
 Finiteness: For any given *n*, multiplying numbers from 1 to *n* terminates (finite loop). OK.
 Definiteness: “Multiply the numbers from 1 to n together” – what if *n* = 0? The description is ambiguous.
Factorial of 0 is 1 by convention. This step is not fully definite without special-case handling.
 Input: *n*, a non-negative integer. OK.
 Output: The product. OK.
 Effectiveness: Yes, multiplication is basic. But if *n* is very large, the product may exceed the computer’s
integer capacity. In a practical implementation we need to specify how overflow is handled.
Refined natural language description B (good algorithm):
text
1. Input n (non-negative integer).
2. If n equals 0, output 1 and stop.
3. Set result to 1.
4. Set i to 1.
5. While i ≤ n:
a. Multiply result by i.
b. Increment i.
6. Output result.
Now definiteness is satisfied (base case for 0 explicit). Finiteness is clear. Input, output, effectiveness all OK.
Additionally, the algorithm is efficient for its purpose (O(n) time), though we could also discuss a recursive version.

5.5.3 Beyond the Five Properties: What Makes an Algorithm “Good”?

In practice, we also care about:
 Efficiency: Time and space complexity (Big O). A correct algorithm that takes 1000 years is useless.
 Simplicity: Easier to understand, implement, debug, and maintain. KISS principle.
 Scalability: How well it handles increasing input sizes.
 Robustness: Handles invalid input gracefully (though error handling is often external to the pure algorithm).
 Modularity: Well-structured into sub-algorithms or functions.

These are not formal mathematical properties but engineering virtues. They become increasingly important as we
move from theoretical algorithm design to real-world software development.

5.6. Expressing Algorithms in Natural Language

Before we learn pseudocode and flowcharts (next week), natural language is the first and most intuitive medium for
expressing algorithms. It is a powerful thinking tool, but it has pitfalls.

5.6.1 Guidelines for Natural Language Algorithm Description

1. Use imperative verbs: “Set,” “Compute,” “If…then,” “While,” “Repeat,” “Output.”
2. Number steps if sequence matters.
3. Be explicit about loops and decisions: Use phrases like “repeat the following for each element” or “if
<condition> then do X else do Y.”
4. Define variables clearly: “Let sum be 0” or “Initialize count to 0.”
5. Handle all cases: Include base cases, edge cases, and error conditions.
6. Avoid pronouns with ambiguous reference: Instead of “it” use “the value of x.”
7. Keep each step simple: If a step requires more than one action or a complex condition, break it down.

Example: Find the Maximum Element in an Array

Poor natural language description:
“Look through the array and pick the biggest one.”

Good natural language description:

text
Let A be an array of numbers of length n.
If n is 0, output an error message and stop.
Set max_value to A[0].
Set index i to 1.
While i is less than n:
If A[i] is greater than max_value:
Set max_value to A[i].
Increment i.
Output max_value.
This second version is precise enough that a human with no programming knowledge could execute it. It is also
directly translatable into pseudocode or code.

5.6.3 Why Natural Language is a Precursor

Natural language algorithms are valuable for:
 Thinking without syntax distraction: You focus on the logic, not on semicolons.
 Communication: Sharing ideas with non-programmers or among team members before implementation.
 Documentation: A natural language description of an algorithm can serve as a comment header in code.
 Stepwise refinement base: You start in natural language and then transform into pseudocode/flowchart.

However, natural language is inherently ambiguous. Words like “or” can be inclusive or exclusive; “if…then” may
miss an “else.” That is why we eventually graduate to formal notations (pseudocode, flowcharts) that remove
ambiguity. But the skill of clear natural language description is a fundamental step.

5.7. Walkthrough: Applying the Full Process to a Computing Problem

Let us integrate everything by solving a complete problem from scratch, using Pólya’s steps, appropriate solution
techniques, and stepwise refinement to produce a natural-language algorithm.

Problem Statement
Given three distinct integers, write a program that determines and outputs the largest of the three.
Step 1: Understand the Problem
 Input: Three integers, say a, b, c, all distinct.
 Output: The value of the largest integer.
 Constraints: The numbers are distinct, so no tie-breaking logic is needed for this version. We assume
standard integer range.
 Abstraction: We just need a comparison logic; no need to store all numbers in a data structure.

Step 2: Devise a Plan

 This is a routine problem. Several plans are possible:
o Plan A (Sequential comparison): Compare a and b, keep the larger; compare that with c. Output the
final larger.
o Plan B (Nested if-else): Use a decision tree.
o Plan C (Sort-based): Put numbers in a list, sort, pick last element.
 We choose Plan A for its simplicity and efficiency (O(1)). Use reduction (the problem reduces to two max
operations) and divide and conquer (compare first two, then compare with third). No creative techniques
needed.

Step 3: Carry Out the Plan – Stepwise Refinement

Level 0 (Natural language, coarse):
 Find the maximum of a and b, then find the maximum of that and c, and output it.
Level 1 (Refined natural language):
text
1. Read three numbers a, b, c.
2. If a > b, set max_ab to a; otherwise set max_ab to b.
3. If max_ab > c, set largest to max_ab; otherwise set largest to c.
4. Output largest.

*Level 2 (More detailed, handling possible non-distinct? We keep distinct per problem statement):*
text
1. Input a, b, c (integer).
2. Let max_val = a.
3. If b > max_val then max_val = b.
4. If c > max_val then max_val = c.
5. Print max_val.
This is a simpler, more general algorithm that works even if numbers are not distinct. It uses a running maximum.

Level 3 (Pseudocode – for later):

text
max_val ← a
if b > max_val then
max_val ← b
if c > max_val then
max_val ← c
output max_val

Step 4: Look Back

 Test: (15, 22, 9) → 22; (5, 5, 5) → 5 (if we drop distinct assumption); (-1, -5, -3) → -1. Works.
 Efficiency: 2 comparisons, O(1). Optimal.
 Generalisation: The running-maximum approach extends easily to *n* numbers in a loop. This teaches a
pattern.
 Proof: By induction, after each comparison, max_val holds the maximum of all numbers seen so far. After
processing all, it holds the overall maximum. Correct.

5.8. Summary
This week we have built the bridge from general problem-solving techniques to the structured design of algorithms.
The key takeaways:
 Pólya’s four-step process – Understand, Devise a Plan, Carry Out the Plan, Look Back – provides a
universal framework that guides you from problem statement to verified solution.
 The fourteen solution techniques we have learned fit naturally into these stages, and knowing where they
belong helps you select the right tool at the right time.
 Algorithm design is not a single leap but a process of stepwise refinement and top-down design, starting
from high-level abstractions and progressively adding detail until the algorithm is completely specified.
 A good algorithm satisfies the five essential properties (finiteness, definiteness, input, output, effectiveness)
and, ideally, is also efficient, simple, and robust.
 Natural language is the first formal medium for expressing algorithms; writing clear, imperative,
unambiguous natural language descriptions is a critical skill that prepares you for pseudocode and flowcharts
in the coming weeks.
Week 6
Solution Formulation and Design – Flowchart, Pseudocode, Decision Tools

6.1. Introduction
In Week 5, we completed the full problem-solving cycle using Pólya’s four steps and learned how to design
algorithms through stepwise refinement and top-down design. We also practised expressing algorithms in natural
language. However, natural language, while a good starting point, suffers from ambiguity and verbosity. As problems
grow in complexity, we need formal, standardised tools to represent our designs with precision and clarity.

This week we will study four such tools:

 Flowcharts: A graphical representation using standard symbols to depict the flow of control.
 Pseudocode: A structured, human-readable notation that mimics programming language constructs but
without strict syntax.
 Decision tables: A tabular method for compactly representing complex decision logic.
 Decision trees: A hierarchical, graphical representation of decisions and their possible consequences.

These tools serve as the bridge between a high-level problem-solving plan and its implementation in a programming
language such as C or Python. They allow you to communicate algorithms to other developers, to reason about
correctness before coding, and to document your work.

6.2. Flowcharts
6.2.1 What Is a Flowchart?
A flowchart is a diagrammatic representation of an algorithm or a process. It uses standardised geometric shapes
connected by arrows (flow lines) to show the sequence of steps and the flow of control. Flowcharts were first
standardised by the American National Standards Institute (ANSI) and later by the International Organization for
Standardization (ISO).
A well-drawn flowchart makes the logic of an algorithm immediately visible. It is particularly useful for:
 Visual learners who benefit from seeing the structure.
 Explaining processes to non-technical stakeholders.
 Debugging by tracing the flow of execution.
 Documenting legacy code.

6.2.2 Standard Flowchart Symbols

Table 6.1: Standard Flowchart Symbols
Symbol Name Purpose
Terminator Represents the start or end of a process/algorithm. Contains “Start” or “Stop”.

Process Represents a computation or an action (e.g., “Set x = x + 1”).

Input/Output Represents reading data from the user or writing data to the screen.

Represents a condition or a branch point. It has one entrance and two or more exit paths,
Decision
typically labelled “Yes/No” or “True/False”.
Used to connect flow lines from different parts of the chart, especially across page
Connector
boundaries.

Flow Line Indicates the direction of control flow.

These are the essential symbols. In this course, we will primarily use the first four.

6.2.3 Flowcharts for Sequential Logic

Sequential logic is the simplest: steps are executed one after another in a fixed order.
Example: Compute the area of a rectangle.
Natural language algorithm:
1. Input length and width.
2. Calculate area = length × width.
3. Output area.

Flowchart:

Start

Read length, width

area = length*width

Print area

Stop

Key points:
 All boxes are rectangles except the start/stop ovals and the input/output parallelograms.
 Flow is straight down. No decisions, no loops.

6.2.4 Flowcharts for Selection (Decision) Logic

Selection logic involves making a decision and branching based on a condition. The diamond symbol is used.
Example: Check if a number is even or odd.
Pseudocode:
1. Input a number n.
2. If n mod 2 equals 0, then print “Even”; else print “Odd”.
Flowchart:
 Start

Read n

N
N mod 2
Print “Odd”
= 0?

Print “Even”

Stop

Key points:
 The decision diamond has one entry and two exits (Yes/No).
 Both paths eventually merge before stopping (common exit point).

Multiple conditions: Nested if-then-else.

Example: Determine letter grade from a numerical score.
 If score ≥ 70 → “A”
 else if score ≥ 60 → “B”
 else if score ≥ 50 → “C”
 else if score ≥ 45 → “D”
 else → “F”
This can be drawn with a cascade of diamonds, each branching to the next condition on “No” and to a grade output
on “Yes”.
2.5 Flowcharts for Iterative (Loop) Logic
Iteration involves repeating a set of steps while a condition is true (or until a condition is met). The flow loops back
to a decision diamond.
Example: Sum of numbers from 1 to N.
Algorithm:
1. Input N.
2. Set sum = 0, i = 1.
3. While i ≤ N:
a. sum = sum + i
b. i = i + 1
4. Print sum.
Flowchart:

Start

Read n

Sum = 0, i=1

Y
i <= N?
Sum = sum + 1

N i=i+1
Print “sum”

Stop

Note: The flow from the process box after “Yes” goes back up to the decision diamond, forming a loop.

Common loop patterns:

 Counter-controlled (for loop): “For i = 1 to N do…” – same structure, incrementing counter.
 Sentinel-controlled (while): Repeat until a special value (e.g., -1) is entered.
 Repeat-until: Check condition at the end of the loop body (do-while).

6.2.6 Guidelines for Drawing Effective Flowcharts

1. Top-to-bottom, left-to-right: Maintain consistency; flow lines should generally go down and right.
2. One entry, one exit for each symbol except decision (one entry, two exits) and connector.
3. Avoid crossing flow lines where possible; use connectors if needed.
4. Labelling: Label decision branches (Yes/No, True/False). Write processes clearly.
5. Keep it readable: Don’t cram too much in one chart; use sub-process symbols or break into modules.
6. Clarity over cleverness: Flowcharts are documentation. If the logic is too complex, consider a decision table
instead.

6.3. Pseudocode
6.3.1 What Is Pseudocode?
Pseudocode (from pseudo meaning “false” or “imitation”) is a human-readable, structured way to describe
algorithms using a mixture of natural language and programming-like constructs. It is not a language with a strict
syntax; it is a convention that you can adapt, provided you remain clear and consistent.
Pseudocode’s advantages:
 No need to worry about compiler errors; you focus purely on logic.
 Easily translated into any programming language (C, Python, Java, etc.).
 Less visually cumbersome than flowcharts for long algorithms.
  Widely used in textbooks and research papers to present algorithms.

6.3.2 Common Pseudocode Conventions

While there is no single standard, the following conventions are widely accepted:
Keywords (often capitalised or bold in textbooks, but just consistent casing is fine):
 START / STOP (or BEGIN / END)
 INPUT, READ, OUTPUT, PRINT, DISPLAY
 IF … THEN … ELSE … ENDIF
 WHILE … DO … ENDWHILE
 FOR … TO … DO … ENDFOR
 REPEAT … UNTIL
 CASE … OF … ENDCASE
 Procedure/function definitions: FUNCTION name(parameters)

Variables and assignment:

 Use the left arrow ← or = for assignment. E.g., sum ← 0 or sum = 0. Be consistent.
 Choose descriptive variable names.
Arithmetic and logic:
 Standard operators: +, -, *, /, MOD, ^ (power).
 Relational: =, ≠ or !=, <, >, ≤, ≥.
 Logical: AND, OR, NOT.
Indentation:
 Use consistent indentation to show block structure, just like in Python or C.
Comments:
 Use // or /* */ for comments explaining the logic.

Example conventions (from various textbooks):

Algorithm LargestOfThree(a, b, c)
Input: Three integers a, b, c
Output: The largest integer
max ← a
if b > max then
max ← b
endif
if c > max then
max ← c
endif
return max

Notice the minimal but clear structure: algorithm name, input/output specification, indented if blocks.

6.3.3 Translating Natural Language Algorithms into Pseudocode

Let’s practise transforming a natural language algorithm into pseudocode.
Problem: Compute the factorial of n (n ≥ 0).
Natural language:
1. Input n.
2. If n equals 0, output 1 and stop.
3. Set result to 1.
4. Set i to 1.
5. While i ≤ n, do:
a. Multiply result by i.
b. Increment i.
6. Output result.

Pseudocode:
text
Algorithm Factorial(n)
Input: non-negative integer n
Output: n!
if n = 0 then
return 1
endif
result ← 1
i←1
while i ≤ n do
result ← result * i
i←i+1
endwhile
return result
Alternative using FOR:
text
result ← 1
for i ← 1 to n do
result ← result * i
endfor
return result
(Note: If n=0, the for loop doesn't execute and result stays 1, which is correct. So we could even omit the explicit
if.)

Key point: The translation process is mechanical once you have a refined natural language algorithm. Each
imperative statement maps to a pseudocode construct.

6.3.4 Selection and Iteration Constructs in Pseudocode

IF-THEN-ELSE:

if condition then
// statements
elseif condition then
// statements
else
// statements
endif
(Some conventions use ELSE IF without an extra keyword.)
CASE (multi-way branch):
case expression of
value1: statements
value2: statements
...
otherwise: statements
endcase

WHILE loop (pre-test):

while condition do
// body
endwhile

REPEAT-UNTIL (post-test):
repeat
// body
until condition

FOR loop (counter-controlled):

for variable ← start to finish do
// body
endfor
or with step: for i ← 1 to n step 2 do ...

6.3.5 Pseudocode Examples for Common Problems

Example 1: Check if a number is prime.

Algorithm IsPrime(n)
Input: integer n > 1
Output: true if prime, false otherwise
if n ≤ 1 then
return false
endif
for i ← 2 to sqrt(n) do
if n mod i = 0 then
return false
endif
endfor
return true

Example 2: Linear search in an array.

Algorithm LinearSearch(A, target)
Input: array A of size n, target value
Output: index of target or -1 if not found
for i ← 0 to n-1 do
if A[i] = target then
return i
endif
 endfor
return -1

Example 3: Simple calculator menu (using case).

Algorithm SimpleCalculator
print "Menu: +, -, *, /"
read op
read a, b
case op of
'+': result ← a + b
'-': result ← a - b
'*': result ← a * b
'/': if b ≠ 0 then
result ← a / b
else
print "Division by zero error"
return
endif
endcase
print result

6.4. Decision Tables

6.4.1 What Is a Decision Table?
A decision table is a tabular representation of complex decision logic, especially when multiple conditions interact
to determine one or more actions. Unlike flowcharts and pseudocode, which show the flow of control, decision
tables focus on combinations of conditions and the corresponding actions in a compact, easy-to-verify format.
Decision tables are extensively used in business rules, software testing, and systems analysis. They help ensure that
all possible combinations of conditions are considered, reducing the risk of missing edge cases.

6.4.2 Structure of a Decision Table

A decision table consists of four quadrants:
Condition Stub Condition Entries
Action Stub Action Entries

 Condition Stub: Lists the conditions (questions) that affect the decision.
 Condition Entries: Each column represents a rule (combination of condition outcomes). Values are typically
Y/N (Yes/No), T/F (True/False), or discrete values.
 Action Stub: Lists the possible actions to be taken.
 Action Entries: For each rule (column), marks (X or ✓) indicate which actions should be executed.

6.4.3 Example: Student Grade Assignment

Problem: A student’s final letter grade depends on their exam score and whether they completed all assignments.
Policy:
 Score ≥ 70 and assignments complete → A
 Score ≥ 70 but assignments incomplete → B
 Score ≥ 50 and assignments complete → B
 Score ≥ 50 but assignments incomplete → C
 Score < 50 → F regardless of assignments.
We can represent this with a decision table.

Step 1: Identify conditions and actions.

Conditions:
1. Score ≥ 70?
2. Score ≥ 50?
3. Assignments complete?
Actions:
1. Assign grade A
2. Assign grade B
3. Assign grade C
4. Assign grade F

Step 2: Create the table. We need columns for each distinct rule. Note that conditions may be limited. Since we
have a score range, we can define conditions as: Score >= 70, 50 <= Score < 70, Score < 50, and then combine with
Assignments complete? Y/N.
But in pure condition list format:
Conditions:
 C1: Score ≥ 70?
 C2: Score ≥ 50? (for cases where C1 is No)
 C3: Assignments complete?
However, careful with condition entries: if C1 is Y, then C2 is irrelevant (but can be set to N/A or Y/N? We'll use
limited entry table, where conditions are evaluated sequentially, but typical decision tables allow "—" for don't care).
Let's do limited entry with Y/N/-.

Decision Table:
Rule 1 2 3 4 5
Conditions
C1: Score ≥ 70? Y Y NNN
C2: Score ≥ 50? ——YYN
C3: Assignments complete? Y N Y N —
Actions
A1: Grade A X
A2: Grade B X X
A3: Grade C X
A4: Grade F X

Here, "—" means "don't care" (condition does not matter). This gives five distinct rules, covering all possibilities.
We could combine rules 2 and 3? Actually, they produce the same action (grade B) but their conditions are different,
so they represent different rule combinations; but we might combine them in an extended entry table where condition
entries can be ranges, but that's advanced.

Interpretation:
 Rule 1: Score ≥ 70 (Y), assignments complete (Y) → A.
 Rule 2: Score ≥ 70 (Y), assignments incomplete (N) → B.
 Rule 3: Score < 70 (N) but ≥ 50 (Y), assignments complete (Y) → B.
 Rule 4: Score < 70 (N) but ≥ 50 (Y), assignments incomplete (N) → C.
  Rule 5: Score < 50 (N) → F.
The decision table clearly shows all cases and ensures completeness.

6.4.4 When to Use Decision Tables

 When there are many conditions that interact (3 or more conditions).
 When the logic is complex and nested if-else would be hard to follow or error-prone.
 In requirements specification to verify that all scenarios are covered.
 In testing: each column can become a test case.

6.4.5 Constructing a Decision Table

1. List all conditions.
2. Determine the number of possible rules: 2^(number of conditions) if all are binary, but often some
combinations are invalid or can be merged.
3. List actions.
4. For each rule column, fill condition entries with Y/N and determine the appropriate action(s).
5. Check for contradictions (same conditions, different actions) and redundancy (two columns can be merged
if only don't-care differs).
6. Verify with domain experts.

6.5. Decision Trees

6.5.1 What Is a Decision Tree?
A decision tree is a graphical, hierarchical representation of decisions and their possible consequences. It resembles
a flowchart but is typically used for decision analysis rather than algorithm flow. Each internal node represents a test
on a condition (or attribute), each branch represents the outcome of the test, and each leaf node represents a decision
outcome or action.
Decision trees are widely used in:
 Machine learning (classification trees).
 Business decision analysis (cost, risk, utility).
 Troubleshooting guides (diagnostic trees).
In algorithm design, decision trees can map out the logic of a selection-based algorithm, similar to a flowchart but
with a focus on the branching structure rather than the sequence of operations.

5.2 Decision Tree for Grade Assignment (same problem)

We can draw a decision tree for the grade policy:
 Score ≥ 70?

Y N

Assgn Score≥50?|
done?|

Y N Y N

Grade A Grade B Assgn?| Grade

F≥50?|
Y N

Assgn Score≥50?|
done?|

[Link]:
 Starting from the root, ask "Score ≥ 70?". If yes, go to "Assignments complete?". If yes → A, else → B.
 If no (Score < 70), ask "Score ≥ 50?". If no → F. If yes, ask "Assignments complete?". If yes → B, else →
C.
This is exactly the nested if-else logic. The decision tree makes the hierarchy explicit.

6.5.3 Decision Trees vs. Flowcharts

Feature Flowchart Decision Tree
Primary use Algorithm/program logic flow Decision analysis, diagnosis, classification
Nodes Various shapes for actions, decisions, Mostly decision nodes (condition) and outcome nodes
I/O
Ordering Shows all steps in sequence and loops Focuses purely on decisions and outcomes; typically no
loops
Complexity Can represent any control flow Best suited for multi-stage decision problems

In practice, for expressing an algorithm's selection logic, a flowchart is more general. A decision tree is a specialised
tool that you may choose when the algorithm is purely a series of decisions leading to actions.

6.5.4 Example: Troubleshooting a Computer That Would not Turn On

Decision tree (simplified):
1. Is the power cable plugged in?
o No → Plug it in and try again.
o Yes → 2. Does the power light come on?
 No → 3. Is the power supply switch on?
 No → Turn it on.
 Yes → Power supply may be faulty.
 Yes → 4. Does the screen display anything?
 No → Check monitor connection.
  Yes → 5. Does the operating system load?
... and so on.
This is a diagnostic decision tree, effectively guiding a technician step by step.

6.5.5 Converting a Decision Tree to Pseudocode or Flowchart

Given a decision tree, you can directly translate it into nested if-else pseudocode or into a flowchart with cascading
diamonds. The decision tree is essentially a “decision-only” flowchart without process boxes for actions other than
the final outcomes.

6.6. Choosing the Right Design Tool

Tool Best For
Flowchart Visualising the overall flow of control, especially loops and complex branching. Good for
communication and documentation.
Pseudocode Algorithms that are linear and procedural, translating directly to code. More compact than
flowchart for long algorithms.
Decision Complex business rules with multiple interacting conditions. Ensures completeness and absence
Table of contradictions.
Decision Tree Hierarchical, branching decision processes; diagnostic and classification logic.
Often you will use a combination: a flowchart for the high-level process, pseudocode for the detailed logic, and
decision tables for particularly intricate rule sets.

6.7. Summary
This week we added four essential design tools to our problem-solving arsenal7
 Flowcharts provide a visual, standardised representation of algorithms using shapes for start/end, processes,
inputs/outputs, and decisions. They handle sequential, selection, and iterative logic through arrows and loops.
 Pseudocode bridges natural language and programming languages. With conventions like if...then...else,
while, and for, it precisely describes algorithms without syntactic overhead.
 Decision tables offer a compact, matrix-based approach for capturing complex rule sets, ensuring
completeness and logical consistency.
 Decision trees hierarchically structure decision processes, making them easy to follow and translate into
nested if-else code.
Week 7
Visual Basic Programming .Net ([Link])

7.1 Overview
Visual Basic Programming .Net ([Link]) is a simple, modern, object-oriented computer programming language
developed by Microsoft to combine the power of .NET Framework and the common language runtime with the
productivity benefits that are the hallmark of Visual Basic. This tutorial will teach you basic [Link] programming
and will also take you through various advanced concepts related to [Link] programming language.

Visual Basic .NET ([Link]) is an object-oriented computer programming language implemented on the .NET
Framework. Although it is an evolution of classic Visual Basic language, it is not backwards-compatible with VB6,
and any code written in the old version does not compile under [Link]. Like all other .NET languages, [Link]
has complete support for object-oriented concepts. Everything in [Link] is an object, including all of the primitive
types (Short, Integer, Long, String, Boolean, etc.) and user-defined types, events, and even assemblies. All objects
inherits from the base class Object.

[Link] is implemented by Microsoft's .NET framework. Therefore, it has full access to all the libraries in the .Net
Framework. It's also possible to run [Link] programs on Mono, the open-source alternative to .NET, not only
under Windows, but even Linux or Mac OSX.

The following reasons make [Link] a widely used professional language −

 Modern, general purpose.
 Object oriented.
 Component oriented.
 Easy to learn.
 Structured language.
 It produces efficient programs.
 It can be compiled on a variety of computer platforms.
 Part of .Net Framework.

Strong Programming Features of [Link]

[Link] has numerous strong programming features that make it endearing to multitude of programmers worldwide.
Let us mention some of these features −
 Boolean Conditions
 Automatic Garbage Collection
 Standard Library
 Assembly Versioning
 Properties and Events
 Delegates and Events Management
 Easy-to-use Generics
 Indexers
 Conditional Compilation
 Simple Multithreading

[Link] Environment
In this chapter, we will discuss the tools available for creating [Link] applications.
We have already mentioned that [Link] is part of .Net framework and used for writing .Net applications. Therefore,
before discussing the available tools for running a [Link] program, let us understand how [Link] relates to the
.Net framework.

.Net framework
The .Net framework is a revolutionary platform that helps you to write the following types of applications −
 Windows applications
 Web applications
 Web services
The .Net framework applications are multi-platform applications. The framework has been designed in such a way
that it can be used from any of the following languages: Visual Basic, C#, C++, Jscript, and COBOL, etc.

All these languages can access the framework as well as communicate with each other.
The .Net framework consists of an enormous library of codes used by the client languages like [Link]. These
languages use object-oriented methodology.

Following are some of the components of the .Net framework −

 Common Language Runtime (CLR)
 The .Net Framework Class Library
 Common Language Specification
 Common Type System
 Metadata and Assemblies
 Windows Forms
 [Link] and [Link] AJAX
 [Link]
 Windows Workflow Foundation (WF)
 Windows Presentation Foundation
 Windows Communication Foundation (WCF)
 LINQ

Integrated Development Environment (IDE) For [Link]

Microsoft provides the following development tools for [Link] programming −
 Visual Studio 2010 (VS)
 Visual Basic 2010 Express (VBE)
 Visual Web Developer

The last two are free. Using these tools, you can write all kinds of [Link] programs from simple command-line
applications to more complex applications. Visual Basic Express and Visual Web Developer Express edition are
trimmed down versions of Visual Studio and has the same look and feel. They retain most features of Visual Studio

7.2 [Link] Structures

Before we study basic building blocks of the [Link] programming language, let us look a bare minimum [Link]
program structure so that we can take it as a reference in upcoming chapters.

[Link] Hello World Example

A [Link] program basically consists of the following parts −
 Namespace declaration
 A class or module
 One or more procedures
 Variables
 The Main procedure
 Statements & Expressions
 Comments

Let us look at a simple code that would print the words "Hello World" −

Imports System
Module Module1
'This program will display Hello World
Sub Main()
[Link]("Hello World")
[Link]()
End Sub
End Module

When the above code is compiled and executed, it produces the following result −
Hello, World!

Let us look various parts of the above program −

 The first line of the program Imports System is used to include the System namespace in the program.
 The next line has a Module declaration, the module Module1. [Link] is completely object oriented, so every
program must contain a module of a class that contains the data and procedures that your program uses.
 Classes or Modules generally would contain more than one procedure. Procedures contain the executable
code, or in other words, they define the behavior of the class. A procedure could be any of the following −
o Function
o Sub
o Operator
o Get
o Set
o AddHandler
o RemoveHandler
o RaiseEvent
 The next line( 'This program) will be ignored by the compiler and it has been put to add additional comments
in the program.
 The next line defines the Main procedure, which is the entry point for all [Link] programs. The Main
procedure states what the module or class will do when executed.
 The Main procedure specifies its behavior with the statement
[Link]("Hello World") WriteLine is a method of the Console class defined in the System
namespace. This statement causes the message "Hello, World!" to be displayed on the screen.
 The last line [Link]() is for the [Link] Users. This will prevent the screen from running and
closing quickly when the program is launched from Visual Studio .NET.

7.3 Compile & Execute [Link] Program

If you are using Visual [Link] IDE, take the following steps −
 Start Visual Studio.
 On the menu bar, choose File → New → Project.
 Choose Visual Basic from templates
 Choose Console Application.
 Specify a name and location for your project using the Browse button, and then choose the OK button.
 The new project appears in Solution Explorer.
 Write code in the Code Editor.
 Click the Run button or the F5 key to run the project. A Command Prompt window appears that contains the
line Hello World.

You can compile a [Link] program by using the command line instead of the Visual Studio IDE
 Open a text editor and add the above mentioned code.
 Save the file as [Link]
 Open the command prompt tool and go to the directory where you saved the file.
 Type vbc [Link] and press enter to compile your code.
 If there are no errors in your code the command prompt will take you to the next line and would generate
[Link] executable file.
 Next, type helloworld to execute your program.
 You will be able to see "Hello World" printed on the screen.

7.4 Basic syntax

[Link] is an object-oriented programming language. In Object-Oriented Programming methodology, a program
consists of various objects that interact with each other by means of actions. The actions that an object may take are
called methods. Objects of the same kind are said to have the same type or, more often, are said to be in the same
class.
When we consider a [Link] program, it can be defined as a collection of objects that communicate via invoking
each other's methods. Let us now briefly look into what do class, object, methods and instance variables mean.
  Object − Objects have states and behaviors. Example: A dog has states - color, name, breed as well as
behaviors - wagging, barking, eating, etc. An object is an instance of a class.
 Class − A class can be defined as a template/blueprint that describes the behaviors/states that objects of its
type support.
 Methods − A method is basically a behavior. A class can contain many methods. It is in methods where the
logics are written, data is manipulated and all the actions are executed.
 Instance Variables − Each object has its unique set of instance variables. An object's state is created by the
values assigned to these instance variables.

Identifiers
An identifier is a name used to identify a class, variable, function, or any other user-defined item. The basic rules
for naming classes in [Link] are as follows −
 A name must begin with a letter that could be followed by a sequence of letters, digits (0 - 9) or underscore.
The first character in an identifier cannot be a digit.
 It must not contain any embedded space or symbol like ? - +! @ # % ^ & * ( ) [ ] { } . ; : " ' / and \. However,
an underscore ( _ ) can be used.
 It should not be a reserved keyword.

[Link] Keywords

The following table lists the [Link] reserved keywords −

AddHandler AddressOf Alias And AndAlso As Boolean
ByRef Byte ByVal Call Case Catch CBool
CByte CChar CDate CDec CDbl Char CInt
Class CLng CObj Const Continue CSByte CShort
CSng CStr CType CUInt CULng CUShort Date
Decimal Declare Default Delegate Dim DirectCast Do
Double Each Else ElseIf End End If Enum
Erase Error Event Exit False Finally For
Friend Function Get GetType GetXML Namespace Global GoTo
Handles If Implements Imports In Inherits Integer
Interface Is IsNot Let Lib Like Long
Loop Me Mod Module MustInherit MustOverride MyBase
MyClass Namespace Narrowing New Next Not Nothing
Not Inheritable Not Overridable Object Of On Operator Option
Optional Or OrElse Overloads Overridable Overrides ParamArray
Partial Private Property Protected Public RaiseEvent ReadOnly
ReDim REM Remove Handler Resume Return SByte Select
Set Shadows Shared Short Single Static Step
Stop String Structure Sub SyncLock Then Throw
To True Try TryCast TypeOf UInteger While
Widening With WithEvents WriteOnly Xor
Week 8
Variables and Data types

8.1 Declaring and assigning a variable using a primitive type

Variables in Visual Basic are declared using the Dim keyword. For example, this declares a new variable
called
counter with the data type Integer:

Dim counter As Integer

A variable declaration can also include an access modifier, such as Public, Protected, Friend, or
Private. This works in conjunction with the variable's scope to determine its accessibility.

Access Modifier Meaning

Public All types which can access the enclosing type
Protected Only the enclosing class and those that inherit from it
Friend All types in the same assembly that can access the enclosing type
Protected Friend The enclosing class and its inheritors, or the types in the same assembly
that can access the enclosing class
Private Only the enclosing Class type
Static Only on local variables and only initializes once.
As a shorthand, the Dim keyword can be replaced with the access modifier in the variable's declaration:
Public TotalItems As Integer
Private counter As Integer
The supported data types are outlined in the table below:

Type Alias Memory Example

allocation
SByte N/A 1 byte Dim example As SByte = 10
Int16 Short 2 bytes Dim example As Short = 10
Int32 Integer 4 bytes Dim example As Integer = 10
Int64 Long 8 bytes Dim example As Long = 10
Single N/A 4 bytes Dim example As Single = 10.95
Double N/A 8 bytes Dim example As Double = 10.95
Decimal N/A 16 bytes Dim example As Decimal = 10.95
Boolean N/A Dictated by implementing Dim example As Boolean = True
platform
Char N/A 2 Bytes Dim example As Char = "A"C
String N/A source Dim example As String = "Stack
Overflow"
DateTime Date 8 Bytes Dim example As Date = [Link]
Byte N/A 1 byte Dim example As Byte = 10
UInt16 UShort 2 bytes Dim example As UShort = 10
UInt32 UInteger 4 bytes Dim example As UInteger = 10
UInt64 ULong 8 bytes Dim example As ULong = 10
Object N/A 4 bytes 32 bit Dim example As Object = Nothing
architecture, 8 bytes 64
bit architecture
There also exist data identifier and literal type characters usable in replacement
for the textual type and or to force literal type:

Type (or Alias) Identifier type character Literal type character

Short N/A example = 10S
Integer Dim example% example = 10 or10I
example =
Long Dim example& % or
example = 10L
Single Dim example! example = 10& or
example = 10F
Double Dim example# example = 10! or
Decimal Dim example@ example =or10R
example = 10#
Char N/A example = "A"C
example = 10D
example = 10@
String Dim example$ N/A
UShort N/A example = 10US
UInteger N/A example = 10UI
ULong N/A example = 10UL

The integral suffixes are also usable with hexadecimal (&H) or octal (&O) prefixes:
example = &H8000S or example = &O77&

Date(Time) objects can also be defined using literal syntax:

Dim example As Date = #7/26/2016 12:8 PM#

Once a variable is declared it will exist within the Scope of the containing type,
Sub or Function declared, as an example:

Public Function IncrementCounter() As Integer

Dim counter As Integer = 0
_counter += 1
Return counter
End Function

The counter variable will only exist until the End Function and then will be out
of scope. If this counter variable is needed outside of the function you will have to
define it at class/structure or module level.

Public Class ExampleClass

Private _counter As Integer

Public Function IncrementCounter() As Integer

_counter += 1
Return _counter
End Function

End Class

Alternatively, you can use the Static (not to be confused with Shared) modifier
to allow a local variable to retain it's value between calls of its enclosing
 method:

Function IncrementCounter() As Integer Static

counter As Integer = 0 counter += 1
Return counter
End Function

Section 2.2: Levels of declaration – Local and Member variables

Local variables - Those declared within a procedure (subroutine or function) of a class
(or other structure). In this example, exampleLocalVariable is a local variable
declared within ExampleFunction():

Public Class ExampleClass1

Public Function
ExampleFunction() As
Integer Dim
exampleLocalVariable
As Integer = 3 Return
exampleLocalVariable
End Function
End Class

The Static keyword allows a local variable to be retained and keep its value after
termination (where usually, local variables cease to exist when the containing
procedure terminates).
On each call to ExampleSub() from Main() the static variable retains the value
it had at the end of the previous call:

Module Module1

Sub Main()
ExampleSub()
ExampleSub()
ExampleSub()
End Sub

Public Sub ExampleSub()

Static exampleStaticLocalVariable As Integer = 0
[Link]([Link])
exampleStaticLocalVariable += 2
End Sub

End Module
8.2 [Link] Data types
Data types refer to an extensive system used for declaring variables or functions of different
types. The type of a variable determines how much space it occupies in storage and how the
bit pattern stored is interpreted.

[Link] provides a wide range of data types. The following table shows all the data types
available.

Storage
Data Type Value Range
Allocation
Depends on
Boolean implementing
True or False
platform
Byte 1 byte 0 through 255 (unsigned)
Char 2 bytes 0 through 65535 (unsigned)
0:00:00 (midnight) on January 1, 0001 through 11:59:59 PM on
Date 8 bytes
December 31, 9999
0 through +/-79,228,162,514,264,337,\
593,543,950,335 (+/-7.9...E+28) with no decimal point; 0
Decimal 16 bytes
through +/-7.9228162514264337593543950335 with 28 places
to the right of the decimal
-1.79769313486231570E+308 through -
4.94065645841246544E-324, for negative values
Double 8 bytes
4.94065645841246544E-324 through
1.79769313486231570E+308, for positive values
Integer 4 bytes -2,147,483,648 through 2,147,483,647 (signed)
-9,223,372,036,854,775,808 through
Long 8 bytes
9,223,372,036,854,775,807(signed)
4 bytes on 32-
bit platform
Object Any type can be stored in a variable of type Object
8 bytes on 64-
bit platform
SByte 1 byte -128 through 127 (signed)
Short 2 bytes -32,768 through 32,767 (signed)
-3.4028235E+38 through -1.401298E-45 for negative values;
Single 4 bytes
1.401298E-45 through 3.4028235E+38 for positive values
Depends on
String implementing 0 to approximately 2 billion Unicode characters
platform
UInteger 4 bytes 0 through 4,294,967,295 (unsigned)
ULong 8 bytes 0 through 18,446,744,073,709,551,615 (unsigned)
Depends on
User- Each member of the structure has a range determined by its data
implementing
Defined type and independent of the ranges of the other members
platform
UShort 2 bytes 0 through 65,535 (unsigned)
Example
The following example demonstrates use of some of the types −

Module DataTypes
Sub Main()
Dim b As Byte
Dim n As Integer
Dim si As Single
Dim d As Double
Dim da As Date
Dim c As Char
Dim s As String
Dim bl As Boolean

b=1
n = 1234567
si = 0.12345678901234566
d = 0.12345678901234566
da = Today
c = "U"c
s = "Me"

If ScriptEngine = "VB" Then

bl = True
Else
bl = False
End If

If bl Then
'the oath taking
[Link](c & " and," & s & vbCrLf)
[Link]("declaring on the day of: {0}", da)
[Link]("We will learn [Link] seriously")
[Link]("Lets see what happens to the floating point variables:")
[Link]("The Single: {0}, The Double: {1}", si, d)
End If
[Link]()
End Sub
End Module

When the above code is compiled and executed, it produces the following result −

U and, Me
declaring on the day of: 12/4/2012 12:00:00 PM
We will learn [Link] seriously
Lets see what happens to the floating point variables:
The Single:0.1234568, The Double: 0.123456789012346
8.3 The Type Conversion Functions in [Link]
[Link] provides the following in-line type conversion functions

[Link]. Functions & Description

1 CBool(expression) Converts the expression to Boolean data type.
2 CByte(expression) Converts the expression to Byte data type.
3 CChar(expression) Converts the expression to Char data type.
4 CDate(expression) Converts the expression to Date data type
5 CDbl(expression) Converts the expression to Double data type.
6 CDec(expression) Converts the expression to Decimal data type.
7 CInt(expression) Converts the expression to Integer data type.
8 CLng(expression) Converts the expression to Long data type.
9 CObj(expression) Converts the expression to Object type.
10 CSByte(expression) Converts the expression to SByte data type.
11 CShort(expression) Converts the expression to Short data type.
12 CSng(expression) Converts the expression to Single data type.
13 CStr(expression) Converts the expression to String data type.
14 CUInt(expression) Converts the expression to UInt data type.
15 CULng(expression) Converts the expression to ULng data type.
16 CUShort(expression) Converts the expression to UShort data type.

Example
The following example demonstrates some of these functions −

Module DataTypes
Sub Main()
Dim n As Integer
Dim da As Date
Dim bl As Boolean = True
n = 1234567
da = Today

[Link](bl)
[Link](CSByte(bl))
[Link](CStr(bl))
[Link](CStr(da))
[Link](CChar(CChar(CStr(n))))
[Link](CChar(CStr(da)))
[Link]()
End Sub
End Module

When the above code is compiled and executed, it produces the following result −

True
-1
True
12/4/2012
1
1

8.4 Accepting Values from User

The Console class in the System namespace provides a function ReadLine for accepting input
from the user and store it into a variable. For example,

Dim message As String

message = [Link]

following example demonstrates it −

Module variablesNdataypes
Sub Main()
Dim message As String
[Link]("Enter message: ")
message = [Link]
[Link]()
[Link]("Your Message: {0}", message)
[Link]()
End Sub
End Module
When the above code is compiled and executed, it produces the following result (assume the
user inputs Hello World) −

Enter message: Hello World

Your Message: Hello World

8.5 [Link] Constants and Enumerations

The constants refer to fixed values that the program may not alter during its execution. These
fixed values are also called literals. Constants can be of any of the basic data types like an
integer constant, a floating constant, a character constant, or a string literal. There are also
enumeration constants as well. The constants are treated just like regular variables except that
their values cannot be modified after their definition.

An enumeration is a set of named integer constants.

Declaring Constants
In [Link], constants are declared using the Const statement. The Const statement is used at
module, class, structure, procedure, or block level for use in place of literal values.
The syntax for the Const statement is −

Example
The following example demonstrates declaration and use of a constant value −

Module constantsNenum
Sub Main()
Const PI = 3.14149
 Dim radius, area As Single
radius = 7
area = PI * radius * radius
[Link]("Area = " & Str(area))
[Link]()
End Sub
End Module

When the above code is compiled and executed, it produces the following result −
Area = 153.933

Declaring Enumerations
An enumerated type is declared using the Enum statement. The Enum statement declares an
enumeration and defines the values of its members. The Enum statement can be used at the
module, class, structure, procedure, or block level.

For example,

Enum Colors
red = 1
orange = 2
yellow = 3
green = 4
azure = 5
blue = 6
violet = 7
End Enum

Example
The following example demonstrates declaration and use of the Enum variable Colors −

Module constantsNenum
Enum Colors
red = 1
orange = 2
yellow = 3
green = 4
azure = 5
blue = 6
violet = 7
End Enum

Sub Main()
[Link]("The Color Red is : " & [Link])
[Link]("The Color Yellow is : " & [Link])
[Link]("The Color Blue is : " & [Link])
[Link]("The Color Green is : " & [Link])
[Link]()
End Sub
End Module
When the above code is compiled and executed, it produces the following result −
The Color Red is: 1
The Color Yellow is: 3
The Color Blue is: 6
The Color Green is: 4
Week 9
VB. Net Statements and Operators

9.1 Statement
A statement is a complete instruction in Visual Basic programs. It may contain keywords,
operators, variables, literal values, constants and expressions.
Statements could be categorized as −
 Declaration statements − these are the statements where you name a variable,
constant, or procedure, and can also specify a data type.
 Executable statements − these are the statements, which initiate actions. These
statements can call a method or function, loop or branch through blocks of code or
assign values or expression to a variable or constant. In the last case, it is called an
Assignment statement.

The declaration statements are used to name and define procedures, variables, properties,
arrays, and constants. When you declare a programming element, you can also define its data
type, access level, and scope. The programming elements you may declare include variables,
constants, enumerations, classes, structures, modules, interfaces, procedures, procedure
parameters, function returns, external procedure references, operators, properties, events, and
delegates. Following are the declaration statements in [Link]

[Link] Statements and Description Example

Dim Statement Dim number As Integer
1 Declares and allocates storage space for one Dim quantity As Integer = 100
or more variables. Dim message As String = "Hello!"
Const maximum As Long = 1000
Const Statement
2 Const naturalLogBase As Object
Declares and defines one or more constants.
= CDec(2.7182818284)
Enum CoffeeMugSize
Jumbo
Enum Statement ExtraLarge
3 Declares an enumeration and defines the Large
values of its members. Medium
Small
End Enum
Class Statement Class Box
Declares the name of a class and introduces Public length As Double
4 the definition of the variables, properties, Public breadth As Double
events, and procedures that the class Public height As Double
comprises. End Class
Structure Statement Structure Box
Declares the name of a structure and Public length As Double
5 introduces the definition of the variables, Public breadth As Double
properties, events, and procedures that the Public height As Double
structure comprises. End Structure
Public Module myModule
6 Module Statement
Sub Main()
 Declares the name of a module and introduces Dim user As String =
the definition of the variables, properties, InputBox("What is your name?")
events, and procedures that the module MsgBox("User name is" & user)
comprises. End Sub
End Module
Interface Statement
Public Interface MyInterface
Declares the name of an interface and
7 Sub doSomething()
introduces the definitions of the members that
End Interface
the interface comprises.
Function myFunction
Function Statement
(ByVal n As Integer) As Double
8 Declares the name, parameters, and code that
Return 5.87 * n
define a Function procedure.
End Function
Sub Statement Sub mySub(ByVal s As String)
9 Declares the name, parameters, and code that Return
define a Sub procedure. End Sub
Declare Function getUserName
Lib "[Link]"
Declare Statement
Alias "GetUserNameA"
10 Declares a reference to a procedure
(
implemented in an external file.
ByVal lpBuffer As String,
ByRef nSize As Integer) As Integer
Public Shared Operator +
(ByVal x As obj, ByVal y As obj) As
Operator Statement
obj
Declares the operator symbol, operands, and
11 Dim r As New obj
code that define an operator procedure on a
' implemention code for r = x + y
class or structure.
Return r
End Operator
ReadOnly Property quote() As String
Property Statement
Get
Declares the name of a property, and the
12 Return quoteString
property procedures used to store and retrieve
End Get
the value of the property.
End Property
Event Statement
13 Public Event Finished()
Declares a user-defined event.
Delegate Function MathOperator(
Delegate Statement ByVal x As Double,
14
Used to declare a delegate. ByVal y As Double
) As Double
9.2 Executable Statement
An executable statement performs an action. Statements calling a procedure, branching to
another place in the code, looping through several statements, or evaluating an expression are
executable statements. An assignment statement is a special case of an executable statement.

Example
The following example demonstrates a decision making statement −
Module decisions
Sub Main()
'local variable definition '
Dim a As Integer = 10

' check the boolean condition using if statement '

If (a < 20) Then
' if condition is true then print the following '
[Link]("a is less than 20")
End If
[Link]("value of a is : {0}", a)
[Link]()
End Sub
End Module

When the above code is compiled and executed, it produces the following result −
a is less than 20;
value of a is : 10

[Link] Operators
An operator is a symbol that tells the compiler to perform specific mathematical or logical
manipulations. [Link] is rich in built-in operators and provides following types of commonly
used operators −
 Arithmetic Operators
 Comparison Operators
 Logical/Bitwise Operators
 Bit Shift Operators
 Assignment Operators
 Miscellaneous Operators

9.3 Arithmetic Operators

Following table shows all the arithmetic operators supported by [Link]. Assume variable A
holds 2 and variable B holds 7

Operator Description Example

^ Raises one operand to the power of another B^A will give 49
+ Adds two operands A + B will give 9
- Subtracts second operand from the first A - B will give -5
* Multiplies both operands A * B will give 14
Divides one operand by another and returns a
/ B / A will give 3.5
floating point result
 Divides one operand by another and returns an
\ B \ A will give 3
integer result
Modulus Operator and remainder of after an
MOD B MOD A will give 1
integer division

Comparison Operators
Following table shows all the comparison operators supported by [Link]. Assume variable A
holds 10 and variable B holds 20, then −

Operator Description Example

Checks if the values of two operands are equal or
= (A = B) is not true.
not; if yes, then condition becomes true.
Checks if the values of two operands are equal or
<> not; if values are not equal, then condition (A <> B) is true.
becomes true.
Checks if the value of left operand is greater than
> the value of right operand; if yes, then condition (A > B) is not true.
becomes true.
Checks if the value of left operand is less than the
< value of right operand; if yes, then condition (A < B) is true.
becomes true.
Checks if the value of left operand is greater than
>= or equal to the value of right operand; if yes, then (A >= B) is not true.
condition becomes true.
Checks if the value of left operand is less than or
<= equal to the value of right operand; if yes, then (A <= B) is true.
condition becomes true.

Apart from the above, [Link] provides three more comparison operators, which we will be
using in forthcoming chapters; however, we give a brief description here.
 Is Operator − It compares two object reference variables and determines if two object
references refer to the same object without performing value comparisons. If object1
and object2 both refer to the exact same object instance, result is True; otherwise, result
is False.
 IsNot Operator − It also compares two object reference variables and determines if two
object references refer to different objects. If object1 and object2 both refer to the exact
same object instance, result is False; otherwise, result is True.
 Like Operator − It compares a string against a pattern.

Logical/Bitwise Operators
Following table shows all the logical operators supported by [Link]. Assume variable A holds
Boolean value True and variable B holds Boolean value False, then −

Operator Description Example

It is the logical as well as bitwise AND operator.
And (A And B) is False.
If both the operands are true, then condition
 becomes true. This operator does not perform
short-circuiting, i.e., it evaluates both the
expressions.
It is the logical as well as bitwise OR operator. If
any of the two operands is true, then condition
Or becomes true. This operator does not perform (A Or B) is True.
short-circuiting, i.e., it evaluates both the
expressions.
It is the logical as well as bitwise NOT operator.
Use to reverses the logical state of its operand. If
Not Not(A And B) is True.
a condition is true, then Logical NOT operator will
make false.
It is the logical as well as bitwise Logical
Exclusive OR operator. It returns True if both
expressions are True or both expressions are False;
Xor otherwise it returns False. This operator does not A Xor B is True.
perform short-circuiting, it always evaluates both
expressions and there is no short-circuiting
counterpart of this operator.
It is the logical AND operator. It works only on
AndAlso (A AndAlso B) is False.
Boolean data. It performs short-circuiting.
It is the logical OR operator. It works only on
OrElse (A OrElse B) is True.
Boolean data. It performs short-circuiting.
IsFalse It determines whether an expression is False.
IsTrue It determines whether an expression is True.

Bit Shift Operators

We have already discussed the bitwise operators. The bit shift operators perform the shift
operations on binary values. Before coming into the bit shift operators, let us understand the
bit operations. Bitwise operators work on bits and perform bit-by-bit operations. The truth
tables for &, |, and ^ are as follows –

p q p&q p|q p^q

0 0 0 0 0
0 1 0 1 1
1 1 1 1 0
1 0 0 1 1

Assume if A = 60; and B = 13; now in binary format they will be as follows −
A = 0011 1100
B = 0000 1101
-----------------
A&B = 0000 1100
A|B = 0011 1101
A^B = 0011 0001
~A = 1100 0011
We have seen that the Bitwise operators supported by [Link] are And, Or, Xor and Not. The
Bit shift operators are >> and << for left shift and right shift, respectively.
Assume that the variable A holds 60 and variable B holds 13, then −

Operator Description Example

Bitwise AND Operator copies a bit to the result if
(A AND B) will give 12, which
And
it exists in both operands. is 0000 1100
Binary OR Operator copies a bit if it exists in
(A Or B) will give 61, which is
Or
either operand. 0011 1101
Binary XOR Operator copies the bit if it is set in
(A Xor B) will give 49, which
Xor
one operand but not both. is 0011 0001
(Not A ) will give -61, which is
Binary Ones Complement Operator is unary and 1100 0011 in 2's complement
Not
has the effect of 'flipping' bits. form due to a signed binary
number.
Binary Left Shift Operator. The left operands
A << 2 will give 240, which is
<< value is moved left by the number of bits specified
1111 0000
by the right operand.
Binary Right Shift Operator. The left operands
A >> 2 will give 15, which is
>> value is moved right by the number of bits
0000 1111
specified by the right operand.

Assignment Operators
There are following assignment operators supported by [Link] −

Operator Description Example

Simple assignment operator, Assigns values from C = A + B will assign value of
=
right side operands to left side operand A + B into C
Add AND assignment operator, It adds right
C += A is equivalent to C = C +
+= operand to the left operand and assigns the result
A
to left operand
Subtract AND assignment operator, It subtracts
C -= A is equivalent to C = C -
-= right operand from the left operand and assigns the
A
result to left operand
Multiply AND assignment operator, It multiplies
C *= A is equivalent to C = C *
*= right operand with the left operand and assigns the
A
result to left operand
Divide AND assignment operator, It divides left
C /= A is equivalent to C = C /
/= operand with the right operand and assigns the
A
result to left operand (floating point division)
Divide AND assignment operator, It divides left
\= operand with the right operand and assigns the C \= A is equivalent to C = C \A
result to left operand (Integer division)
 Exponentiation and assignment operator. It raises
C^=A is equivalent to C = C ^
^= the left operand to the power of the right operand
A
and assigns the result to left operand.
<<= Left shift AND assignment operator C <<= 2 is same as C = C << 2
>>= Right shift AND assignment operator C >>= 2 is same as C = C >> 2
Concatenates a String expression to a String
Str1 &= Str2 is same as
&= variable or property and assigns the result to the
Str1 = Str1 & Str2
variable or property.

Miscellaneous Operators
There are few other important operators supported by [Link].

Operator Description Example

AddHandler [Link],
AddressOf Returns the address of a procedure.
AddressOf Button1_Click
It is applied to an operand in an
asynchronous method or lambda Dim result As res = Await
Await
expression to suspend execution of the AsyncMethodThatReturnsResult()
method until the awaited task completes. Await AsyncMethod()
It returns a Type object for the specified
type. The Type object provides
GetType MsgBox(GetType(Integer).ToString())
information about the type such as its
properties, methods, and events.
Dim add5 = Function(num As
Function It declares the parameters and code that Integer) num + 5
Expression define a function lambda expression. 'prints 10
[Link](add5(5))
It uses short-circuit evaluation to
Dim num = 5
conditionally return one of two values.
If [Link](If(num >= 0,
The If operator can be called with three
"Positive", "Negative"))
arguments or with two arguments.

Operator Precedence
Operator precedence determines the grouping of terms in an expression. This affects how an
expression is evaluated. Certain operators have higher precedence than others; for example, the
multiplication operator has higher precedence than the addition operator −
For example, x = 7 + 3 * 2; here, x is assigned 13, not 20 because operator * has higher
precedence than +, so it first gets multiplied with 3*2 and then adds into 7.
Here, operators with the highest precedence appear at the top of the table, those with the lowest
appear at the bottom. Within an expression, higher precedence operators will be evaluated first.

Operator Precedence
Await Highest
Exponentiation (^)
Unary identity and negation (+, -)
Multiplication and floating-point division (*, /)
Integer division (\)
Modulus arithmetic (Mod)
Addition and subtraction (+, -)
Arithmetic bit shift (<<, >>)
All comparison operators (=, <>, <, <=, >, >=, Is, IsNot,
Like, TypeOf...Is)
Negation (Not)
Conjunction (And, AndAlso)
Inclusive disjunction (Or, OrElse)
Exclusive disjunction (Xor) Lowest
Week 10
Decision Making

10.1 [Link] Decision Making

Decision making structures require that the programmer specify one or more conditions to be
evaluated or tested by the program, along with a statement or statements to be executed if the
condition is determined to be true, and optionally, other statements to be executed if the
condition is determined to be false.

Following is the general form of a typical decision making structure found in most of the
programming languages −

[Link] provides the following types of decision making statements. Click the following links
to check their details.

Statement Description
An If...Then statement consists of a boolean expression
If ... Then statement
followed by one or more statements.
An If...Then statement can be followed by an optional Else
If...Then...Else statement statement, which executes when the boolean expression is
false.
You can use one If or Else if statement inside another If or
nested If statements
Else if statement(s).
A Select Case statement allows a variable to be tested for
Select Case statement
equality against a list of values.
You can use one select case statement inside another select
nested Select Case statements
case statement(s).
10.2 [Link] – Loops
There may be a situation when you need to execute a block of code several number of times.
In general, statements are executed sequentially: The first statement in a function is executed
first, followed by the second, and so on. Programming languages provide various control
structures that allow for more complicated execution paths. A loop statement allows us to
execute a statement or group of statements multiple times and following is the general form of
a loop statement in most of the programming languages.

[Link] provides following types of loops to handle looping requirements. Click the following
links to check their details.

Loop Type Description

It repeats the enclosed block of statements while a Boolean
Do Loop condition is True or until the condition becomes True. It could be
terminated at any time with the Exit Do statement.
It repeats a group of statements a specified number of times and
For...Next a loop index counts the number of loop iterations as the loop
executes.
It repeats a group of statements for each element in a collection.
For Each...Next This loop is used for accessing and manipulating all elements in
an array or a [Link] collection.
It executes a series of statements as long as a given condition is
While... End While
True.
 It is not exactly a looping construct. It executes a series of
With... End With
statements that repeatedly refer to a single object or structure.
You can use one or more loops inside any another While, For or
Nested loops
Do loop.

Loop Control Statements

Loop control statements change execution from its normal sequence. When execution leaves a
scope, all automatic objects that were created in that scope are destroyed. [Link] provides the
following control statements.

Control Statement Description

Terminates the loop or select case statement and transfers
Exit statement execution to the statement immediately following the loop or
select case.
Causes the loop to skip the remainder of its body and
Continue statement
immediately retest its condition prior to reiterating.
Transfers control to the labeled statement. Though it is not
GoTo statement
advised to use GoTo statement in your program.

For...Next loop is used for repeating the same action for a finite number of
times. The statements inside the following loop will be executed 11 times. The
first time, i will have the value 0, the second time it will have the value 1, the last
time it will have the value 10.

For i As Integer = 0 To 10
'Execute the action
[Link]([Link])
Next

Any integer expression can be used to parameterize the loop. It is permitted, but
not required, for the control variable (in this case i) to also be stated after the
Next. It is permitted for the control variable to be declared in advance, rather
than within the For statement.

Dim StartIndex As Integer = 3 Dim EndIndex As

Integer = 7 Dim i As Integer
For i = StartIndex To EndIndex – 1
'Execute the action
[Link]([Link])
Next i

Being able to define the Start and End integers allows loops to be created that
directly reference other objects, such as:

For i = 0 to [Link] - 1
[Link]([Link](i).Cells(0).[Link])
Next
This would then loop through every row in DataGridView1 and perform the action
of writing the value of Column 1 to the Console. (The -1 is because the first row of the
counted rows would be 1, not 0)
It is also possible to define how the control variable must increment.

For i As Integer = 1 To 10 Step 2

[Link]([Link])
Next

This outputs:

13579

It is also possible to decrement the control variable (count down).

For i As
Integer = 10
To 1 Step -1
[Link]
ine([Link])
Next
This outputs:
10 9 8 7 6 5 4 3 2 1

Short Circuiting
Any loop may be terminated or continued early at any point by using the Exit or
Continue statements.
Exiting
You can stop any loop by exiting early. To do this, you can use the keyword Exit
along with the name of the loop.

Exiting a loop early is a great way to boost performance by only looping the
necessary number of times to satisfy

Dim Numbers As Integer() = {1,2,3,4,5}

Dim SoughtValue As Integer = 2
Dim SoughtIndex
For Each i In Numbers
If i = 2 Then
SoughtIndex = i
Exit For
End If
Next
[Link](SoughtIndex)

Continue Statement
Along with exiting early, you can also decide that you need to just move on to the next
loop iteration. This is easily done by using the Continue statement. Just like Exit, it is
proceeded by the loop name.
 Here's an example of preventing even numbers from being added to the sum.

Dim Numbers As Integer() = {1,2,3,4,5}

Dim SumOdd As Integer = 0
For Each i In Numbers
If Numbers(i) \ 2 = 0 Then Continue For
SumOdd += Numbers(i)
Next

Using Advice
There are two alternative techniques that can be used instead of using Exit or
Continue.

You can declare a new Boolean variable, initializing it to one value and
conditionally setting it to the other value inside the loop; you then use a
conditional statement (e.g. If) based on that variable to avoid execution of
the statements inside the loop in subsequent iterations.

One of the objections to this technique is that it may be inefficient. For example,
if in the above example N is 1000000 and the first element of the array A is equal
to SoughtValue, the loop will iterate a further 999999 times without doing
anything useful. However, this technique can have the advantage of greater clarity
in some cases.

Dim Found As Boolean = False Dim FoundIndex As Integer

For i As Integer = 0 To N - 1
If Not Found AndAlso A(i) = SoughtValue Then
FoundIndex = i Found = True
End If
Next

You can use the GoTo statement to jump out of the loop. Note that you cannot use
GoTo to jump into a loop.

Dim FoundIndex As Integer

For i As Integer = 0 To N - 1
If A(i) = SoughtValue Then
FoundIndex = i
GoTo Found
End If
Next
[Link]
("Not found")
Found:
[Link](FoundIndex)

While loop to iterate while some condition is true

A While loop starts by evaluating a condition. If it is true, the body of the
loop is executed. After the body of the loop is executed, the While
 condition is evaluated again to determine whether to re-execute the body.

Dim iteration As Integer = 1

While iteration <= 10
[Link](iter
[Link]() & "
")
iteration += 1
End While

This outputs:

1 2 3 4 5 6 7 8 9 10

Warning: A While loop can lead to an infinite loop. Consider what would happen if the
line of code that increments iteration were removed. In such a case the condition
would never be True and the loop would continue indefinitely.

9.5 Nested Loop

A nested loop is a loop within a loop, an inner loop within the body of an outer one. How
this works is that the first pass of the outer loop triggers the inner loop, which executes
to completion. Then the second pass of the outer loop triggers the inner loop again. This
repeats until the outer loop finishes. a break within either the inner or outer loop would
interrupt this process.
The Structure of a For Next nested loop is:

For counter1=startNumber to endNumber (Step increment)

For counter2=startNumber to
endNumber (Step increment)
One or more VB statements
Next counter2
Next counter1

Example :

For firstCounter = 1 to 5
Print “First Loop of ” + firstCounter
For secondCounter= 1 to 4
Print “Second Loop of ” + secondCounter
Next secondCounter
Next firstCounter
Do...Loop

Use Do...Loop to repeat a block of statements While or Until a condition is

true, checking the condition either at the beginning or at the end of the loop.
Dim x As Integer = 0
Do
[Link](x &
" ") x += 1
Loop While x < 10

Or
Dim x As Integer = 0
Do While x < 10
[Link](x & " ")
x += 1
Loop

0123456789

Dim x As Integer = 0
Do
[Link](x & ")
x += 1
Loop Until x = 10

Or

Dim x As Integer = 0
Do Until x = 10
[Link](x & " ")
x += 1
Loop

0123456789

Continue Do can be used to skip to the next iteration of the loop:

Dim x As Integer = 0
Do While x < 10 x += 1
If x Mod 2 = 0 Then Continue Do
End If
[Link](x & " ")
Loop

13579

You can terminate the loop with Exit Do - note that in this example, the lack
of any condition would otherwise cause an infinite loop:

Dim x As Integer = 0
Do
[Link](x & " ")
 x += 1
If x = 10 Then
Exit Do
End If
Loop

0123456789
Week 11
Basic Contyrols and Strings

11.1 Basic Controls

An object is a type of user interface element you create on a Visual Basic form by using a
toolbox control. In fact, in Visual Basic, the form itself is an object. Every Visual Basic control
consists of three important elements −
 Properties which describe the object,
 Methods cause an object to do something and
 Events are what happens when an object does something.

Control Properties
All the Visual Basic Objects can be moved, resized or customized by setting their properties.
A property is a value or characteristic held by a Visual Basic object, such as Caption or Fore
Color.
Properties can be set at design time by using the Properties window or at run time by using
statements in the program code.
Object. Property = Value
where
 Object is the name of the object you're customizing.
 Property is the characteristic you want to change.
 Value is the new property setting.

For example,

[Link] = "Hello"

You can set any of the form properties using Properties Window. Most of the properties can be
set or read during application execution. You can refer to Microsoft documentation for a
complete list of properties associated with different controls and restrictions applied to them.

Control Methods
A method is a procedure created as a member of a class and they cause an object to do
something. Methods are used to access or manipulate the characteristics of an object or a
variable. There are mainly two categories of methods you will use in your classes −
 If you are using a control such as one of those provided by the Toolbox, you can call
any of its public methods. The requirements of such a method depend on the class being
used.
 If none of the existing methods can perform your desired task, you can add a method to
a class.

For example, the MessageBox control has a method named Show, which is called in the code
snippet below

Public Class Form1

Private Sub Button1_Click(ByVal sender As [Link], ByVal e As [Link])
Handles [Link]
[Link]("Hello, World")
End Sub
End Class
Control Events
An event is a signal that informs an application that something important has occurred. For
example, when a user clicks a control on a form, the form can raise a Click event and call a
procedure that handles the event. There are various types of events associated with a Form like
click, double click, close, load, resize, etc.
Following is the default structure of a form Load event handler subroutine. You can see this
code by double clicking the code which will give you a complete list of the all events associated
with Form control.

Private Sub Form1_Load(sender As Object, e As EventArgs) Handles [Link]

'event handler code goes here
End Sub

Here, Handles [Link] indicates that Form1_Load() subroutine handles Load event.
Similar way, you can check stub code for click, double click. If you want to initialize some
variables like properties, etc., then you will keep such code inside Form1_Load() subroutine.
Here, important point to note is the name of the event handler, which is by default Form1_Load,
but you can change this name based on your naming convention you use in your application
programming.

Basic Controls
[Link] provides a huge variety of controls that help you to create rich user interface.
Functionalities of all these controls are defined in the respective control classes. The control
classes are defined in the [Link] namespace.
The following table lists some of the commonly used controls:

[Link]. Widget & Description

Forms
1
The container for all the controls that make up the user interface.
TextBox
2
It represents a Windows text box control.
Label
3
It represents a standard Windows label.
Button
4
It represents a Windows button control.
ListBox
5
It represents a Windows control to display a list of items.
ComboBox
6
It represents a Windows combo box control.
RadioButton
7 It enables the user to select a single option from a group of choices when paired with
other RadioButton controls.
CheckBox
8
It represents a Windows CheckBox.
PictureBox
9
It represents a Windows picture box control for displaying an image.
 ProgressBar
10
It represents a Windows progress bar control.
ScrollBar
11
It Implements the basic functionality of a scroll bar control.
DateTimePicker
12 It represents a Windows control that allows the user to select a date and a time and to
display the date and time with a specified format.
TreeView
13
It displays a hierarchical collection of labeled items, each represented by a TreeNode.
ListView
14 It represents a Windows list view control, which displays a collection of items that can
be displayed using one of four different views.

11.2 [Link] - Dialog Boxes

There are many built-in dialog boxes to be used in Windows forms for various tasks like
opening and saving files, printing a page, providing choices for colors, fonts, page setup, etc.,
to the user of an application. These built-in dialog boxes reduce the developer's time and
workload.
All of these dialog box control classes inherit from the CommonDialog class and override the
RunDialog() function of the base class to create the specific dialog box.
The RunDialog() function is automatically invoked when a user of a dialog box calls its
ShowDialog() function.
The ShowDialog method is used to display all the dialog box controls at run-time. It returns a
value of the type of DialogResult enumeration. The values of DialogResult enumeration are:

 Abort − returns [Link] value, when user clicks an Abort button.

 Cancel − returns [Link], when user clicks a Cancel button.
 Ignore − returns [Link], when user clicks an Ignore button.
 No − returns [Link], when user clicks a No button.
 None − returns nothing and the dialog box continues running.
 OK − returns [Link], when user clicks an OK button
 Retry − returns [Link] , when user clicks an Retry button
 Yes − returns [Link], when user clicks an Yes button

The following diagram shows the common dialog class inheritance −

All these above-mentioned classes have corresponding controls that could be added from the
Toolbox during design time. You can include relevant functionality of these classes to your
application, either by instantiating the class programmatically or by using relevant controls.
When you double click any of the dialog controls in the toolbox or drag the control onto the
form, it appears in the Component tray at the bottom of the Windows Forms Designer, they do
not directly show up on the form. The following table lists the commonly used dialog box
controls. Click the following links to check their detail:

[Link]. Control & Description

ColorDialog
1 It represents a common dialog box that displays available colors along with controls
that enable the user to define custom colors.
FontDialog
2 It prompts the user to choose a font from among those installed on the local computer
and lets the user select the font, font size, and color.
OpenFileDialog
3
It prompts the user to open a file and allows the user to select a file to open.
SaveFileDialog
4 It prompts the user to select a location for saving a file and allows the user to specify
the name of the file to save data.
PrintDialog
5 It lets the user to print documents by selecting a printer and choosing which sections
of the document to print from a Windows Forms application

11.3 [Link] Strings

In [Link], you can use strings as array of characters, however, more common practice is to
use the String keyword to declare a string variable. The string keyword is an alias for the
[Link] class.

Creating a String Object

You can create string object using one of the following methods −
 By assigning a string literal to a String variable
  By using a String class constructor
 By using the string concatenation operator (+)
 By retrieving a property or calling a method that returns a string
 By calling a formatting method to convert a value or object to its string representation

The following example demonstrates this −

Module strings
Sub Main()
Dim fname, lname, fullname, greetings As String
fname = "Rowan"
lname = "Atkinson"
fullname = fname + " " + lname
[Link]("Full Name: {0}", fullname)

'by using string constructor

Dim letters As Char() = {"H", "e", "l", "l", "o"}
greetings = New String(letters)
[Link]("Greetings: {0}", greetings)

'methods returning String

Dim sarray() As String = {"Hello", "From", "Tutorials", "Point"}
Dim message As String = [Link](" ", sarray)
[Link]("Message: {0}", message)

'formatting method to convert a value

Dim waiting As DateTime = New DateTime(2012, 12, 12, 17, 58, 1)
Dim chat As String = [Link]("Message sent at {0:t} on {0:D}", waiting)
[Link]("Message: {0}", chat)
[Link]()
End Sub
End Module

When the above code is compiled and executed, it produces the following result −
Full Name: Rowan Atkinson
Greetings: Hello
Message: Hello From Tutorials Point
Message: Message sent at 5:58 PM on Wednesday, December 12, 2012

Properties of the String Class

The String class has the following two properties

[Link] Property Name & Description

Chars
1
Gets the Char object at a specified position in the current String object.
Length
2
Gets the number of characters in the current String object.

The following example demonstrates some of the methods mentioned above −

Comparing Strings

Module strings
Sub Main()
Dim str1, str2 As String
str1 = "This is test"
str2 = "This is text"

If ([Link](str1, str2) = 0) Then

[Link](str1 + " and " + str2 + " are equal.")
Else
[Link](str1 + " and " + str2 + " are not equal.")
End If
[Link]()
End Sub
End Module

When the above code is compiled and executed, it produces the following result −
This is test and This is text are not equal.

String Contains String

Module strings
Sub Main()
Dim str1 As String
str1 = "This is test"

If ([Link]("test")) Then
[Link]("The sequence 'test' was found.")
End If
[Link]()
End Sub
End Module

When the above code is compiled and executed, it produces the following result −
The sequence 'test' was found.

Getting a Substring:

Module strings
Sub Main()
Dim str As String
str = "Last night I dreamt of San Pedro"
[Link](str)

Dim substr As String = [Link](23)

[Link](substr)
[Link]()
End Sub
End Module
When the above code is compiled and executed, it produces the following result −
Last night I dreamt of San Pedro
San Pedro.

Joining Strings

Module strings
Sub Main()
Dim strarray As String() = {
"Down the way where the nights are gay",
"And the sun shines daily on the mountain top",
"I took a trip on a sailing ship",
"And when I reached Jamaica",
"I made a stop"
}
Dim str As String = [Link](vbCrLf, strarray)
[Link](str)
[Link]()
End Sub
End Module

When the above code is compiled and executed, it produces the following result −

Down the way where the nights are gay

And the sun shines daily on the mountain top
I took a trip on a sailing ship
And when I reached Jamaica
I made a stop

11.4 [Link] Functions

A procedure is a group of statements that together perform a task when called. After the
procedure is executed, the control returns to the statement calling the procedure. [Link] has
two types of procedures
 Functions
 Sub procedures or Subs
Functions return a value, whereas Subs do not return a value.

Defining a Function
The Function statement is used to declare the name, parameter and the body of a function. The
syntax for the Function statement is −

[Modifiers] Function FunctionName [(ParameterList)] As ReturnType

[Statements]
End Function

where,
 Modifiers − specify the access level of the function; possible values are: Public, Private,
Protected, Friend, Protected Friend and information regarding overloading, overriding,
sharing, and shadowing.
  FunctionName − indicates the name of the function
 ParameterList − specifies the list of the parameters
 ReturnType − specifies the data type of the variable the function returns

Example
Following code snippet shows a function FindMax that takes two integer values and returns
the larger of the two.

Function FindMax(ByVal num1 As Integer, ByVal num2 As Integer) As Integer

' local variable declaration */
Dim result As Integer

If (num1 > num2) Then

result = num1
Else
result = num2
End If
FindMax = result
End Function

Function Returning a Value

In [Link], a function can return a value to the calling code in two ways −
 By using the return statement
 By assigning the value to the function name

The following example demonstrates using the FindMax function −

Module myfunctions
Function FindMax(ByVal num1 As Integer, ByVal num2 As Integer) As Integer
' local variable declaration */
Dim result As Integer

If (num1 > num2) Then

result = num1
Else
result = num2
End If
FindMax = result
End Function
Sub Main()
Dim a As Integer = 100
Dim b As Integer = 200
Dim res As Integer

res = FindMax(a, b)
[Link]("Max value is : {0}", res)
[Link]()
End Sub
End Module
When the above code is compiled and executed, it produces the following result −
Max value is : 200

Recursive Function
A function can call itself. This is known as recursion. Following is an example that calculates
factorial for a given number using a recursive function −

Module myfunctions
Function factorial(ByVal num As Integer) As Integer
' local variable declaration */
Dim result As Integer

If (num = 1) Then
Return 1
Else
result = factorial(num - 1) * num
Return result
End If
End Function
Sub Main()
'calling the factorial method
[Link]("Factorial of 6 is : {0}", factorial(6))
[Link]("Factorial of 7 is : {0}", factorial(7))
[Link]("Factorial of 8 is : {0}", factorial(8))
[Link]()
End Sub
End Module

When the above code is compiled and executed, it produces the following result −
Factorial of 6 is: 720
Factorial of 7 is: 5040
Factorial of 8 is: 40320

11.5 Error Handling

Try...Catch...Finally Statement

Structure:
Try
'Your program will try to run the code in this block.

'If any exceptions are thrown, the code in the Catch

Block will be executed, 'without executing the lines
after the one which caused the exception.
Catch ex As [Link]
'If an exception occurs when processing the Try
block, each Catch statement 'is examined in
textual order to determine which handles the
exception. 'For example, this Catch block
handles an IOException.
Catch ex As Exception
'This catch block handles all Exception types.
'Details of the exception, in this case, are
in the "ex" variable. 'You can show the
error in a MessageBox with the below line.
[Link]([Link])
Finally

'A finally block is always executed, regardless of if an Exception

occurred.

End Try

Example Code
Try
Dim obj = Nothing

Dim prop = [Link] 'This line will throw a

NullReferenceException

[Link]("Test.") ' This line will NOT be executed

Catch ex As [Link]
' Code that reacts to IOException.

Catch ex As NullReferenceException
' Code that reacts to a NullReferenceException
[Link]("NullReferenceException: " &
[Link]) [Link]("Stack Trace: " &
[Link])
Catch ex As Exception

' Code that reacts to any other exception.

Finally
' This will always be run, regardless of if an exception is
thrown.

[Link]("Completed")

End Try

Creating custom exception and throwing

You can create a custom exception and throw them during the execution of your
function. As a general practice you should only throw an exception when your
function could not achieve its defined functionality.

Private Function OpenDatabase(Byval Server as String, Byval User as

String, Byval Pwd as String)

if [Link]="" then
Throw new Exception("Server Name cannot be blank")

elseif [Link] ="" then

Throw new Exception("User name cannot be blank")

elseif [Link]="" then
Throw new Exception("Password cannot be blank")

endif

'Here add codes for connecting to the server