MODULE 2

Operating Systems
An operating system is the software that controls the overall operation of a computer. It provides the
means by which a user can store and retrieve files, provides the interface by which a user can request the
execution of programs, and provides the environment necessary to execute the programs requested.

Example:
1. Windows, which is provided in numerous versions by Microsoft and widely used in the PC arena.
2. UNIX, which is a popular choice for larger computer systems as well as PCs. In fact, UNIX is the
core of two other popular operating systems: Mac OS, and Solaris.
3. Linux, which was originally developed noncommercially by computer enthusiasts and is now
available through many commercial sources, including IBM.

2.1 The History of Operating Systems

• Today’s operating systems are large, complex software packages that have grown from humble
beginnings.
• The computers of the 1940s and 1950s were not very flexible or efficient. Machines
occupied entire rooms. Users had to:
o Insert punched cards
o Mount tapes
o Set switches manually
No operating system → everything done manually
• The execution of each program, called a job, was handled as an isolated activity—the
machine was prepared for executing the program, the program was executed, and then
all the tapes, punched cards, etc. had to be retrieved before the next program preparation
could begin.
• When several users needed to share a machine, sign-up sheets were provided so that users
could reserve the machine for blocks of time. During the time period allocated to a user, the
machine was totally under that user’s control.
• In such an environment, operating systems began as systems for simplifying program
setup and for streamlining the transition between jobs.
• A computer operator was introduced. Users submitted jobs(required data and special
directions)to operator. And operator executed them later.
• Batch processing—the execution of jobs by collecting them in a single batch, then
executing them without further interaction with the user.
• In batch processing systems, the jobs residing in mass storage wait for execution in a job
queue. (Figure 1).
Job Queue (FIFO) - First job submitted → first executed (First in First out)
-Sometimes priority based
156 Module 2 Operating Systems
JCL (Job Control Language) -Instructions for running jobs
When the job was selected for execution, the operating system printed these instructions at
a printer where they could be read and followed by the computer operator.
Advantage: Reduced manual work
Disadvantage: No user interaction with their jobs.

• This communication between the operating system and the computer operator is still seen
today, as witnessed by PC operating systems that report such errors as “net- work not
available” and “printer not responding.

Figure 1 Batch processing

• New operating systems were developed that allowed a program being executed to carry on
a dialogue with the user through remote terminals a feature known as interactive
processing (Figure 2).
Figure 2 Interactive processing

• Successful interactive processing is that the actions of the computer be sufficiently fast to coordinate with the
needs of the user rather than forcing the user to conform to the machine’s timetable.

• Real-Time Processing: computer is forced to execute tasks under a deadline. System must respond
within a fixed time (deadline).
Example: 1. typing on keyboard → instant response
2. Flight booking systems.
Important: Response must match real-world timing.
• Time-Sharing Systems
i. Operating systems that provided service to multiple users at the same time: a feature called time-
sharing.
ii. (1960s–1970s): Computers were expensive → many users shared one system.
Solution: Time-sharing
How it works:
a. CPU time divided into small intervals
b. Each user gets a small time slice
c. Switching happens very fast → looks like simultaneous execution
d. Supports multiple users at same time.

• Multiprogramming:
i. Time is divided into intervals and then the execution of each job is restricted to only one interval
at a time.
ii. Multiple programs loaded into memory
iii. CPU switches between them
• Multitasking:
i. Single user runs multiple tasks simultaneously

• Difference between Time-sharing & Multitasking:

Time-sharing → many users
Multitasking → one user, many tasks

• Modern Systems
i. No more computer operators.
ii. Users interact directly with systems
iii. Role replaced by: System Administrator.

• Responsibilities:
i. Manage systems
ii. Install software
iii. Handle users/accounts
iv. Solve issues

