II PUC COMPUTER SCIENCE

II PUC
COMPUTER SCIENCE
Prepared by:
SANGAMESH. G. B
LECTURER IN COMPUTER SCIENCE
DEEKSHA @ NAVKIS RESIDENTIAL PU COLLEGE,
BANGALORE NORTH - 562162

PREPARED BY: SANGAMESH G B 1

II PUC COMPUTER SCIENCE

PREPARED BY: SANGAMESH G B 2

II PUC COMPUTER SCIENCE

CONTENTS

CHAPTER-01: EXCEPTION HANDLING IN PYTHON

CHAPTER-02: FILE HANDLING IN PYTHON

CHAPTER-03: STACK

CHAPTER-04: QUEUE

CHAPTER-05: SORTING

CHAPTER-06: SEARCHING

CHAPTER-07: UNDERSTANDING DATA

CHAPTER-08: DATABASE CONCEPTS

CHAPTER-09: STRUCTURED QUERY LANGUAGE

CHAPTER-10: COMPUTER NETWORKS

CHAPTER-11: DATA COMMUNICATION

CHAPTER-12: SECURITY ASPECTS

CHAPTER-13: PROJECT BASED LEARNING

PREPARED BY: SANGAMESH G B 3

II PUC COMPUTER SCIENCE

PREPARED BY: SANGAMESH G B 4

 II PUC COMPUTER SCIENCE

Government of Karnataka
Department of School Education (Pre-University)
II PUC Computer Science
Blue Print
Part Part Part Part Part
Chapter Description Hours A B C D E Total
VSA-01 VSA-01 SA-02 SA-03 E-05 E-05
[MCQ] [FIB] Marks Marks Marks Marks Marks
[LOTS] [HOTS]

Chapter-01 Exception Handling 6 1 1 1 05

Chapter-02 File Handling 6 1 1 1 05

Chapter-03 Stack 9 1 1 1 08

Chapter-04 Queue 9 1 1 1 08

Chapter-05 Sorting 12 2 1 1 10

Chapter-06 Searching 12 1 1 1 10

Chapter-07 Understanding Data 6 1 05

Chapter-08 Database Concepts 13 1 1 1 1 1 12

Chapter-09 Structured Query Language 17 3 2 1 1 1 15

Chapter-10 Computer Networks 13 2 1 1 1 12

Chapter-11 Data Communication 10 2 1 1 09

Chapter-12 Security Aspects 07 1 1 06

Chapter-13 Project Based Learning -

Marks Allotted 120 15 05 07 07 07 03 105

Maximum Marks to be obtained 15 05 04 04 04 02 70

PREPARED BY: SANGAMESH G B 5

II PUC COMPUTER SCIENCE

PREPARED BY: SANGAMESH G B 6

II PUC COMPUTER SCIENCE

UNIT - A
PYTHON PROGRAMMING

Computational Thinking and Programming

This unit includes:

Chapter-01: Exception Handling in Python

Chapter-02: File Handling in Python

Chapter-03: Stacks

Chapter-04: Queues

Chapter-05: Sorting

Chapter-06: Searching

PREPARED BY: SANGAMESH G B 7

II PUC COMPUTER SCIENCE

PREPARED BY: SANGAMESH G B 8

 II PUC COMPUTER SCIENCE

CHAPTER – 01
EXCEPTION HANDLING IN PYTHON

In this chapter:
Introduction
Syntax Errors
Exceptions
Built-in Exceptions
Raising Exceptions
Finally Clause
1. Introduction:
Sometimes while executing python program, the program does not execute at all or the program
executes but generates unexpected output or behaves abnormally.
These occur when there are syntax errors, runtime errors or logical errors in the code.
In python, exceptions are errors that get triggered automatically. However, exceptions can be
forcefully triggered and handled through program code.

2. Syntax Errors:
 Syntax errors are detected when we have not followed the rules or syntax of the particular
programming language while writing the program.
 Syntax errors occurs before execution of program or parsing stage
 Syntax errors are also known as parsing errors.

Common Syntax errors that occurs in Python:

 Missing Punctuation: missing of Semicolons, Colons, Commas or brackets
 Missing parenthesis: Incorrect use of parenthesis
 Misspelling: Incorrectly typing keywords, variable names or function
 Missing Keywords
 Improper Indentation
 Unmatched quotes

 Programming Example:

Example-01:

def test ( ) :
marks=20
if marks>10:
print “GOOD SCORE”

SyntaxError X

X Missing parenthesis in call to ‘print’, Did you mean print ‘GOOD SCORE’

OK

PREPARED BY: SANGAMESH G B 9

II PUC COMPUTER SCIENCE

 On encountering a syntax error, Python stops execution until the error is corrected.
(The interpreter does not execute the program unless we rectify the errors, save and rerun the
program)
 When syntax error is encountered, Python displays name of the error and a small description
about the error.

 Handling Syntax Errors:

a. In Shell mode:
Python displays the name of the error and a small description about the error
Example:

b. In Script mode:
A dialog box specifying the name of the error and a small description about the error
Example:

PREPARED BY: SANGAMESH G B 10

 II PUC COMPUTER SCIENCE

3. Exception:
An exception is a python object that represents an error that occurs during the execution of
program even if program is syntactically correct.
OR
In python, exceptions are errors that get triggered automatically. However, exceptions can be
forcefully triggered and handled through program code.
OR
Exceptions are unexpected events or errors that occurs while a program is running

 When exception occurs, it is said to be raised and may disrupt the normal flow of program
execution.
 The run time error is called an exception

 Some common exceptions are:

 Number is divided by zero
 Trying to open file that does not exist.
 If incorrect indentation is given
 Accessing an invalid memory location
 Invalid input
 Hard disk crash

 This type of errors might disrupt the normal execution of the program and are called exceptions.
 An exception needs to be handled by the exception handler or programmer so that the program
does not terminate abnormally.

 Example:
result = 10 / 0
Exception: ZeroDivisionError

OR

Example:

a=10
b=int(input(“Enter the value for b=”))
print(a/b)

Enter the value for b=0

Traceback (most recent call last):
File "C:/Users/Admin/[Link]", line 3, in <module>
print(a/b)
ZeroDivisionError: division by zero

 A traceback is a structured block of text displayed when an exception is raised. It provides

information about the sequence of function calls leading to the exception, helping in debugging
the program

PREPARED BY: SANGAMESH G B 11

 II PUC COMPUTER SCIENCE

4. Types of exceptions:
a. Built-in exceptions
b. User defined exceptions

a. Built-in Exceptions:
 These are commonly occurring exceptions, which are usually defined in the
compiler/interpreter.
 There are several built-in exceptions in python that are raised when error occurs.
 These built-in exceptions will display the exact reasons of errors along with the raised exception
name.
 The programmer then has to take appropriate action to handle it.

Built-in Exceptions:
Built-in exceptions are pre-defined errors in Python to handle common runtime errors.
[Link] Built-in Exceptions Explanation
01 SyntaxError It is raised when there is error in syntax of program (Python code)
02 ValueError It is raised when there is wrong value for the data type
OR
It is raised when a built-in operation receives an argument that the
right data type but mismatched or inappropriate values.
03 IOError It is raised when the file specified in a program statement cannot be
opened
04 KeyboardInterrupt It is raised when user accidentally click the Delete or Escape key
05 ImportError It is raised when the requested module definition is not opened or
found
06 EOFError It is raised when the end of file condition is reached without reading
any data by input().
07 ZeroDivisionError It is raised when denominator in a division operation is zero
08 IndexError It is raised when the index or subscript in a sequence is out of range
09 NameError It is raised when local or global variable name is not defined
10 IndentationError It is raised due to incorrect indentation in the program code
11 TypeError It is raised when an operator is supplied with a value of incorrect
data type
12 OverFlowError It is raised when the result of a calculation exceeds the maximum
limit for numeric data type.

b. User defined exceptions

A user-defined exceptions in python is a custom error created by the programmer to handle
specific situations in a program

5. Raising Exceptions:
 When error is detected in a program, the python interpreter raises (throws) an exception
 The exception handlers are designed to execute when a specific exception is raised
 The programmers can also forcefully raise exceptions in a program using raise and assert
statement

The raising exceptions are:

a. The raise statement
b. The assert statement

PREPARED BY: SANGAMESH G B 12

II PUC COMPUTER SCIENCE

a. The raise statement:

The raise statement can be used to throw or raise an exception manually.
- Using the Keyword- raise

Syntax:
raise exception-name[(optional argument)]

Example:
exception(“OOPs! Error Occurred”)

- The argument is optional and generally a string that is displayed when an exception is
raised.
- When an exception is raised, the message:
“OOPS : An exception has occurred” is displayed along with a brief description of error
- The error detected may be a built-in exception or may be a user-defined exception.
- This displays the message and a stack traceback showing the function calls leading to the
exception

- Programming example

Example-01:
a=20
b=int(input("Enter the b value: "))
if b==0:
raise ZeroDivisionError("Cannot divide by zero")
else:
print(a/b)

Output:
Enter the b value: 0
Traceback (most recent call last):
File "C:\Users\Admin\[Link]", line 4, in <module>
raise ZeroDivisionError("Cannot divide by zero")
ZeroDivisionError: Cannot divide by zero

Example-02:
length=int(input("Enter the number="))
if length>10:
raise IndexError("Index length is only 10")
print("Length is larger than 10")
else:
print("No error, Length is less than 10")

Output:
Enter the number=15
Traceback (most recent call last):
File "C:\Users\Admin\[Link]", line 3, in <module>
raise IndexError("Index length is only 10")
IndexError: Index length is only 10

PREPARED BY: SANGAMESH G B 13

II PUC COMPUTER SCIENCE

b. Assert Statement:
 The assert statement is used to test an expression or condition in the program code.
- Using the keyword assert

 If the result after testing comes false, then the exception (Assertion Error) is raised.
 This assert statement is generally used in the beginning of the function or after the function
call to check for valid input

Syntax:
assert Expression[, arguments]

- On encountering an assert statement, python evaluates the expression given immediately

after assert keyword
- If this expression is false, an assertion error is raised which can be handled like any other
exceptions.
- It is commonly used for debugging purposes to check conditions in code

Example-01:

num1=int(input("Enter the numerator:"))

num2=int(input("Enter the denominator:"))
assert num2!=0 , ("Denominator cannot be zero")
quotient=num1/num2
print("The quotient is", quotient)

Output:
Enter the numerator:20
Enter the denominator:0
Traceback (most recent call last):
File "C:/Users/Admin/[Link]", line 3, in <module>
assert num2!=0 ,("Denominator cannot be zero")
AssertionError: Denominator cannot be zero

Example-02:
print("Use of assert statement")
def negativecheck(number):
assert(number>=0), "OOPS... Negative Number"
print("The number is",number)
print(negativecheck(100))
print(negativecheck(-350))

Output:
Use of assert statement
The number is 100
None
AssertionError: OOPS... Negative Number

PREPARED BY: SANGAMESH G B 14

 II PUC COMPUTER SCIENCE

6. Exception Handling:
It is the process of writing additional code in a program to give proper messages or instructions to
the user on encountering an exception.

 Each and every exception has to be handled by the programmer to avoid the program crashing
abruptly.
 In python, exceptions are handled or implemented by using try and except, else and finally
blocks

 Needs of exception handling:

a. Essential to prevent program crashes by capturing and managing runtime errors.
b. Exceptions handling code for every distinct code can be created.
c. Separates main program logic from error detection and correction code.
d. The compiler/interpreter tracks the exact error location.
e. Exception code can be done for both user defined and built-in exceptions.

OR

a. Prevents program crashes or causes.

b. Improve users experience
c. Helps in easier debugging
d. Ensures proper resource management
e. Makes program more robust
f. Improved program reliability
g. Simplified error handling
h. Cleaner code
i. To capture and handle runtime errors gracefully.
j. To provide meaningful feedback to the user.
k. To ensure proper clean-up of resources

Q. What are the main purposes / primary purpose of exception handling?

The main purposes / primary purpose of exception handling are:
- To prevent program crashes
- To manage runtime errors gracefully

PREPARED BY: SANGAMESH G B 15

 II PUC COMPUTER SCIENCE

7. Process of Handling Exceptions:

 When an error occurs, Python interpreter creates an object called the exception object.

 This object contains information about the error like its type, file name and position in the
program where the error has occurred.

 The object is handed over to the runtime system to find an appropriate code to handle this
particular exception.

 This process of creating an exception object and handing it over to the runtime system is called
throwing an exception.

 When an exception occurs while executing a particular program statement, the control jumps to
an exception handler, abandoning the execution of the remaining program statements

 The runtime system searches the entire program for a block of code, called the exception
handler that can handle the raised exception.

 The runtime system first searches the method in which the error occurred and the exception was
raised. If not found, it searches the method from which this method was called.

 This hierarchical search in reverse order continues until the exception handler is found.
 This entire list of methods is known as the call stack.

 When a suitable handler is found in the call stack, it is executed by the runtime process.

 The process of executing a suitable handler is known as catching the exception.

 If the runtime system cannot find an appropriate exception after searching all the methods in the
call stack, then the program execution stops.

OR

PREPARED BY: SANGAMESH G B 16

II PUC COMPUTER SCIENCE

Process of Handling Exceptions

When an error occurs, Python creates an exception object containing details like the error type, file
name, and error position. This object is passed to the run time system to find the appropriate
exception handler.

 Key Steps in Exception handling process:

a. Throwing an exception
b. Searching for exception handler
c. Catching the exception
d. Handling Exceptions

