[Concepts] Paper 4

CHAPTER 9: SORTING ALGORITHMS
CHAPTER 10: SEARCHING ALGORITHMS
CHAPTER 11: ABSTRACT DATA TYPES
CHAPTER 12: RECURSION
CHAPTER 13: OBJECT-ORIENTED PROGRAMMING
CHAPTER 14: FILE PROCESSING
CHAPTER 15: EXCEPTION HANDLING
[Python] Important Algorithms

CHAPTER 9: SORTING ALGORITHMS

9.1 BUBBLE SORT

9.1.1 How It Works

Compare adjacent elements
Swap if in wrong order
Repeat for entire list
Each pass places largest unsorted element at end
Continue until no swaps needed

9.1.2 Pseudocode

<PSEUDOCODE>

DECLARE myList : ARRAY[0:8] OF INTEGER
DECLARE UB : INTEGER
DECLARE LB : INTEGER
DECLARE index : INTEGER
DECLARE swap : BOOLEAN
DECLARE temp : INTEGER
DECLARE top : INTEGER

UB ← 8
LB ← 0
top ← UB

REPEAT
 swap ← FALSE
 FOR index ← LB TO top - 1
 IF myList[index] > myList[index + 1] THEN
 temp ← myList[index]
 myList[index] ← myList[index + 1]
 myList[index + 1] ← temp
 swap ← TRUE
 ENDIF
 NEXT index
 top ← top - 1
UNTIL NOT swap OR top = 0

9.1.3 Python Code

<PYTHON>

def bubbleSort(myList):
 n = len(myList)
 for i in range(n):
 swap = False
 for j in range(0, n-i-1):
 if myList[j] > myList[j+1]:
 myList[j], myList[j+1] = myList[j+1], myList[j]
 swap = True
 if not swap:
 break

myList = [70, 46, 43, 27, 57, 41, 45, 21, 14]
bubbleSort(myList)
print(myList)

9.1.4 Complexity

Best Case: O(n) - already sorted
Worst Case: O(n²) - reverse sorted
Space: O(1)

9.2 INSERTION SORT

9.2.1 How It Works

Assume first element is sorted
Take next element
Insert into correct position in sorted portion
Repeat until all elements sorted

9.2.2 Pseudocode

<PSEUDOCODE>

DECLARE myList : ARRAY[0:9] OF INTEGER
DECLARE UB : INTEGER
DECLARE LB : INTEGER
DECLARE index : INTEGER
DECLARE key : INTEGER
DECLARE place : INTEGER

UB ← 9
LB ← 0

FOR index ← LB + 1 TO UB
 key ← myList[index]
 place ← index - 1
 WHILE place >= LB AND myList[place] > key
 myList[place + 1] ← myList[place]
 place ← place - 1
 END WHILE
 myList[place + 1] ← key
NEXT index

9.2.3 Python Code

<PYTHON>

def insertionSort(arr):
 for i in range(1, len(arr)):
 key = arr[i]
 j = i - 1
 while j >= 0 and key < arr[j]:
 arr[j + 1] = arr[j]
 j -= 1
 arr[j + 1] = key

myList = [12, 11, 13, 5, 6]
insertionSort(myList)
print(myList)

9.2.4 Complexity

Best Case: O(n) - already sorted
Worst Case: O(n²) - reverse sorted
Space: O(1)

CHAPTER 10: SEARCHING ALGORITHMS

10.1 LINEAR SEARCH

10.1.1 How It Works

Start at first element
Compare with target
If match, return position
If not, move to next element
Repeat until found or end of list

10.1.2 Pseudocode

<PSEUDOCODE>

DECLARE myList : ARRAY[0:9] OF INTEGER
DECLARE upperBound : INTEGER
DECLARE lowerBound : INTEGER
DECLARE index : INTEGER
DECLARE item : INTEGER
DECLARE found : BOOLEAN

upperBound ← 9
lowerBound ← 0
OUTPUT "Enter item to find"
INPUT item
found ← FALSE
index ← lowerBound

REPEAT
 IF item = myList[index] THEN
 found ← TRUE
 ELSE
 index ← index + 1
 ENDIF
UNTIL found = TRUE OR index > upperBound