• Today, the existence of a computer operator has essentially disappeared, especially in the arena of
personal computers where the computer user assumes all of the responsibilities of computer
operation.
• Even most large computer installations run essentially unattended. Indeed, the job of computer
operator has given way to that of a system administrator.
• Operating systems have grown from simple programs that retrieved and executed programs one at a
time into complex systems that coordinate time- sharing, maintain programs and data files in the
machine’s mass storage devices, and respond directly to requests from the computer’s users.
• The development of multiprocessor machines has led to operating systems that provide time-
sharing/ multitasking capabilities by assigning different tasks to different processors as well as by
sharing the time of each single processor. These operating systems must wrestle with such
158 Module 2 Operating Systems
problems as load balancing ((dynamically allocating tasks to the various processors so that all
processors are used efficiently) as well as scaling (breaking tasks into a number of subtasks
compatible with the number of processors available).

2.2 Operating System Architecture

To understand the composition of a typical operating system, we first consider the complete spectrum of
software found within a typical computer system. Then we will concentrate on the operating system itself.

A Software Survey
.
Figure 3 Software classification

Utility Operating

• Machine’s software is divided into two broad categories: application software and
system software (Figure 3).

1. Application software: it consists of the programs for performing tasks particular to

the machine’s utilization.
Examples of application software include spreadsheets, database systems, desktop
publishing systems, accounting systems, program development software, and games.
2. System software: it performs those tasks that are common to computer systems in
general. In a sense, the system software provides the infrastructure that the
application software requires.

Within the class of system software are two categories.

(i) Software units collectively known as utility software.
(ii) Operating system

(i) Utility software: it consists of software units that extend (or perhaps customize) the
capabilities of the operating system. It supports and extends OS functionality
Other instances of utility software include software to compress and
 decompress data, software for playing multimedia presentations, and software for
handling network communication.
Examples: Disk formatting tools, File copy tools, Antivirus, Compression software,
Media players.

(ii) Operating system

Components of an Operating System
In order to perform the actions requested by the computer’s users, an operating system
must be able to communicate with those users.
Components of an Operating System: An OS has 2 main parts:
1. User Interface (UI): The portion of an operating system that handles this
communication is often called the user interface. It allows user to interact with
computer
Older user interfaces, called shells, communicated with users through textual
messages using a keyboard and monitor screen.
Types:
a. CLI (Command Line Interface) → Older user interfaces, called text-based
(shells), communicated with users through textual messages using a keyboard and
monitor screen.
b. GUI (Graphical User Interface) → objects to be manipulated, such as files and
programs, are represented pictorially on the display as icons. These systems allow users to
issue commands by using one of several common input devices. Examples: Windows
GUI, UNIX shells.
More recently, advances in fine-grained touch screens allow users to
manipulate icons directly with their fingers. Whereas today’s GUIs use two-dimensional
image projection systems, three-dimensional interfaces that allow human users to
communicate with computers by means of 3D projection systems, tactile sensory devices,
and surround sound audio reproduction systems are subjects of current research.

Figure 4 The user interface acts as an intermediary between users and the operating system’s
kernel

Kernel

User interface
160 Module 2 Operating Systems

• Although an operating system’s user interface plays an important role in establishing a

machine’s functionality, this framework merely acts as an intermediary between the
computer’s user and the real heart of the operating system (Figure 4).
• This distinction between the user interface and the internal parts of the operating system
is emphasized by the fact that some operating systems allow a user to select among
different interfaces to obtain the most comfortable interaction for that particular user.
• An important component within today’s GUI shells is the window manager, which
allocates blocks of space on the screen, called windows, and keeps track of which
application is associated with each window.
• When an application wants to display something on the screen, it notifies the window
manager, and the window manager places the desired image in the window assigned to
the application.
• In turn, when a mouse button is clicked, it is the window manager that computes the
mouse’s location on the screen and notifies the appropriate application of the mouse
action.
• In contrast to an operating system’s user interface, the internal part of an operating
system is called the kernel. An operating system’s kernel contains those software
components that perform the very basic functions required by the computer installation.

2. Kernel Components
1. File Manager: The file manager maintains records of all the files stored in mass storage,
including where each file is located, which users are allowed to access the various files, and
which portions of mass storage are available for new files or extensions to existing files.
These records are kept on the individual storage medium containing the related
files so that each time the medium is placed online, the file manager can retrieve them and
thus know what is stored on that particular medium.
Concepts:
i) Directory / Folder: most file managers allow files to be grouped into a bundle.
ii) Subdirectories: allowing directories to contain other directories.
iii) Path (e.g., /home/docs/file): A chain of directories within directories.