a. Throwing an exception:
The process of creating an exception object and handling it over to the run time system is called
throwing an exception. (When an error occurs, Python creates an exception object and transfers
control to the runtime system
 Each time an error is detected in a program, the python interpreter raises (throws) an exception.
 Exception handlers are designed to execute when a specific exception is raised
 Programmers can also forcefully raise exceptions in a program using raise and assert statements
 Once an exception is raised, no further statement in the block of code is executed.

Syntax:
raise nameerror
assert condition, “Message”

b. Searching for exception handler:

 The runtime searches the program for a suitable exception handler
 It searches first in the current method, then moves to the caller method in reverse order through
the call stack
 The runtime searches for an appropriate exception handler in the call stack.

c. Catching the exception:

 An exception is said to be caught when a code that is designed to handle a particular exception
is executed.
 Catching an exception means handling of an exception by exception handler using try and
except blocks.
 An exception, if any are caught in the try block and handled in except block.

d. Handling Exceptions: The matched handler executes specific code to resolve the error.

 Programming Example:
try:
num = int(input("Enter a number: "))
result = 10 / num
except ZeroDivisionError:
print("Division by zero is not allowed.")
except ValueError:
print("Invalid input! Please enter an integer.")

PREPARED BY: SANGAMESH G B 17

II PUC COMPUTER SCIENCE

Figure: Steps of handling exceptions (Flowchart)

Figure: Steps of handling exception (Flowchart of exception handling)

PREPARED BY: SANGAMESH G B 18

 II PUC COMPUTER SCIENCE

8. Catching the exception using the try and except blocks:

 The try… and except blocks are used to catch and handling exceptions in python program,
 Code that might raise an exception is placed inside the try block, and the handling of the exception is
done in the except block.

How it works:
In the execution of the program, if an exception is encountered (raised) then the try block
execution is stopped and the control is shifted to except block, where we can handle the error or
take appropriate actions.

a. try: The try block contains the code that might raise an exception

[Every try block is followed by except block]

b. except: The except block contains the code to handle the exception.

Syntax:
try:
# code that might raise an exception
except [exception_name]:
# code to handle the exception

Example:
print("catching exceptions using try and except blocks")
try:
n=50
d=int(input("Enter the denominator="))
quotient=(n/d)
print(quotient)
print("Division is performed successfully")
except ZeroDivisionError:
print("Denominator as Zero...not allowed")
print("Outside try…except block")

OR
Q. Explain catching exception use of try… and except block with suitable example
Ans:
A try...except block is used to catch and handle exceptions in Python.
- try block: Contains code that might raise an exception.
- except block: Contains code to handle specific exceptions.

Syntax:
try:
# code that might raise an exception
except [exception_name]:
# code to handle the exception

Example:
try:
result = 5 / 0
except ZeroDivisionError:
print("Cannot divide by zero!")

PREPARED BY: SANGAMESH G B 19

 II PUC COMPUTER SCIENCE

9. Use of multiple except blocks:

A single try block may handle different exceptions types separately by using multiple except block
and designed to handle specific error.
OR
Multiple except blocks allows handling different types of exceptions in a single try block. Each
block can be tailored to handle a specific exception raised by the try block.
[Multiple except blocks handles different exception types separately.]

 In the code, two types of exceptions – ZeroDivisonError and ValueError are handled using two
excepts blocks for a single try block
 When an exception is raised, a search for the matching except block is made till it is handled.
 If no match is found, then the program terminates

Example-01:
print("use of multiple except blocks")
try:
n=50
d=int(input("Enter the denominator="))
quotient=(n/d)
print(quotient)
print("Division is performed successfully")
except ZeroDivisionError:
print("Denominator as Zero...not allowed")
except ValueError:
print("only Integer should be entered")

Output-01:
use of multiple except blocks
Enter the denominator=12
4.166666666666667
Division is performed successfully

10. Use of except without specifying an exception:

 If an exception is raised for which no handler is created by the programmer, then such an
exception can be handled by adding an except clause without specifying any exception.
 This except clause should be added as the last clause of try…except block.

Example-01:
print("use of except without specfiying any exception")
try:
n=50
d=int(input("Enter the denominator="))
quotient=(n/d)
print(quotient)
print("Division is performed successfully")
except ZeroDivisionError:
print("Denominator as Zero...not allowed")
except:
print("OOPS... Some exception raised")

PREPARED BY: SANGAMESH G B 20

 II PUC COMPUTER SCIENCE

11. Catching All Exceptions: Using a generic except clause.

A generic except block is used to catch any exception that is not explicitly handled by the previous
except blocks. It is a fall-back mechanism for unanticipated errors
Use Case:
- To handle unexpected exceptions.
-It should be placed after all specific except blocks
Example:
try:
num = int(input("Enter a number: "))
result = 10 / num
except Exception as e:
print(f"An error occurred: {e}")

12. try…except…else clause

In python, we can put an optional else clause along with the try… except clause.
a. try: The try block contains code that might raise an exception.
b. except: The except block contains code to handle the exception
c. else: The else block executes only if no exception occurs in the try block.
Syntax:
try:
# code that might raise an exception
except [exception_name]:
# code to handle exception
else:
# if there is no exception then this block get executed

Example:

print("handling exception using try...except.... else block")

try:
n=50
d=int(input("Enter the denominator="))
quotient=(n/d)
print("Division is performed successfully")
except ZeroDivisionError:
print("Denominator as Zero...not allowed")
except valueError:
print("Only Integer should be entered")
else:
print("The result of division operation is",quotient)

Output:
handling exception using try...except.... else block
Enter the denominator=4
Division is performed successfully
The result of division operation is 12.5

PREPARED BY: SANGAMESH G B 21

 II PUC COMPUTER SCIENCE

13. Finally clause:

 The code or statements inside the finally block are always executed regardless of whether of an
exception occurred in the try block or not.
 It is typically used for clean-up actions, like closing files or releasing resources.
 The finally clause is an optional part of the try statement in Python.
 Python provides a keyword – finally

Syntax:
try:
# code that may raise an exception
except [exception_name]:
# code to handle exception]
else:
# if there is no exception then this block get executed
finally:
# code will always be executed

Example-01:
print("handling exception using try...except.... else...finally")
try:
n=50
d=int(input("Enter the denominator="))
quotient=(n/d)
print("Division is performed successfully")
except ZeroDivisionError:
print("Denominator as Zero...not allowed")
except valueError:
print("Only Integer should be entered")
else:
print("The result of division operation is",quotient)
finally:
print("Over and Out... ")

Output-01:
handling exception using try...except.... else...finally
Enter the denominator=4
Division is performed successfully
The result of division operation is 12.5
Over and Out...

PREPARED BY: SANGAMESH G B 22

 II PUC COMPUTER SCIENCE

14. Recovering and continuing with finally clause:

If an error has been detected in the try block and the exception has been thrown, the appropriate
except block will be executed to handle the error. But if the exception is not handled by any of the
except clauses, then it is re-raised after the execution of the finally block.

Example-01:
print("practicing for try block")
try:
n=50
d=int(input("Enter the denominator="))
quotient=(n/d)
print("Division is performed successfully")
except ZeroDivisionError:
print("Denominator as Zero...not allowed")
else:
print("The result of division operation is",quotient)
finally:
print("Over and Out... ")

Output-01:

handling exception using try...except.... else...finally

Enter the denominator=4
Division is performed successfully
The result of division operation is 12.5
Over and out...

PREPARED BY: SANGAMESH G B 23

 II PUC COMPUTER SCIENCE

Review Questions:

1. “Every syntax error is an exception but every exception cannot be a syntax error.” Justify the
statement.
Syntax is a specific type of exception that is detected when we have not followed the rules or
syntax of the particular programming language while writing the program. On the other hand,
An exception is a python object that represents an error that occurs during the execution of
program even if program is syntactically correct. This includes not only syntax error but also
runtime errors or logical errors.
Therefore, every syntax error is an exception but every exception cannot be a syntax error.”
OR
Syntax errors are mistakes in the code’s structure or grammar, such as missing colons or incorrect
indentation, which prevent the code from being parsed. They are caught before the program runs
and must be fixed for the program to execute.
Exceptions, on the other hand, occur during the execution of syntactically correct code when
something unexpected happens, like trying to divide by zero. Thus, while all syntax errors are
exceptions (as they represent issues to be corrected), not all exceptions are syntax errors; some are
runtime issues that arise despite correct syntax.

2. Differentiate between syntax errors and exceptions with examples.

The Differentiate between Syntax error and Exceptions
Feature Syntax Errors Exceptions
Definition Errors in the structure of the Errors occurring during program execution.
code
Detection Detected during compilation Detected during runtime.
(parsing phase).
Fixability Must be fixed before Can be handled using exception handling.
running the code
Examples Missing colons, incorrect Division by zero, accessing undefined files.
indentation
Example print("Hello" (missing )) 5 / 0 raises ZeroDivisionError
code

OR
Syntax Errors:
• Occur when the code violates Python’s grammatical rules.
• Detected before the program runs (parsing stage).
• Examples: Missing colons, improper indentation.
Exceptions:
• Occur during runtime when the code encounters an error.
• Can be handled using exception handling mechanisms.
• Examples: Division by zero, file not found

3. What is Syntax error?

An error that occurs when the rules or syntax of the programming language are not followed
Such as missing colons, missing, parenthesis or incorrect indentation etc.
4. What is Exception in Python?
An exception is a python object that represents an error that occurs during the execution of
program even if program is syntactically correct.
Some common exceptions are Number is divided by zero, Trying to open file that does not exist.

PREPARED BY: SANGAMESH G B 24

 II PUC COMPUTER SCIENCE

5. When are the following built-in exceptions raised? Give examples to support your answer
a. ImportError
b. IOError
c. NameError
d. ZeroDivisionError

a. ImportError:
It is raised when the requested module definition is not opened.
Example:
import module
Output:
ModuleNotFoundError: No module named ‘module’
b. IOError:
It is raised when the file specified in a program statement cannot be opened
Example:
File = open (“[Link]”, “r”)
Output:
FileNotFoundError: [Error 2] No such file or directory: “[Link]’
c. NameError:
It is raised when local or global variable is not defined
Example:
Print(var+40)
Output:
NameError: name ‘var’ is not defined.
d. ZeroDivisionError:
It is raised when denominator in a division operation is zero
Example:
Print(50/0)
Output:
ZeroDivisionError: division by zero

6. Describe the use of built-in exceptions in Python with examples.

OR
What are built-in exceptions? List any three with examples.

Built-in exceptions are pre-defined errors in Python to handle common runtime errors.
[Built-in exceptions are pre-defined errors in Python’s standard library that handle common
runtime issues.]
Exception When it Occurs Example
ZeroDivisionError Raised when Dividing a number by 10 / 0
zero
ValueError Raised when there is wrong value int("abc")
for the data type
NameError Raised when referencing a variable print(x) (where x is undefined).
that is not defined
IndexError Raised when accessing an invalid lst = [1,2];
index in a sequence print(lst[5])
TypeError Raised when an operation is 5 + "hello"
performed on incompatible types Adding a string and an integer
(Operation is applied to an
incorrect data type)

PREPARED BY: SANGAMESH G B 25

 II PUC COMPUTER SCIENCE

7. Explain OverflowError with an example.

Answer:
OverflowError is raised when a numerical operation exceeds the maximum representable limit.
Example:
try:
result = 10 ** 1000
except OverflowError:
print("Result is too large.")

8. Define the following:

a. Exception Handling
b. Throwing an exception
c. Catching an exception

a. Exception Handling
It is the process of writing additional code in a program to give proper messages or
instructions to the user on encountering an exception
b. Throwing an exception
The process of creating an exception object and handling it over to the run time system is
called throwing an exception. (The process where Python creates an exception object when an
error occurs and passes it to the runtime system)
c. Catching an exception
An exception is said to be caught when a code that is designed to handle a particular exception
is executed (Catching an exception means raising an exception)
OR
The process of executing the appropriate exception handler to deal with the raised exception

9. Define the following:

a. Exception handler:
b. Try block
c. Except block
d. Else block
e. Finally block
f. Raise statement
g. Assert statement

a. Exception handler: Exception handlers are the codes that are designed to execute when a
specific execution is raised.
[A block of code written to handle errors in a program and prevent it from crashing]
b. Try block: The try block contains code that might raise an exception
c. Except block: The except block contains code to handle the exception
(An exception is caught is try block and handles in except block)
d. Else block: The else block executes only if no exception occurs in the try block.
e. Finally block: The finally block are always executed regardless of whether an exception
occurred in try block or not
f. Multiple except: Multiple except blocks handles different exception types separately
g. Raise statement: The raise statement can be used to throw or raise an exception manually.
(Using the Keyword- raise).
h. Assert statement: The assert statement is used to test an expression in the program code.
(Using the keyword assert)

PREPARED BY: SANGAMESH G B 26

 II PUC COMPUTER SCIENCE

10. What are the needs of exception handling?

a. To handle runtime errors and prevent abnormal termination of the program
b. To separate error-handling code from the main logic of the program
c. To allow specific handling for different types of exception using separate exception handlers
d. To help the interpreter locate and manage errors efficiently

11. Consider the code given below and fill in the blanks.

Example-01:

print("Learning exceptions")
try:
num1=int(input(“Enter the first number=”))
num2=int(input(“Enter the second number=”))
quotient=(num1/num2)
print("Both the number entered were correct”)
except ____________________ : # to enter only integers
print("Please enter only numbers")
except _____________________: # Denominator should not be zero
print(“Number 2 should not be zero)
else:
print("Great…you are a good programmer”)
___________________________: #To be executed at the end
print("JOB OVER…GO GET SOME REST")

Output:
print("Learning exceptions")
try:
num1=int(input(“Enter the first number=”))
num2=int(input(“Enter the second number=”))
quotient=(num1/num2)
print("Both the number entered were correct”)
except ValueError: # to enter only integers
print("Please enter only numbers")
except ZeroDivisionError: # Denominator should not be zero
print(“Number 2 should not be zero)
else:
print("Great…you are a good programmer”)
finally: #To be executed at the end
print("JOB OVER…GO GET SOME REST")

PREPARED BY: SANGAMESH G B 27

 II PUC COMPUTER SCIENCE

12. What is the use of finally clause ? Use finally clause in the problem given in question-7

Example-01:

print("Learning exceptions")
try:
num1=int(input(“Enter the first number=”))
num2=int(input(“Enter the second number=”))
quotient=(num1/num2)
print("Both the number entered were correct”)
except ____________________ : # to enter only integers
print("Please enter only numbers")
except _____________________: # Denominator should not be zero
print(“Number 2 should not be zero)
else:
print("Great…you are a good programmer”)
___________________________: #To be executed at the end
print("JOB OVER…GO GET SOME REST")

Output-01:

Learning exceptions
try:
Enter the first number=12
Enter the second number=4
3.0
Both the number entered were correct
JOB OVER…GO GET SOME REST

Output-02:

Learning exceptions
try:
Enter the first number=var
Please enter only numbers
JOB OVER…GO GET SOME REST

Output-03:

Learning exceptions
try:
Enter the first number=33
Enter the second number=0
Number 2 should not be zero
JOB OVER…GO GET SOME REST

PREPARED BY: SANGAMESH G B 28

 II PUC COMPUTER SCIENCE

13. Write a code using the math module where you use the wrong number of arguments for a method
and handle the ValueError exception.
Answer:
import math
try:
result = [Link](16, 2) # Incorrect number of arguments
except TypeError:
print("Incorrect number of arguments provided to sqrt() method")

14. What is the traceback in Python, and what does it include?

A traceback is a detailed error message displayed when an exception occurs. It includes:
o The sequence of function calls leading to the error.
o The exception type raised.
o The line of code where the exception occurred.

15. How are exceptions raised and caught in Python? Explain the call stack.
Answer:
- Raising Exceptions: Python raises exceptions when runtime errors occur (e.g., dividing by zero).
Programmers can raise exceptions manually using the raise statement.

- Catching Exceptions: Exceptions are handled using try...except blocks. Python matches the
exception type with available handlers.

Call Stack:
The call stack is a sequence of function calls made during execution. If an exception is raised,
Python searches the call stack for a matching handler. If no handler is found, the program
terminates with a traceback.

16. Explain the else clause in Python exception handling with an example.
Answer:
The else clause executes only if no exception occurs in the try block.
OR
If there is no exceptions raised from the try block then code inside the try block will be executed
and also else block will be executed:

Example:
try:
num = int(input("Enter a number: "))
result = 10 / num
except ZeroDivisionError:
print("Cannot divide by zero!")
else:
print(f"Division successful: {result}")

17. What is the role of the call stack in exception handling?

Answer:
The call stack is a sequence of function calls made during program execution. When an exception
occurs:
- Python searches the call stack for an appropriate exception handler.
- If no handler is found, the program terminates, displaying a traceback.

PREPARED BY: SANGAMESH G B 29

 II PUC COMPUTER SCIENCE

 Multiple Choice Questions (MCQs)

1. What type of errors are exceptions in python?

a) Logical error b) Syntax error c) Runtime errors d) Parsing errors
2. What happens when a syntax error occurs in Python?
a) Program continues with incorrect output b) Program halts with a description of the error
c) Program fixes the error automatically d) Program warns but does not stop
3. What are syntax errors also known as?
a) Runtime errors b) Logical errors c) Parsing errors d) None of the above
4. Which Python mode provides immediate feedback on syntax errors?
a) Script mode b) Shell mode c) IDE mode d) Debug mode
5. When does a ZeroDivisionError occur?
a) Dividing by a negative number b) Using a zero numerator
c) Dividing by zero d) Using zero in mathematical expressions
6. What does Python do when an exception is raised during execution?
a) Continues execution b) Skips the error
c) Terminates the program abruptly d) Jumps to exception handling code if present
7. Which exception is raised when a variable is not defined?
a) NameError b) ValueError c) SyntaxError d) TypeError
8. What does the IOError exception indicate?
a) An undefined variable b) A file that cannot be opened
c) A division by zero d) An incorrect argument type
9. Which exception is raised for incorrect indentation?
a) ValueError b) TypeError c) IndentationError d) SyntaxError
10. Which keyword is used to manually raise an exception?
a) assert b) raise c) throw d) except
11. What happens after an exception is raised using the raise statement?
a) The remaining statements in the block are executed
b) The current block stops execution
c) Execution continues in the same block
d) None of the above
12. What exception does the assert statement raise if the condition is False?
a) AssertionError b) ValueError c) SyntaxError d) RuntimeError
13. What is the main purpose of exception handling?
a) To debug syntax errors b) To prevent program crashes
c) To increase execution speed d) To optimize performance
14. Which block is used to catch exceptions in Python?
a) try b) except c) else d) finally
15. Which block is always executed, irrespective of whether an exception occurred?
a) try b) except c) else d) finally
16. What happens if multiple except blocks are present for a single try block?
a) All are executed b) The first matching block is executed
c) None are executed d) Only the last block is executed
17. When is the else clause executed in a try…except block?
a) If no exception occurs b) If an exception occurs
c) Always executed d) Never executed
18. Which block comes immediately after the try block?
a) except b) else c) finally d) None
19. What is the primary use of the finally block?
a) To catch specific exceptions b) To execute cleanup code
c) To handle syntax errors d) To ensure program optimization

PREPARED BY: SANGAMESH G B 30

 II PUC COMPUTER SCIENCE

20. Which statement is true for the finally block?

a) It executes only if an exception occurs b) It executes only if no exception occurs
c) It executes regardless of exceptions d) It does not execute under any condition
21. Which exception is handled in the following code?
try:
num = int(input("Enter a number: "))
except ValueError:
print("Invalid input!")
a) ZeroDivisionError b) SyntaxError c) ValueError d) TypeError
22. What happens if no exception is raised in the try block?
a) The except block executes b) The else block executes
c) Both except and else blocks execute d) The program terminates
23. What will happen if an exception not matched by any except block occurs?
a) The program continues b) The program terminates
c) The last except block is executed d) None of the above
24. In a try…except block with multiple except clauses, which block is executed first?
a) The first except block b) The most specific matching block
c) The last except block d) None of the above
25. What can be included in the raise statement for additional information?
a) Exception name only b) Optional arguments like a string message
c) Exception handling code d) None of the above
26. What does the following code output?
try:
raise ValueError("Custom error message")
except ValueError as e:
print(e)
a) Nothing b) “ValueError”
c) “Custom error message” d) Program terminates with error
27. Which exception is user-defined?
a) ImportError b) ZeroDivisionError
c) AssertionError d) Any exception created by the programmer
28. What is printed by the following code?
try:
raise NameError("Example")
except NameError:
print("NameError occurred")
a) NameError b) NameError occurred c) Example d) None of the above
29. Which exception does an assert statement raise if the expression is False?
a) ValueError b) SyntaxError c) AssertionError d) NameError
30. What happens if the assert condition evaluates to True?
a) The program halts b) An exception is raised
c) Execution continues d) The next except block is executed
31. What does the runtime system do when an exception occurs?
a) Terminates the program immediately b) Searches for a handler in the call stack
c) Ignores the exception d) Converts it to a warning
32. What happens if no handler is found in the call stack?
a) The program terminates b) The exception is ignored
c) Execution continues d) The exception is logged but execution continues
33. What does the following code do?
try:
x=1/0
except ZeroDivisionError:

PREPARED BY: SANGAMESH G B 31

 II PUC COMPUTER SCIENCE

print("Cannot divide by zero!")

a) Prints “Cannot divide by zero!” b) Terminates with ZeroDivisionError
c) Ignores the error d) None of the above
34. Which statement is valid for catching exceptions?
a) Only one except block is allowed b) try block can have multiple except blocks
c) No try block is needed d) None of the above
35. What is the output of the following code?
try:
print(1 / 0)
except ZeroDivisionError:
print("Exception handled")
finally:
print("Finally block executed")
a) Exception handled, Finally block executed b) Finally block executed
c) Program terminates with ZeroDivisionError d) None of the above
36. Which block will execute even if an exception is not raised?
a) try b) except c) finally d) None of the above
37. What is the purpose of a generic except block?
a) Handle syntax errors b) Handle errors not specifically caught
c) Optimize performance d) Ignore exceptions
38. Which block is recommended for clean-up operations?
a) try b) except c) finally d) else
39. What does the following code print?
try:
int("abc")
except ValueError:
print("ValueError handled")
a) ValueError b) Program terminates
c) ValueError handled d) None of the above
40. What happens when an exception is raised but not caught?
a) The program terminates b) It continues execution
c) It enters the finally block and resumes d) None of the above
41. What is the purpose of an else clause in a try block?
a) It is mandatory b) Executes if no exception occurs
c) Always executes regardless of exceptions d) It defines error recovery steps
42. Which block can have more than one occurrence in exception handling?
a) try b) except c) else d) finally
43. What is the output of the following code if the input is 0?
try:
result = 50 / int(input("Enter a number: "))
except ZeroDivisionError:
print("Cannot divide by zero!")
except ValueError:
print("Invalid input!")
finally:
print("Execution complete.")
a) Cannot divide by zero!
Execution complete.
b) Invalid input!
Execution complete.
c) 50 divided by 0
d) Program terminates with ZeroDivisionError

PREPARED BY: SANGAMESH G B 32

 II PUC COMPUTER SCIENCE

44. Which exception is raised if the following code is executed and the input is abc?
try:
num = int(input("Enter a number: "))
except ValueError:
print("Invalid input!")
a) ValueError b) TypeError c) SyntaxError d) NameError
45. What does exception handling ensure?
a) Errors are ignored b) Code runs faster
c) Program does not crash abruptly d) Syntax errors are corrected automatically
46. What is the primary benefit of a try…finally structure?
a) Better syntax b) Clean termination or recovery
c) Handling specific exceptions d) Ignoring runtime errors
47. What exception is raised if input() encounters EOF?
a) ValueError b) EOFError c) TypeError d) SyntaxError
48. When is the OverFlowError raised?
a) A file cannot be opened
b) Division by zero occurs
c) A calculation exceeds the max limit for a numeric type
d) An undefined variable is accessed
49. What is the process of finding an exception handler called?
a) Raising an exception b) Catching an exception
c) Searching the call stack d) None of the above
50. What happens when an exception is successfully caught?
a) It propagates b) Execution terminates
c) Control resumes after the try block d) None of the above
51. The exception is raised when the requested module definition is not found
a) io error b) Syntax error c) import error d) index error
52. Given Q=N/D, if D=0 and N=50, which built-in exception occur?
a) Syntax Error b) Index Error c) Value Error d) ZeroDivisionError
53. The exception raised when the local or global variable is not defined is
a) Import Error b) TypeError c) ValueError d) NameError
54. What is the primary purpose of the assert statement in Python?
a) To catch exceptions during program execution
b) To define functions for debugging
c) To Test if a condition is True and raise an exception if it is True
d) To handle error in user input
55. Why should exceptions be handled in Python?
a) To ensure that errors are ignored b) To make program run faster
c) To avoid the program crashing abruptly d) To execute the program without error