IF found THEN
 OUTPUT "Item found at index", index
ELSE
 OUTPUT "Item not found"
ENDIF

10.1.3 Python Code

<PYTHON>

myList = [4, 2, 8, 17, 9, 3, 7, 12, 34, 21]
item = int(input("Enter item to find: "))
found = False

for x in range(len(myList)):
 if myList[x] == item:
 found = True
 print(f"Item found at index {x}")
 break

if not found:
 print("Item not found")

10.1.4 Complexity

Time: O(n)
Space: O(1)

10.2 BINARY SEARCH

10.2.1 Prerequisites

List MUST be sorted

10.2.2 How It Works

Find middle element
Compare with target
If match, return position
If target > middle, search right half
If target < middle, search left half
Repeat until found or sublist empty

10.2.3 Pseudocode

<PSEUDOCODE>

DECLARE myList : ARRAY[0:9] OF INTEGER
DECLARE UB : INTEGER
DECLARE LB : INTEGER
DECLARE index : INTEGER
DECLARE item : INTEGER
DECLARE found : BOOLEAN

UB ← 9
LB ← 0

OUTPUT "Enter item to find"
INPUT item
found ← FALSE

REPEAT
 index ← INT((UB + LB) / 2)
 IF item = myList[index] THEN
 found ← TRUE
 ELSE
 IF item > myList[index] THEN
 LB ← index + 1
 ELSE
 UB ← index - 1
 ENDIF
 ENDIF
UNTIL found = TRUE OR LB > UB

IF found THEN
 OUTPUT "Item found at index", index
ELSE
 OUTPUT "Item not found"
ENDIF

10.2.4 Python Code

<PYTHON>

myList = [16, 19, 21, 27, 36, 42, 55, 67, 76]
item = int(input("Enter item to find: "))

min = 0
max = len(myList) - 1
found = False
index = 0

while found is False and min <= max:
 index = int((max + min) / 2)
 if item == myList[index]:
 found = True
 elif item < myList[index]:
 max = index - 1
 else:
 min = index + 1

if found:
 print(f"Item found at index {index}")
else:
 print("Item not found")

10.2.5 Complexity

Time: O(log n)
Space: O(1)

CHAPTER 11: ABSTRACT DATA TYPES

11.1 STACKS

11.1.1 Characteristics

LIFO: Last In, First Out
Add and remove from only one end (top)

11.1.2 Operations

Push (Add):

<PSEUDOCODE>

PROCEDURE Push(item)
 IF topPointer < stackFull THEN
 topPointer ← topPointer + 1
 myStack[topPointer] ← item
 ELSE
 OUTPUT "Stack is full"
 ENDIF
ENDPROCEDURE

Pop (Remove):

<PSEUDOCODE>

PROCEDURE Pop()
 IF topPointer = -1 THEN
 OUTPUT "Stack is empty"
 ELSE
 item ← myStack[topPointer]
 topPointer ← topPointer - 1
 ENDIF
ENDPROCEDURE

11.1.3 Python Implementation

<PYTHON>

class Stack:
 def __init__(self, StackFull):
 self.StackFull = StackFull
 self.TopPointer = -1
 self.stack = []
 for i in range(StackFull):
 self.stack.append(0)
 
 def push(self, item):
 if self.TopPointer < self.StackFull - 1:
 self.TopPointer += 1
 self.stack[self.TopPointer] = item
 else:
 print("Stack is full")
 
 def pop(self):
 if self.TopPointer == -1:
 print("Stack is empty")
 return None
 else:
 item = self.stack[self.TopPointer]
 self.TopPointer -= 1
 return item
 
 def printStack(self):
 print(self.stack)

myStack = Stack(10)
myStack.push(5)
myStack.push(10)
print(myStack.pop()) # Returns 10

11.1.4 Uses

Interrupt handling
Evaluating RPN expressions
Procedure call stack
Undo mechanisms

11.2 QUEUES

11.2.1 Characteristics

FIFO: First In, First Out
Add to rear, remove from front
Can be circular

11.2.2 Operations

Enqueue (Add):

<PSEUDOCODE>