2. Device Drivers: software units that communicate with the controllers to carry out
operations on the peripheral devices attached to the machine.[Communicate with hardware
devices]
Examples: Printer driver, Keyboard driver, Disk driver
Purpose: Convert general commands → device-specific instructions.

3. Memory Manager: it is charged with the task of coordinating the machine’s use of main
memory. It manages main memory (RAM)
Functions:
i. Allocate memory to programs
 ii. Prevent memory conflicts
iii. Track free/used memory

Virtual Memory:
• It uses disk to act like extra RAM.
Virtual Memory: RAM + Disk Storage

• Uses paging: Data divided into pages and Swapped between RAM & disk
Example: 4GB RAM behaves like 8GB.

Two additional components within the kernel of an operating system are the
scheduler(Decides which process runs next.) and dispatcher(Gives CPU to selected process).

Figure 5 The booting process

Operating

Operating Operating

What is boot strapping (Booting)?

• It is the process of loading the operating system (OS) into main memory (RAM) when the
computer is switched ON/ starting a computer.

• Steps:
1. Computer turns ON
2. CPU starts from a fixed location
3. Boot Loader runs (stored in ROM)
4. OS is loaded from disk → RAM
5. Control transferred to OS

• It is this procedure that transfers the operating system from mass storage (where it is permanently
stored) into main memory (which is essentially empty when the machine is first turned on).
• A computer’s main memory is typically constructed from volatile technologies—meaning that the
memory loses the data stored in it when the computer is turned off. Thus, the contents of main
162 Module 2 Operating Systems
memory must be replenshed each time the computer is restarted.
• In a general-purpose computer, a program called the boot loader is permanently stored in the
machine’s ROM. This, then, is the program that is initially executed when the machine is turned on.
• The instructions in the boot loader direct the CPU to transfer the operating system from a
predetermined location into the volatile area of main memory (Figure 5).
• Modern boot loaders can copy an operating system into main memory from a variety of locations.
• The overall process of executing the boot loader and thus starting the operating system is called
booting the computer.
• While it is possible to update operating systems and boot loaders stored in ROM (often called a
firmware update), the technological limits make mass storage the most common choice for more
traditional computer systems.

Key Components:
1. ROM (Read Only Memory)
• Non-volatile (data not lost)
• Stores boot loader
2. Boot Loader
• Loads OS into memory
3. Firmware
• Software stored in ROM
Examples: BIOS, EFI.

2.3 Coordinating the Machine’s Activities

The Concept of a Process

• The activity of executing a program under the control of the operating system is known as a
process. Associated with a process is the current status of the activity, called the process state.
• Program vs Process
Program → Static (just instructions stored in memory)
Process → Dynamic (program in execution)
Example: Program = recipe
Process = cooking using that recipe.

Process State: Snapshot of process at a given time. Changes continuously during execution.
Includes:
i) Program counter (current instruction)
ii) CPU registers
iii) Memory values

Process Administration: it is handled by 2 main components: Scheduler and Dispatcher.

• Scheduler: it maintains a record of the processes present in the computer system.
Functions:
i. It introduces new processes to this pool
ii. It removes completed processes from the pool.
iii. It maintains Process Table.
 • To keep track of all the processes, the scheduler maintains a block of information in main memory
called the process table. Each entry contains:
[Link] allocated to process.
ii. Process priority.
iii. Process state (Ready / Waiting)

Process States: Ready → Process is ready to execute

Waiting → Process is waiting for an event (I/O completion, keyboard/ User input,
message from another process, etc.)