PREPARED BY: SANGAMESH G B 33

 II PUC COMPUTER SCIENCE

 FILL IN THE BLANKS

1. A ________ error occurs when the rules of the programming language are not followed.
Answer: Syntax
2. Errors that occur during program execution and disrupt its normal flow are called ________.
Answer: Exceptions
3. The ________ block in Python is used to catch exceptions and handle them appropriately.
Answer: except
4. A division by zero operation raises the ________ exception.
Answer: ZeroDivisionError
5. The ________ exception is raised when a variable is referenced but has not been defined.
Answer: NameError
6. The Python statement used to manually raise an exception is ________.
Answer: raise
7. A ________ block is always executed, regardless of whether an exception occurred or not.
Answer: finally
8. The ________ exception occurs when the file specified in a program cannot be opened.
Answer: IOError
9. The process of identifying and handling exceptions is called ________.
Answer: Exception handling
10. The ________ statement is used in Python to test conditions and raise an AssertionError if
the condition evaluates to False.
Answer: assert
11. A block of code suspected to raise exceptions is enclosed within a ________ block.
Answer: try
12. A(n) ________ exception can be created by programmers to handle specific errors not covered
by built-in exceptions.
Answer: user-defined
13. The exception raised when an input operation hits the end of the file without reading any
data is ________.
Answer: EOFError
14. Python provides a structured block of text, known as ________, that contains information
about the sequence of function calls during an exception.
Answer: traceback
15. The ________ clause in Python is executed only if the try block completes successfully without
any exceptions.
Answer: else
16. A(n) ________ exception is raised when an invalid value is passed to a built-in method or
operation.
Answer: ValueError
17. The exception raised due to incorrect indentation in Python is ________.
`Answer: IndentationError
18. The Python runtime system searches the ________ to find an appropriate handler for the
raised exception.
Answer: call stack
19. A(n) ________ exception occurs when an index is out of the valid range of a sequence.
Answer: IndexError
20. The process of identifying a suitable handler for a raised exception is called ________ the
exception.
Answer: catching
21. The exception raised when the requested module is not found is ________.
Answer: ImportError

PREPARED BY: SANGAMESH G B 34

II PUC COMPUTER SCIENCE

22. The exception raised when a key is not found in a dictionary is ________.
Answer: KeyError
23. The exception raised when a calculation exceeds the maximum limit for a numeric type is
________.
Answer: OverflowError
24. The ________ block is placed after a try block to handle multiple exceptions using separate
handlers.
Answer: except
25. When no specific handler is defined for an exception, a generic ________ block can be used.
Answer: except
26. The exception raised when the user presses an interrupt key like Ctrl+C is ________.
Answer: KeyboardInterrupt
27. The method or block of code responsible for responding to a specific type of exception is called
a(n) ________.
Answer: exception handler
28. Python’s standard library includes numerous ________ exceptions to handle commonly
occurring errors.
Answer: built-in
29. When an exception occurs, the normal flow of the program is ________.
Answer: interrupted
30. The try block is mandatory when using the ________ clause in Python exception handling.
Answer: except

PREPARED BY: SANGAMESH G B 35

II PUC COMPUTER SCIENCE

PREPARED BY: SANGAMESH G B 36

 II PUC COMPUTER SCIENCE

CHAPTER – 02
FILE HANDLING IN PYTHON

In this chapter:
Introduction to Files
Types of Files
Opening and Closing a Text File
Writing to a Text File
Reading from a Text File
Setting Offsets in a File
Creating and Traversing a Text File
The Pickle Module
1. Introduction
File handling refers to the process of performing operations on a file such as creating, opening,
reading, writing and closing it, through a programming interface. It involves managing the data
flow between the program and the file system on the storage device, ensuring that data is
handled safely and efficiently.

 In Python, data stored in variables is temporary and disappears after the program ends.
 To store data permanently, we use files, which are saved on secondary storage (e.g., hard
disks).
 Files allow us to store inputs, outputs, and objects for later use.
 A Python file (source code) is saved with a .py extension

2. File
A file is a named location on a secondary storage media, where data are permanently stored for
later access.

Types of files:
i. Text file
ii. Binary file

i. Text file:
[Link] is a file that stores information in the form of ASCII, UNICODE characters.
[Link] contains sequence of characters, consisting of alphabets, numbers and other special symbols.
[Link] is in human readable or understandable form
[Link] files can be opened and edited using any text editor (Ex: Notepad).
[Link] with extensions like .txt, .py, .csv, .doc etc. are examples of text files
[Link] line of a text file is terminated by a special character, called End of Line (EOL) or
Delimiters
g. In this file, certain internal translation takes place
h. The default EOL character in python is newline (\n)
i. The contents in the text file are usually separated by whitespace, but comma (,) and tab (\t) are
also commonly used to separate values in a text file.

Example:
The ASCII value of 'A' is 65 → Binary: 1000001

PREPARED BY: SANGAMESH G B 37

 II PUC COMPUTER SCIENCE

ii. Binary file:

a. It is a file that stores information in the form of stream of bytes (sequence of 0’s and 1’s)
b. It represents actual contents like images, audios, videos and executable files.
c. It is not in human readable format (machine-readable form)
d. Binary files can only be opened and edited using specialized software (Ex: media player)
e. Files with extensions like .jpg, .pdf, .exe, .mp3 etc. are some examples of binary files.
f. No EOL character or Delimiters character are used to terminate line of text.
g. In this file, no internal translation takes place
h. Change in single bit can corrupt a complete binary file.
i. Errors occurred in binary file is very difficult to remove.

3. Give the differences between Text file and Binary file

[Link] Text file Binary file
01 It is a file that stores information in the It is a file that stores information in the form
form of ASCII, UNICODE characters of stream of bytes (sequence of 0’s and 1’s)
02 It contains sequence of characters, It represents actual contents like images,
consisting of alphabets, numbers and audios, videos and executable files
other special symbols
03 It is in human readable or understandable It is not in human readable form (machine-
form readable form)
04 Text files can be opened and edited using Binary files can only be opened and edited
any text editor (Eg: Notepad) using specialized software.(Eg: Media player)
05 Example: Files with extensions like .txt, Examples: Files with extensions like .jpg,
.py, .csv, .doc etc. .pdf, .exe, .mp3 etc.
06 Each line of a text file is terminated by a No EOL character or Delimiters character are
special character, called End of Line used to terminate line of text
(EOL) or Delimiters
07 In this file, certain internal translation In this file, no internal translation takes place
takes place
08 Text files can be easily edited or Binary files requires specific software to edit
modified or modify

4. Opening and Closing a Text files

In real world applications, computer programs deal with data coming from different sources
like databases, CSV files, HTML, XML, JSON, etc. We broadly access files either to write or
read data from it. But operations on files include creating and opening a file, writing data in a
file, traversing a file, reading data from a file and so on. Python has the io module that
contains different functions for handling files

4a. Opening a file:

In python, Files are opened using the open() function which returns a file object.
(To open a file in python, we use the open() function or method)
Syntax:
file_object=open (“file_name”, “access_mode”)

Example-1:
myobject=open (“[Link]”, “r+”)
Example-2:
myobject=open (“[Link]”, “a”)

 This function returns a file object called file handle which is stored in the variable
file_object.

PREPARED BY: SANGAMESH G B 38

II PUC COMPUTER SCIENCE

 File attributes (Attributes of file object):

The file object has certain attributes that tells us basic information about the file

 <[Link]> returns true if the file is closed and false otherwise.

 <[Link]> returns the access mode in which the file was opened.
 <file. name> returns the name of the file.

4b. Closing a file:

Close( ) method is used to close a file and release the memory.
[When a program is done with read/write operation then file need to close using close ( )
method. While closing a file, the system frees the memory allocated to it]
Syntax:
file_object.close ( )
Example-1:
[Link] ( )

4c. Opening a file using a “with” clause:

In Python, we can also open a file using “with” clause.
It is a simpler way to open and close a file automatically
Syntax:
with open (“file_name”, “access_mode”) as file_object :

Example:
with open (“myfile”, “r+”) as myobject :

• Automatically closes the file when the block is exited.

 The advantage of using with clause is that any file that is opened using this clause is closed
automatically, once the control comes outside the with clause.
 In case the user forgets to close the file explicitly or if an exception occurs, the file is closed
automatically.

PREPARED BY: SANGAMESH G B 39

 II PUC COMPUTER SCIENCE

5. Access Modes:
The access mode is an optional argument that represents the mode in which the file has to be
accessed by the program. It is also referred to as processing mode.

File Open Modes / File Access modes:

File Description File offset position
Modes
Read modes:
<r> Opens the file in read only mode Beginning of the file
It is a default file access mode in python
<r+> Open the file in both read and write mode Beginning of the file
or
<+r>
Write modes:
Open the file in write mode, Overwrites existing file or Beginning of the file
<w> creates a new file
[Open the file in write mode, if the file already exists,
all the contents will be overwritten. If the file does not
exist, then a new file will be created.]
<w+> Open the file both read and write mode, Overwrites Beginning of the file
existing file or creates a new file
Binary modes:
<rb> Opens the file in binary and read only mode Beginning of the file
<wb+> Open the file in read, write and binary mode, Overwrites Beginning of the file
or or creates a new file
<+wb> [Open the file in read, write and binary mode, if the file
already exists, all the contents will be overwritten. If the
file does not exist, then a new file will be created.]
Append modes:
Open the file in append mode. Adds data at the end of End of the file
<a> the file. If the file does not exist, then a new file will be
created.
<a+> Open the file in append and read mode. If the file does End of the file
or not exist, then a new file will be created.
<+a>

 File modes determine operations allowed on a file.

Syntax:
file_object = open("[Link]", "Access_mode")

Examples:
myobject = open("[Link]", "r")
myobject = open("[Link]", "r+")
myobject = open("[Link]", "a+")

PREPARED BY: SANGAMESH G B 40

 II PUC COMPUTER SCIENCE

6. Writing to a Text file:

In python, data can be written to a text file using the write( ) or writelines( ) methods after
opening the file in write (‘w’) or append (‘a’) mode.

There are two methods for writing a file

a. The write ( ) method
b. The writelines ( ) method

a. The write() method:

write() method takes a single string as an argument and writes it to the text file.

Syntax:
file_object.write(string)

Example-01: [Writes a single string]

myobject=open(“[Link]”,‘w’)
[Link](“Hey I have started #using files in Python\n”)
[Link]( )

Example-02: [Writing numbers:]

marks = 58
[Link](str(marks))

• Used to write a single string to the text file.

• Returns the number of characters written on single execution
• To mark the end of line, a newline character (∖n) must be added manually.
• Numeric data must be converted to string str( ) before being written

b. The writelines() method:

This method is used to writes multiple strings to a file.
We need to pass an iterable object like lists, tuple, etc.

Syntax:
file_object.writelines(list_of_strings)

Example:
myobject=open(“myfi [Link]”,‘w’)
lines = [“Hello everyone\n”, “I have offered Computer Science\n”, “Learning Python
programming”]
[Link](lines)
[Link]()

PREPARED BY: SANGAMESH G B 41

 II PUC COMPUTER SCIENCE

7. Reading from the file:

In python, data can be read from a text file after opening it in “r”, “r+”, “w”, “w+”, or “a+” mode.
There are three main methods for reading data from the file.

There are two methods for writing a file

a. The read( ) method
b. The readline( ) method
c. The readlines( ) method

a. The read( ) method:

This method is used to read a specified number of bytes of a data from the file.

Syntax-01: read(n)
file_object.read(n)

Example-01: [Reads n bytes from the file]

myobject = open("[Link]", 'r')
print([Link](10))
[Link]()

Syntax-02: read()
file_object.read()

Example-02: Reads the entire file content.

myobject = open("[Link]", 'r')
print([Link]())
[Link]()

b. The readline( ) method:

This method reads one complete line from a file, where each line terminates with a newline
(\n) character.
It can also read a specified number of bytes.

Syntax:
file_object.readline(n)

Example: readline(n)
myobject = open("[Link]", 'r')
print([Link](10))
[Link]()

• Reads one line or up to n bytes until newline character.

c. The readlines( ) method:

This method reads all lines and returns them as a list of strings, where each line ends with a
newline character (\n).

Syntax:
file_object.readlines( )

PREPARED BY: SANGAMESH G B 42

II PUC COMPUTER SCIENCE

Example: readlines(n)
myobject = open("[Link]", 'r')
print([Link]( ))
[Link]()

• Reads all lines and returns a list.

Output:
[“Hello everyone\n”, “ I have offered Computer Science\n”, “Learning Python language”]

 Split ( ) and splitlines ( ) methods:

a. Split( ) method
b. Splitlines( ) methods

a. Split ( ):
This method is used to splits each line into list of words separately from the text file.
Example:
for line in d:
words = [Link]()
print(words)

Output:
[‘Hello’, ‘ everyone’]
[‘I’. ‘have’, ‘offered’, ‘Computer’,’ Science’]
[‘Learning’, ‘ Python’, ‘language’]

b. Splitlines ( ):
This method is used to split a string into a list of lines from the text file.
Example:
for line in d:
words = [Link]()
print(words)

Output:
[‘Hello everyone’]
[‘I have offered Computer Science’]
[‘Learning Python language’]

 Programming Example: Writing and reading to the text file

myobject = open("[Link]", "w")
sentence = input("Enter the contents to be written in the file: ")
[Link](sentence)
[Link]()

print("Now reading the contents of the file: ")

fobject = open("[Link]", "r")
for str in fobject:
print(str)
[Link]()

PREPARED BY: SANGAMESH G B 43

 II PUC COMPUTER SCIENCE

8. File Offset Methods:

In python, to access data in a random (non-sequential) fashion, we can use the offset methods

 There are two setting offsets methods in a file

a. tell( )
b. seek( )

a. tell( ):
This method returns an integer that specifies the current position of the file object in the file.
Syntax:
file_object.tell()
Example:
[Link]()

b. seek( ):
This method is used to position the file object at a particular position in a file
Syntax:
file_object.seek(offset [, reference_point] )
Example:
[Link](5, 0) # Move to 5th byte from start

 offset: Number of bytes by which the file object is to be moved

 reference point: Indicates the starting position of the file object (To count the offset from)
 Reference point can have any of the following values:
o 0 – Beginning of the file (default)
o 1 – Current position of the file
o 2 – End of the file

• Moves pointer to specified position from reference point (0 = start, 1 = current, 2 = end).
• Moves pointer to specified position.

 Program Example: Application of tell( ) and seek()

fileobject = open("[Link]", "r+")
str = [Link]()
print(str)
print("Initially, position:", [Link]())
[Link](0)
print("Now at beginning:", [Link]())
[Link](10)
print("Pointer at:", [Link]())
print([Link]())
[Link]()

 tell(): It returns the current position of the file object in bytes from beginning
 seek():To move the file object to a specific position in a file.

PREPARED BY: SANGAMESH G B 44

 II PUC COMPUTER SCIENCE

9. Creating and Traversing a Text file:

a. Creating a file and writing data

 Use open ( ) method to create a file
 Specify filename and access mode
 Mode “w” overwrites existing file, and “a” appends to it
 If file does not exist, new file is created

Example:
fileobject=open(“[Link]”, “w+”)

 Program: To create a text file and write data in it

fileobject = open("[Link]", "w+")
while True:
data = input("Enter data to save in the text file: ")
[Link](data)
ans = input("Do you wish to enter more data?(y/n): ")
if ans == 'n': break
[Link]()

b. Traversing a file and displaying data

 Open the file in read mode “r”
 Use read( ) or readline( ) to access data
 Loop through lines and display

Example:
fileobject=open(“[Link]”, “r”)

 Program: To display data from a text file.

fileobject = open("[Link]", "r")
str = [Link]()
while str:
print(str)
str = [Link]()
[Link]()

 Program: To perform reading and writing operation in a text file

fileobject = open("[Link]", "w+")
while True:
line = input("Enter a sentence ")
[Link](line + "\n")
choice = input("Do you wish to enter more data? (y/n): ")
if [Link]() == 'n': break
print("File position:", [Link]())
[Link](0)
print("Reading contents:")
print([Link]())
[Link]()

PREPARED BY: SANGAMESH G B 45

 II PUC COMPUTER SCIENCE

10. Pickle Module:

The pickle module is used for to serializing and deserializing any python object structure.
- Allowing for easy storage and retrieval

Pickling: It is the process of converting Python objects into byte streams

 Serialization (pickling):
It is the process of converting python objects into byte stream to store in a binary file.
- Using a [Link]( )

 Deserialization (unpickling):
It is the process of converting byte stream to python object. (Reverse process of pickling)
- Using a [Link]( )

• Serialization and Deserialization- Done using pickle module

 Methods in Pickle module:

There are two methods in pickle module are:
a. dump( ) method
b. load( ) method

a. dump( ) method:
This method is used for serializing (Pickling) and writing the python objects into a binary file.
 The file in which data to be dumped should open with binary write mode (wb).
Syntax;
[Link](data_object, file_object)
Example:
import pickle
listvalues = [1, "Geetika", 'F', 26]
fileobject = open("[Link]", "wb")
[Link](listvalues, fileobject)
[Link]()

b. load( ) method:
This method is used for deserializing (unpickling) and reading the python objects from a
binary file.
 The file to be loaded should be open in binary read mode (rb).
Syntax;
variable = [Link](file_object)
Example-01:
import pickle
print(“The data that were stored in file are:”)
fileobject=open(“[Link]”,”rb”)
objectvar=[Link](fileobject)
[Link]( )
print(objectvar)

Example-02:
fileobject = open("[Link]", "rb")
objectvar = [Link](fileobject)
[Link]()
print(objectvar)

PREPARED BY: SANGAMESH G B 46

II PUC COMPUTER SCIENCE

 Programming Example: Pickle module – dump( ) and load( ) method

import pickle
while True:
print("[Link] Binary file, [Link] the file, [Link]")
a=int(input("choose a command 1-2-3-exit:"))

if a==1:
f=open("[Link]","wb")
x=int(input("how many students:"))
for i in range(x):
name=input("Name:")
english=int(input("English marks:"))
lang=int(input("Language marks:"))
phy=int(input("physics marks:"))
chem=int(input("Chemistry marks:"))
maths=int(input("maths marks:"))
cs=int(input("cs marks:"))
t=[name,english,lang,phy,chem,maths,cs]
[Link](t,f)
[Link]()

elif a==2:
f=open("[Link]","rb")
try:
while True:
p=[Link](f)
print(p)
except:
[Link]()

PREPARED BY: SANGAMESH G B 47

 II PUC COMPUTER SCIENCE

11. Exercise:

1. Explain in detail the various file opening modes with their file pointer positions and suitable
use cases
Mode Use Case Pointer Position
“r” Read existing files Beginning of the file
“w” Create/overwrite files Beginning of the file
“r+” or “+r” Read/write existing files Beginning of the file
“w+” or “+w” Create/overwrite with read Beginning of the file
capability
“b” Binary mode suffix: Beginning of the file
Ex: “rb” , “wb”
“a” Append to existing files End of the file
“a+” or “+a” Append with read capability End of the file

2. Explain the complete file handling process in Python with proper syntax and examples for
each step.
The file handling process in Python:
• Opening: file = open("[Link]", "r") or with open("[Link]", "w") as file:
• Writing: [Link]("Content") or [Link](["Line1\n", "Line2\n"])
• Reading: content = [Link]() or lines = [Link]()
• Positioning: pos = [Link]() and [Link](offset)
• Closing: [Link]() (automatic in with statement)
• Example:
with open("[Link]", "w+") as f:
[Link]("Sample text\n")
[Link](0)
print([Link]())

3. Compare and contrast text files and binary files with respect to: storage format, readability,
extensions, and use cases.
Ans:
• Storage Format: Text uses ASCII/Unicode; Binary uses raw bytes
• Readability: Text is human-readable; Binary requires special programs
• Extensions: Text (.txt, .py); Binary (.dat, .jpg)
• Use Cases: Text for configuration/data; Binary for media/executables
• Example:
# Text file operation
with open("[Link]", "w") as f:
[Link]("Hello")

# Binary file operation

with open("[Link]", "wb") as f:
[Link](b'\x48\x65\x6c\x6c\x6f')

4. Explain the file object attributes and methods with suitable examples for each. Answer:

• Attributes:
– name: print([Link]) # Shows filename
– mode: print([Link]) # Shows access mode
– closed: print([Link]) # True/False

PREPARED BY: SANGAMESH G B 48

 II PUC COMPUTER SCIENCE

• Methods:
– read(): content = [Link](10) # First 10 bytes
– seek(): [Link](5) # Move to 5th byte
– tell(): pos = [Link]() # Current position
– flush(): [Link]() # Force write to disk

5. Create a comprehensive program that demonstrates all file object methods (read, write,
seek, tell, flush) with proper documentation.
Answer:
# Demonstrate all key file methods

with open("demo_methods.txt", "w+") as f: # Open in write/read mode

# WRITE
[Link]("Line 1\nLine 2\nLine 3\n")
print(f"Initial write - Position: {[Link]()}") # Should show 18 bytes

# FLUSH
[Link]() # Force write to disk

# SEEK
[Link](0) # Rewind to start
print(f"After seek(0) - Position: {[Link]()}") # 0

# READ
content = [Link](10) # First 10 chars
print(f"Partial read: {content}")
print(f"After read(10) - Position: {[Link]()}") # 10

# READLINE
[Link](0)
print("Full content:")
while True:
line = [Link]()
if not line: break
print([Link]())

6. Write a program to accept string/sentences from the user till the user enters “END”.
Save the data in a text file and then display only those sentences which begin with an
uppercase alphabet.
Answer:
with open("[Link]", "w") as f:
while True:
line = input("Enter sentence (END to stop): ")
if line == "END": break
[Link](line + "\n")

# Display filtered content

with open("[Link]", "r") as f:
for line in f:
if [Link]() and line[0].isupper():
print([Link]())

PREPARED BY: SANGAMESH G B 49

 II PUC COMPUTER SCIENCE

7. Write a program to enter the following records in a binary file:

Item No (integer)
Item_Name (string)
Qty (integer)
Price (float)

Display records in format:

Item No:
Item Name:
Quantity:
Price per item:
Amount: (Price * Qty)

Answer:
import pickle

# Writing records
with open("[Link]", "wb") as f:
while True:
item_no = int(input("Enter Item No (0 to stop): "))
if item_no == 0: break
name = input("Item Name: ")
qty = int(input("Quantity: "))
price = float(input("Price: "))
[Link]([item_no, name, qty, price], f)

# Reading records
with open("[Link]", "rb") as f:
while True:
try:
item = [Link](f)
print(f"\nItem No: {item[0]}")
print(f"Item Name: {item[1]}")
print(f"Quantity: {item[2]}")
print(f"Price per item: {item[3]}")
print(f"Amount: {item[2] * item[3]}")
except EOFError:
break

PREPARED BY: SANGAMESH G B 50

 II PUC COMPUTER SCIENCE

 Multiple Choice Questions (MCQs)

1. What is the primary purpose of storing data in files?
a) To execute programs faster b) permanently store data for later access
c) To reduce memory usage d) To improve program readability
2. Where are files stored in a computer system?
a) Primary memory (RAM) b) Secondary storage media
c) CPU registers d) Cache memory
3. Which of the following is a text file extension?
a) .txt b) .jpg c) .exe d) .mp3
4. What is the main difference between text and binary files?
a) Text files are smaller in size
b) Binary files contain human-readable characters
c) Text files consist of ASCII/Unicode characters
d) Binary files cannot be opened in Python
5. What happens if a binary file is opened in a text editor?
a) It displays the correct content b) It shows garbage values
c) It automatically converts to text d) It asks for a password
6. Which of the following is an example of a binary file?
a) A .csv file b) A .py file c) A .docx file d) A .txt file
7. What is the default EOL character in Python?
a) \r b) \n c) \t d) \0
8. Which encoding scheme is commonly used for text files?
a) ASCII b) JPEG c) MPEG d) ZIP
9. Which function is used to open a file in Python?
a) file_open() b) open() c) load() d) read()
10. What is the default mode for opening a file?
a) Read mode (‘r’) b) Write mode (‘w’) c) Append mode (‘a’) d) Binary mode (‘b’)
11. Which mode is used to open a file for both reading and writing?
a) ‘r’ b) ‘w+’ c) ‘a’ d) ‘b’
12. What happens if a file opened in ‘w’ mode already exists?
a) The file is opened in read mode b) The existing content is overwritten
c) The file is deleted d) An error occurs
13. Which attribute returns the access mode of a file?
a) [Link] b) [Link] c) [Link] d) [Link]
14. How is a file closed in Python?
a) [Link]() b) close(file) c) [Link]() d) exit(file)
15. What is the advantage of using the with clause to open a file?
a) It allows faster file operations b) It automatically closes the file
c) It encrypts the file d) It compresses the file
16. Which method is used to write a single string to a file?
a) writeline() b) write() c) append() d) insert()
17. What does the write() method return?
a) The number of characters written b) The file object
c) The content of the file d) None
18. How can numeric data be written to a text file?
a) Directly using write() b) By converting it to a string first
c) Using the dump() method d) It cannot be written
19. Which method is used to write multiple strings to a file?
a) writelines() b) write() c) appendlines() d) insertlines()
20. What is the purpose of the flush() method?
a) To close the file b) To clear the buffer and write contents to the file
c) To read the file d) To delete the file

PREPARED BY: SANGAMESH G B 51

 II PUC COMPUTER SCIENCE

21. Which method reads a specified number of bytes from a file?

a) read() b) readline() c) readlines() d) seek()
22. What happens if no argument is passed to the read() method?
a) It reads one line b) It reads the entire file
c) It returns an error d) It reads 10 bytes
23. Which method reads one complete line from a file?
a) read() b) readline() c) readlines() d) load()
24. What does the readlines() method return?
a) A single string b) A list of strings c) A tuple of strings d) A dictionary of strings
25. How can you read a file line by line using a loop?
a) Using readline() in a while loop b) Using read() in a for loop
c) Using seek() in a loop d) Using dump() in a loop
26. What does the split() function do when reading a file?
a) Splits the file into multiple files b) Splits each line into a list of words
c) Joins multiple lines d) Closes the file
27. Which method returns the current position of the file object?
a) seek() b) tell() c) pos() d) offset()
28. What is the purpose of the seek() method?
a) To close the file b) To move the file object to a specific position
c) To read the file d) To write to the file
29. What is the default reference point for the seek() method?
a) Beginning of the file (0) b) Current position (1)
c) End of the file (2) d) Middle of the file
30. How do you move the file object to the 10th byte from the beginning?
a) seek(10, 0) b) seek(0, 10) c) seek(10, 1) d) seek(10, 2)
31. What happens if a file opened in ‘a’ mode does not exist?
a) An error occurs b) A new file is created
c) The file is deleted d) The file is opened in read mode
32. Which mode is used to open a file for both reading and writing without overwriting existing
content?
a) ‘r+’ b) ‘w+’ c) ‘a+’ d) ‘b+’
33. How can you iterate over all lines in a file?
a) Using a for loop on the file object b) Using a while loop with readline()
c) Both a and b d) Using seek()
34. What is the output of [Link]() after writing data to a file?
a) The number of lines written b) The current byte position of the file object
c) The file size d) The number of characters written
35. What is the purpose of the pickle module?
a) To read text files b) To serialize and deserialize Python objects
c) To write binary files d) To compress files
36. Which method is used to write Python objects to a binary file?
a) write() b) dump() c) load() d) pickle()
37. Which method is used to read Python objects from a binary file?
a) read() b) load() c) get() d) unpickle()
38. What mode is used to open a binary file for writing?
a) ‘w’ b) ‘wb’ c) ‘wr’ d) ‘w+’
39. What happens if a binary file is corrupted?
a) It can be easily fixed b) It becomes unreadable
c) It automatically repairs itself d) It converts to a text file
40. Which exception is raised when the end of a binary file is reached during unpickling?
a) FileNotFoundError b) EOFError c) IOError d) ValueError

PREPARED BY: SANGAMESH G B 52

 II PUC COMPUTER SCIENCE

41. What is serialization?

a) Converting Python objects to byte streamsb) Reading text files
c) Writing binary files d) Closing files
42. What is deserialization?
a) Converting byte streams to Python objectsb) Writing text files
c) Reading binary files d) Opening files
43. Which module is required for pickling and unpickling?
a) io b) pickle c) os d) sys
44. What is the output of [Link] if the file is open?
a) True b) False c) 1 d) 0
Answer: b) False
45. Which method is used to forcefully write buffer contents to a file?
a) close() b) flush() c) write() d) dump()
46. What is the purpose of the splitlines() method?
a) To split a file into multiple files b) To split a string into a list of lines
c) To join lines in a file d) To close a file
47. Which of the following is not a file attribute?
a) [Link] b) [Link] c) [Link] d) [Link]
48. What is the correct way to open a file for reading and writing in binary mode?
a) open(“[Link]”, “r+b”) b) open(“[Link]”, “rwb”)
c) open(“[Link]”, “br+”) d) open(“[Link]”, “b+r”)
49. What is the correct syntax for the with clause?
a) with open(“[Link]”, “r”) as f: b) with open(“[Link]”, “r”) -> f:
c) with open(“[Link]”, “r”) in f: d) with open(“[Link]”, “r”) f:
50. What is the purpose of the io module in Python?
a) To handle file operations b) To perform mathematical calculations
c) To create graphical interfaces d) To connect to databases
51. The method which is used to convert python objects for writing data in a binary file
a) load b) dump c) Seek d) tell()
52. The function which returns an integer that specifies the current position of the file_object in the
file is
a) seek b) load c) tell d) dump()
53. The default file opening mode in Python is
a) <r> the read only mode b) <w> the write mode
c) <a> the append mode d) <r+> the read and write mode
54. Which of the following access mode opens a file for reading only?
a) r b) -r c) r+ d) rb
55. Which of the following access mode opens a file in binary and read only
b) <br> b) <rb> c) <r> d) <wb>

PREPARED BY: SANGAMESH G B 53

 II PUC COMPUTER SCIENCE

 Fill in the blanks (FIB)

1. A file is a named location on ________ storage media where data is permanently stored.
Answer: secondary
2. The two main types of files are ________ files and binary files.
Answer: text
3. Text files store data using ________ or Unicode encoding schemes.
Answer: ASCII
4. The default End of Line (EOL) character in Python is ________.
Answer: \n
5. Binary files store data in ________ format that is not human-readable.
Answer: byte
6. The ________ function is used to open a file in Python.
Answer: open()
7. The default file opening mode is ________.
Answer: ‘r’ (read mode)
8. To open a file for both reading and writing, we use ________ mode.
Answer: ‘r+’
9. The ________ method returns the current position of the file pointer.
Answer: tell()
10. To move the file pointer to a specific position, we use the ________ method.
Answer: seek()
11. The ________ clause automatically closes the file when the block ends.
Answer: with
12. The ________ method writes a single string to a file.
Answer: write()
13. The ________ method writes multiple strings from an iterable to a file.
Answer: writelines()
14. To read a specified number of bytes from a file, we use the ________ method.
Answer: read()
15. The ________ method reads one complete line from a file.
Answer: readline()
16. The ________ method reads all lines and returns them as a list.
Answer: readlines()
17. The ________ module is used for serializing and deserializing Python objects.
Answer: pickle
18. The ________ method converts Python objects to byte streams for storage.
Answer: dump()
19. The ________ method loads Python objects from binary files.
Answer: load()
20. Files opened in ________ mode will overwrite existing content.
Answer: ‘w’
21. The ________ mode allows appending data to the end of an existing file.
Answer: ‘a’
22. The ________ attribute returns True if a file is closed.
Answer: closed
23. The ________ attribute returns the name of the file.
Answer: name
24. The ________ method forces writing of buffered data to the file.
Answer: flush()
25. To handle non-text data like images, we open files in ________ mode.
Answer: binary (‘b’)

PREPARED BY: SANGAMESH G B 54

 II PUC COMPUTER SCIENCE

26. The ________ exception occurs when trying to read past EOF in pickle.
Answer: EOFError
27. The ________ method splits strings at whitespace by default.
Answer: split()
28. The ________ method splits strings at line boundaries.
Answer: splitlines()
29. In file operations, ________ refers to converting objects to byte streams.
Answer: serialization
30. The ________ function converts numbers to strings before file writing.
Answer: str()

PREPARED BY: SANGAMESH G B 55

II PUC COMPUTER SCIENCE

PREPARED BY: SANGAMESH G B 56

 II PUC COMPUTER SCIENCE

CHAPTER – 03
STACK

In this chapter:
Introduction
Stack
Operations on Stack
Implementation of Stack in Python
Notations for Arithmetic Expressions
Conversion from Infix to Postfix Notation
Evaluation of Postfix Expression
1. What is a data structure?
A data structure is a specialized format for organizing and storing the data.
Examples: String, List, Set, Tuple. Array, Linked Lists, Stack, Queue, Trees, Graphs, etc.

2. What is a stack?
A Stack is a linear data structure where elements are inserted and deleted from same end (TOP).
This end is commonly referred as “TOP”

 Stack follows the ordering principle of Last-In First-Out (LIFO).

 In python, A stack can be implemented using the “list” data type or data structure
 The basic operations of Stack are: PUSH and POP

3. Applications of Stack in Real-life

The applications of Stack in real life are:
a. Pile of cloths in almirah
b. Multiple chairs in a vertical file
c. Bangles worn on wrist
d. Pile of boxes kept one on one
e. Stack of plates
f. Stack of Books

4. Applications of Stack in Programming

The Applications of Stack in Programming / Computer Science are:
a. Reversing a string
b. Undo and Redo operations in editors
c. Web Browsers Back Button
d. Parentheses matching in expression
e. Polish notation
f. Conversion of infix expression into prefix and postfix
g. Evaluation of postfix expression
OR
The Applications of stacks in programming / Computer Science are:
a. Reversing a String: Characters pushed then popped in reverse order.
b. Undo and Redo operations: Recent changes are pushed; undo pops last action.
c. Web Browsers Back Button: Maintains history as stack; back pops last page.
d. Parenthesis Matching in Expression: Stack stores opening brackets; ensures matching.
e. Function Call Management; In compiled languages, stack maintains function calls

PREPARED BY: SANGAMESH G B 57

 II PUC COMPUTER SCIENCE

5. Explain the applications of Stack in Computer Science / Programming

The Applications of stacks in Computer Science / Programming are:
a. Reversing a String: Characters are Pushed (added) to a stack and popped in reverse order to
reverse the string.
b. Undo and Redo operations: Each edit (text/image) is pushed onto a stack. Undo removes the
last change, redo re-applies it.
(In a text or image editor, stack are used to keep track of recent changes, allowing the user to
undo or redo actions)
c. Web Browsers Back Button: Browsers use stacks to store the history of visited web pages, The
BACK button works by popping the last visited page from the stack
(Navigated pages are pushed onto a stack. Pressing “Back” pops the last visited page and returns to the
previous one.)
d. Parenthesis Matching in Expression: Compilers use stacks to check balanced parenthesis in
arithmetic expressions
(During program execution, a stack is used to ensure every opening parenthesis has a matching
closing one. It helps identify syntax errors like unmatched or misnested parentheses)
e. Function Call Management; In compiled languages, stack maintains function calls

6. Operations of Stack
The operations performed on stack are:
a. PUSH( )
 Overflow( )
b. POP( )
 Underflow( )
c. isEmpty( )
d. isFull( )
e. Peek( )
f. Size( )

a. PUSH( ): Adding a new element into the Stack at Top end

 Overflow( ): Trying to add new element to full stack, results in exception is called as Overflow
b. POP( ): Deleting an element from the stack from Top end
 Underflow( ): Trying to delete an element from empty stack, results in exception is called as
Underflow.
c. isEmpty( ): To check whether stack is empty or not
d. isFull( ): To check whether stack is full or not
e. Peek( ): To check top most element of the stack
f. Size( ): To check the number of elements in stack

7. Differentiate between PUSH and POP operations.

[Link] PUSH POP
01 Adding a new element to the top of Removing the element from the top of the
the Stack (Insertion) stack (Deletion)
02 It is an insertion operation It is an deletion operation
02 Trying to add new element to full Trying to delete an element from empty
stack, results in exception is called stack, results in exception is called as
as Overflow Underflow.
03 We can add elements to a stack We can delete an elements from a stack
until it is full until it becomes empty.

PREPARED BY: SANGAMESH G B 58

 II PUC COMPUTER SCIENCE

8. Implementation of stack in python

Steps for Implementation of stack in python:
 Create an empty stack by assigning an empty list to the identifier
 Define a function to check whether stack is empty or not
 Define a function PUSH() to insert an element to the stack
 Define a function POP() to delete an element from the stack
 Define a function len() to read the number of elements in the stack
 Define a function TOP to read top most element of the stack

 Implementation of stack using function:

# Create an empty stack
glassStack = list()

# Check if stack is empty

def isEmpty(glassStack):
if len(glassStack) == 0
return True
else:
return False

# PUSH operation
def opPush(glassStack, element):
[Link](element)

# Return stack size

def size(glassStack):
return len(glassStack)

# Return top element

def top(glassStack):
if isEmpty(glassStack):
print("Stack is empty")
return None
else:
x=len(glassStack)
element=glassStack[x-1]
return element
# POP operation
def opPop(glassStack):
if isEmpty(glassStack):
print("underflow")
return None
else:
return [Link]()

# Display all elements (from TOP to bottom)

def display(glassStack):
x=len(glassStack)
print(“Current elements in the stack are:”)
for i in range(x-1, -1, -1):
print(glassStack[i])

PREPARED BY: SANGAMESH G B 59

II PUC COMPUTER SCIENCE

Sample Program:
glassStack = list() # create empty stack

element = 'glass1'
print("Pushing element", element)
opPush(glassStack, element)

element = 'glass2'
print("Pushing element", element)
opPush(glassStack, element)

print("Current number of elements in stack is", size(glassStack))

element = opPop(glassStack)
print("Popped element is", element)

element = 'glass3'
print("Pushing element", element)
opPush(glassStack, element)

print("Top element is", top(glassStack))

display(glassStack)

# delete all elements

while True:
item = opPop(glassStack)
if item is None:
break
print("Popped element is", item)

print("Stack is empty now")

PREPARED BY: SANGAMESH G B 60

 II PUC COMPUTER SCIENCE

9. Notations for Arithmetic Expressions:

There are three notations for arithmetic expressions are:
a. Infix
b. Prefix (Polish)
c. Postfix (Reverse of polish)

a. Infix:
Operators are placed between the operands.
Infix rule  BODMAS
Examples:
x+y
x*y+z
3 * (4 + 5)
(x + y) / (z + 5)
(a - b) * c

b. Prefix:
Operators are placed before the corresponding operands.
Examples:
+xy
+*xyz
* 3+45
/+xy*z5
*-abc

c. Postfix:
Operators are placed after the corresponding operands.
Examples:
xy+
xy*z+
345+*
xy+z5*/
ab-c*

PREPARED BY: SANGAMESH G B 61

 II PUC COMPUTER SCIENCE

10. Conversion from Infix to Postfix Notation

 Algorithm: conversion from infix to postfix expression
Step-1: Create an empty string named postExp to store the converted postfix expression
Step-2: INPUT infix expression in a variable, say inEXP
Step-3: For each character in inEXP, REPEAT Step4
Step-4: If character is left parentheses THEN PUSH on the stack
ELSE IF character is right parenthesis
THEN POP the elements from the stack and append the string
postEXP until the stack and append the string
While discarding both left and right parenthesis
ELSE IF character is an operator
THEN IF precedence is lower than of operator at the top of the stack
THEN POP elements from the stack till an
Operator with precedence less than the current
Operator is encountered and append to string
PostEXP before pushing this operator on the
postStack
ELSE PUSH operator on the stack
ELSE Append the character to postEXP
Step-5: Pop elements from the stack and append to postEXP until stack is empty
Step-6: OUTPUT postEXP

 Example: (x + y) / (z * 8 )

OR

 Algorithm: conversion from infix to postfix expression

Step-1: Create an empty string postEXP and stack Stack
Step-2: For each character in infix expression
• If ( → PUSH to stack
• If ) → POP and add to postExp until ( is found
• If operator:
– POP higher or equal precedence operators and append to postExp
– PUSH current operator
• If operand → Append to postExp
Step-3: POP remaining operators to postExp.

Example: (x + y) / (z * 8) → xy+z8/

PREPARED BY: SANGAMESH G B 62

 II PUC COMPUTER SCIENCE

Q. Convert infix to postfix:

Example-01: (x + y) / (z * 8) → xy+z8*/

Therefore the postfix expression is xy + z8 * /

PREPARED BY: SANGAMESH G B 63

 II PUC COMPUTER SCIENCE

Example-02:
Convert the following infix notation A + B – C * D to Postfix notation Showing stack and string
contents at each steps
Solution:

Symbol: A + B -
Action: Append Push Append Pop

Initial
stack
Empty + + -

Postfix A A AB AB+
String(PostExp)

Symbol: C * D -
Action: Append Push Append pop

* *
- - -

Postfix AB+C AB+C AB+CD AB+CD*-

String(PostExp)
Therefore Postfix expression is AB+CD*-

Example-03:
Convert the following infix notation 8 * ( 3 + 5 ) to Postfix notation Showing stack and string
contents at each steps
Solution:

Symbol: 8 * ( 3
Action: Append Push Push Append

Initial
stack ( (
Empty * * *

Postfix 8 8 * 83
String(PostExp)

Symbol: + 5 )
Action: Push Append Pop
+ +
( (
* *

Postfix 83 835 835+*

String(PostExp)
Therefore Postfix expression is 8 3 5 + *

PREPARED BY: SANGAMESH G B 64

 II PUC COMPUTER SCIENCE

Example-04
Q, Conversion of Infix to postfix: (p+q) / r*3
Symbol Stack Postfix
( (
p ( p
+ (+ p
q (+ pq
) pq+
/ / pq+r
r / pq+r/
* * pq+r/3
3 * pq+r/3*

Final Answer: Postfix expression is pq+r/3*

Example-05
Q. Conversion of Infix to postfix: A+B-C*D
Symbol Stack Postfix
A A
+ + A
B + AB
- - AB+
C - AB+C
* -* AB+C
D -* AB+CD
End AB+CD*-

Final Answer Postfix expression is AB+CD*-

Example-06
Q. Conversion of Infix to postfix: (a + (b * c) / (d – e) ) = abc*de-/+
Symbol Stack Postfix
( ( Empty
a ( a
+ (+ a
( (+( a
b (+( ab
* (+(* ab
c (+(* abc
) (+ abc*
/ (+/ abc*
( (+/( abc*
d (+/( abc*d
- (+/(- abc*d
e (+/(- abc*de
) (+/ abc*de-
) Empty abc*d-/+

Final Answer Postfix expression is abc*d-/+

PREPARED BY: SANGAMESH G B 65

 II PUC COMPUTER SCIENCE

11. Evaluation of Postfix Expression

 Algorithm: Evaluation of Postfix expression
Step-1: Input postfix expression in a variable, say postEXP
Step-2: For each character in postEXP, REPEAT Step-3
Step-3: If character is an operand
THEN PUSH character on the stack
ELSE POP two elements from the stack,
apply the operator on the popped element and
PUSH the computed value onto the Stack
Step-4: IF Stack has a single element
THEN POP the element and OUTPUT as a net result
ELSE OUTPUT “Invalid Postfix expression”
Example: 7 8 2 * 4 / +  Result 11

OR
 Algorithm: Evaluation of Postfix expression
Step-1: For each character in postfix expression:
* If operand → PUSH to stack
* If operator → POP two operands, apply operation, PUSH result
Step-2: At the end, if one item in stack → Result
Step-3: Else → Invalid expression
Example: 7 8 2 * 4 / +  Result 11

Q. What is the role of a stack in evaluating a postfix expression? Explain the process with steps.
To evaluate a postfix expression using stack:
1. Read the postfix expression left to right.
2. If an operand is encountered, push it onto the stack.
3. If an operator is encountered, pop two elements, apply the operator, and push the result back.
4. After processing, the final result will be the only value remaining in the stack.

 Examples:
 Evaluation of postfix expression
Expression: 7 4 -3 * 1 5 + / *

PREPARED BY: SANGAMESH G B 66

II PUC COMPUTER SCIENCE

Example-01:
Q. Evaluate Postfix expression: 7 8 2 * 4 / +

Final Answer: 7 8 2 * 4 / +  Result 11

Example-02:
Give a step-by-step evaluation of the postfix expression: A B * C / D *
Where A=3, B=5, C=1. D=4
Solution: Given Postfix expression: A B * C / D *
Substitute the value: A=3, B=5, C=1, D=4; Then the expression becomes: 3 5 * 1 / 4 *

Symbol: 3 5 * 1
Action: Push Push Pop Push

Initial
Stack 5 1
Empty 3 3 15 15

Symbol: / 4 * End of Input Expression

Action: Pop Push Pop Pop

Final
4 Stack
15 15 60 Empty

The Result is 60

PREPARED BY: SANGAMESH G B 67

II PUC COMPUTER SCIENCE

Example-03:
Evaluate Postfix expression: 7 4 -3 * 1 5 + / *
Solution:

Symbol: 7 4 -3 *
Action: Push Push Push Pop

Initial -3
stack 4 4 -12
Empty 7 7 7 7

Symbol: 1 5 + /
Action: Push Push Pop Pop

5
1 1 6
-12 -12 -12 -2
7 7 7 7

Symbol: * End of Input Expression

Action: Pop Pop

Final
-14 Empty
Stack

The Result is -14

PREPARED BY: SANGAMESH G B 68

 II PUC COMPUTER SCIENCE

Question and Answers

1. Write the syntax and an example of the PUSH operation in Python.
Syntax:
[Link](element)
Example:
glassStack = []
[Link]('glass1')

2. What is underflow? When does it occur in stack operations?

• Underflow( ): Trying to delete(POP) an element from empty stack, results in exception is
called as Underflow.
[Underflow is a condition where an element is attempted to be removed (POP) from an empty
stack.]
• It results in an exception because there are no elements to delete.

3. Write a program to reverse a string using stack

Solution:
def reverseString(s):
stack = []
for char in s:
[Link](char)
rev = ''
while stack:
rev += [Link]()
return rev
print(reverseString("PYTHON"))
OUTPUT:
NOHTYP

4. Implementation of PUSH operation in stack using python (Adding element to stack)

def push(s):
ele=int(input(“Enter the element:”))
[Link](ele)
print(“The stack elements after push=”, s)

5. Write an algorithm to check whether a string is palindrome or not using deque

Step-1: Start traversing string from left side, a character at a time
Step-2: Insert the character in deque as normal queue using INSERTREAR
Step-3: Repeat step-1 and step-2 for all characters of string
Step-4: Remove one character from the front end and one character from rear end of the deque
using DELETIONFRONT and DELETIONREAR
Step-5: Match these two removed characters
Step-6: If they are same then repeat Step-4 and step-5 till deque is empty or left with only one
character, eventually string is palindrome else stop as string is not palindrome

PREPARED BY: SANGAMESH G B 69

 II PUC COMPUTER SCIENCE

6. Conversion of infix expression into prefix and postfix expression

Type Infix Prefix Postfix
Notations <operand1> <Operator> <operator(s)> <operands(s)>
<operand2 <operands(s)> <operators(s)>
Example-01 x+y +xy xy+
Example-02 x*y+z +*xyz xy*z+
Example-03 3*(4+5) * 3+ 4 5 345+*
Example-04 (x+y) / (z*5) / + xy*z5 xy+z5*/
Example-05 (a+b) * (c+d) *+ab+cd ab+cd+*
Example-06 a+(b*c) % d +a%(*bc)d a(bc)*+d%

7. Convert the following Infix to Prefix

a. (A+B)*C = (+AB)*C  *+ABC
b. A+B-C = (+AB)-C  -+ABC
c. (A+B) / (X-Y) = (+AB) / (-XY)  /+AB-XY
d. A^B * C-D = (^AB) * C-D = (*^ABC)-D  -*^ABCD

8. Convert the following Infix to Postfix

e. (A+B)*C = (AB+)*C  AB+C*
f. A+B-C = (AB+)-C  AB+C-
g. (A+B) / (X-Y) = (AB+) / (XY-)  AB+XY-/
h. A^B * C-D = (AB^) * C-D = (AB^C*)-D  AB^C*D

9. Convert the following infix notations to postfix notations. Show stack and string contents at
each
Examples:
a. A + B - C * D
Postfix: AB+CD*-
b. A * ((C + D)/E)
Postfix: ACD+E/*
c. (A + B) * C
Postfix: AB+C*
d. A+B-C
Postfix: AB+C-
e. (A + B) / (X – Y)
Postfix: AB+XY-/
A^B*C-D
f. Postfix: AB^C*D-

PREPARED BY: SANGAMESH G B 70

 II PUC COMPUTER SCIENCE

 Multiple Choice Questions (MCQs)

1. What is the principle followed by stack?
a) FIFO b) LIFO c) LILO d) FILO
2. In Python, which data type is commonly used to implement a stack?
a) Tuple b) Set c) List d) Dictionary
3. What will happen if a POP operation is performed on an empty stack?
a) Overflow b) Underflow c) Top Element Removed d) Nothing Happens
4. Which of the following is NOT a real-life example of a stack?
a) Bangles worn on wrist b) Queue at a movie theatre
c) Pile of books d) Stack of chairs
5. Which method in Python list is used to remove the top element in a stack?
a) remove() b) del() c) pop() d) discard()
6. In infix expressions, where are the operators placed?
a) After operands b) Before operands c) Between operands d) At the end
7. What is postfix notation also known as?
a) Forward Polish b) Prefix c) Infix d) Reverse Polish
8. Which function checks if a stack is empty?
a) isEmpty() b) emptyStack() c) checkEmpty() d) None
9. What type of error occurs when trying to push an element into a full stack (in languages with
fixed stack size)?
a) Syntax Error b) Runtime Error c) Overflow d) Underflow
10. What would be the result of evaluating the postfix expression: 7 8 2 * 4 / +?
a) 15 b) 11 c) 14 d) 10
11. Which operator has the highest precedence in arithmetic expressions?
a) + b) - c) * d) =
12. In the conversion of infix to postfix, where are the operators stored during processing?
a) Queue b) List c) Stack d) Array
13. Which function is used to read the topmost element from the stack?
a) pop() b) top() c) peek() d) get()
14. What is the output of the top() function when the stack is empty?
a) 0 b) Error c) None d) Null
15. What is the postfix equivalent of the infix expression (x + y)/(z * 8)?
a) xy+z8*/ b) +xyz8/ c) /+xyz8 d) x+yz/8
16. Which of the following is a valid use of stack in text/image editors?
a) Spell check b) Redo/Undo c) Save file d) Crop image
17. Which stack operation returns the number of elements?
a) Size() b) length() c) count() d) getSize()
18. During infix to postfix conversion, what happens when a right parenthesis is encountered?
a) It is ignored b) It is pushed to stack
c) Operators are popped till left parenthesis d) Nothing happens
19. Which one of the following statements is FALSE about stack operations in Python (based on
the chapter)?
a) append() is used to push elements b) pop() removes the topmost element
c) We declare stack size in Python c) Stack can be implemented using list
20. What is the postfix expression equivalent of: A * ((C + D) / E)?
a) ACD+E/* b) AC+DE/ c) ACD+E/ d) AC+D/E*
21. The correct example for postfix expression is
a) *43+45 b) *3*(4+5) c) 345+* d) xy+z5*1

PREPARED BY: SANGAMESH G B 71

 II PUC COMPUTER SCIENCE

22. Choose Correct Answer

Assertion (A): A Stack follows LIFO rule
Reason (R): Insertion and deletion takes place at same end
a) Both A true, and R is the correct reason
b) Both A true, but R is not the correct reason
c) A is false, but R is correct reason
d) A is false, but R is not correct reason
23. Choose Correct Answer
Assertion (A): Stack data structure is used in accessing link of last visited webpage
Reason (R): The ordering principle is FIFO
e) Both A true, and R is the correct reason
f) Both A true, but R is not the correct reason
g) A is false, but R is correct reason
h) A is false, but R is not correct reason
24. Choose Correct Answer
Assertion (A): A Stack is a linear data structure that stores the elements in FIFO order
Reason (R): In stack a new element is added and removed from one end only
a) Both A and R are true, and R is the correct explanation of A
b) Both A and R are true, but R is not the correct explanation of A
c) A is true, but R is false
d) A is false, but R is true
25. Choose Correct Answer
Assertion (A): Stack is a linear data structure that follows Last-In-First-Out (LIFO) order.
Reason (R): In a stack, insertion and deletion happen at the same end known as TOP.
a) Both A and R are true, and R is the correct explanation of A
b) Both A and R are true, but R is not the correct explanation of A
c) A is true, but R is false
d) A is false, but R is true
26. Choose Correct Answer
Assertion (A): The pop() method in Python list implementation of a stack removes the first
element.
Reason (R): In stack implementation, elements are always inserted and removed from the
beginning of
the list.
a) Both A and R are true, and R is the correct explanation of A
b) Both A and R are true, but R is not the correct explanation of A
c) A is true, but R is false
d) A is false, but R is true
27. Choose Correct Answer
Assertion (A): Stack is a useful data structure for reversing a string.
Reason (R): Stack allows deletion of elements from the bottom, enabling reverse traversal.
a) Both A and R are true, and R is the correct explanation of A
b) Both A and R are true, but R is not the correct explanation of A
c) A is true, but R is false
d) A is false, but R is true
28. Choose Correct Answer
Assertion (A): A stack is used for matching parentheses in expressions.
Reason (R): Stack helps in storing and retrieving nested structures in reverse order.
a) Both A and R are true, and R is the correct explanation of A
b) Both A and R are true, but R is not the correct explanation of A
c) A is true, but R is false
d) A is false, but R is true

PREPARED BY: SANGAMESH G B 72

 II PUC COMPUTER SCIENCE

29. Choose Correct Answer

Assertion (A): Overflow condition occurs when an element is inserted into a full stack in Python.
Reason (R): Python lists have a fixed size and cannot grow beyond a limit.
a) Both A and R are true, and R is the correct explanation of A
b) Both A and R are true, but R is not the correct explanation of A
c) A is true, but R is false
d) A is false, but R is true
30. Choose Correct Answer
Assertion (A): Infix expressions are easy for humans to read but difficult for machines to evaluate.
Reason (R): Infix expressions require knowledge of operator precedence and parentheses
handling.
a) Both A and R are true, and R is the correct explanation of A
b) Both A and R are true, but R is not the correct explanation of A
c) A is true, but R is false
d) A is false, but R is true
31. Choose Correct Answer
Assertion (A): In postfix notation, parentheses are not required.
Reason (R): Postfix notation places operators in a way that respects operator precedence
inherently.
a) Both A and R are true, and R is the correct explanation of A
b) Both A and R are true, but R is not the correct explanation of A
c) A is true, but R is false
d) A is false, but R is true
32. Choose Correct Answer
Assertion (A): While converting an infix expression to postfix, operands are pushed onto the
stack.
Reason (R): The stack is used to hold operands and not operators.
a) Both A and R are true, and R is the correct explanation of A
b) Both A and R are true, but R is not the correct explanation of A
c) A is true, but R is false
d) A is false, but R is true
33. Choose Correct Answer
Assertion (A): In evaluation of postfix expression, operators are pushed onto the stack.
Reason (R): Stack helps evaluate binary operators from left to right.
a) Both A and R are true, and R is the correct explanation of A
b) Both A and R are true, but R is not the correct explanation of A
c) A is true, but R is false
d) A is false, but R is true
34. Choose Correct Answer
Assertion (A): Stack is a helpful structure in browser history navigation.
Reason (R): The back button uses LIFO mechanism to navigate to the previous pages.
a) Both A and R are true, and R is the correct explanation of A
b) Both A and R are true, but R is not the correct explanation of A
c) A is true, but R is false
d) A is false, but R is true

PREPARED BY: SANGAMESH G B 73

 II PUC COMPUTER SCIENCE

10. Fill in the Blanks:

1. A ______ is a linear data structure in which insertion and deletion are done from the same end.
Answer: Stack
2. Stack follows the ______ principle, where the last element added is the first one removed.
Answer: LIFO (Last-In-First-Out)
3. In Python, a stack can be implemented using the ______ data type.
Answer: list
4. The operation to insert an element into a stack is called ______.
Answer: PUSH
5. The operation to remove the topmost element from a stack is called ______.
Answer: POP
6. Attempting to remove an element from an empty stack leads to ______ condition.
Answer: Underflow
7. In stack implementation using Python list, elements are added using the ______ method.
Answer: append()
8. The ______ function in stack returns the number of elements present.
Answer: size
9. The ______ function retrieves the most recently added element without removing it.
Answer: Top
10. The postfix expression of (x + y)/(z * 8) is ______.
Answer: xy+z8*/
11. Infix notation places operators ______ the operands.
Answer: between
12. Postfix notation is also called ______ notation.
Answer: Reverse Polish
13. During infix to postfix conversion, only ______ are pushed onto the stack.
Answer: operators
14. In evaluation of postfix expression, only ______ are pushed onto the stack.
Answer: operands
15. The isEmpty() function returns
Answer: True
16. State TRUE or FALSE for the following cases:
a) Stack is a linear data structure
b) Stack does not follow LIFO rule
c) PUSH operation may result into underflow condition
d) In POSTFIX notation for expression, operators are placed after operands
Answers:
a) True
b) False
c) False
d) True

PREPARED BY: SANGAMESH G B 74

 II PUC COMPUTER SCIENCE

CHAPTER – 04
QUEUE

In this chapter:

Introduction to Queue
Operations on Queue
Implementation of Queue using Python
Introduction to Deque
Implementation of Deque using Python
1. What is a data structure?
A data structure is a specialized format for organizing and storing the data.
Examples: String, List, Set, Tuple. Array, Linked Lists, Stack, Queue, Trees, Graphs, etc.

2. What is a Queue?
A Queue is a linear data structure where elements are inserted and deleted from different ends.

 Queue follows the ordering principle of First-In First-Out (FIFO)

 Queue is also known as a First come First Served (FCFS) approach
 Front and Rear are used to indicate beginning and end of the Queue.
 In Queue, Insertion occurs at Rear (Tail) end of the Queue
 In Queue, Deletion occurs at Front (Head) end of the Queue
 In python, A Queue can be implemented using the “list” data type or data structure
 The basic operations of Queue are: Enqueue( ) and Dequeue( )

3. Applications of Queue in Real-life

The applications of Queue in real life are:
a. Queue in railway station for tickets
b. Queue in Movie theaters to buy tickets
c. Queue in airports for security checkup
d. Queue of vehicles in petrol pumps
e. Queue in ATM centers
f. Queue in Toll booths

4. Applications of Queue in Computer Programming

The Applications of Queue in Programming are:
a. Handling multiple users requests on a Web server
b. Job scheduling in multitasking operating system
c. Managing multiple print requests in a printer queue
d. Simulation and modeling
e. Various features of operating System
f. Multi-programming flat form systems
g. Different types of scheduling algorithms
h. Used in round robin technique or algorithm
i. CPU task in scheduling in Operating Systems

PREPARED BY: SANGAMESH G B 75

 II PUC COMPUTER SCIENCE

5. Operations of Queue
The operations performed on Queue are:
a. Enqueue( )
b. Dequeue( )
c. isEmpty( )
d. isFull( )
e. Peek( )
f. Size( )

a. Enqueue( ): Adding a new element into the Queue in Rear end

b. Dequeue( ): Deleting an element from the Queue from Front end
c. isEmpty( ): To check whether Queue is empty or not
d. isFull( ): To check whether Queue is full or not
e. Peek( ): To view the element at front end of the queue without removing
f. Size( ): To check the number of elements in Queue

6. Visual Example (Queue of alphabets)

enqueue('Z') → Z
enqueue('X') → Z X
enqueue('C') → Z X C
dequeue( ) → X C
enqueue('V') → X C V
dequeue( ) → CV
dequeue( ) →V

Visual Example (Queue of alphabets)

Operation performed Status of Queue after operation

Enqueue(Z) F Z R

Enqueue(X) F Z X R

Enqueue(C) F Z X C R

Dequeue( ) F X C R

Enqueue(V) F X C V R

Dequeue( ) F C V R

Dequeue F V R

Figure: various Stages of operations

PREPARED BY: SANGAMESH G B 76

 II PUC COMPUTER SCIENCE

Q. For the elements Z, X and C perform enqueuer and dequeuer operations:

Solution:
Initially Queue is empty [ ]
Operation Queue Status
Enqueue(Z) [Z]
Enqueue(X) [ Z, X ]

Enqueue(C) [ Z, X, C ]
Dequeue( ) [ X, C ]

Dequeue( ) [C]

Dequeue( ) []

7. Implementation of Queue in python

Functions :
# Creating Queue
myQueue = list()

# To add elements to Rear end of queue  Enqueue( )

def enqueue(myQueue, element):
[Link](element)

#To check queue is empty  isEmpty( )

def isEmpty(myQueue):
if len(myQueue) = = 0
return True
Else:
return False

#To delete element from Front end of Queue  Dequeue( )

def dequeue(myQueue):
if isEmpty(myQueue):
print(“Queue is empty/Underflow")
return None
else:
return [Link](0)

#To check size of Queue

def size(myQueue):
return len(myQueue)

#To check front end of Queue  peek( )

def peek(myQueue):
if isEmpty(myQueue):
print("Queue is empty/Underflow")
return None
else:
return myQueue[0]

 Note: The append( ) function always adds an element at the end of the list. Hence Rear of the
queue

PREPARED BY: SANGAMESH G B 77

II PUC COMPUTER SCIENCE

 Programming Example:

Program : Simulation of a Queue in a Bank

myQueue = list()

#Each persons to be assigned a code as P1, P2, P3 _ _ _ _ _

element = input("Enter person’s code to enter in queue: ")
enqueue(myQueue, element)
element = input("Enter person’s code for insertion in queue: ")
enqueue(myQueue, element)

print("Person removed from queue is:", dequeue(myQueue))

print("Number of people in the queue is:", size(myQueue))

element = input("Enter person’s code to enter in queue: ")

enqueue(myQueue, element)

element = input("Enter person’s code to enter in queue: ")

enqueue(myQueue, element)

element = input("Enter person’s code to enter in queue: ")

enqueue(myQueue, element)

print("Now removing remaining people from queue:")

while not isEmpty(myQueue):

print("Person removed from queue is", dequeue(myQueue))

_______________________________________________________________________________

Output:

PREPARED BY: SANGAMESH G B 78

 II PUC COMPUTER SCIENCE

Introduction to Deque (Deck)

 Note: Deque (Pronounced  Deck)

8. What is Deque (Double Ended Queue)?

A Deque (Double Ended Queue) is a data structure that allows insertion and deletion of elements
occur from both ends (any ends)

 Deque is also called as Double Ended Queue

 Deque is a version (type) of Queue.
 Deque can be Stack(LIFO) and Queue(FIFO)
 Insertion occurs at both Rear and Front ends
 Deletion occurs at both Rear and Front ends
 Rear is also known as Tail
 Front is also known as Head

9. Applications of Deque in Real-life:

The Applications of real-life are:
a. Re-entry at ticket counter
b. Toll booth queue re-direction

10. Applications of Deque in Computer Programming

The applications of deque in Computer programming are:
a. Browser history navigation
b. Undo and Redo in text Editors
c. Palindrome Checking
d. Multi-processor scheduling program
e. Vehicles in toll plaza. Enter and Go from both ends.
f. Customer Care Calls

11. Operation on Deque (Double Ended Queue)

The operations performed on Deque are:
a. InsertFront( )
b. InsertRear( )
c. DeletionFront( )
d. DeletionRear( )
e. isEmpty( )
f. getFront( )
g. getRear( )

a) InsertFront( ): It is used to add new element into the deque at Front end
b) InsertRear( ): It is used to add new element into the deque at Rear end. (Same as normal queue)
c) DeletionFront( ): It is used to delete an element from deque from Front end (same as normal
Quque)
d) DeletionRear( ): It is used to delete an element from deque from Rear end.
e) isEmpty( ): It is used to check if deck is empty or not.
f) getFront( ): It is used to view Front element without removing
g) getRear( ): It is used to view Rear element without removing

PREPARED BY: SANGAMESH G B 79

 II PUC COMPUTER SCIENCE

12. Palindrome using deque( Double Ended Queue)

Algorithm  To check whether string is palindrome using Deque

 Describe the steps of palindrome checking using deque.

Step-1: Traverse the string character by character from left to right.
Step-2: Insert each character into the deque from the rear.
Step-3: Remove one character from the front and one from the rear, and compare.
Step-4: Repeat until all characters are compared or only one remains.
Step-5: If all pairs match  Then the string is palindrome; Otherwise, it is not

Example:
Algorithm: To check whether string is palindrome using Deque

PREPARED BY: SANGAMESH G B 80

 II PUC COMPUTER SCIENCE

13. Implementation of Deque (Double Ended Queue) using Python

Functions:
# Creating Deque
mydeque = list()

# To add elements to Rear end of deque  InsertRear( ) and Append( )

def insertRear(mydeque, element):
[Link](element)

# To add elements to Front end of deque  InsertFront( ) and Append( )

def insertFront(mydeque, element):
[Link](element)

#To delete element from Front end of deque  DeletionFront( )

def deleteFront(mydeque):
if isEmpty(mydeque):
print(“Deque is empty/Underflow")
return None
else:
return [Link](0)

#To delete element from Rear end of deque  DeletionRear( )

def deleteRear(mydeque):
if isEmpty(mydeque):
print(“Deque is empty/Underflow")
return None
else:
return [Link]( )

#To check front element of deque  getFront( )

def getFront(mydeque):
if isEmpty(mydeque):
print(“Deque is empty/Underflow")
return None
else:
return mydeque[0]

#To check Rear element of deque  getRear( )

def getRear(mydeque):
if isEmpty(mydeque):
print(“Deque is empty/Underflow")
return None
else:
return mydeque[len(mydeque) -1]

#To check deque is empty  isEmpty( )

def isEmpty(mydeque):
if len(mydeque) = = 0
return True
else:
return False

PREPARED BY: SANGAMESH G B 81

 II PUC COMPUTER SCIENCE

14. Menu-driven Deque Program

Menu-driven Deque Program
def main():
dQu = list()
choice = int(input("Enter 1 to use as queue, 2 otherwise: "))

if choice == 1:
element = input("Data for insertion at rear: ")
insertRear(dQu, element)
print("Data at front:", getFront(dQu))
element = input("Data for insertion at rear: ")
insertRear(dQu, element)
print("Removed:", deletionFront(dQu))
print("Removed:", deletionFront(dQu))
else:
element = input("Data for insertion at front: ")
insertFront(dQu, element)
print("Data at rear:", getRear(dQu))
element = input("Data for insertion at front: ")
insertFront(dQu, element)
print("Removed:", deletionRear(dQu))
print("Removed:", deletionRear(dQu))

PREPARED BY: SANGAMESH G B 82

 II PUC COMPUTER SCIENCE

 Multiple Choice Questions (MCQs)

1. What principle does a queue follow?
a) FIFO b) LIFO c) FILO d) Random
2. In a queue, the element is inserted at the:
a) Middle b) Front c) Rear d) Random position
3. What happens when you try to dequeue from an empty queue?
a) Overflow b) Error c) Underflow d) Crash
4. Which operation is used to add an element to a queue?
a) Pop b) Dequeue c) Peek d) Enqueue
5. In a queue implemented with a Python list, [Link](0) removes the element from:
a) End b) Middle c) Front d) None
6. What does the isEmpty() function check in a queue?
a) Queue is full b) Queue has only one item
c) Queue has elements d) Queue is empty
7. In the context of a printer, how are print jobs managed?
a) LIFO b) FIFO c) Random d) Priority only
8. Which Python function is used to insert an element at the rear in a queue?
a) insert() b) append() c) pop() d) push()
9. The peek() operation in queue is used to:
a) Delete the last element b) Check if queue is full
c) View the front element without deleting d) View the rear element
10. In the bank queue example, which operation is used when a person enters the queue?
a) Dequeue b) Append c) Peek d) Enqueue
11. Which of the following is NOT required in Python while implementing a queue using a list?
a) isFull() b) isEmpty() c) peek() d) dequeue()
12. What is a deque?
a) A type of priority queue b) Queue with limited size
c) Double-ended queue d) Stack with extra features
13. Which operation removes an element from the rear of a deque?
a) deletionFront b) pop(0) c) deletionRear d) enqueue
14. If you insert and delete elements from the same end in a deque, it behaves as a:
a) Queue b) Stack c) List d) Tree
15. What is the output of getRear(myDeque) if myDeque = [23, 45, 67]?
a) 23 b) 45 c) 67 d) Error
16. In palindrome checking using deque, characters are compared from:
a) Front only b) Rear only c) Front and Rear d) Middle
17. What does [Link](0, element) do in deque?
a) Inserts at rear b) Inserts at front
c) Replaces the first element d) Deletes the first element
18. In Python, what will pop() do if no index is given in a list?
a) Removes front b) Removes last c) Removes middle d) None of the above
19. In a multitasking OS, how are jobs scheduled if FIFO is used?
a) The latest job is processed first b) Jobs are randomly selected
c) Only one job is processed permanently d) Jobs are processed in the order they arrive
20. Which operation would you perform to add an element at the front of a deque?
a) insertRear() b) append() c) insertFront() d) enqueue()
21. Deque is a version of queue which allows insertion and deletion at
a) Front end b) rear end c) both ends d) not both ends
22. An arrangement of linear data structure in which insertion and removal of elements can happen
from any end (both ends) is known as
a) Stack b) Queue c) Deque d) Enqueue

PREPARED BY: SANGAMESH G B 83

 II PUC COMPUTER SCIENCE

23. The operation used to view elements at the front of the queue, without removing it from the queue
is
a) Dequeue b) Peek c) Enqueue d) Tell
24. In which data structure can insertion and deletion of elements occur from both end (any ends)?
a) Stack b) Queue c) Deque d) Enqueue
25. In a queue, the end where elements are added is called
a) Front b) Rear c) HEAD d) START
26. Which built-in method is used to remove an item from REAR end of the Deque?
a) POP(0) b) append(item) c) POP() d) remove(item)

PREPARED BY: SANGAMESH G B 84

 II PUC COMPUTER SCIENCE

 Exercise
Fill in the Blanks:
1. ____________________ is a linear list of elements in which insertion and deletion takes place
from different ends.
Answer: Queue
2. Operations on a queue are performed in __________________ order.
Answer: FIFO (First In First Out)
3. Insertion operation in a queue is called ______________ and deletion operation in a queue is
called ___________________.
Answer: enqueue, dequeue
4. Deletion of elements is performed from _______________ end of the queue.
Answer: front
5. Elements ‘A’, ‘S’, ‘D’ and ‘F’ are present in the queue, and they are deleted one at a time,
________________________ is the sequence of element received.
Answer: A, S, D, F
6. _______________ is a data structure where elements can be added or removed at either end, but
not in the middle.
Answer: Deque
7. A deque contains ‘z’, ‘x’, ‘c’, ‘v’ and ‘b’. Elements received after deletion are ‘z’, ‘b’, ‘v’, ‘x’ and
‘c’. ____________________________ is the sequence of deletion operation performed on deque.
Answer: deletionFront(), deletionRear(), deletionRear(), deletionFront(), deletionFront()
8. A queue is a linear list of elements in which insertion takes place at the __________ and deletion at
the __________.
Answer: rear, front
9. Queue follows the __________ strategy, where the first element inserted is the first one to be
removed.
Answer: FIFO (First In First Out)
10. The operation to insert an element into a queue is called __________.
Answer: enqueue
11. The operation to remove an element from a queue is called __________.
Answer: dequeue
12. Attempting to remove an element from an empty queue results in an error called __________.
Answer: underflow
13. In Python, the __________ method is used to add an element at the rear of a list.
Answer: append()
14. A queue implemented using Python list does not require an __________ function because the list
size is dynamic.
Answer: isFull
15. The __________ function is used to check if the queue contains no elements.
Answer: isEmpty()
16. To view the front element of a queue without removing it, the __________ operation is used.
Answer: peek
17. A __________ allows insertion and deletion from both ends of the list.
Answer: deque (double-ended queue)
18. In Python, elements can be inserted at the front of a deque using the __________ method.
Answer: insert(0, element)
19. To delete an element from the rear of a deque, the __________ method is used in Python.
Answer: pop()
20. To remove the front element from a deque, the __________ method is used with index 0.
Answer: pop(0)
21. A data structure that can behave like both a queue and a stack is known as __________.
Answer: deque

PREPARED BY: SANGAMESH G B 85

 II PUC COMPUTER SCIENCE

22. In palindrome checking using deque, characters are compared by removing from __________ and
__________ ends.
Answer: front, rear

 Exercise:
1. Compare and contrast queue with stack.
[Link] Queue Stack
01 Follows FIFO (First In First Out) Follows LIFO (Last In First Out)
02 Insertion at rear, deletion at front Insertion and deletion at the same end
03 Used in print queues, job scheduling Used in undo operations, expression
evaluation

2. How is queue data type different from deque data type?

Compare and contrast queue with Deque.
[Link] Queue Deque
01 Insertion only at rear Insertion at both front and rear ends
02 Deletion only from front Deletion from both front and rear ends
03 Less flexible More flexible
04 Cannot simulate stack behaviour Can simulate both stack and Queue

3. Explain with examples how queues are used in real life and in computer science applications.
Answer:
Real-life applications:
a. Bank queues: First customer is served first.
b. Toll booths: Vehicles are allowed in FIFO order.
c. Customer care calls (IVRS): Callers wait in order of arrival.

Computer science applications:

a. Print queue: Print jobs are handled one by one in order.
(Managing multiple print requests in a printer queue)
b. Web server: Handles requests in FIFO order.
(Handling multiple users request on a web server)
c. Job scheduling in OS: Jobs wait in queue for processor time
(Job scheduling in a multitasking operating system)
OR
Give the application of queues in computer science.
a. Suppose there is a web-server hosting a web-site to declare results. This server can handle a
maximum of 50 concurrent requests to view results. So to serve thousands of user requests, a
Queue would be the most appropriate data structure to use.
b. Some Operating Systems (OS) are required to handle multiple tasks called - jobs, seeking to
use the processor. In a multitasking operating system, jobs are lined up (queued) and then
given access to the processor according to some order. The simplest way is to give access to
the processor on a FIFO basis, that is according to the order in which the jobs arrive with a
request for the processor.
c. When we send print commands from multiple files from the same computer or from different
computers using a shared printer. Queue is used to send print commands using a shared printer

4. How does FIFO describe queue?

FIFO stands for First-In-First-Out, which means that the element inserted first in the queue is the
one that is removed first. It ensures that elements are served in the same order as they arrive, just
like people standing in a queue.

PREPARED BY: SANGAMESH G B 86

 II PUC COMPUTER SCIENCE

5. What is overflow and when does it occur in a queue?

Overflow is an error that occurs when a dequeue operation is attempted on an full queue, i.e.,
when there are full queue to insert a new element.

6. What is underflow and when does it occur in a queue?

Underflow is an error that occurs when a dequeue operation is attempted on an empty queue, i.e.,
when there are no elements to remove.

7. Write a menu-driven Python program using queue to implement movement of shuttlecock in its
box.
Solution:
(Interpretation: Assuming each shuttlecock is added and removed in FIFO order)

def enqueue(box, shuttle):

[Link](shuttle)

def dequeue(box):
if len(box) > 0:
return [Link](0)
else:
return "Box is empty"

def isEmpty(box):
return len(box) == 0

def main():
box = []
while True:
print("\n1. Add Shuttlecock")
print("2. Remove Shuttlecock")
print("3. Exit")
choice = int(input("Enter choice: "))
if choice == 1:
shuttle = input("Enter shuttlecock code: ")
enqueue(box, shuttle)
elif choice == 2:
print("Removed:", dequeue(box))
elif choice == 3:
break
else:
print("Invalid choice")

8. Show the status of queue after each operation:

Operations:
enqueue(34)
enqueue(54)
dequeue()
enqueue(12)
dequeue()
enqueue(61)

PREPARED BY: SANGAMESH G B 87

 II PUC COMPUTER SCIENCE

peek()
dequeue()
dequeue()
dequeue()
dequeue()
enqueue(1)

Solution: (Step-by-step deque status):

1. enqueue(34) → [34]
2. enqueue(54) → [34, 54]
3. dequeue() → [54]`
4. enqueue(12) → [54, 12]
5. dequeue() → [12]
6. enqueue(61) → [12, 61]
7. peek() → 12
8. dequeue() → [61]
9. dequeue() → []
10. dequeue() → Underflow (queue is empty)
11. dequeue() → Underflow
12. enqueue(1) → [1]