PROCEDURE Enqueue(item)
 IF queueLength < queueFull THEN
 IF rearPointer < upperBound THEN
 rearPointer ← rearPointer + 1
 ELSE
 rearPointer ← 1
 ENDIF
 queue[rearPointer] ← item
 queueLength ← queueLength + 1
 ELSE
 OUTPUT "Queue is full"
 ENDIF
ENDPROCEDURE

Dequeue (Remove):

<PSEUDOCODE>

PROCEDURE Dequeue()
 IF queueLength = 0 THEN
 OUTPUT "Queue is empty"
 ELSE
 item ← queue[frontPointer]
 IF frontPointer = upperBound THEN
 frontPointer ← 1
 ELSE
 frontPointer ← frontPointer + 1
 ENDIF
 queueLength ← queueLength - 1
 ENDIF
ENDPROCEDURE

11.2.3 Python Implementation

<PYTHON>

class Queue:
 def __init__(self, QueueFull):
 self.QueueFull = QueueFull
 self.FrontPointer = 0
 self.RearPointer = -1
 self.QueueLength = 0
 self.queue = []
 for i in range(QueueFull):
 self.queue.append(0)
 
 def enQueue(self, item):
 if self.QueueLength < self.QueueFull:
 if self.RearPointer < self.QueueFull - 1:
 self.RearPointer += 1
 else:
 self.RearPointer = 0
 self.queue[self.RearPointer] = item
 self.QueueLength += 1
 else:
 print("Queue is full")
 
 def deQueue(self):
 if self.QueueLength == 0:
 print("Queue is empty")
 return None
 else:
 item = self.queue[self.FrontPointer]
 if self.FrontPointer == self.QueueFull - 1:
 self.FrontPointer = 0
 else:
 self.FrontPointer += 1
 self.QueueLength -= 1
 return item

11.2.4 Uses

Print queues
Task scheduling
Breadth-first search

11.3 LINKED LISTS

11.3.1 Characteristics

Dynamic data structure
Nodes contain data and pointer to next node
Can grow/shrink easily

11.3.2 Node Structure

<PYTHON>

class Node:
 def __init__(self, item):
 self.Data = item
 self.Pointer = -1

11.3.3 Linked List Operations

Insert:

<PYTHON>

def add(self, itemAdd):
 # Find position and insert
 # Update pointers

Delete:

<PYTHON>

def delete(self, itemDelete):
 # Find node
 # Update pointers to bypass

Search:

<PYTHON>

def search(self, itemFind):
 # Traverse until found or end

11.3.4 Uses

Dynamic memory allocation
Implementation of other ADTs
Symbol tables

11.4 BINARY TREES

11.4.1 Characteristics

Hierarchical structure
Each node has at most two children
Left child < parent, Right child > parent (in ordered tree)

11.4.2 Node Structure

<PYTHON>

class Node:
 def __init__(self, item):
 self.Data = item
 self.LeftPointer = -1
 self.RightPointer = -1
 self.UpPointer = -1

11.4.3 Operations

Insert:

Start at root
Compare with current node
Go left if smaller, right if larger
Repeat until empty position found

Search:

Start at root
Compare with current node
If match, found
If target < current, go left; else go right
Repeat until found or null pointer

Traverse (In-order):

<PYTHON>

def inOrder(self, Pointer):
 if Pointer == -1:
 return
 self.inOrder(self.tree[Pointer].leftPointer)
 print(self.tree[Pointer].Data)
 self.inOrder(self.tree[Pointer].rightPointer)

CHAPTER 12: RECURSION

12.1 WRITING RECURSIVE ALGORITHMS

12.1.1 Essential Components

Base Case: Condition that stops recursion
Recursive Case: Function calls itself with modified parameters

12.1.2 Examples

Sum of Numbers:

<PYTHON>

def sum(n):
 if n == 1:
 return 1
 else:
 return n + sum(n-1)

Counting Characters in String:

<PYTHON>

def count(char, string):
 if string == "":
 return 0
 elif string[0] == char:
 return 1 + count(char, string[1:])
 else:
 return count(char, string[1:])

Reverse String:

<PYTHON>

def reverse(string):
 if len(string) <= 1:
 return string
 else:
 return reverse(string[1:]) + string[0]

12.1.3 Tracing Recursion

<TEXT>