Dispatcher (Execution Manager):

• It is the component of the kernel that supervises the execution of the scheduled processes.

• In a Time Sharing / Multitasking system this task is accomplished by multiprogramming;

that is, dividing time into short segments, each called a time slice (typically measured in
milliseconds or microseconds), and then switching the CPU’s attention among the processes as
each is allowed to execute for one time slice (Figure 6).

• Each process gets a turn to execute.

• The procedure of changing from one process to another is called a process switch (or a
context switch).

• During switching:
– Current process state is saved.
– Next process state is loaded.

• The dispatcher controls CPU execution of processes.

• Each time the dispatcher awards a time slice to a process, it initiates a timer circuit that will
indicate the end of the slice by generating a signal called an interrupt.

• Role of Interrupts
i. Each time slice is controlled using a timer.
ii. When time is over Interrupt signal is generated

• CPU Reaction to Interrupt

i. Completes current instruction
ii. Saves current process state
iii. Executes Interrupt Handler (part of dispatcher)
iv. This stops current process and gives control back to dispatcher.

• Process State Saving: To resume later, system saves:

i) Program Counter
ii) Register values
164 Module 2 Operating Systems
iii) Memory data
This saved information is called Process State.

Figure 6 Multiprogramming between process A and process B

Interrupt Interrupt Interrupt Interrupt Interrupt

2.4 Handling Competition among Processes

• One of the key responsibilities of an Operating System is resource allocation to the process.

• A resource can be:

Hardware → Printer, CPU, Memory
Software → Files, Process table, Time slices.

• Different OS components handle allocation:

File Manager → Files & storage
Memory Manager → Memory space
Scheduler → Process table
Dispatcher → CPU time

• Proper allocation is critical; poor design can lead to system errors.

Semaphores: Let us consider a time-sharing/multitasking operating system controlling the activities

of a computer with a single printer.
• If a process needs to print its results, it must request that the operating system give it access to
the printer’s device driver.
• At this point, the operating system must decide whether to grant this request, depending on
whether the printer is already being used by another process.
• If it is not, the operating system should grant the request and allow the process to continue;
otherwise, the operating system should deny the request and classify the process as a waiting
 process until the printer becomes avail- able.

• Problem (Resource Conflict)

Example: Single Printer.

• If two processes access it simultaneously → incorrect output.

• One approach to this task would be to use a flag, which in this context refers to a bit in memory
whose states are often referred to as set and clear.

• Simple Flag Approach: Use a flag variable:

– clear flag (value 0) → Printer free
– set flag (value 1) → Printer busy.

• However, this simple flag system has a problem. The task of testing and possibly setting the
flag may require several machine instructions.

• Problem: Checking and setting flag takes multiple steps. A process may get interrupted in
between. Leads to both processes using printer simultaneously. This is called a race condition.

• Solution: Method 1: Disable Interrupts: Prevent interruption during flag checking.

Method 2: Test-and-Set Instruction: Checks and sets flag in one atomic operation.
Suppose the printer is currently available, and a process requests use of it. The flag is retrieved
from main memory and found to be clear, indicating that the printer is available.

• How it works: Process checks semaphore

If free → enters and sets it
If busy → waits
After completion → clears semaphore
166 Module 2 Operating Systems
Deadlock
• Another problem that can arise during resource allocation is deadlock, the
condition in which two or more processes are blocked from progressing
because each is waiting for a resource that is allocated to another.
• For example, Process A →it has printer, waiting for CD
Process B →it has CD, waiting for printer
Both are stuck → Deadlock
• If the scheduler has no space left in the process table and each process in
the system must create an additional process before it can complete its
task, then no process can continue. Such conditions, as in other settings
(Figure 7), can severely degrade a system’s performance.
Analysis of deadlock has revealed that it cannot occur unless all three of
the following conditions are satisfied:
1. There is competition for nonsharable resources.
2. The resources are requested on a partial basis; that is, having
received some resources, a process will return later to request more.
3. Once a resource has been allocated, it cannot be forcibly retrieved.