9. Show the status of deque after each operation:

Operations:
peek()
insertFront(12)
insertRear(67)
deletionFront()
insertRear(43)
deletionRear()
deletionFront()
deletionRear()

Solution: (Step-by-step deque status):

1. peek() → Deque is empty
2. insertFront(12) → [12]
3. insertRear(67) → [12, 67]
4. deletionFront() → [67]
5. insertRear(43) → [67, 43]
6. deletionRear() → [67]
7. deletionFront() → []
8. deletionRear() → Underflow (deque is empty)

PREPARED BY: SANGAMESH G B 88

 II PUC COMPUTER SCIENCE

10. Write a Python program to check whether the given string is palindrome or not using deque.

def isPalindrome(string):
deque = [ ]
for ch in string:
[Link](ch)

while len(deque) > 1:

front = [Link](0)
rear = [Link]()
if front != rear:
return False
return True

Example usage
s = input("Enter a string: ")
if isPalindrome(s):
print("Palindrome")
else:
print("Not a palindrome”)

11. Explain any five applications of deque from real life and computer science contexts.
A deque (double-ended queue) is a linear data structure that allows insertion and deletion at both
ends—front and rear. Due to this flexibility, deque is used in various real-life and computer science
scenarios:

Computer science applications:

a. Re-entry in Ticket Queue (Real-life):
A person who has already purchased a train ticket may return to the counter for a query and be
allowed to rejoin from the front of the queue instead of the rear. This is possible only with a
deque structure.
b. Toll Booth Management (Real-life):
At highway toll plazas, if one booth becomes free, vehicles from the rear of other queues may
shift to the front of the available booth’s queue, involving both front and rear deletions and
insertions – ideal for deque.
c. Palindrome Checking (Computer Science):
Characters of a string are inserted into a deque from the rear. Then, characters are compared
and removed from both front and rear to check if the string is a palindrome.
d. Undo/Redo Functionality in Editors:
The undo/redo feature in text editors uses deque, where operations can be pushed and popped
from either end, simulating both stack and queue behavior.
e. Browser Tab History Navigation:
URLs visited in a browser are stored in a deque. The most recent URL is reopened first
(LIFO),
and the oldest can be discarded from the rear (FIFO), based on memory limits.

Thus, deque is a versatile data structure capable of handling complex real-world and
programming scenarios efficiently.

PREPARED BY: SANGAMESH G B 89

II PUC COMPUTER SCIENCE

PREPARED BY: SANGAMESH G B 90

 II PUC COMPUTER SCIENCE

CHAPTER – 05
SORTING

In this chapter:

Introduction
Bubble Sort
Selection Sort
Insertion sort
Time Complexity of Algorithm
1. What is a sorting?
It is a process of placing or re-arranging a collection of elements into a particular order (i.e.
Ascending, Descending, Alphabetical etc.) in a list.

 Advantages:
 It is essential for easy data retrieval
 It is used for efficient searching
 It is used for rearranging elements for efficient access

 Common Applications:
 Dictionaries (Alphabetical order)
 Exam seating arrangements (Register number, name subject wise etc.)
 Sorting by weight or height

2. Different types of Sorting techniques

The different types of sorting techniques are:
 Bubble Sort
 Selection sort
 Insertion Sort

i. Bubble Sort:
Bubble sort is the simplest sorting algorithm that works repeatedly swapping the adjacent
elements in case they are unordered in n-1 passes.
• The result in a time complexity of bubble sort is O(n2)

 Steps for processing the bubble sort:

Concept
o Compares adjacent elements and swaps them if they are in the wrong order.
o After each pass, the largest unsorted element “bubbles up” to its correct position.
o Requires n – 1 passes for a list of size n.

 What is the basic principle behind bubble sort?

Bubble sort works repeatedly comparing adjacent elements in a list and swapping them if they
are in wrong order.
In each pass, the largest element “Bubble Up” to its correct position. This process continues for
multiple passes until the entire list is sorted.
For a list with n elements, a total of n-1 passes are required and with every pass, the number of
elements to be compared decreases

PREPARED BY: SANGAMESH G B 91

II PUC COMPUTER SCIENCE

 Demonstrates the working of the bubble sort method

(Arranging the elements in Ascending order)

Example-01 :
Arrange the elements of the following list1 having 6 elements
list1 = [8, 7, 13, 1. -9, 4]

Solution: Bubble Sort Passes

 Let us consider a list having 6 elements as list1 = [8, 7, 13, 1, -9, 4]
 Each pass compares adjacent elements and swaps if needed.
Pass 1:
[8, 7, 13, 1, -9, 4]

→ Swap 8 and 7 → [7, 8, 13, 1, -9, 4]

→ No Swap (8,13)
→ Swap 13 and 1 → [7, 8, 1, 13, -9, 4]
→ Swap 13 and -9 → [7, 8, 1, -9, 13, 4]
→ Swap 13 and 4 → [7, 8, 1, -9, 4, 13]

Pass 2:
[7, 8, 1, -9, 4, 13]

→ No Swap (7,8)
→ Swap 8 and 1 → [7, 1, 8, -9, 4, 13]
→ Swap 8 and -9 → [7, 1, -9, 8, 4, 13]
→ Swap 8 and 4 → [7, 1, -9, 4, 8, 13]

Pass 3:
[7, 1, -9, 4, 8, 13]

→ Swap 7 and 1 → [1, 7, -9, 4, 8, 13]

→ Swap 7 and -9 → [1, -9, 7, 4, 8, 13]
→ Swap 7 and 4 → [1, -9, 4, 7, 8, 13]

Pass 4:
[1, -9, 4, 7, 8, 13]
→ Swap 1 and -9 → [-9, 1, 4, 7, 8, 13]

Pass 5:
No swaps → Sorting complete.
Final list: [-9, 1, 4, 7, 8, 13]

Optimization Tip: If no swaps occur in a pass, the list is already sorted — the algorithm can
be terminated early

PREPARED BY: SANGAMESH G B 92

II PUC COMPUTER SCIENCE

In Visual view :- Bubble Sort

PREPARED BY: SANGAMESH G B 93

II PUC COMPUTER SCIENCE

 Algorithm: Bubble sorting Technique

Q. Write an algorithm to perform Bubble sort technique
OR
Write an algorithm to sort an element in a list using Bubble sort method
Solution:
Step-1: Set i = 0

Step-2: While i < n Repeat Steps 3 to 8

Step-3: Set j = 0

Step-4: While j < n - i - 1 Repeat Steps 5 to 7

Step-5: If numList[j] > numList[j+1], Then

Step-6: Swap numList[j] and numList[j+1]

Step-7: SET j = j + 1

Step-8: SET i = i + 1

 Implementation of Bubble sort using Python Programming

Program: Bubble Sort

def bubble_Sort(list1):
n = len(list1)
for i in range(n):
for j in range(0, n-i-1):
if list1[j] > list1[j+1]:
list1[j], list1[j+1] = list1[j+1], list1[j]
numList = [8, 7, 13, 1, -9, 4]
bubble_Sort(numList)
print("The sorted list is:")
for i in range(len(numList)):
print(numList[i], end=" ")

PREPARED BY: SANGAMESH G B 94

II PUC COMPUTER SCIENCE

ii. Selection Sort:

In selection sort, the smallest element is selected and swapped with the leftmost elements and
becomes part of sorted list and process continue till last elements.

 The time complexity of selection sort is O(n2) in all cases (best, average, and worst)

 Steps for processing the Selection sort:

Concept
 The list is divided into sorted and unsorted parts.
 The smallest element from the unsorted list is selected and swapped with the first unsorted
element.
 Requires n – 1 passes for n elements.

 Demonstrates the working of the Selection sort method (Arranging the elements in Ascending
order)
Example-01 :
Arrange the elements of the following list1 having 6 elements
list1 = [8, 7, 13, 1. -9, 4]

Solution:
Selection Sort Passes:
 Let us consider a list having 6 elements as list1 = [8, 7, 13, 1, -9, 4]

Sorted List Unsorted List

Pass 1 - Smallest is -9 → Swap with 8
[-9, 7, 13, 1, 8, 4]  [-9] [7, 13, 1, 8, 4]

Pass 2 - Smallest in [7, 13, 1, 8, 4] is 1 → Swap with 7

[-9, 1, 13, 7, 8, 4]  [-9, 1] [13, 7, 8, 4]

Pass 3 - Smallest in [13,7,8,4] is 4 → Swap with 13

[-9, 1, 4, 7, 8, 13]  [-9, 1, 4] [7, 8, 13]

Pass 4 - Smallest in [7,8,13] is 7 (already in place)

[-9, 1, 4, 7, 8, 13]  [-9, 1, 4, 7] [8, 13]

Pass 5 - Already sorted

[-9, 1, 4, 7, 8, 13]  [-9, 1, 4, 7, 8, 13] Sorted list

PREPARED BY: SANGAMESH G B 95

II PUC COMPUTER SCIENCE

Visual View: Selection Sort Method

Pass-1 Pass-2

8 7 13 1 -9 4 -9 7 13 1 8 4

8 7 13 1 -9 4 -9 7 13 1 8 4

8 7 13 1 -9 4 -9 7 13 1 8 4

8 7 13 1 -9 4 -9 7 13 1 8 4
Swap

8 7 13 1 -9 4 -9 7 13 1 8 4
Swap Swap 1 with 7

8 7 13 1 -9 4 -9 1 13 7 8 4
Swap -9 with 8 Sorted Unsorted

-9 7 13 1 8 4
Sorted Unsorted

Pass-3 Pass-4

-9 1 13 7 8 4 -9 1 4 7 8 13

-9 1 13 7 8 4 -9 1 4 7 8 13
No Swap

-9 1 13 7 8 4 -9 1 4 7 8 13
Swap No Swap already sorted

-9 1 13 7 8 4 -9 1 4 7 8 13
Swap 4 with 13 Sorted Unsorted

-9 1 4 7 8 13
Sorted Unsorted

Pass-5 Final Sorted list is:

-9 1 4 7 8 13 -9 1 4 7 8 13
No Swap

-9 1 4 7 8 13
No Swap already sorted

-9 1 4 7 8 13
Sorted

PREPARED BY: SANGAMESH G B 96

II PUC COMPUTER SCIENCE

Example-02:
Write the process to sort the following elements using selection sort method. 90, 30, -2, 6, 45, 72
Selection Sort Method
Pass-1 Pass-2

90 30 -2 6 45 72 -2 30 90 6 45 72

90 30 -2 6 45 72 -2 30 90 6 45 72

90 30 -2 6 45 72 -2 30 90 6 45 72

90 30 -2 6 45 72 -2 30 90 6 45 72
Swap

90 30 -2 6 45 72 -2 30 90 6 45 72
Swap Swap 6 with 30

90 30 -2 6 45 72 -2 6 90 30 45 72
Swap -2 with 90 Sorted Unsorted

-2 30 90 6 45 72
Sorted Unsorted
Pass-3 Pass-4

-2 6 90 30 45 72 -2 6 30 90 45 72

-2 6 90 30 45 72 -2 6 30 90 45 72
Swap

-2 6 90 30 45 72 -2 6 30 90 45 72
Swap Swap 45 with 90

-2 6 90 30 45 72 -2 6 30 45 90 72
Swap 30 with 90 Sorted Unsorted

-2 6 30 90 45 72
Sorted Unsorted
Pass-5 Final Sorted list is:

-2 6 30 45 90 72 -2 6 30 45 72 90
Swap

-2 6 30 45 90 72
Swap 72 with 90
-2 6 30 45 72 90
Sorted

PREPARED BY: SANGAMESH G B 97

II PUC COMPUTER SCIENCE

 Algorithm: Selection sorting Technique

Q. Write an algorithm to perform Selection sort technique
OR
Write an algorithm to sort an element in a list using Selection sort method
Solution:
Step-1: Set i = 0

Step-2: While i < n Repeat: Steps 3 to 11

Step-3: Set min = i, flag = 0

Step-4: Set j = i + 1

Step-5: While j < n Repeat: Steps 6 to 10

Step-6: If numList[j] < numList[min]:

Step-7: min = j

Step-8: flag = 1

Step-9: If flag == 1:

Step-10: Swap numList[i], numList[min]

Step-11: Set i = i + 1

 Implementation of Selection sort using Python Programming

Program: Selection Sort (Method-1)
def selection_Sort(list2):
flag = 0
n=len(list2)
for i in range(n) :
min=i
for j in range (i+1, len(list2)):
if list2[j] < list2[min]:
min=j
flag=1
if flag == 1:
list2[min], list[i] = list2[i], list2[min]

numList = [8, 7, 13, 1, -9, 4]

selection_Sort(numList)
print("The sorted list is:")
for i in range(len(numList)):
print(numList[i], end=" ")

Output:
The sorted list is :
-9 1 4 7 8 13

PREPARED BY: SANGAMESH G B 98

 II PUC COMPUTER SCIENCE

OR
Program: Selection Sort (Method-2)
def selection_Sort(list2):
n = len(list2)
for i in range(n):
min = i
for j in range(i + 1, n):
if list2[j] < list2[min]:
min = j
list2[i], list2[min] = list2[min], list2[i]

numList = [8, 7, 13, 1, -9, 4]

selection_Sort(numList)
print("The sorted list is:")
for i in range(len(numList)):
print(numList[i], end=" ")

iii. Insertion sort:

Insertion sort places the element of a list at its suitable place in each pass, It is similar to the
placing of cards at its right position while playing cards.
 The time complexity of insertion sort based on the initial order of the elements in the input list:
Best case is O(n), average and worst case is O(n2)
Concept
 Elements from the unsorted part are picked and inserted into the correct position of the sorted
part.
 Like arranging cards in hand

 Demonstrates the working of the Insertion sort method

(Arranging the elements in Ascending order)
Example-01 :
Arrange the elements of the following list1 having 6 elements
list1 = [8, 7, 3, 1. -9, 4]
Solution:
Insertion Sort Passes:
Let us consider a list having 6 elements as list1 = [8, 7, 13, 1, -9, 4]
Initial List: [8, 7, 13, 1, -9, 4]

Pass-1: Insert 7 into sorted [8]

[7, 8, 13, 1, -9, 4]

Pass-2: Insert 13 into sorted [7,8]

[7, 8, 13, 1, -9, 4]

Pass-3: Insert 1 into sorted [7,8,13]

[1, 7, 8, 13, -9, 4]

Pass:4: Insert -9 into sorted [1,7,8,13]

[-9, 1, 7, 8, 13, 4]
Pass-5: Insert 4 into sorted [-9,1,7,8,13]
[-9, 1, 4, 7, 8, 13]

PREPARED BY: SANGAMESH G B 99

II PUC COMPUTER SCIENCE

Example-01: Visual View – Insertion Sort

PREPARED BY: SANGAMESH G B 100

II PUC COMPUTER SCIENCE

Example-02:
Write the process to sort the following elements using insertion sort method, 80, 60, 20, 40, 50, 11
Insertion Sort Method
Pass-1 Pass-4
Swap Swap

80 60 20 40 50 11 20 40 60 80 50 11
Swap
60 80 20 40 50 11
20 40 60 50 80 11
Pass-2 No Swap
Swap
20 40 50 60 80 11
60 80 20 40 50 11
Swap 20 40 50 60 80 11

60 20 80 40 50 11
20 60 80 40 50 11

Pass-3 Pass-5
Swap Swap

20 60 80 40 50 11 20 40 50 60 80 11
Swap Swap

20 60 40 80 50 11 20 40 50 60 11 80
No Swap Swap

20 40 60 80 50 11 20 40 50 11 60 80
Swap
20 40 60 80 50 11
20 40 11 50 60 80
Swap

20 11 40 50 60 80

11 20 40 50 60 80
Final Sort list is:
11 20 40 50 60 80

PREPARED BY: SANGAMESH G B 101

II PUC COMPUTER SCIENCE

 Algorithm: Insertion sorting Technique

Q. Write an algorithm to perform Insertion sort technique
OR
Write an algorithm to sort an element in a list using Insertion sort method
Solution:
Step-1: Set i = 1

Step-2: While i < n Repeat: Steps 3 to 9

Step-3: temp = numList[i]

Step-4: Set j = i - 1

Step-5: While j > 0 and numList[j] > temp Repeat: Steps 6 to 7

Step-6: numList[j+1] = numList[j]

Step-7: Set j = j - 1

Step-8: numList[j+1] = temp # insert temp at position j

Step-9: Set i = i + 1

 Implementation of Insertion sort using Python Programming

Program: Insertion Sort

def insertion_Sort(list3):
n = len(list3)
for i in range(n):
temp = list3[i]
j = i-1
while j >= 0 and temp < list3[j]:
list3[j+1] = list3[j]
j=j-1
list3[j+1] = temp

numList = [8, 7, 13, 1, -9, 4]

insertion_Sort(numList)
print("The sorted list is:")
for i in range(len(numList)):
print(numList[i], end=" ")

Output:
The sorted list is :
-9 1 4 7 8 13

PREPARED BY: SANGAMESH G B 102

 II PUC COMPUTER SCIENCE

3. Time complexity of algorithm:

Time complexity is performed to explain how an algorithm will perform when the input grows
larger and how fast an algorithm will execute.
OR
The amount of time taken for execution of an algorithm is called Time complexity

 Time complexity is expressing using Big-O notation

Types of Time Complexity:

 How to estimate the time complexity of algorithm (Basic Complexity Concepts)
a. Constant Time (O(1)): No loops.
The input time remains constant regardless of input size
[Algorithm without any loop, time remains constant]
b. Linear Time (O(n)): Single(one) loop.
The execution time grows linearly with the input size
[Algorithm with one loop, time grows linearly]
c. Quadratic Time (O(n²)): Nested loops.
The execution time is proportional to the square of the input size
[Algorithm with nested loops, time grows an n²]
d. Exponential Time O(2^n):
The execution time doubles with each increase in the input size
e. Logarithmic Time O(log n):
The execution time grows logarithmically with the input size
f. Linearithmic Time O(n log n):
The execution time grows linearly with the input size

Note: All three sorting algorithms  (Bubble sort, Selection sort, Insertion sort) have O(n²)
complexity due to nested loops.

OR
Time complexity of algorithm
The amount of time taken for execution of an algorithm is called Time complexity
• Time complexity is performed to explain how an algorithm will perform when the input grows
larger and how fast an algorithm will execute.
• Helps choose suitable algorithms for large datasets
• Time complexity is expressing using Big-O notation

 How to estimate the time complexity of algorithm

 When algorithm will not have any loop then its time complexity will be 1 and it is called as
constant time algorithm
 When algorithms have any loop (1, n) then its time complexity will be n and it is called as linear
time algorithm.
 When algorithms have any nested loop (n and m) then its time complexity will be m*n and it is
called as Quadratic time algorithm.
 If there is a nested loop and also a single loop, the time complexity will be estimated on the
basis of the nested loop only.

Note: Based on the time complexity we decide which algorithm is good case and worst case.

PREPARED BY: SANGAMESH G B 103

 II PUC COMPUTER SCIENCE

4. Explain Best case and Worst case complexity

Best case and worst case complexity:
a. Best case complexity:
The scenario where the algorithm performs the minimum amount of work
• Time complexity – O(1)
b. Worst case Complexity:
The scenario where the algorithm performs the maximum amount of work
• Time complexity – O(n)
c. Average case Complexity:
The scenario where the algorithm performs the average amount of work
• Time complexity – O(n)

5. What is swapping?
Swapping means changing the position of two elements with each other

6. Insertion Sort
Example-03: Visual View
Let us consider a list having 6 elements as list1 = [23, 1, 10, 1, 5, 2]
Initial List: [23, 1, 10, 1, 5, 2]

Summary:
 Sorting: Re-arranging elements for efficient access.
 Bubble Sort: Repeated adjacent swaps, n-1 passes.
 Selection Sort: Select and place smallest, reduce unsorted list.
 Insertion Sort: Insert each element into sorted part at the correct position.
 Time Complexity: Helps choose suitable algorithms for large datasets

PREPARED BY: SANGAMESH G B 104

 II PUC COMPUTER SCIENCE

 Multiple Choice Questions (MCQs)

1. Sorting is _________ in a particular order
a) An arrangement of elements b) Finding of elements
c) deletion of elements d) Insertion of elements
2. In bubble sort while arranging elements in ascending order the largest element will move towards
the _______of the list.
a) Anywhere b) end c) beginning d) middle
3. Which of the following sorting technique compares adjacent elements and swaps until sorting.
a) Selection sort b) Insertion sort c) Heap sort d) Bubble sort
4. The bubble sort technique makes a total of ____ passes to sort in a list of n elements.
a) n b) n2 c) n-1 d) n+1
5. In which sorting mechanism smallest element from the unordered list move towards the left in an
ascending order arrangement.
a) Selection sort b) Insertion sort c) Heap sort d) Bubble sort
6. The selection sort technique makes a total of ____ passes to sort in a list of n elements.
a) n b) n2 c) n-1 d) n+1
7. In which sorting type each element in the unsorted list is considered one by one and inserted into
appropriate position.
a) Selection sort b) Insertion sort c) Heap sort d) Bubble sort
8. In bubble sort while sorting in ascending order, which element reaches its correct position after
the first pass
a) The smallest element b) The middle element
c) The largest element d) The second largest element
9. (A) In selection sort the smallest element is selected in each pass and placed in its correct position
(B) In selection sort the nth element is the last, and it is already in place
a) A is True and B is False b) A is False and B is True
c) Both A and B are True d) Both A and B are False
10. (A) In Bubble sort largest element is moved to its correct position in each pass
(B) Bubble sort makes a total n-1 passes to sort a list of n elements
a) A is True and B is False b) A is False and B is True
c) Both A and B are True d) Both A and B are False
11. Changing the position of two elements with each other means
a) Sorting b) Hashing c) Swapping d) Searching
12. The nested will have the time complexity as
a) n2 b) log n c) 1 d) n
13. The time complexity of a quadratic time algorithm is
a) n2 b) n3 c) log (n) d) 1
14. The number of passes required to sort a list of size 100 using bubble sort is
a) 100 b) 1000 c) 10 d) 99
15. In which sorting technique all elements are traversed to find smallest element
a) Bubble sort b) Selection sort c) Insertion sort d) Quick sort
16. In which sorting algorithm is the smallest element found in the unsorted part and then swapped
with the leftmost element?
a) Bubble sort b) Insertion sort c) Selection sort d) Quick sort
17. The time complexity of an algorithm without loop is ________
a) O(1) b) O(log n) c) O(n) d) O(n3)
18. The time complexity of Bubble sort is
a) O(1) b) O(log n) c) O(n) d) O(n2)
19. The time complexity of Selection sort is
b) O(1) b) O(log n) c) O(n) d) O(n2)
20. The time complexity of Insertion sort is
c) O(1) b) O(log n) c) O(n) d) O(n2)

