# [Concepts] Paper 4 # CHAPTER 9: SORTING ALGORITHMS ## 9.1 BUBBLE SORT ### 9.1.1 How It Works 1. Compare adjacent elements 2. Swap if in wrong order 3. Repeat for entire list 4. Each pass places largest unsorted element at end 5. 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 1. Assume first element is sorted 2. Take next element 3. Insert into correct position in sorted portion 4. 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 1. Start at first element 2. Compare with target 3. If match, return position 4. If not, move to next element 5. 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 1. Find middle element 2. Compare with target 3. If match, return position 4. If target > middle, search right half 5. If target < middle, search left half 6. 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 1. **Base Case:** Condition that stops recursion 2. **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 ```python def factorial(n): #Task 1: Factorial function if n==0: #Case 1: 0! return 1 else: #Case 2: ! return n*factorial(n-1) #multiply with factorial of n-1 ``` Recursive arithmetic sum ```python 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 th term return arithmetic_sum_2(term1,com_dif,(n-1))+(n-1)*com_dif+term1 ``` Iterative arithmetic sum ```python 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 ```python 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 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 ```python def compound_interest(initial,inc,n): return initial*((1+(inc/100))**n) ``` PIN, deposit & withdraw ```python 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.") ```