Figure .7 A deadlock resulting from competition for nonsharable railroad intersections

 • The point of isolating these conditions is that the deadlock problem can be removed by
attacking any one of the three.
• Techniques that attack the third condition fall into the category known as deadlock
detection and correction schemes.
• Techniques that attack the first two conditions are known as deadlock avoidance
schemes.
• One, for example, attacks the second condition and second attacks the first condition.
• Technique of holding data for output at a later but more convenient time is called
spooling.

2.5 Security
• The operating system (OS) plays a major role in maintain system security. Security includes
reliability and protection of data and resource.
Example: Loss of data due to file manager error -lack of security.
• System crash causing data loss – lack of reliability.
• Hence, a well-designed and dependable OS ensures security.
• Role of Software Engineering:
i) security is not limited to OS alone.
ii) It is a part of software engineering, which focuses on
(a)Developing reliable software.
(b) Reducing errors and vulnerabilities.

Attacks from the Outside

• An important task performed by operating systems is to protect the computer’s resources from
access by unauthorized personnel.
• In the case of computers used by multiple people, this is usually approached by means of
establishing “accounts” for the various authorized users—an account being essentially a record
within the operating system containing such entries as the user’s name, password, and privileges to
be granted to that user.
• The operating system can then use this information during each login procedure (a sequence of
transactions in which the user establishes initial contact with a computer’s operating system) to
control access to the system.
• OS protects resources using user accounts.
• Each account contains:
– Username
– Password
– Access privileges
• During login, OS verifies user identity
168 Module 2 Operating Systems
• Accounts are established by a person known as the super user or the administrator. This person gains
highly privileged access to the operating system by identifying him- or herself as the administrator
(usually by name and password) during the login procedure.
• Once this contact is established, the administrator can alter settings within the operating system,
modify critical software packages, adjust the privileges granted to other users, and perform a variety
of other maintenance activities that are denied normal users.
• Responsibilities of Administrator (Super User).
– Modify system settings
– Manage users
– Assign permissions
– Monitor system activities.
–
• Auditing Software: it tracks and analyses system activities.
– It helps detect:
– Multiple failed login attempts
– Unusual user behaviour
Example: A normal user suddenly accessing advanced tools → suspicious

• Sniffing Software: Malicious programs that:

– It records user activities
– Steal login credentials
Example: Fake login screen to capture passwords

• User Carelessness (Major Issue): Common security weaknesses:

– Weak passwords (names, DOB)
– Sharing passwords
– Not updating passwords
– Using unapproved software
• The solution of this is organizations enforce security policies

Attacks from Within

• Occurs when: An intruder gains access or an authorized user behaves maliciously.
• Goals of Intruder
– Access restricted data
– Modify or destroy system files
– Insert malicious programs

Examples of Internal Attacks:

1. Accessing memory beyond allowed limits.
2. Retrieving restricted files.
3. Modifying system settings

• Memory Protection Mechanism: OS allocates specific memory to each process and CPU uses:
i) Base register (lower limit)
ii) Limit register (upper limit)

• Working of Memory Protection Mechanism:

 – Every memory access is checked.
– If access is outside limits, the CPU generates an interrupt and control returns to OS.

Problem Without Protection: A process could:

– Modify memory limits.
– Access unauthorized memory

• This leads to serious security threats.

•

Privileged and Non-Privileged Modes

a) Privileged Mode
• Full access to all instructions
• Used by OS
b) Non-Privileged Mode
• Limited access
• Used by user processes
•
Privileged Instructions
• Can only run in privileged mode
• Examples:
– Changing memory limits.
– Switching CPU modes.

Protection Mechanism
• If a process tries to execute a privileged instruction:
→ Interrupt occurs
→ OS takes control.

Role During Execution

• When system starts → CPU in privileged mode
• When process runs:
→ OS switches CPU to non-privileged mode
• Ensures process cannot harm system

Importance of Privilege Control