PREPARED BY: SANGAMESH G B 105

 II PUC COMPUTER SCIENCE

21. The Bubble sort makes how many passes to sort a list of n elements?
a) n b) n2 c) n-1 d) n+1
22. The Selection sort makes how many passes to sort a list of n elements?
b) n b) n2 c) n-1 d) n+1
23. The Insertion sort makes how many passes to sort a list of n elements?
c) n b) n2 c) n-1 d) n+1

PREPARED BY: SANGAMESH G B 106

 II PUC COMPUTER SCIENCE

CHAPTER – 06
SEARCHING

In this chapter:

Introduction
Linear search
Binary Search
Searching by Hashing
1. What is a searching?
It is the process of locating a particular element (called key) in a collection of elements
OR
It is a process of finding or locating a particular element (key) in a list of elements
 It determines whether the key (particular element) is present or not.

2. Types of searching techniques

Three main techniques:
 Linear Search
 Binary Search
 Search by Hashing

3. Linear Search:
 It compares each element of the list with the key until a match is found or the list ends.
 It works on both sorted and unsorted lists
 Searching the elements from beginning to end
 Simpler to implement
 It is also called as Sequential Search or serial search
 Time complexity: O(n)
 Advantages: Useful for unsorted or small-sized lists.
 Disadvantage: This searching is slow and Time consuming, when list contains large number of