sum(4)
= 4 + sum(3)
= 4 + (3 + sum(2))
= 4 + (3 + (2 + sum(1)))
= 4 + (3 + (2 + 1))
= 4 + (3 + 3)
= 4 + 6
= 10

CHAPTER 13: OBJECT-ORIENTED PROGRAMMING

13.1 CLASSES AND OBJECTS

13.1.1 Defining Classes

<PYTHON>

class Person:
 def __init__(self, name, age):
 self.name = name # Property
 self.age = age # Property
 
 def get_name(self): # Method
 return self.name
 
 def set_name(self, name):
 self.name = name

13.1.2 Creating Objects

<PYTHON>

person1 = Person("John", 25)
person2 = Person("Jane", 30)

print(person1.get_name()) # Output: John
person1.set_name("Bob")

13.2 INHERITANCE

13.2.1 Basic Inheritance

<PYTHON>

class Person:
 def __init__(self, name, age):
 self.name = name
 self.age = age
 
 def display(self):
 print(f"Name: {self.name}, Age: {self.age}")

class Student(Person):
 def __init__(self, name, age, student_id):
 super().__init__(name, age) # Call parent constructor
 self.student_id = student_id
 
 def display(self):
 super().display() # Call parent method
 print(f"Student ID: {self.student_id}")

student = Student("John", 20, "S12345")
student.display()

13.2.2 Polymorphism

<PYTHON>

class Animal:
 def speak(self):
 pass

class Dog(Animal):
 def speak(self):
 return "Woof"

class Cat(Animal):
 def speak(self):
 return "Meow"

animals = [Dog(), Cat()]
for animal in animals:
 print(animal.speak()) # Different output for same method

13.3 ENCAPSULATION

13.3.1 Private Attributes

<PYTHON>

class BankAccount:
 def __init__(self, balance):
 self.__balance = balance # Private (double underscore)
 
 def get_balance(self):
 return self.__balance
 
 def deposit(self, amount):
 if amount > 0:
 self.__balance += amount
 
 def withdraw(self, amount):
 if amount <= self.__balance:
 self.__balance -= amount

account = BankAccount(1000)
print(account.get_balance()) # OK
# print(account.__balance) # Error - private
account.deposit(500)

13.4 GETTERS AND SETTERS

13.4.1 Purpose

Control access to private attributes.

<PYTHON>

class Person:
 def __init__(self, name):
 self.__name = name
 
 def get_name(self): # Getter
 return self.__name
 
 def set_name(self, name): # Setter
 self.__name = name

CHAPTER 14: FILE PROCESSING

14.1 FILE OPERATIONS IN PYTHON

14.1.1 Opening Files

<PYTHON>

# Read mode
file = open("data.txt", "r")

# Write mode (overwrites)
file = open("data.txt", "w")

# Append mode
file = open("data.txt", "a")

14.1.2 Reading Files

<PYTHON>

# Read entire file
content = file.read()

# Read line by line
line = file.readline()

# Read all lines into list
lines = file.readlines()

14.1.3 Writing Files

<PYTHON>

# Write string
file.write("Hello\n")

# Write list of strings
file.writelines(["Line 1\n", "Line 2\n"])

14.1.4 Closing Files

<PYTHON>

file.close()

# Or use context manager (auto-close)
with open("data.txt", "r") as file:
 content = file.read()

14.2 RANDOM FILE ACCESS

14.2.1 Direct Access

<PYTHON>

import struct

# Write record at specific position
def write_record(file, position, record):
 file.seek(position * record_size)
 file.write(struct.pack('i10s', record['id'], record['name'].encode()))

# Read record at specific position
def read_record(file, position):
 file.seek(position * record_size)
 data = file.read(record_size)
 return struct.unpack('i10s', data)

CHAPTER 15: EXCEPTION HANDLING

15.1 TRY-EXCEPT

15.1.1 Basic Structure

<PYTHON>

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

15.1.2 Multiple Exceptions

<PYTHON>

try:
 file = open("data.txt", "r")
 data = int(file.read())
except FileNotFoundError:
 print("File not found")
except ValueError:
 print("Invalid number")

15.1.3 Finally Block

<PYTHON>

try:
 file = open("data.txt", "r")
 content = file.read()
except FileNotFoundError:
 print("File not found")