It Prevents:
– Unauthorized memory access
– Misuse of CPU time
– Direct hardware access
 170 Chapter 5 Algorithms

Alogoritm
• We have seen that before a computer can perform a task, it must be given an algorithm telling it
precisely what to do; consequently, the study of algorithms is the cornerstone of computer science
.

1. The Concept of an Algorithm

• An algorithm is a step-by-step procedure used to perform a task or solve a problem.
• It tells how to do something
• Used in both:
– Computers
– Daily life
Example: code, solving equations, etc

An Informal Review
We use algorithms in many areas such as:
• Number conversion: from one form to another
• Error detection and corrections
• Data compression and decompression
• Multiprogramming
• Even a computer’s CPU works using an algorithm.

As long as the halt instruction has not been executed continue to execute the following steps:
a. Fetch an instruction.
b. Decode the instruction.
c. Execute the instruction.

• Algorithms in Daily Life: Algorithms are not only technical.

Example: Shelling peas: - Obtain a basket of unshelled peas and an empty bowl.
As long as there are unshelled peas in the basket continue to execute the following steps:
a. Take a pea from the basket.
b. Break open the pea pod.
c. Dump the peas from the pod into the bowl.
d. Discard the pod.

The Formal Definition of an Algorithm

Figure 1 The definition of an algorithm

An algorithm is an ordered set

of unambiguous, executable steps that
defines a terminating process.
 5.3 Algorithm Discovery 171
• This definition has 4 important properties/ design steps

Property 1: Ordered Steps:

• Steps in an algorithm must have a well-established structure in terms of the order of their execution.
Steps must be in a proper order
• This does not mean, however, that the steps must be executed in a sequence consisting of a first step,
followed by a second, and so on.
• Some algorithms, known as parallel algorithms, contain more than one sequence of steps, each
designed to be executed by different processors in a multiprocessor machine.
• Order can be:
Sequential
Parallel
Parallel Algorithms:
• Multiple steps run at the same time
• Used in multiprocessor systems
• Steps may branch and join.

Property 2: Executable (Effective) Steps:

• consider the requirement that an algorithm must consist of executable steps.
• Each step must be possible to perform
• Should be practical
Not valid: “List all positive integers” (infinite) which would be impossible to perform because there are
infinitely many positive integers. Thus, any set of instructions involving this instruction would not be an
algorithm.
Valid: Finite, doable/manageable steps

Property 3: Unambiguous Steps:

• The steps in an algorithm be unambiguous. This means that during execution of an algorithm, the
information in the state of the process must be sufficient to determine uniquely and completely the
actions required by each step.
• Steps must be clear and precise
• No confusion or guessing.
• No creativity needed
• Only follow instructions exactly

Property 4: Terminating Process:

• which means that the execution of an algorithm must lead to an end.
• Algorithm must end after finite steps.
• Must produce a result.

Abstract Nature of Algorithms

• Difference between an algorithm and its representation — a difference that is like the one between a
story and a book.
• A story is abstract, or conceptual, in nature.
• A book is a physical representation of a story.
 172 Chapter 5 Algorithms
Like: Story (idea) vs Book (representation).
• Algorithm is an idea (concept)
• Not a physical thing

Representation of Algorithm: Same algorithm can be represented in different ways:

Example: Temperature conversion
• Formula: F = (9/5)C + 32
• Steps:
Multiply C by 9/5
Add 32
• Algorithm is same, only representation changes.

2. Algorithm Representation
• Algorithm representation means how we express or write an algorithm We need a proper way
(language/system) to describe steps clearly This section introduces: Primitives and Pseudocode

Primitives
• The representation of an algorithm requires some form of language.
• In the case of humans this might be a traditional natural language (English, Spanish, Russian,
Japanese) or perhaps the language of pictures, such natural channels of communication lead to
misunderstandings, some- times because the terminology used has more than one meaning.
• Example:
“Visiting grandchildren can be nerve-racking”
Meaning 1: Grandchildren cause stress
Meaning 2: Visiting them is stressful
So, representation must be clear and precise.