elements.

 Algorithm: Linear Search

Q Write an algorithm to perform linear search method
OR
Write an algorithm to search an element(key) using Linear search
Algorithm: Linear Search
Linear_Search(numList, key, n)

Step 1: SET index = 0

Step 2: WHILE index < n, REPEAT Step 3
Step 3: IF numList[index] = key THEN
PRINT “Element found at position”, index+1
STOP
ELSE
index = index + 1
Step 4: PRINT “Search unsuccessful”

PREPARED BY: SANGAMESH G B 107

II PUC COMPUTER SCIENCE

 Example-01:
Consider the following elements stored in the list
List: L = [5, 7, 2, 9, 3]
Searching element Key = 9 using linear search method
Number of elements/size of list: n=5

Solution:

Index 0 1 2 3 4
Values (L) 5 7 2 9 3

Condition Elements Element

Index Index < n? Compare L[index]=key Found? Index+1
0 0 < 5 (True) L[0] = ele 5 = 9 (False) Not Found 0+1=1
1 1 < 5 (True) L[1] = ele 7 = 9 (False) Not Found 1+1=2
2 2 < 5 (True) L[2] = ele 2 = 9 (False) Not Found 2+1=3
3 3 < 5 (True) L[3] = ele 9 = 9 (True) Found 3+1=4
4 4 < 5 (True) L[4] = ele
Searching element key-9 found at the position 4

 Example-02:
Consider the following elements stored in the list
List: L = [5, 7, 2, 9, 3]
Searching element Key = 8 using linear search method
Number of elements/size of list: n=5

Solution:

Index 0 1 2 3 4
Values (L) 5 7 2 9 3

Condition Elements Element

Index Index < n? Compare L[index]=key Found? Index+1
0 0 < 5 (True) L[0] = ele 5 = 8 (False) Not Found 0+1=1
1 1 < 5 (True) L[1] = ele 7 = 8 (False) Not Found 1+1=2
2 2 < 5 (True) L[2] = ele 2 = 8 (False) Not Found 2+1=3
3 3 < 5 (True) L[3] = ele 9 = 8 (False) Not Found 3+1=4
4 4 < 5 (True) L[4] = ele 3 = 8 (False) Not Found 4+1=5
5 5 < 5 (False) Control terminates
Searching element key-8 not found in the list

PREPARED BY: SANGAMESH G B 108

II PUC COMPUTER SCIENCE

 Program: Linear Search

Write a program to perfom linear search
def linearSearch(list, key):
for index in range(0, len(list)):
if list[index] == key:
return index + 1
return None

list1 = [ ]
maximum = int(input("How many elements in your list? "))
print(“Enter each element and press enter:”)
for i in range(0, maximum):
n = int(input())
[Link](n)