finally:
 if 'file' in locals():
 file.close()

15.1.4 Raising Exceptions

<PYTHON>

def divide(a, b):
 if b == 0:
 raise ValueError("Cannot divide by zero")
 return a / b

try:
 result = divide(10, 0)
except ValueError as e:
 print(e)

[Python] Important Algorithms

Factorial function

def factorial(n):   #Task 1: Factorial function 
    if n==0:    #Case 1: 0!
        return 1
    
    else:   #Case 2: <positive_integer>!
        return n*factorial(n-1) #multiply with factorial of n-1

Recursive arithmetic sum

def arithmetic_sum_2(term1,com_dif,n):   #Task 2(alternative): Arithmetic Sum Function – Recursive method
    if n==1:    #Case 1: last term to add(=the first term of the sequence)
        return term1
    else:   #Case 2: add <positive integer>th term
        return arithmetic_sum_2(term1,com_dif,(n-1))+(n-1)*com_dif+term1

Iterative arithmetic sum

def arithmetic_sum_1(term1,com_dif,n):   #Task 2: Arithmetic Sum function – Formula method
    return (n/2)*(2*term1+(n-1)*com_dif)

Recursive geometric sum

def geometric_sum_2(term1,com_rat,n):   #Task 3: Geometric Sum function – Recursive method
    if n==1:    #Case 1: last term to add(=the first term of the sequence)
        return float(term1)
    else:   #Case 2: add <positive integer>th term
        return float(geometric_sum_2(term1,com_rat,(n-1))+term1*(com_rat**(n-1)))  #perform nth term addition

Iterative geometric sum

def geometric_sum_1(term1,com_rat,n):   #Task 3: Geometric Sum function – Formula method
    return (term1-(com_rat**n))/(1-com_rat)

Fibonacci function

def fibonacci(term1,term2,n):   #Task 4: Fibonacci function
    if n == 0:
        return term1
    elif n == 1:
        return term2
    else:
        return fibonacci(term1,term2,(n-1))+fibonacci(term1,term2,(n-2))

Compound Interest

def compound_interest(initial,inc,n):
    return initial*((1+(inc/100))**n)

PIN, deposit & withdraw

correct_pin=1111
enter_pin=0
attempt=0
balance=100.00
option=0
save=0.00
password=True
while attempt<3 and password:
    while True:
        try:
            enter_pin=str(input("Enter PIN (4 digits)"))
            if len(str(enter_pin))==4 and int(enter_pin)>=0 and int(enter_pin)<=9999:
                break
            else:
                print("invalid format")
        except ValueError:
            print("invalid format")
    if int(enter_pin)==int(correct_pin):
        password=False
    else:
        attempt+=1
        print("wrong")

def deposit():
    global balance
    while True:
        try:
            save=float(input("How much you save"))
            if save>0:
                break
            else:
                print("can't save that amount")
        except ValueError:
            print("invalid format")
    balance+=save

def withdraw():
    global balance
    while True:
        try:
            take=float(input("How much you withdraw"))
            if take>0 and take<=balance:
                break
            else:
                print("can't withdraw that amount")
        except ValueError:
            print("invalid format")
    balance-=take

def change_pin():
    global correct_pin
    while True:
        try:
            new=str(input("Enter new PIN(4digits)"))
            if len(str(new))==4 and int(new)>=0 and int(new)<=9999 and new!=correct_pin:
                break
            elif new==correct_pin:
                print("there is no change")
            else:
                print("invalid password")
        except ValueError:
            print("invalid format")
    correct_pin=new
    print("Change successful")
        
if not(password):
    Out=False
    while not(Out):
        print("MENU")
        print(f"Balance: {balance}")
        print("Deposit[1]")
        print("Withdraw[2]")
        print("Change PIN[3]")
        print("Exit[4]")
        while True:
            try:
                option=int(input("Enter Option(number key)"))
                if option>=1 and option<=4:
                    break
                else:
                    print("no such option")
            except ValueError:
                print("invalid format")
        if option==1:
            deposit()
        elif option==2:
            withdraw()
        elif option==3:
            change_pin()
        else:
            Out=True
    
else:
    print("Max attempt reached")

if Out==True:
    print("End.")