• Computer science approaches these problems by establishing a well-defined set of building blocks
from which algorithm representations can be constructed. Such a building block is called a
primitive.
• Primitives have:
– Fixed meaning.
– Clear definition.

• Advantages of Primitives
1. Remove ambiguity.
2. Ensure uniform level of detail.
3. Make algorithms easy to understand.

Programming Language: A collection of primitives along with a collection of rules stating how
the primitives can be combined to represent more complex ideas constitutes a programming
language.
 5.3 Algorithm Discovery 173
• Each primitive has its own syntax and semantics.
• Syntax: The form or structure of a primitive.
Example: symbols, keywords
• Semantics: The meaning of the primitive.
Example: Word: “air”
Syntax → letters (a, i, r)
Semantics → gas around us.

Low-Level vs High-Level Representation

• Low-Level (Machine Language)
1. Uses basic machine instructions
2. Very detailed.
3. Difficult and tedious
• High-Level
1. Uses abstract (higher-level) primitives
2. Easier to understand
3. Used in programming languages

Pseudocode
• In general, a pseudocode is a notational system in which ideas can be expressed informally
during the algorithm development process.
• One way to obtain a pseudocode is simply to loosen the rules of a formal programming language,
borrowing the syntax-semantic structures of the language, intermixed with less formal
constucts.
• There are many such pseudocode variants, because there are many programming languages in
existence. Two particularly popular choices are loose versions of the languages Algol and
Pascal, largely because these were widely used in textbooks and academic papers for decades.
• Features of Pseudocode
1. Easy to read and understand.
2. Uses simple keywords like if, else, while.
3. Language independent.
4. Uses indentation for clarity.
5. Provides a consistent and concise representation.

Basic Structures in Pseudocode:

1. Assignment Statement: Used to store computed values/ save the result so we can refer to it
later.
Syntax: name = expression
 174 Chapter 5 Algorithms
• Example: RemainingFunds = CheckingBalance + SavingsBalance.

2. Selection (Decision Making): Used to choose between two alternatives

• Syntax: if (condition):
activity
else:
activity
• Example: if (marks >= 40):
print("Pass")
else:
print("Fail")

3. Repetition (Loop): Used to repeat a set of steps

• Syntax: while (condition):
activity
• Example: while (tickets > 0):
sell ticket

4. Functions: Used to define reusable blocks of code

• Syntax: def FunctionName():
statements
• Example of Pseudocode: Program to print “Hello” three times:
def Greetings():
Count = 3
while (Count > 0):
print("Hello")
Count = Count - 1
Explanation:
• Initialize Count = 3
• Print "Hello"
• Decrease count
• Repeat until count becomes 0
•
Advantages of Pseudocode
1. Improves understanding of algorithm
2. Easy to convert into programming language
3. Helps in detecting errors early
4. No strict syntax rules
 5.3 Algorithm Discovery 175

4. Algorithm Discovery
Program development involves two main steps:
i) Discovering the algorithm
ii) Representing it as a program
Among these, algorithm discovery is more difficult it requires problem-solving skills After all,
discovering an algorithm to solve a problem requires finding a method of solving that problem. Thus,
to understand how algorithms are discovered is to understand the problem-solving process.

The Art of Problem Solving

• The techniques of problem solving and the need to learn more about them are not unique to
computer science but rather are topics pertinent to almost any field.
• The close association between the process of algorithm discovery and that of general problem
solving has caused computer scientists to join with those of other disciplines in the search for better
problem-solving techniques.
• As evidence of the elusive, artistic nature of problem solving, the following loosely defined
problem-solving phases presented by the mathematician G. Polya in 1945 remain the basic
principles on which many attempts to teach problem- solving skills are based today.
• Discovering an algorithm means finding a method to solve a problem.
• It is not a fixed process, It is more like an art than a science.
• Some problems may not even have algorithmic solutions.

Polya’s Problem-Solving Phases:

Phase 1. Understand the problem.
Phase 2. Devise a plan for solving the problem.
Phase 3. Carry out the plan.
Phase 4. Evaluate the solution for accuracy and for its potential as a tool
for solving other problems.
Translated into the context of program development, these phases become
Phase 1. Understand the problem.
Phase 2. Get an idea of how an algorithmic function might solve the problem.
Phase 3. Formulate the algorithm and represent it as a program.
Phase 4. Evaluate the program for accuracy and for its potential as a tool
for solving other problems.
• Having presented Polya’s list, we should emphasize that these phases are not steps to be followed when
trying to solve a problem but rather phases that will be completed sometime during the solution process.
The key word here is followed.

As an example, consider the following problem:

Person A is charged with the task of determining the ages of person B’s three children. B tells A
 176 Chapter 5 Algorithms
that the product of the children’s ages is 36. After considering this clue, A replies that another clue
is required, so B tells A the sum of the children’s ages. Again, A replies that another clue is
needed, so B tells A that the oldest child plays the piano. After hearing this clue, A tells B the
ages of the three children. How old are the three children?

• At first glance the last clue seems to be totally unrelated to the problem, yet it is apparently this
clue that allows A to finally determine the ages of the children. How can this be? Let us proceed
by formulating a plan of attack and following this plan, even though we still have many
questions about the problem. Our plan will be to trace the steps described by the problem
statement while keeping track of the information available to person A as the story progresses.
• The first clue given A is that the product of the children’s ages is 36. This means that the triple
representing the three ages is one of those listed in Figure 2(a). The next clue is the sum of
the desired triple. We are not told what this sum is, but we are told that this information is not
enough for A to isolate the correct triple; therefore the desired triple must be one whose sum
appears at least twice in the table of Figure 2(b).
• But the only triples appearing in Figure 2(b) with identical sums are (1,6,6) and (2,2,9), both of
which produce the sum 13. This is the information available to A at the time the last clue is
given. It is at this point that we finally understand the significance of the last clue. It has
nothing to do with playing the piano; rather it is the fact that there is an oldest child. This rules
out the triple (1,6,6) and thus allows us to conclude that the children’s ages are 2, 2, and 9.

Figure 2 Analyzing the possibilities

(1,1,36) (1,6,6) 1 + 1 + 36 = 38 1 + 6 + 6 = 13
(1,2,18) (2,2,9) 1 + 2 + 18 = 21 2 + 2 + 9 = 13
(1,3,12) (2,3,6) 1 + 3 + 12 = 16 2 + 3 + 6 = 11
(1,4,9) (3,3,4) 1 + 4 + 9 = 14 3 + 3 + 4 = 10

Getting a Foot in the Door

• We have been discussing problem solving from a somewhat philosophical point
of view while avoiding a direct confrontation with the question of how we
should go about trying to solve a problem.
• There are, of course, numerous problem-solving approaches, each of which can
be successful in certain settings. We will identify some of them shortly.
• For now, we note that there seems to be a common thread running through
these techniques, which simply stated is “get your foot in the door.” As an
example, let us consider the following simple problem:
Before A, B, C, and D ran a race they made the following predictions:
A predicted that B would win.
B predicted that D would be last.
C predicted that A would be third.
 5.3 Algorithm Discovery 177
D predicted that A’s prediction would be correct.
Only one of these predictions was true, and this was the prediction
made by the winner. In what order did A, B, C, and D finish the race?
• The predictions of A and D were equivalent and only one prediction was true,
the predictions of both A and D must be false.
• Thus neither A nor D were winners.
• At this point we have our foot in the door, and obtaining the complete solution
to our problem is merely a matter of extending our knowledge from here.
• If A’s prediction was false, then B did not win either. The only remaining
choice for the winner is C. Thus, C won the race, and C’s prediction was true.
• Consequently, we know that A came in third.
• That means that the finishing order was either CBAD or CDAB. But the
former is ruled out because B’s prediction must be false. Therefore the
finishing order was CDAB.
178 Chapter 5 Algorithms