key = int(input("Enter the number to be searched:"))

position = linearSearch(list1, key)
if position is None:
print("Number", key, "is not present in the list")
else:
print("Number", key, "is present at position", position)

PREPARED BY: SANGAMESH G B 109

 II PUC COMPUTER SCIENCE

4. Binary Search :
Repeatedly divides list into halves and compares key with the middle element.
 Requires a sorted list.
 More efficient than linear search.

[ This searching method will be used only when items are in sorted order, Here elements will be
checked and splits collection of items into two parts and again do the same ]

 Applications of Binary Search

• Indexing in databases
• Implementing routing tables in routers
• Searching in sorted dictionary/telephone directory
• Data compression,

 Applications of modified binary search

• Indexing in database: Quick locate records in large sorted datasets
• Implementing routing tables in routers: Efficiently find the best route for data packets
• Searching in sorted dictionaries or directories: Quickly find a word or entry in a sorted list

 Working process of Binary search algorithm

 Binary search work on either ascending or descending order
Binary search requires a sorted list.
Repeatedly divides list into halves and compares key with the middle element.
 The middle element of the list is found:
Mid = ( first + last ) /2 and compared with the key
 Three possibilities occurs in binary search are:
- If the middle element matches or equals the key, the search is successful
- If the key is smaller than middle element, then search continue in the left half of the list
- If the key is larger than middle element, then search continue in the right half of the list
 This process of dividing continues until the key is found or the list cannot be divided
further (i.e., start index > end index)
 Each comparison helps to eliminate half of the remaining elements, making the algorithm
much faster than linear search
 The name binary search comes from this idea of dividing the list into two halves (Binary
splitting) at each step.

 Algorithm: Binary Search

Write an algorithgm to perfom Binary search
Step-1: Set first = 0, last = n – 1, pos= -1
Step-2: WHILE first <= last, REPEAT Step 4
Step-3: Calculate: mid = (first + last) // 2
Step-4: IF numList[mid] = = key THEN
PRINT "Element found at position", mid + 1
STOP
ELSE :
IF numList[mid] > key THEN
last = mid - 1
ELSE
first = mid + 1
Step 5: PRINT "Search unsuccessful"

PREPARED BY: SANGAMESH G B 110

II PUC COMPUTER SCIENCE

 Example-01:
Consider the following elements stored in the list
List: L = [10, 20, 30, 40, 50]
Searching element Key = 40 using binary search method
Number of elements/size of list: n=5

Solution:

Index 0 1 2 3 4
Values (L) 10 20 30 40 50

Iteration Mid Comparison

(Pass/steps) Start End Mid=(Start+End)/2 Key ele= L[mid] Results
1 0 4 (0+4)/2 = 2 40 =30 False
Mid=2
Searching element (40) is greater than mid element (30), Does not matched
Then start Mid+1 (2+1=3)
2 3 4 (3+4)/2 = 7/2= 3.5=3 40 = 40 True
Mid=3
Searching element (40) is equals to mid element (40), matched

Final Result: Searching element Key-40 found in the position 4(mid+1)

 Example-02:
Consider the following elements stored in the list
List: L = [10, 20, 30, 40, 50, 60]
Searching element Key = 70 using binary search method
Number of elements/size of list: n=6

Solution:
Index 0 1 2 3 4 5
Values (L) 10 20 30 40 50 60

Iteration Mid Comparison

(Pass/steps) Start End Mid=(Start+End)/2 Key ele= L[mid] Results
1 0 5 (0+5)/2 = 2.5 70 =30 False
Mid=2
Searching element (70) is greater than mid element (30), Does not matched
Then start Mid+1 (2+1=3)
2 3 5 (3+5)/2 = 8/2= 4 70 = 50 False
Mid=4
Searching element (70) is greater than mid element (50), Does not matched
Then start Mid+1 (4+1=5)
3 5 5 (5+5)/2 = 10/2= 5 70 = 60 False
Mid=5
Searching element (70) is greater than mid element (60), Does not matched
Then Mid+1 (5+1=6)  Out of range condition
Since the condition (Start < = end ) is false, then the comparison ends
Final Result: Searching element Key-70 is not found

PREPARED BY: SANGAMESH G B 111

II PUC COMPUTER SCIENCE

 Program: Binary Search

Write a program to perfom Binary search
def binarySearch(list, key):
first = 0
last = len(list) - 1
while first <= last:
mid = (first + last)//2
if list[mid] == key:
return mid
elif key > list[mid]:
first = mid + 1
else:
last = mid - 1
return -1
numList = [ ]
print("Enter elements in ascending order (-999 to stop):")
num = int(input())
while num != -999:
[Link](num)
num = int(input())
key = int(input("Enter the number to be searched: "))
pos = binarySearch(numList, key)
if pos != -1:
print(key, "is found at position", pos + 1)
else:
print(key, "is not found in the list")

PREPARED BY: SANGAMESH G B 112

 II PUC COMPUTER SCIENCE

5. Search by Hashing:
Hashing is a technique used to search an element in a single step by Hash function to calculate
value an index in the list.
OR
Hashing is a technique used to find the presence of key in a list in just one step

 Explain how it improves the efficiency of searching:

 It uses a special formula called hash function to calculate the index position of each element in
a new list called hash table
 The hash functions assigns each element a unique index value, allowing fast and direct access
to data instead of searching through the entire list, this makes searching operation very
efficient
 A simple hash function is the remainder(Modulus %) method
Formula:
h(element) = element % size of table [Hash function computes index:]
• Direct access method using a hash function.
• Searches key in constant time O(1).

 Example:
List1= [56, 24, 93, 17, 70, 31, 45] Hash Table size=10

• Let us consider an empty hash table with 10 positions.

Index/
Position 0 1 2 3 4 5 6 7 8 9
Value None None None None None None None None None None

• Let us consider a list of number [56, 24, 93, 17, 70, 31, 45]
List1= [56, 24, 93, 17, 70, 31, 45]

• We can use the hash function remainder

Element 56 24 93 17 70 31 45
Value 56%10=6 24%10=4 93%10=3 17%10=7 70%10=0 31%10=1 45%10=5

• After computing the hash value, each element is inserted at its designated position in the has table.
Index 0 1 2 3 4 5 6 7 8 9
Value 70 31 None 93 24 45 56 17 None None

• Now, To search for a key, we can calculate the index using the hashing function to compare the
element at that index with the key to declare whether the element is present in the list or not
• This search operation involves just one comparison and hence the same amount of time is always
required to search a key irrespective of the size of the list

PREPARED BY: SANGAMESH G B 113

II PUC COMPUTER SCIENCE

Program: Search by Hashing

Program: Hashing in Python

def hashFind(key, hashTable):
if hashTable[key % 10] == key:
return (key % 10) + 1
else:
return None
hashTable = [None]*10
L = [34, 16, 2, 93, 80, 77, 51]
for i in L:
hashTable[i % 10] = i
key = int(input("Enter the number to be searched: "))
position = hashFind(key, hashTable)
if position:
print("Number", key, "present at", position, "position")
else:
print("Number", key, "is not present in the hash table")

OR

Program: Hashing in Python

hashtable=[None,None,None,None,None,None,None,NoneNone,None]
list1=[34,16,2,93,80,77,51]
key=int(input(“Enter the element to search:”))
for i in range(0,len(list1)):
hashtable[list1[i] %10] = list1[i]
for i in range (0,len(hastable)):
print(“hashindex=”,i, “value=”, hashtable[i])
if hashtable[key%10]==key:
print(“Element found”)
else:
print(“Element does not exist”)

Output:

Enter the element to search: 51

Hashindex= 0 Value= 80
Hashindex= 1 Value= 51
Hashindex= 2 Value= 2
Hashindex= 3 Value= 93
Hashindex= 4 Value= 34
Hashindex= 5 Value= None
Hashindex= 6 Value= 16
Hashindex= 7 Value= 77
Hashindex= 8 Value= None
Hashindex= 9 Value= None
Element found

PREPARED BY: SANGAMESH G B 114

 II PUC COMPUTER SCIENCE

6. Collision in hashing:
Collision occurs when multiple elements hash to the same index.
[When two or more elements map to the same slot in the hash table, it is called collision]

• Requires collision resolution techniques

• A perfect hash function prevents collision by mapping each element uniquely.

7. Comparison: Linear – Binary – Hashing searching Techniques

List Time Description

Technique Best For Requirement Complexity
notes
Linear Small/Unordered None O(n) Simple but slow for large n
Search lists
Binary Large/Sorted lists Sorted O(log n) Fast, requires sorted input
Search
Hashing Fastest lookups Hash Function O(1) or Needs collision handling
Constant

Exercise:
1. What is searching? Which method is used in simple hash function that works with numerical values?
• Searching: It is the process of finding the position of a particular element in a collection of elements
(Searching means locating a particular element in a collection of elements)
• Remainder (Modulus %) method is used in simple hash function that works with numerical values

2. List three possibilities that occurs in binary search

Three possibilities occur in binary search are:
- If the middle element matches or equals the key, the search is successful
- If the key is smaller than middle element, then search continue in the left half of the list
- If the key is larger than middle element, then search continue in the right half of the list

3. Define Hashing and Perfect hash function

a. Hashing:
A technique to find the presence of a key in a list in just one step using the formula called a
Hash function, making searching very efficient
b. Perfect hash function:
The hash function, where every item maps to a unique index in the hash table so no collision
occur

4. What is collision situation and collision resolution in Hashing?

a. Collision situation:
When two are more elements are mapped to the same slot in the hash table, it is called a
Collision.
[Collision occurs when multiple elements hash to the same index]
b. Collision resolution:
It is a technique used to handle and store multiple data items that are assigned the same hash
address in a hash table

PREPARED BY: SANGAMESH G B 115

 II PUC COMPUTER SCIENCE

5. Fill in the Blanks:

1. The process of locating a particular element in a collection of elements is called _______.

Answer: Searching
2. In linear search, each element is compared with the key in a _______ manner.
Answer: sequential
3. Another name for linear search is _______ search.
Answer: serial
4. The maximum number of comparisons in linear search is equal to _______, where n is the
number of elements.
Answer: n
5. In binary search, the list must be _______ before applying the search.
Answer: sorted
6. Binary search divides the list into _______ parts after every unsuccessful comparison.
Answer: two / halves
7. The mid index in binary search is calculated as _______.
Answer: (first + last) // 2
8. Binary search reduces the search area by _______ each time.
Answer: half
9. In hashing, the formula used to compute index using the remainder method is _______.
Answer: element % size of hash table
10. The table where elements are stored using hash function values is called a _______.
Answer: hash table
11. A situation where two or more elements map to the same index in a hash table is called a
_______.
Answer: collision
12. The process of finding a new position for elements during collision is known as _______.
Answer: collision resolution
13. A hash function that maps every key to a unique index is called a _______ hash function.
Answer: perfect
14. The time complexity of binary search in the worst case is _______.
Answer: O(log n)
15. In the worst case of linear search, the key may be found at the _______ of the list or not present
at all.
Answer: end

PREPARED BY: SANGAMESH G B 116