FORM 6 COMPUTER SCIENCE

Complete Study Guide

Advanced Algorithms, Programming & Databases

ZIMSEC A-Level Syllabus Aligned

Comprehensive Coverage with 10+ Examples, Exercises & Exam Practice

PART 1: ADVANCED ALGORITHMS

1.1 Recursive Algorithms

Recursion is a programming technique where a function calls itself to solve smaller
instances of the same problem. It consists of a base case (terminating condition) and a
recursive case (self-call).

Example 1: Recursive Factorial Function

// Pseudocode - Recursive Factorial
FUNCTION Factorial(n)
// Base case: n = 0 or n = 1
IF n <= 1 THEN
RETURN 1
ENDIF

// Recursive case: n! = n × (n-1)!

RETURN n × Factorial(n - 1)
END FUNCTION

// Python Implementation
def factorial(n):
"""
Calculate factorial using recursion
Base case: factorial(0) = 1, factorial(1) = 1
Recursive case: n! = n × (n-1)!
"""
# Base case
if n <= 1:
return 1
# Recursive case
return n * factorial(n - 1)

# Test the function

print(f"5! = {factorial(5)}") # Output: 120
print(f"0! = {factorial(0)}") # Output: 1
print(f"10! = {factorial(10)}") # Output: 3628800

Trace Table for factorial(4):

Call n Returned Value Status

factorial(4) 4 ? Called
factorial(3) 3 ? Called (waiting)
factorial(2) 2 ? Called (waiting)
factorial(1) 1 1 Base case - returns 1
factorial(2) 2 2×1=2 Returns 2
factorial(3) 3 3×2=6 Returns 6
factorial(4) 4 4×6=24 Returns 24
Explanation: The factorial function demonstrates recursion well:

 Base case: When n ≤ 1, return 1 (stops recursion)

 Recursive case: Return n × factorial(n-1)
 Each call reduces n by 1, eventually hitting base case

Example 2: Recursive Fibonacci Sequence

// Pseudocode - Recursive Fibonacci
FUNCTION Fibonacci(n)
// Base cases
IF n = 0 THEN
RETURN 0
ELSE IF n = 1 THEN
RETURN 1
ENDIF

// Recursive case
RETURN Fibonacci(n - 1) + Fibonacci(n - 2)
END FUNCTION

// Python Implementation
def fibonacci(n):
"""
Generate nth Fibonacci number using recursion
Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
"""
# Base cases
if n == 0:
return 0
elif n == 1:
return 1
# Recursive case
else:
return fibonacci(n - 1) + fibonacci(n - 2)

# Generate Fibonacci sequence

for i in range(10):
print(f"F({i}) = {fibonacci(i)}")
# Output:
# F(0) = 0
# F(1) = 1
# F(2) = 1
# F(3) = 2
# F(4) = 3
# F(5) = 5
# F(6) = 8
# F(7) = 13
# F(8) = 21
# F(9) = 34

Trace for fibonacci(5):

 fibonacci(5) = fibonacci(4) + fibonacci(3)

 fibonacci(4) = fibonacci(3) + fibonacci(2)
 fibonacci(3) = fibonacci(2) + fibonacci(1) = 1 + 1 = 2
 fibonacci(2) = fibonacci(1) + fibonacci(0) = 1 + 0 = 1
 Result: fibonacci(5) = 2 + 3 = 5

Example 3: Recursive Binary Search

// Pseudocode - Recursive Binary Search
FUNCTION BinarySearch(array, target, first, last)
// Base case: not found
IF first > last THEN
RETURN -1 // Element not found
ENDIF

// Calculate middle index

middle ← (first + last) DIV 2

// Base case: element found

IF array[middle] = target THEN
RETURN middle
ENDIF

// Recursive case: search in appropriate half

IF array[middle] > target THEN
RETURN BinarySearch(array, target, first, middle - 1)
ELSE
RETURN BinarySearch(array, target, middle + 1, last)
ENDIF
END FUNCTION

// Python Implementation
def binary_search_recursive(arr, target, first, last):
"""
Recursive binary search
Returns index if found, -1 otherwise
"""
# Base case: not found
if first > last:
return -1
 middle = (first + last) // 2

# Base case: element found

if arr[middle] == target:
return middle

# Recursive case: search in appropriate half

elif arr[middle] > target:
return binary_search_recursive(arr, target, first, middle - 1)
else:
return binary_search_recursive(arr, target, middle + 1, last)

# Test the function

sorted_array = [11, 22, 33, 44, 55, 66, 77, 88, 99]
result = binary_search_recursive(sorted_array, 55, 0, len(sorted_array) - 1)
print(f"Element 55 found at index: {result}") # Output: 4

Explanation: The recursive binary search:

 Base case 1: first > last means search space exhausted (-1 returned)
 Base case 2: array[middle] = target means element found
 Recursive case: Search left or right half based on comparison

Example 4: Recursive Quick Sort

// Pseudocode - Recursive Quick Sort
ALGORITHM QuickSort(array, low, high)
IF low < high THEN
pivot_index ← Partition(array, low, high)
QuickSort(array, low, pivot_index - 1) // Sort left partition
QuickSort(array, pivot_index + 1, high) // Sort right partition
ENDIF
END ALGORITHM

FUNCTION Partition(array, low, high)

pivot ← array[high] // Choose last element as pivot
i ← low - 1

FOR j ← low TO high - 1 DO

IF array[j] <= pivot THEN
i ← i + 1
SWAP array[i], array[j]
ENDIF
ENDFOR

SWAP array[i + 1], array[high]

RETURN i + 1
END FUNCTION

// Python Implementation
def quick_sort(arr, low, high):
"""Recursive quick sort implementation"""
if low < high:
# Partition the array and get pivot index
 pivot_index = partition(arr, low, high)

# Recursively sort elements before and after partition

quick_sort(arr, low, pivot_index - 1)
quick_sort(arr, pivot_index + 1, high)

def partition(arr, low, high):

"""Partition function - places pivot in correct position"""
pivot = arr[high] # Choose last element as pivot
i = low - 1

for j in range(low, high):

if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]

arr[i + 1], arr[high] = arr[high], arr[i + 1]

return i + 1

# Test
data = [64, 34, 25, 12, 22, 11, 90]
quick_sort(data, 0, len(data) - 1)
print(f"Sorted array: {data}") # [11, 12, 22, 25, 34, 64, 90]

Trace for Quick Sort [64, 34, 25, 12, 22, 11, 90]:

 Initial: pivot = 90, after partition: [64, 34, 25, 12, 22, 11, 90]
 QuickSort(0,5) on [64, 34, 25, 12, 22, 11]
 Continue recursively until sorted
 Final: [11, 12, 22, 25, 34, 64, 90]

Example 5: Recursive Array Sum

// Pseudocode - Recursive Array Sum
FUNCTION SumArray(array, n)
// Base case: empty array or single element
IF n <= 0 THEN
RETURN 0
ENDIF

// Recursive case: first element + sum of rest

RETURN array[n-1] + SumArray(array, n - 1)
END FUNCTION

// Python Implementation
def sum_array_recursive(arr, n):
"""
Calculate sum of array elements recursively
"""
# Base case
if n <= 0:
return 0
# Recursive case
return arr[n - 1] + sum_array_recursive(arr, n - 1)
# Alternative using list slicing
def sum_array_slicing(arr):
"""Sum array using list slicing"""
if len(arr) == 0:
return 0
return arr[0] + sum_array_slicing(arr[1:])

# Test
numbers = [1, 2, 3, 4, 5]
print(f"Sum using recursion: {sum_array_recursive(numbers, len(numbers))}") #
15
print(f"Sum using slicing: {sum_array_slicing(numbers)}") # 15

Explanation: Recursive array sum demonstrates divide-and-conquer:

 Base case: Empty array returns 0

 Recursive case: Last element + sum of rest (array without last)

Example 6: Recursive Power Function

// Pseudocode - Recursive Power
FUNCTION Power(base, exponent)
// Base case
IF exponent = 0 THEN
RETURN 1
ENDIF

// Recursive case: base^exp = base × base^(exp-1)

RETURN base × Power(base, exponent - 1)
END FUNCTION

// Python Implementation
def power(base, exponent):
"""
Calculate base raised to exponent recursively
"""
# Base case
if exponent == 0:
return 1
# Recursive case
return base * power(base, exponent - 1)

# Test
print(f"2^10 = {power(2, 10)}") # 1024
print(f"3^4 = {power(3, 4)}") # 81
print(f"5^0 = {power(5, 0)}") # 1

// Optimized version with exponent halving

FUNCTION PowerOptimized(base, exponent)
IF exponent = 0 THEN
RETURN 1
ENDIF

IF exponent MOD 2 = 0 THEN

half ← PowerOptimized(base, exponent DIV 2)
 RETURN half × half
ELSE
RETURN base × PowerOptimized(base, exponent - 1)
ENDIF
END FUNCTION

Trace for power(2, 4):

 power(2, 4) = 2 × power(2, 3)
 power(2, 3) = 2 × power(2, 2)
 power(2, 2) = 2 × power(2, 1)
 power(2, 1) = 2 × power(2, 0)
 power(2, 0) = 1 (base case)
 Result: 2 × 2 × 2 × 2 × 1 = 16

Example 7: Recursive String Reversal

// Pseudocode - Recursive String Reversal
FUNCTION ReverseString(str)
// Base case: empty string or single character
IF LENGTH(str) <= 1 THEN
RETURN str
ENDIF

// Recursive case: last char + reverse of rest

RETURN LAST(str) + ReverseString(ALL_BUT_LAST(str))
END FUNCTION

// Python Implementation
def reverse_string(s):
"""
Reverse a string recursively
"""
# Base case
if len(s) <= 1:
return s
# Recursive case: last char + reverse of rest
return s[-1] + reverse_string(s[:-1])

# Test
text = "Hello World"
reversed_text = reverse_string(text)
print(f"Original: {text}") # Hello World
print(f"Reversed: {reversed_text}") # dlroW olleH

# Recursive Palindrome Check

def is_palindrome(s):
"""
Check if string is palindrome using recursion
"""
# Base case
if len(s) <= 1:
return True
# Check first and last characters
 if s[0] != s[-1]:
return False
# Recursive case: check middle portion
return is_palindrome(s[1:-1])

# Test palindrome
print(f"'racecar' is palindrome: {is_palindrome('racecar')}") # True
print(f"'hello' is palindrome: {is_palindrome('hello')}") # False

Trace for reverse_string("Hello"):

 reverse_string("Hello") = "o" + reverse_string("Hell")

 reverse_string("Hell") = "l" + reverse_string("Hel")
 reverse_string("Hel") = "l" + reverse_string("He")
 reverse_string("He") = "e" + reverse_string("H")
 reverse_string("H") = "H" (base case)
 Result: "o" + "l" + "l" + "e" + "H" = "olleH"

Example 8: Recursive Merge Sort

// Pseudocode - Recursive Merge Sort
ALGORITHM MergeSort(array, left, right)
IF left < right THEN
middle ← (left + right) DIV 2

// Recursively sort first and second halves

MergeSort(array, left, middle)
MergeSort(array, middle + 1, right)

// Merge the sorted halves

Merge(array, left, middle, right)
ENDIF
END ALGORITHM

// Python Implementation
def merge_sort(arr):
"""
Merge sort implementation using recursion
Time Complexity: O(n log n)
Space Complexity: O(n)
"""
if len(arr) <= 1:
return arr

# Divide: find middle point

mid = len(arr) // 2

# Conquer: recursively sort both halves

left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])

# Combine: merge sorted halves

return merge(left, right)
def merge(left, right):
"""Merge two sorted arrays"""
result = []
i = j = 0

while i < len(left) and j < len(right):

if left[i] <= right[j]:
[Link](left[i])
i += 1
else:
[Link](right[j])
j += 1

[Link](left[i:])
[Link](right[j:])
return result

# Test
data = [38, 27, 43, 3, 9, 82, 10]
sorted_data = merge_sort(data)
print(f"Original: {data}")
print(f"Sorted: {sorted_data}")

Explanation: Merge sort uses divide-and-conquer:

 Divide: Split array into two halves

 Conquer: Recursively sort each half
 Combine: Merge sorted halves back together
 Time complexity: O(n log n) - efficient for large datasets

Example 9: Recursive Binary Tree Traversal

// Python Implementation - Binary Tree Node and Traversals
class TreeNode:
def __init__(self, value):
[Link] = value
[Link] = None
[Link] = None

def inorder_traversal(node):
"""
Inorder traversal: Left -> Root -> Right
For BST, gives sorted order
"""
if node is not None:
inorder_traversal([Link])
print([Link], end=" ")
inorder_traversal([Link])

def preorder_traversal(node):
"""
Preorder traversal: Root -> Left -> Right
Used for creating tree copies
"""
if node is not None:
 print([Link], end=" ")
preorder_traversal([Link])
preorder_traversal([Link])

def postorder_traversal(node):
"""
Postorder traversal: Left -> Right -> Root
Used for deleting trees
"""
if node is not None:
postorder_traversal([Link])
postorder_traversal([Link])
print([Link], end=" ")

# Build a sample tree

# 50
# / \
# 30 70
# / \ / \
# 20 40 60 80

root = TreeNode(50)
[Link] = TreeNode(30)
[Link] = TreeNode(70)
[Link] = TreeNode(20)
[Link] = TreeNode(40)
[Link] = TreeNode(60)
[Link] = TreeNode(80)

print("Inorder: ", end="")

inorder_traversal(root) # 20 30 40 50 60 70 80

print("\nPreorder: ", end="")

preorder_traversal(root) # 50 30 20 40 70 60 80

print("\nPostorder: ", end="")

postorder_traversal(root) # 20 40 30 60 80 70 50

Explanation: Tree traversals demonstrate recursion:

 Inorder: Left subtree → Root → Right subtree (BST: sorted order)

 Preorder: Root → Left subtree → Right subtree (create/explore)
 Postorder: Left subtree → Right subtree → Root (delete tree)

Example 10: Tower of Hanoi

// Pseudocode - Tower of Hanoi
ALGORITHM TowerOfHanoi(n, source, destination, auxiliary)
IF n = 1 THEN
DISPLAY "Move disk 1 from ", source, " to ", destination
RETURN
ENDIF

// Move n-1 disks from source to auxiliary

TowerOfHanoi(n - 1, source, auxiliary, destination)
 // Move nth disk from source to destination
DISPLAY "Move disk ", n, " from ", source, " to ", destination

// Move n-1 disks from auxiliary to destination

TowerOfHanoi(n - 1, auxiliary, destination, source)
END ALGORITHM

// Python Implementation
def tower_of_hanoi(n, source, destination, auxiliary):
"""
Solve Tower of Hanoi puzzle
n: number of disks
source: name of source peg
destination: name of destination peg
auxiliary: name of auxiliary peg
"""
if n == 1:
print(f"Move disk 1 from {source} to {destination}")
return

# Move n-1 disks from source to auxiliary

tower_of_hanoi(n - 1, source, auxiliary, destination)

# Move nth disk from source to destination

print(f"Move disk {n} from {source} to {destination}")

# Move n-1 disks from auxiliary to destination

tower_of_hanoi(n - 1, auxiliary, destination, source)

# Test for 3 disks

print("Solution for 3 disks:")
tower_of_hanoi(3, 'A', 'C', 'B')

Output for 3 disks:

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Explanation: Tower of Hanoi is a classic recursion problem:

 Base case: n=1, move directly from source to destination

 Recursive strategy: Move n-1 to auxiliary, move largest, move n-1 to destination
 Number of moves: 2^n - 1 (for n disks)
 Time complexity: O(2^n)

Example 11: Recursive Greatest Common Divisor (GCD)

// Pseudocode - Recursive GCD using Euclidean Algorithm
FUNCTION GCD(a, b)
 // Base case
IF b = 0 THEN
RETURN a
ENDIF

// Recursive case: GCD(a, b) = GCD(b, a MOD b)

RETURN GCD(b, a MOD b)
END FUNCTION

// Python Implementation
def gcd(a, b):
"""
Calculate GCD using Euclidean Algorithm recursively
GCD(48, 18) = GCD(18, 48 mod 18) = GCD(18, 12)
= GCD(12, 18 mod 12) = GCD(12, 6)
= GCD(6, 12 mod 6) = GCD(6, 0)
= 6
"""
if b == 0:
return a
return gcd(b, a % b)

# Extended GCD
def extended_gcd(a, b):
"""Extended Euclidean Algorithm"""
if a == 0:
return b, 0, 1
gcd, x1, y1 = extended_gcd(b % a, a)
x = y1 - (b // a) * x1
y = x1
return gcd, x, y

# Test
print(f"GCD(48, 18) = {gcd(48, 18)}") # 6
print(f"GCD(100, 25) = {gcd(100, 25)}") # 25
print(f"GCD(17, 13) = {gcd(17, 13)}") # 1 (coprime)

Explanation: The Euclidean algorithm for GCD:

 Base case: GCD(a, 0) = a

 Recursive case: GCD(a, b) = GCD(b, a mod b)
 Much more efficient than prime factorization

Example 12: Recursive Linear Search

// Pseudocode - Recursive Linear Search
FUNCTION LinearSearch(array, target, index)
// Base case: element not found
IF index >= LENGTH(array) THEN
RETURN -1
ENDIF

// Base case: element found

IF array[index] = target THEN
RETURN index
 ENDIF

// Recursive case: search in next index

RETURN LinearSearch(array, target, index + 1)
END FUNCTION

// Python Implementation
def linear_search_recursive(arr, target, index=0):
"""
Search for target in array recursively
Returns index if found, -1 otherwise
"""
# Base case: reached end of array
if index >= len(arr):
return -1

# Base case: element found

if arr[index] == target:
return index

# Recursive case: search next element

return linear_search_recursive(arr, target, index + 1)

# Test
numbers = [10, 25, 30, 45, 55, 70, 85]
print(f"Element 45 found at index: {linear_search_recursive(numbers, 45)}") # 3
print(f"Element 50 found at index: {linear_search_recursive(numbers, 50)}") # -
1

# Alternative: Search from end

def linear_search_from_end(arr, target, index=-1):
"""Search from the end of array"""
if abs(index) > len(arr):
return -1
if arr[index] == target:
return len(arr) + index
return linear_search_from_end(arr, target, index - 1)

Explanation: Recursive linear search:

 Base case 1: Index exceeds array bounds → return -1

 Base case 2: Element found at current index → return index
 Recursive case: Check next element (index + 1)
 Time complexity: O(n) - same as iterative version

1.2 Exercises: Advanced Algorithms

Exercise 1: Recursive Sum of Digits

Write a recursive function that calculates the sum of digits of a number. Example:
sum_digits(123) = 1 + 2 + 3 = 6

Exercise 2: Recursive Count of Elements

Write a recursive function that counts the number of elements in a list/array.
Exercise 3: Recursive Maximum Finder
Write a recursive function that finds the maximum value in an array without using loops.

Exercise 4: Recursive String Length

Write a recursive function that calculates the length of a string without using the built-in
len() function.

Exercise 5: Towers of Hanoi Moves

Calculate the minimum number of moves required to solve Tower of Hanoi with 5 disks.
Show your calculation.

ANSWERS

Answer 1: Recursive Sum of Digits

def sum_digits(n):
"""Calculate sum of digits recursively"""
# Base case
if n == 0:
return 0
# Recursive case
return n % 10 + sum_digits(n // 10)

# Test
print(sum_digits(123)) # 6
print(sum_digits(4567)) # 22

# Trace for sum_digits(123):

# sum_digits(123) = 3 + sum_digits(12)
# sum_digits(12) = 2 + sum_digits(1)
# sum_digits(1) = 1 + sum_digits(0)
# sum_digits(0) = 0 (base case)
# Result: 3 + 2 + 1 + 0 = 6

Answer 2: Recursive Count of Elements

def count_elements(arr):
"""Count elements in array recursively"""
# Base case: empty array
if len(arr) == 0:
return 0
# Recursive case: 1 + count of rest
return 1 + count_elements(arr[1:])

# Alternative with index

def count_elements_index(arr, n):
if n <= 0:
return 0
return 1 + count_elements_index(arr, n - 1)

# Test
numbers = [1, 2, 3, 4, 5]
print(count_elements(numbers)) # 5
print(count_elements([])) # 0

Answer 3: Recursive Maximum Finder

def find_max(arr):
"""Find maximum using recursion"""
# Base case: single element
if len(arr) == 1:
return arr[0]
# Recursive case
rest_max = find_max(arr[1:])
return arr[0] if arr[0] > rest_max else rest_max

# Test
numbers = [5, 2, 8, 1, 9, 3]
print(f"Maximum: {find_max(numbers)}") # 9

Answer 4: Recursive String Length

def string_length(s):
"""Calculate string length recursively"""
# Base case
if s == "":
return 0
# Recursive case
return 1 + string_length(s[1:])

# Test
print(string_length("Hello")) # 5
print(string_length("")) # 0

Answer 5: Towers of Hanoi Moves

For n disks, minimum moves = 2^n - 1

 For 5 disks: 2^5 - 1 = 32 - 1 = 31 moves

 For 4 disks: 2^4 - 1 = 16 - 1 = 15 moves
 For 3 disks: 2^3 - 1 = 8 - 1 = 7 moves (as shown in example)

PART 2: ADVANCED PROGRAMMING

2.1 Object-Oriented Programming (OOP)

Object-Oriented Programming (OOP) is a paradigm that organizes code around objects
rather than functions. The four pillars of OOP are: Encapsulation, Abstraction, Inheritance,
and Polymorphism.

Example 1: Classes and Objects (Python)

// Python - Class Definition and Object Creation
class Student:
"""Class to represent a Student object"""
 # Class variable (shared by all instances)
school_name = "ZIMSEC High School"

# Constructor method (initializer)

def __init__(self, name, student_id, age):
# Instance variables (unique to each object)
[Link] = name
self.student_id = student_id
[Link] = age
[Link] = [] # Empty list for each student
print(f"New student created: {name}")

# Instance method
def add_grade(self, grade):
"""Add a grade to student's record"""
[Link](grade)

def calculate_average(self):
"""Calculate average grade"""
if len([Link]) == 0:
return 0
return sum([Link]) / len([Link])

# String representation
def __str__(self):
return f"Student: {[Link]} (ID: {self.student_id})"

# Creating objects (instances)

student1 = Student("John Smith", "S001", 17)
student2 = Student("Mary Jane", "S002", 16)

# Accessing attributes
print([Link]) # John Smith
print(Student.school_name) # ZIMSEC High School

# Calling methods
student1.add_grade(85)
student1.add_grade(92)
student1.add_grade(78)
print(f"Average: {student1.calculate_average():.2f}") # 85.00

# String representation
print(student1) # Student: John Smith (ID: S001)

Explanation: Classes and objects fundamentals:

 Class: Blueprint/template for creating objects

 Object/Instance: Specific realization of a class
 __init__(): Constructor that initializes object state
 self: Reference to current instance
 Instance variables: Unique to each object
 Class variables: Shared by all instances
Example 2: Encapsulation (Python)
// Python - Encapsulation with Private Attributes
class BankAccount:
"""Bank account with encapsulated data"""

def __init__(self, account_number, balance):

# Private attributes (using underscore convention)
self._account_number = account_number # Protected
self.__balance = balance # Private
self.__transaction_history = []

# Getter method (accessor)

def get_balance(self):
"""Get current balance"""
return self.__balance

# Setter method (mutator) with validation

def deposit(self, amount):
"""Deposit money with validation"""
if amount > 0:
self.__balance += amount
self.__record_transaction(f"Deposit: ${amount}")
return True
return False

def withdraw(self, amount):

"""Withdraw money with validation"""
if amount > 0 and amount <= self.__balance:
self.__balance -= amount
self.__record_transaction(f"Withdrawal: ${amount}")
return True
return False

# Private method
def __record_transaction(self, description):
"""Private method to record transactions"""
self.__transaction_history.append(description)

# Public method to access history

def get_transaction_history(self):
"""Get transaction history"""
return self.__transaction_history.copy()

# Using the encapsulated class

account = BankAccount("ACC001", 1000)

# Access through methods (controlled access)

print(f"Balance: ${account.get_balance()}") # $1000

# Modify through validated methods

[Link](500)
[Link](200)

print(f"Balance: ${account.get_balance()}") # $1300

print(f"History: {account.get_transaction_history()}")

# Cannot directly access private attributes

# print(account.__balance) # AttributeError!
# account.__record_transaction("Test") # AttributeError!

Explanation: Encapsulation benefits:

 Data hiding: Private attributes cannot be accessed directly

 Validation: Setter methods can validate data before assignment
 Control: Getters and setters control how data is accessed
 _single: Protected (convention)
 __double: Private (name mangling)

Example 3: Inheritance (Python)

// Python - Inheritance
class Person:
"""Base class for all people"""
def __init__(self, name, age):
[Link] = name
[Link] = age

def introduce(self):
return f"My name is {[Link]} and I am {[Link]} years old."

# Single Inheritance: Student inherits from Person

class Student(Person):
"""Student class inheriting from Person"""
def __init__(self, name, age, student_id):
# Call parent constructor
super().__init__(name, age)
self.student_id = student_id
[Link] = []

def add_grade(self, grade):

[Link](grade)

def get_average(self):
return sum([Link]) / len([Link]) if [Link] else 0

# Multiple Inheritance: TeachingAssistant inherits from Person and Student

class TeachingAssistant(Student, Person):
"""TA that is both a Student and a Person"""
def __init__(self, name, age, student_id, department):
Person.__init__(self, name, age)
Student.__init__(self, name, age, student_id)
[Link] = department

# Multilevel Inheritance: GraduateStudent -> Student -> Person

class GraduateStudent(Student):
"""Graduate student (extends Student)"""
def __init__(self, name, age, student_id, thesis_topic):
super().__init__(name, age, student_id)
 self.thesis_topic = thesis_topic
self.research_area = "Computer Science"

# Using inheritance
student = Student("John", 17, "S001")
print([Link]()) # From parent class

grad_student = GraduateStudent("Mary", 24, "G001", "AI Research")

print(grad_student.introduce())
print(f"Research: {grad_student.research_area}")

# Check inheritance
print(f"isinstance(student, Person): {isinstance(student, Person)}") # True
print(f"issubclass(GraduateStudent, Student): {issubclass(GraduateStudent,
Student)}") # True

Explanation: Inheritance types:

 Single: One parent, one child class

 Multiple: Child inherits from multiple parents
 Multilevel: Grandparent → Parent → Child
 Hierarchical: One parent, multiple children
 super(): Calls parent class methods
 isinstance() and issubclass(): Check inheritance relationships

Example 4: Polymorphism (Python)

// Python - Polymorphism
# Different classes with same method names

class Shape:
"""Base shape class"""
def area(self):
"""Calculate area (to be overridden)"""
raise NotImplementedError("Subclass must implement area()")

class Rectangle(Shape):
def __init__(self, width, height):
[Link] = width
[Link] = height

def area(self): # Override parent's method

return [Link] * [Link]

class Circle(Shape):
def __init__(self, radius):
[Link] = radius

def area(self): # Override parent's method

import math
return [Link] * [Link] ** 2

class Triangle(Shape):
def __init__(self, base, height):
 [Link] = base
[Link] = height

def area(self): # Override parent's method

return 0.5 * [Link] * [Link]

# Polymorphic function
def print_area(shape):
"""Print area of any shape - polymorphism in action"""
print(f"Area: {[Link]():.2f}")

# Using polymorphism
shapes = [
Rectangle(5, 3),
Circle(4),
Triangle(6, 4)
]

for shape in shapes:

print_area(shape) # Works with any shape type!

# Output:
# Area: 15.00
# Area: 50.27
# Area: 12.00

# Operator overloading
class Vector:
def __init__(self, x, y):
self.x = x
self.y = y

def __add__(self, other): # Overload + operator

return Vector(self.x + other.x, self.y + other.y)

def __str__(self):
return f"({self.x}, {self.y})"

v1 = Vector(1, 2)
v2 = Vector(3, 4)
v3 = v1 + v2 # Uses __add__ method
print(v3) # (4, 6)

Explanation: Polymorphism types:

 Method overriding: Child class redefines parent method

 Duck typing: Object behavior matters, not type
 Operator overloading: Custom behavior for operators
 Runtime polymorphism: Method resolution at runtime

Example 5: Abstraction (Python)

// Python - Abstraction using Abstract Classes
from abc import ABC, abstractmethod
# Abstract base class
class Vehicle(ABC):
"""Abstract class representing a vehicle"""

def __init__(self, brand, model):

[Link] = brand
[Link] = model

@abstractmethod
def calculate_fuel_efficiency(self):
"""Abstract method - must be implemented by subclasses"""
pass

def display_info(self):
"""Concrete method - shared by all vehicles"""
return f"{[Link]} {[Link]}"

# Concrete implementations
class Car(Vehicle):
def __init__(self, brand, model, num_doors, engine_size):
super().__init__(brand, model)
self.num_doors = num_doors
self.engine_size = engine_size

def calculate_fuel_efficiency(self):
# Real implementation
return 30 - (self.engine_size * 2) # km/L

class Motorcycle(Vehicle):
def __init__(self, brand, model, engine_cc):
super().__init__(brand, model)
self.engine_cc = engine_cc

def calculate_fuel_efficiency(self):
return 40 + (self.engine_cc / 100) # km/L

# Using abstraction
car = Car("Toyota", "Corolla", 4, 1.8)
moto = Motorcycle("Honda", "CBR", 600)

print(car.display_info())
print(f"Fuel efficiency: {car.calculate_fuel_efficiency()} km/L")

print(moto.display_info())
print(f"Fuel efficiency: {moto.calculate_fuel_efficiency()} km/L")

# Cannot instantiate abstract class

# vehicle = Vehicle("Generic", "Car") # TypeError!

Explanation: Abstraction benefits:

 Hides complex implementation details

 ABC (Abstract Base Class): Cannot be instantiated
 @abstractmethod: Must be implemented by subclasses
 Provides clear interface for users
 Enforces implementation in child classes

Example 6: Composition (Python)

// Python - Composition
class Engine:
"""Component class"""
def __init__(self, horsepower):
[Link] = horsepower

def start(self):
return "Engine started!"

class Car:
"""Car class with composition (HAS-A relationship)"""
def __init__(self, make, model, engine_hp):
[Link] = make
[Link] = model
[Link] = Engine(engine_hp) # Composition: Car HAS Engine

def start_car(self):
return f"{[Link]} {[Link]}: {[Link]()}"

def get_horsepower(self):
return [Link]

# Using composition
my_car = Car("Toyota", "Camry", 200)
print(my_car.start_car())
print(f"Horsepower: {my_car.get_horsepower()}")

# Address book example with composition

class Address:
def __init__(self, street, city, country):
[Link] = street
[Link] = city
[Link] = country

class Contact:
def __init__(self, name, email, address):
[Link] = name
[Link] = email
[Link] = address # Composition

def display(self):
return f"{[Link]}\n{[Link]}\n{[Link]}"

contact = Contact("John", "john@[Link]",

Address("123 Main St", "Harare", "Zimbabwe"))
print([Link]())

Explanation: Composition vs Inheritance:

 Composition: "HAS-A" relationship (Car HAS Engine)

 Inheritance: "IS-A" relationship (Student IS-A Person)
 Composition is more flexible and loosely coupled
 Use composition when possible for better design

Example 7: Advanced File Handling with Exception Handling

// Python - Advanced File Handling with Exception Handling
import os
import json

class FileHandler:
"""Advanced file handling with error handling"""

@staticmethod
def read_file_safe(filename):
"""Read file with comprehensive error handling"""
try:
with open(filename, 'r', encoding='utf-8') as file:
content = [Link]()
return content, None
except FileNotFoundError:
return None, "File not found!"
except PermissionError:
return None, "Permission denied!"
except UnicodeDecodeError:
return None, "Encoding error!"
except Exception as e:
return None, f"Unexpected error: {str(e)}"

@staticmethod
def write_file_safe(filename, content):
"""Write file with backup"""
backup_name = filename + ".bak"

# Create backup if file exists

if [Link](filename):
try:
with open(filename, 'r') as src:
with open(backup_name, 'w') as dst:
[Link]([Link]())
except:
pass # Backup failed, continue anyway

try:
with open(filename, 'w', encoding='utf-8') as file:
[Link](content)
return True, "File written successfully!"
except Exception as e:
return False, f"Write error: {str(e)}"

@staticmethod
def read_csv_like_data(filename):
"""Read and parse CSV-like data"""
data = []
content, error = FileHandler.read_file_safe(filename)
 if error:
return None, error

lines = [Link]().split('\n')
headers = lines[0].split(',')

for line in lines[1:]:

values = [Link](',')
if len(values) == len(headers):
[Link](dict(zip(headers, values)))

return data, None

# Using the file handler

content, error = FileHandler.read_file_safe("[Link]")
if error:
print(f"Error: {error}")
else:
print("File content:")
print(content)

# JSON handling
def save_to_json(filename, data):
"""Save data to JSON file"""
try:
with open(filename, 'w') as f:
[Link](data, f, indent=4)
return True
except Exception as e:
print(f"JSON save error: {e}")
return False

def load_from_json(filename):
"""Load data from JSON file"""
try:
with open(filename, 'r') as f:
return [Link](f), None
except Exception as e:
return None, str(e)

# Example
students = [
{"name": "John", "age": 17},
{"name": "Mary", "age": 16}
]
save_to_json("[Link]", students)
data, _ = load_from_json("[Link]")
print(data)

Explanation: Exception handling patterns:

 try-except: Catch and handle exceptions

 Specific exceptions first: FileNotFoundError, then Exception
 return error as tuple: (data, error) for clean handling
 with statement: Automatically closes files

Example 8: Advanced Data Structures - Stacks and Queues

// Python - Stack and Queue Implementation
class Stack:
"""LIFO (Last In First Out) data structure"""

def __init__(self):
[Link] = []

def push(self, item):

"""Add item to top of stack"""
[Link](item)

def pop(self):
"""Remove and return top item"""
if self.is_empty():
return None
return [Link]()

def peek(self):
"""Return top item without removing"""
if self.is_empty():
return None
return [Link][-1]

def is_empty(self):
return len([Link]) == 0

def size(self):
return len([Link])

def __str__(self):
return str([Link])

class Queue:
"""FIFO (First In First Out) data structure"""

def __init__(self):
[Link] = []

def enqueue(self, item):

"""Add item to rear of queue"""
[Link](0, item)

def dequeue(self):
"""Remove and return front item"""
if self.is_empty():
return None
return [Link]()

def front(self):
"""Return front item without removing"""
if self.is_empty():
 return None
return [Link][-1]

def is_empty(self):
return len([Link]) == 0

def size(self):
return len([Link])

# Using Stack - Check balanced parentheses

def is_balanced(expression):
"""Check if parentheses are balanced"""
stack = Stack()
matching = {')': '(', '}': '{', ']': '['}

for char in expression:

if char in '({[':
[Link](char)
elif char in ')}]':
if stack.is_empty() or [Link]() != matching[char]:
return False

return stack.is_empty()

# Using Queue - Printer simulation

from collections import deque

class PrinterQueue:
"""Simulate a printer queue"""
def __init__(self):
[Link] = deque()

def add_job(self, document):

[Link](document)

def print_job(self):
if [Link]:
job = [Link]()
print(f"Printing: {job}")
return job
return None

# Test
stack = Stack()
[Link](1)
[Link](2)
[Link](3)
print(f"Stack: {stack}") # [1, 2, 3]
print(f"Pop: {[Link]()}") # 3
print(f"Peek: {[Link]()}") # 2

print(f"Balanced '()': {is_balanced('()')}") # True

print(f"Balanced '({[ ]})': {is_balanced('({[ ]})')}") # False

queue = Queue()
[Link]("Doc1")
[Link]("Doc2")
[Link]("Doc3")
print(f"Queue: {[Link]}") # ['Doc3', 'Doc2', 'Doc1']
print(f"Dequeue: {[Link]()}") # Doc1

Explanation: Stack and Queue applications:

 Stack: Undo operations, function calls, expression evaluation

 Queue: Print spooling, task scheduling, BFS
 Stack: push/pop - O(1) with list
 Queue: enqueue/dequeue - O(1) with [Link]

Example 9: Linked List Implementation

// Python - Singly Linked List Implementation
class Node:
"""Node class for linked list"""
def __init__(self, data):
[Link] = data
[Link] = None

class LinkedList:
"""Singly linked list implementation"""

def __init__(self):
[Link] = None
[Link] = 0

def append(self, data):

"""Add element to end of list"""
new_node = Node(data)

if [Link] is None:
[Link] = new_node
else:
current = [Link]
while [Link]:
current = [Link]
[Link] = new_node

[Link] += 1

def prepend(self, data):

"""Add element to beginning of list"""
new_node = Node(data)
new_node.next = [Link]
[Link] = new_node
[Link] += 1

def delete(self, data):

"""Delete first occurrence of data"""
if [Link] is None:
return False
 if [Link] == data:
[Link] = [Link]
[Link] -= 1
return True

current = [Link]
while [Link]:
if [Link] == data:
[Link] = [Link]
[Link] -= 1
return True
current = [Link]

return False

def find(self, data):

"""Find element and return index"""
current = [Link]
index = 0

while current:
if [Link] == data:
return index
current = [Link]
index += 1

return -1

def __str__(self):
"""String representation"""
elements = []
current = [Link]
while current:
[Link](str([Link]))
current = [Link]
return " -> ".join(elements) + " -> None"

def get_size(self):
return [Link]

def is_empty(self):
return [Link] == 0

# Using the linked list

ll = LinkedList()
[Link](1)
[Link](2)
[Link](3)
[Link](0)

print(f"List: {ll}") # 0 -> 1 -> 2 -> 3 -> None

print(f"Size: {ll.get_size()}") # 4
print(f"Find 2: {[Link](2)}") # 2
[Link](2)
print(f"After delete: {ll}") # 0 -> 1 -> 3 -> None
Explanation: Linked List vs Array:

 Array: O(1) random access, O(n) insertion/deletion

 Linked List: O(n) random access, O(1) insertion/deletion at known position
 Linked List: Dynamic size, no wasted memory
 Array: Better cache performance, simpler implementation

Example 10: Exception Classes and Custom Exceptions

// Python - Custom Exception Classes
class InvalidAgeError(Exception):
"""Raised when age is invalid"""
def __init__(self, age, message="Age must be between 0 and 150"):
[Link] = age
[Link] = message
super().__init__([Link])

class InsufficientFundsError(Exception):
"""Raised when withdrawal exceeds balance"""
def __init__(self, balance, amount):
[Link] = balance
[Link] = amount
[Link] = f"Insufficient funds: Balance ${balance}, Requested $
{amount}"
super().__init__([Link])

class BankAccount:
"""Bank account with custom exception handling"""

def __init__(self, account_holder, initial_balance=0):

self.account_holder = account_holder
self.__balance = initial_balance

@property
def balance(self):
return self.__balance

def deposit(self, amount):

if amount <= 0:
raise ValueError("Deposit amount must be positive")
self.__balance += amount
return self.__balance

def withdraw(self, amount):

if amount <= 0:
raise ValueError("Withdrawal amount must be positive")
if amount > self.__balance:
raise InsufficientFundsError(self.__balance, amount)
self.__balance -= amount
return self.__balance

def set_age(self, age):

if not 0 <= age <= 150:
raise InvalidAgeError(age)
 self.__age = age

# Using custom exceptions

account = BankAccount("John", 1000)

try:
[Link](2000)
except InsufficientFundsError as e:
print(f"Error: {[Link]}")
print(f"Balance: ${[Link]}, Attempted: ${[Link]}")

try:
account.set_age(200)
except InvalidAgeError as e:
print(f"Invalid age: {[Link]} - {[Link]}")

# Chaining exceptions
class DatabaseConnectionError(Exception):
"""Base exception for database errors"""
pass

class DatabaseConnectionTimeout(DatabaseConnectionError):
"""Connection timeout specific error"""
pass

class DatabaseQueryError(DatabaseConnectionError):
"""Query execution error"""
pass

Explanation: Custom exception benefits:

 Semantic meaning: Descriptive names like InsufficientFundsError

 Encapsulation: Store related error data in exception
 Hierarchical: Group related exceptions (DatabaseConnectionError)
 Better debugging: Clear indication of what went wrong

2.2 Exercises: Advanced Programming

Exercise 1: Bank Account Class

Create a BankAccount class with encapsulation. Include methods for deposit, withdrawal,
and balance inquiry. Add validation to prevent negative deposits and overdrafts.

Exercise 2: Inheritance Hierarchy

Create an inheritance hierarchy for a zoo: Animal (base class) → Mammal, Bird → specific
animals like Lion, Eagle.

Exercise 3: Shape Polymorphism

Create an abstract Shape class with an area() method. Implement Circle, Rectangle, and
Triangle subclasses. Write a function that calculates total area of a list of shapes.
Exercise 4: Linked List Operations
Extend the LinkedList class with methods to reverse the list and find the middle element.

Exercise 5: Custom Exception

Create a custom InvalidGradeError exception and use it in a Student class that validates
grades between 0 and 100.

ANSWERS

Answer 1: Bank Account Class

class BankAccount:
def __init__(self, account_holder, balance=0):
self._account_holder = account_holder # Protected
self.__balance = balance # Private

def deposit(self, amount):

if amount < 0:
raise ValueError("Cannot deposit negative amount")
self.__balance += amount
return self.__balance

def withdraw(self, amount):

if amount < 0:
raise ValueError("Cannot withdraw negative amount")
if amount > self.__balance:
raise ValueError("Insufficient funds")
self.__balance -= amount
return self.__balance

def get_balance(self):
return self.__balance

Answer 2: Zoo Inheritance Hierarchy

class Animal:
def __init__(self, name, age):
[Link] = name
[Link] = age

def speak(self):
raise NotImplementedError

class Mammal(Animal):
def __init__(self, name, age, fur_color):
super().__init__(name, age)
self.fur_color = fur_color

class Bird(Animal):
def __init__(self, name, age, wing_span):
super().__init__(name, age)
self.wing_span = wing_span

class Lion(Mammal):
 def speak(self):
return "Roar!"

class Eagle(Bird):
def speak(self):
return "Screech!"

Answer 3: Shape Polymorphism

from abc import ABC, abstractmethod

class Shape(ABC):
@abstractmethod
def area(self):
pass

class Circle(Shape):
def __init__(self, radius):
[Link] = radius
def area(self):
return 3.14 * [Link] ** 2

class Rectangle(Shape):
def __init__(self, width, height):
[Link] = width
[Link] = height
def area(self):
return [Link] * [Link]

def total_area(shapes):
return sum([Link]() for shape in shapes)

Answer 4: Linked List Operations

def reverse(self):
prev = None
current = [Link]
while current:
next_node = [Link]
[Link] = prev
prev = current
current = next_node
[Link] = prev

def find_middle(self):
slow = fast = [Link]
while fast and [Link]:
slow = [Link]
fast = [Link]
return [Link]

Answer 5: Custom Exception

class InvalidGradeError(Exception):
def __init__(self, grade):
[Link] = grade
 super().__init__(f"Invalid grade: {grade}")

class Student:
def add_grade(self, grade):
if not 0 <= grade <= 100:
raise InvalidGradeError(grade)
[Link](grade)

PART 3: ADVANCED DATABASE SYSTEMS

3.1 Database Normalization (3NF)

Third Normal Form (3NF) builds on 2NF by removing transitive dependencies. A table is in
3NF if it is in 2NF and no non-key attribute depends on another non-key attribute.

Example 1: Normalization to 3NF

-- UNNORMALIZED TABLE
/*
StudentCourseEnrollment:
StudentID | StudentName | Age | CourseID | CourseName | Instructor | DeptName |
DeptHead
S001 | John Smith | 17 | C001 | Programming| Dr. Brown | CS |
Prof. A
S001 | John Smith | 17 | C002 | Database | Dr. Jones | CS |
Prof. A
S002 | Mary Jane | 18 | C001 | Programming| Dr. Brown | CS |
Prof. A
S003 | Bob Wilson | 17 | C003 | Networks | Dr. Smith | CS |
Prof. A
*/

-- Problems with unnormalized:

-- 1. Data redundancy (CS Dept info repeated)
-- 2. Update anomaly (changing DeptHead requires multiple updates)
-- 3. Insertion anomaly (can't add department without student)
-- 4. Delete anomaly (deleting student removes department info)

-- NORMALIZATION TO 3NF:

-- Table 1: Students (StudentID is key)

CREATE TABLE Students (
StudentID VARCHAR(10) PRIMARY KEY,
StudentName VARCHAR(50) NOT NULL,
Age INT
);

-- Table 2: Courses (CourseID is key)

CREATE TABLE Courses (
CourseID VARCHAR(10) PRIMARY KEY,
CourseName VARCHAR(50) NOT NULL,
Instructor VARCHAR(50),
DeptID VARCHAR(10) NOT NULL -- Foreign key to Departments
);
-- Table 3: Departments (DeptID is key)
CREATE TABLE Departments (
DeptID VARCHAR(10) PRIMARY KEY,
DeptName VARCHAR(50) NOT NULL,
DeptHead VARCHAR(50) NOT NULL
);

-- Table 4: Enrollments (links Students and Courses)

CREATE TABLE Enrollments (
EnrollmentID INT PRIMARY KEY AUTO_INCREMENT,
StudentID VARCHAR(10) NOT NULL,
CourseID VARCHAR(10) NOT NULL,
FOREIGN KEY (StudentID) REFERENCES Students(StudentID),
FOREIGN KEY (CourseID) REFERENCES Courses(CourseID)
);

-- Why is this in 3NF?

-- 1NF: All values are atomic
-- 2NF: No partial dependencies (all non-keys depend on full primary key)
-- 3NF: No transitive dependencies
-- - DeptName depends on DeptID (not directly on StudentID/CourseID)
-- - DeptHead depends on DeptName (transitive) -> SOLVED with Departments
table

Explanation: 3NF requirements:

 1NF: Atomic values, no repeating groups

 2NF: 1NF + No partial dependencies on composite keys
 3NF: 2NF + No transitive dependencies
 Transitive dependency: A → B → C where A is PK

Example 2: Complex SQL Queries

-- Complex SQL Queries with Multiple JOINs

-- Query: Get student details with enrolled courses and grades

SELECT
[Link],
[Link],
[Link],
[Link],
[Link]
FROM Students s
INNER JOIN Enrollments e ON [Link] = [Link]
INNER JOIN Courses c ON [Link] = [Link]
INNER JOIN Departments d ON [Link] = [Link]
WHERE [Link] IN ('A', 'B', 'A+', 'A-', 'B+')
ORDER BY [Link], [Link];

-- Query: Students with average grade above 75

SELECT
[Link],
[Link],
AVG([Link]) AS AvgGradePoint,
 COUNT([Link]) AS CoursesEnrolled
FROM Students s
INNER JOIN Enrollments e ON [Link] = [Link]
INNER JOIN Grades g ON [Link] = [Link]
GROUP BY [Link], [Link]
HAVING AVG([Link]) > 3.0
ORDER BY AvgGradePoint DESC;

-- Query: Courses with enrollment statistics

SELECT
[Link],
[Link],
COUNT([Link]) AS TotalStudents,
AVG([Link]) AS AvgGrade,
MAX([Link]) AS HighestGrade,
MIN([Link]) AS LowestGrade
FROM Courses c
LEFT JOIN Enrollments e ON [Link] = [Link]
LEFT JOIN Grades g ON [Link] = [Link]
GROUP BY [Link], [Link]
HAVING COUNT([Link]) > 0
ORDER BY TotalStudents DESC;

-- Query: Subquery - Find students enrolled in more courses than average

SELECT
[Link],
COUNT([Link]) AS CourseCount
FROM Students s
INNER JOIN Enrollments e ON [Link] = [Link]
GROUP BY [Link], [Link]
HAVING COUNT([Link]) > (
SELECT AVG(CourseCount)
FROM (SELECT COUNT(CourseID) AS CourseCount
FROM Enrollments
GROUP BY StudentID) AS CourseCounts
);

Explanation: Complex query techniques:

 Multiple JOINs: Connect related tables

 Subqueries: Nested SELECT statements
 HAVING: Filter groups (like WHERE for groups)
 Aggregate functions: COUNT, AVG, MAX, MIN

Example 3: Database Triggers

-- SQL Triggers for Automation

-- Trigger: Auto-update course enrollment count

DELIMITER //
CREATE TRIGGER after_enrollment_insert
AFTER INSERT ON Enrollments
FOR EACH ROW
BEGIN
UPDATE Courses
 SET EnrollmentCount = EnrollmentCount + 1
WHERE CourseID = [Link];

-- Log the enrollment

INSERT INTO EnrollmentLog (Action, StudentID, CourseID, ActionDate)
VALUES ('INSERT', [Link], [Link], NOW());
END//

-- Trigger: Prevent deletion of core courses

CREATE TRIGGER prevent_course_deletion
BEFORE DELETE ON Courses
FOR EACH ROW
BEGIN
IF [Link] = TRUE THEN
SIGNAL SQLSTATE '45000'
SET MESSAGE_TEXT = 'Cannot delete core courses';
END IF;
END//

-- Trigger: Auto-set enrollment date

CREATE TRIGGER set_enrollment_date
BEFORE INSERT ON Enrollments
FOR EACH ROW
BEGIN
IF [Link] IS NULL THEN
SET [Link] = CURDATE();
END IF;
END//

DELIMITER ;

-- Trigger: Audit trail for grade changes

CREATE TABLE GradeAudit (
AuditID INT AUTO_INCREMENT PRIMARY KEY,
StudentID VARCHAR(10),
OldGrade VARCHAR(2),
NewGrade VARCHAR(2),
ChangedBy VARCHAR(50),
ChangeDate DATETIME
);

CREATE TRIGGER grade_change_audit

AFTER UPDATE ON Enrollments
FOR EACH ROW
BEGIN
IF [Link] != [Link] THEN
INSERT INTO GradeAudit (StudentID, OldGrade, NewGrade, ChangedBy,
ChangeDate)
VALUES ([Link], [Link], [Link], USER(), NOW());
END IF;
END//

Explanation: Database triggers:

 BEFORE/AFTER: When trigger fires

 INSERT/UPDATE/DELETE: Trigger events
 NEW/OLD: Reference new/old values
 SIGNAL: Raise custom errors

Example 4: Stored Procedures

-- SQL Stored Procedures

DELIMITER //

-- Procedure: Calculate and update student GPA

CREATE PROCEDURE CalculateStudentGPA(IN student_id VARCHAR(10))
BEGIN
DECLARE total_points DECIMAL(5,2);
DECLARE total_credits INT;

-- Calculate total quality points

SELECT SUM([Link] * [Link]), SUM([Link])
INTO total_points, total_credits
FROM Enrollments e
INNER JOIN Courses c ON [Link] = [Link]
INNER JOIN Grades g ON [Link] = [Link]
WHERE [Link] = student_id;

-- Update student GPA if they have courses

IF total_credits > 0 THEN
UPDATE Students
SET GPA = total_points / total_credits,
TotalCredits = total_credits
WHERE StudentID = student_id;
END IF;
END//

-- Procedure: Enroll student in course with validation

CREATE PROCEDURE EnrollStudent(
IN p_student_id VARCHAR(10),
IN p_course_id VARCHAR(10),
OUT p_result VARCHAR(100)
)
BEGIN
DECLARE v_student_count INT;
DECLARE v_course_exists INT;

-- Check if already enrolled

SELECT COUNT(*) INTO v_student_count
FROM Enrollments
WHERE StudentID = p_student_id AND CourseID = p_course_id;

IF v_student_count > 0 THEN

SET p_result = 'Student already enrolled in this course';
ELSE
-- Check prerequisites (simplified)
-- In reality, this would check Prerequisite table

INSERT INTO Enrollments (StudentID, CourseID, EnrollmentDate)

 VALUES (p_student_id, p_course_id, CURDATE());

SET p_result = 'Enrollment successful';

END IF;
END//

-- Procedure: Generate enrollment report

CREATE PROCEDURE GenerateEnrollmentReport()
BEGIN
SELECT
[Link],
[Link],
COUNT([Link]) AS EnrolledStudents,
CASE
WHEN COUNT([Link]) = 0 THEN 'No Enrollment'
WHEN COUNT([Link]) < 10 THEN 'Low Enrollment'
WHEN COUNT([Link]) < 30 THEN 'Normal'
ELSE 'High Enrollment'
END AS Status
FROM Departments d
INNER JOIN Courses c ON [Link] = [Link]
LEFT JOIN Enrollments e ON [Link] = [Link]
GROUP BY [Link], [Link], [Link]
ORDER BY [Link], EnrolledStudents DESC;
END//

DELIMITER ;

-- Call stored procedures

CALL CalculateStudentGPA('S001');
CALL EnrollStudent('S001', 'CS101', @result);
SELECT @result;
CALL GenerateEnrollmentReport();

Explanation: Stored procedures:

 Pre-compiled SQL code stored in database

 IN parameters: Input to procedure
 OUT parameters: Return values from procedure
 Benefits: Performance, security, maintainability

Example 5: Database Transactions

-- SQL Transactions for Data Integrity

-- Start a transaction
START TRANSACTION;

-- Transfer funds from one account to another

UPDATE Accounts SET Balance = Balance - 500 WHERE AccountID = 'ACC001';
UPDATE Accounts SET Balance = Balance + 500 WHERE AccountID = 'ACC002';

-- Record the transaction

INSERT INTO Transactions (FromAccount, ToAccount, Amount, TransactionDate)
VALUES ('ACC001', 'ACC002', 500, NOW());
-- If all successful, commit
COMMIT;

-- If error occurs, rollback

-- ROLLBACK;

-- Example with error handling

DELIMITER //
CREATE PROCEDURE TransferFunds(
IN from_acc VARCHAR(10),
IN to_acc VARCHAR(10),
IN amount DECIMAL(10,2),
OUT p_success BOOLEAN
)
BEGIN
DECLARE EXIT HANDLER FOR SQLEXCEPTION
BEGIN
ROLLBACK;
SET p_success = FALSE;
END;

START TRANSACTION;

-- Check sufficient balance

IF (SELECT Balance FROM Accounts WHERE AccountID = from_acc) < amount THEN
ROLLBACK;
SET p_success = FALSE;
ELSE
UPDATE Accounts SET Balance = Balance - amount WHERE AccountID =
from_acc;
UPDATE Accounts SET Balance = Balance + amount WHERE AccountID = to_acc;
INSERT INTO Transactions (FromAccount, ToAccount, Amount) VALUES
(from_acc, to_acc, amount);
COMMIT;
SET p_success = TRUE;
END IF;
END//
DELIMITER ;

-- ACID Properties:
-- Atomicity: All or nothing (transaction complete)
-- Consistency: Database stays valid
-- Isolation: Concurrent transactions don't interfere
-- Durability: Committed changes are permanent

Explanation: Transaction management:

 COMMIT: Save changes permanently

 ROLLBACK: Undo all changes in transaction
 ACID: Atomicity, Consistency, Isolation, Durability
 EXIT HANDLER: Catch and handle errors
Example 6: Database Indexing
-- SQL Indexes for Performance

-- Create index on frequently queried column

CREATE INDEX idx_student_name ON Students(LastName, FirstName);

-- Create unique index (prevents duplicates)

CREATE UNIQUE INDEX idx_email ON Students(Email);

-- Create composite index for multi-column queries

CREATE INDEX idx_enrollment_student_course
ON Enrollments(StudentID, CourseID);

-- Create index with WHERE clause (partial index)

CREATE INDEX idx_active_students
ON Students(StudentID)
WHERE Status = 'Active';

-- Drop index
DROP INDEX idx_student_name ON Students;

-- EXPLAIN to analyze query performance

EXPLAIN SELECT * FROM Students WHERE LastName = 'Smith';

EXPLAIN ANALYZE
SELECT [Link], [Link]
FROM Students s
INNER JOIN Enrollments e ON [Link] = [Link]
INNER JOIN Courses c ON [Link] = [Link]
WHERE [Link] = 'Smith';

-- Index types:
-- B-Tree (default): Range queries, equality
-- Hash: Fast equality lookups
-- Full-text: Text search
-- Spatial: Geographic data

-- Best practices:
-- 1. Index columns used in WHERE, JOIN, ORDER BY
-- 2. Don't over-index (slows down INSERT/UPDATE)
-- 3. Consider selectivity (unique values / total rows)
-- 4. Monitor query performance with EXPLAIN

Explanation: Database indexing:

 Indexes speed up data retrieval

 Trade-off: Faster reads, slower writes
 B-Tree: Default, good for most cases
 Composite: Multiple columns in one index
 EXPLAIN: Analyze query execution plan
Example 7: Database Security
-- SQL Database Security

-- Create user with limited privileges

CREATE USER 'student_app'@'localhost'
IDENTIFIED BY 'secure_password123';

-- Grant specific privileges

GRANT SELECT, INSERT, UPDATE ON [Link] TO 'student_app'@'localhost';
GRANT SELECT ON [Link] TO 'student_app'@'localhost';

-- Grant read-only access to specific columns

GRANT SELECT (StudentID, FirstName, LastName)
ON [Link] TO 'student_app'@'localhost';

-- Revoke privileges
REVOKE INSERT ON [Link] FROM 'student_app'@'localhost';

-- Create role
CREATE ROLE 'course_admin';
GRANT ALL ON [Link] TO 'course_admin';
GRANT 'course_admin' TO 'admin_user'@'localhost';

-- Row-level security (simulated with views)

CREATE VIEW StudentGradeView AS
SELECT
StudentID,
CourseID,
Grade
FROM Enrollments;

-- Prevent access to sensitive data

CREATE VIEW PublicStudentInfo AS
SELECT StudentID, FirstName, LastName
FROM Students;

-- Audit table for security monitoring

CREATE TABLE AccessAudit (
AuditID INT AUTO_INCREMENT PRIMARY KEY,
UserName VARCHAR(50),
ActionType VARCHAR(20),
TableAccessed VARCHAR(50),
AccessTime DATETIME,
IPAddress VARCHAR(20)
);

-- Trigger to log access

CREATE TRIGGER audit_student_access
AFTER SELECT ON Students
FOR EACH ROW
BEGIN
INSERT INTO AccessAudit (UserName, ActionType, TableAccessed, AccessTime)
VALUES (USER(), 'SELECT', 'Students', NOW());
END//
-- Best practices:
-- 1. Principle of least privilege
-- 2. Use roles for permission management
-- 3. Regular password rotation
-- 4. Encrypt sensitive data at rest
-- 5. Use parameterized queries (prevent SQL injection)

Explanation: Database security:

 User accounts: Limit access per user

 GRANT/REVOKE: Control privileges
 Roles: Group privileges for easier management
 Views: Restrict data access
 Encryption: Protect sensitive data

Example 8: Database Backup and Recovery

-- MySQL Backup and Recovery Commands

-- Full backup using mysqldump

mysqldump -u root -p SchoolDB > backup_2024.sql

-- Backup specific tables

mysqldump -u root -p SchoolDB Students Enrollments > tables_backup.sql

-- Backup with compression

mysqldump -u root -p SchoolDB | gzip > [Link]

-- Restore from backup

mysql -u root -p SchoolDB < backup_2024.sql

-- Point-in-time recovery using binary logs

-- First restore from last full backup
mysql -u root -p SchoolDB < backup_2024.sql
-- Then apply binary logs
mysqlbinlog binlog.000001 | mysql -u root -p

-- Export data to CSV

SELECT StudentID, FirstName, LastName
INTO OUTFILE '/tmp/[Link]'
FIELDS TERMINATED BY ','
ENCLOSED BY '"'
LINES TERMINATED BY '\n'
FROM Students;

-- Import data from CSV

LOAD DATA INFILE '/tmp/[Link]'
INTO TABLE Students
FIELDS TERMINATED BY ','
ENCLOSED BY '"'
LINES TERMINATED BY '\n';

-- Backup strategies:
-- 1. Full backup: Complete database copy
-- 2. Incremental: Changes since last backup
-- 3. Differential: Changes since last full backup
-- 4. Point-in-time: Specific moment recovery

-- Python script for automated backup

import subprocess
from datetime import datetime

def backup_database():
timestamp = [Link]().strftime('%Y%m%d_%H%M%S')
filename = f'backup_{timestamp}.sql'

result = [Link]([
'mysqldump', '-u', 'root', '-pPassword',
'SchoolDB', '>', filename
])

return [Link] == 0, filename

Explanation: Backup strategies:

 Full backup: Complete copy, largest size

 Incremental: Changes only, smallest
 Differential: Since last full, medium
 Point-in-time: Using transaction logs

Example 9: Database Connectivity from Python

// Python - Database Connectivity using sqlite3
import sqlite3

def create_connection(db_file):
"""Create a database connection"""
try:
conn = [Link](db_file)
print(f"Connected to {db_file}")
return conn
except [Link] as e:
print(f"Error: {e}")
return None

def execute_query(conn, query, data=None):

"""Execute INSERT/UPDATE/DELETE query"""
try:
cursor = [Link]()
if data:
[Link](query, data)
else:
[Link](query)
[Link]()
return [Link]
except [Link] as e:
print(f"Error: {e}")
[Link]()
 return None

def execute_select(conn, query, data=None):

"""Execute SELECT query"""
try:
cursor = [Link]()
if data:
[Link](query, data)
else:
[Link](query)
return [Link]()
except [Link] as e:
print(f"Error: {e}")
return None

# Using the database functions

conn = create_connection('[Link]')

# Create tables
create_table_sql = """
CREATE TABLE IF NOT EXISTS Students (
StudentID TEXT PRIMARY KEY,
FirstName TEXT NOT NULL,
LastName TEXT NOT NULL,
Age INTEGER
);
"""
execute_query(conn, create_table_sql)

# Insert data using parameterized query (prevents SQL injection)

insert_sql = "INSERT INTO Students VALUES (?, ?, ?, ?)"
student_data = ('S001', 'John', 'Smith', 17)
execute_query(conn, insert_sql, student_data)

# Query data
select_sql = "SELECT * FROM Students WHERE LastName = ?"
results = execute_select(conn, select_sql, ('Smith',))

for row in results:

print(f"ID: {row[0]}, Name: {row[1]} {row[2]}, Age: {row[3]}")

[Link]()

# Using SQLite with context manager

with [Link]('[Link]') as conn:
cursor = [Link]()
[Link]("SELECT * FROM Students")
for row in [Link]():
print(row)

Explanation: Python database connectivity:

 sqlite3: Built-in Python module for SQLite

 [Link](): Run SQL queries
 Parameterized queries: Prevent SQL injection
 commit(): Save changes
 context manager (with): Auto-close connection

Example 10: Database Design Patterns

// Database Design Patterns

-- PATTERN 1: Many-to-Many Relationship

-- Student takes multiple Courses, Course has multiple Students

CREATE TABLE Students (

StudentID VARCHAR(10) PRIMARY KEY,
StudentName VARCHAR(50)
);

CREATE TABLE Courses (

CourseID VARCHAR(10) PRIMARY KEY,
CourseName VARCHAR(50)
);

-- Junction/Bridge table
CREATE TABLE StudentCourses (
StudentID VARCHAR(10),
CourseID VARCHAR(10),
EnrollmentDate DATE,
PRIMARY KEY (StudentID, CourseID),
FOREIGN KEY (StudentID) REFERENCES Students(StudentID),
FOREIGN KEY (CourseID) REFERENCES Courses(CourseID)
);

-- PATTERN 2: One-to-One Relationship

-- Each Student has one StudentProfile

CREATE TABLE StudentProfiles (

StudentID VARCHAR(10) PRIMARY KEY,
Bio TEXT,
ProfilePicture BLOB,
FOREIGN KEY (StudentID) REFERENCES Students(StudentID)
);

-- PATTERN 3: Self-Referencing
-- Employee reports to another Employee

CREATE TABLE Employees (

EmployeeID VARCHAR(10) PRIMARY KEY,
EmployeeName VARCHAR(50),
ManagerID VARCHAR(10),
FOREIGN KEY (ManagerID) REFERENCES Employees(EmployeeID)
);

-- PATTERN 4: Hierarchical Data (Adjacency List)

-- Categories with subcategories

CREATE TABLE Categories (

CategoryID INT PRIMARY KEY AUTO_INCREMENT,
 CategoryName VARCHAR(50),
ParentCategoryID INT,
FOREIGN KEY (ParentCategoryID) REFERENCES Categories(CategoryID)
);

-- PATTERN 5: Audit Fields (Created/Modified tracking)

CREATE TABLE Products (

ProductID INT PRIMARY KEY AUTO_INCREMENT,
ProductName VARCHAR(100),
Price DECIMAL(10,2),
CreatedAt DATETIME DEFAULT CURRENT_TIMESTAMP,
UpdatedAt DATETIME DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP,
CreatedBy VARCHAR(50),
ModifiedBy VARCHAR(50),
IsDeleted BOOLEAN DEFAULT FALSE
);

-- Soft delete pattern (mark as deleted instead of removing)

SELECT * FROM Products WHERE IsDeleted = FALSE;

-- PATTERN 6: Polymorphic Associations

-- Comments can belong to different entities (Posts, Photos, etc.)

CREATE TABLE Comments (

CommentID INT PRIMARY KEY AUTO_INCREMENT,
CommentText TEXT,
EntityType VARCHAR(20), -- 'Post' or 'Photo'
EntityID INT, -- ID of the related entity
CommentDate DATETIME
);

-- Better: Separate junction tables for each type

CREATE TABLE PostComments (
CommentID INT PRIMARY KEY,
PostID INT,
FOREIGN KEY (CommentID) REFERENCES Comments(CommentID),
FOREIGN KEY (PostID) REFERENCES Posts(PostID)
);

Explanation: Database design patterns:

 Many-to-Many: Junction table with two FKs

 One-to-One: Shared primary key
 Self-referencing: FK points to same table
 Soft delete: IsDeleted flag instead of DELETE
 Audit fields: Track creation/modification

3.2 Exercises: Advanced Databases

Exercise 1: 3NF Normalization

Normalize the following table to 3NF:
Invoice(InvoiceNumber, InvoiceDate, CustomerName, CustomerAddress, ProductID,
ProductName, Quantity, UnitPrice, TotalAmount)

Exercise 2: Complex SQL Query

Write a SQL query to find the top 5 students with the highest GPA, including their name, ID,
and GPA, from the Students, Enrollments, Courses, and Grades tables.

Exercise 3: Stored Procedure

Create a stored procedure that accepts a course ID and returns the course name, number of
enrolled students, and average grade.

Exercise 4: Trigger Creation

Create a trigger that automatically updates the course enrollment count whenever a student
is enrolled or unenrolled.

Exercise 5: Database Security

Design a database security scheme with three roles: Admin (full access), Teacher (can view
and update grades), and Student (can view own grades only).

ANSWERS

Answer 1: 3NF Normalization

 Invoices(InvoiceNumber PK, InvoiceDate, CustomerID FK)
 Customers(CustomerID PK, CustomerName, CustomerAddress)
 Products(ProductID PK, ProductName, UnitPrice)
 InvoiceItems(InvoiceNumber FK, ProductID FK, Quantity, PRIMARY
KEY(InvoiceNumber, ProductID))

Answer 2: Complex SQL Query

SELECT [Link], [Link],
AVG([Link]) AS GPA
FROM Students s
JOIN Enrollments e ON [Link] = [Link]
JOIN Grades g ON [Link] = [Link]
GROUP BY [Link], [Link]
ORDER BY GPA DESC
LIMIT 5;

Answer 3: Stored Procedure

CREATE PROCEDURE GetCourseStats(IN course_id VARCHAR(10))
BEGIN
SELECT [Link],
COUNT([Link]) AS EnrolledStudents,
AVG([Link]) AS AverageGrade
FROM Courses c
LEFT JOIN Enrollments e ON [Link] = [Link]
LEFT JOIN Grades g ON [Link] = [Link]
WHERE [Link] = course_id
 GROUP BY [Link], [Link];
END//

Answer 4: Trigger Creation

CREATE TRIGGER UpdateEnrollmentCount
AFTER INSERT ON Enrollments
FOR EACH ROW
BEGIN
UPDATE Courses SET EnrolledCount = EnrolledCount + 1
WHERE CourseID = [Link];
END//

CREATE TRIGGER DecreaseEnrollmentCount

AFTER DELETE ON Enrollments
FOR EACH ROW
BEGIN
UPDATE Courses SET EnrolledCount = EnrolledCount - 1
WHERE CourseID = [Link];
END//

Answer 5: Database Security Scheme

-- Create roles
CREATE ROLE admin, teacher, student;

-- Admin privileges
GRANT ALL PRIVILEGES ON SchoolDB.* TO admin;

-- Teacher privileges
GRANT SELECT, UPDATE ON [Link] TO teacher;
GRANT SELECT ON [Link] TO teacher;
GRANT SELECT ON [Link] TO teacher;

-- Student privileges (view own only)

CREATE VIEW StudentOwnGrades AS
SELECT * FROM Grades
WHERE StudentID = CURRENT_USER();

GRANT SELECT ON [Link] TO student;

GRANT SELECT ON [Link] TO student;

PART 4: SAMPLE EXAMINATION PAPERS

EXAMINATION 1: RECURSION AND ADVANCED ALGORITHMS

Time: 1 hour | Total Marks: 50

Question 1 (15 marks)

a) Explain the concept of recursion with a real-world analogy.

b) What is a base case in recursion? Why is it important?

Question 2 (15 marks)

Write a recursive function to calculate the sum of all elements in an array. Include the base
case and recursive case.

Question 3 (10 marks)

Trace the recursive Fibonacci function for n=5. Show all recursive calls.

Question 4 (10 marks)

Compare recursion and iteration. When would you prefer one over the other?

EXAMINATION 2: OBJECT-ORIENTED PROGRAMMING

Time: 1 hour | Total Marks: 50

Question 1 (15 marks)

Explain the four pillars of Object-Oriented Programming (OOP) with examples.

Question 2 (15 marks)

Create a class hierarchy for vehicles including a base Vehicle class and Car and Motorcycle
subclasses. Include appropriate attributes and methods.

Question 3 (10 marks)

What is polymorphism? Demonstrate with a code example showing method overriding.

Question 4 (10 marks)

Explain the difference between composition and inheritance. When would you use each?
EXAMINATION 3: ADVANCED DATABASES
Time: 1 hour | Total Marks: 50

Question 1 (15 marks)

Explain the three normal forms (1NF, 2NF, 3NF) with examples of what each solves.

Question 2 (10 marks)

Write a SQL query using JOINs to display student names, course names, and grades for all
enrollments.

Question 3 (10 marks)

What are database triggers? Write an example trigger that logs changes to a table.

Question 4 (15 marks)

Explain ACID properties. How do they ensure database integrity?

EXAMINATION 4: COMPREHENSIVE EXAM

Time: 2 hours | Total Marks: 100

Section A: Advanced Algorithms (40 marks)

 1. Write a recursive function for string palindrome checking

 2. Trace Tower of Hanoi for 4 disks
 3. Compare time complexity of recursive vs iterative solutions
 4. Explain divide-and-conquer with merge sort example

Section B: Advanced Programming (30 marks)

 5. Design an abstract class with three subclasses showing polymorphism

 6. Implement a custom exception class with proper error handling
 7. Explain encapsulation and demonstrate with a bank account example
Section C: Advanced Databases (30 marks)

 8. Normalize a given table to 3NF

 9. Write a stored procedure with transaction handling
 10. Design a database security scheme with roles

EXAMINATION 5: FINAL EXAM PREPARATION

Time: 3 hours | Total Marks: 100

Part 1: Advanced Algorithms (35 marks)

 Recursion fundamentals and base cases (10 marks)

 Recursive algorithm analysis and complexity (10 marks)
 Binary search and merge sort trace (10 marks)
 Tower of Hanoi solution (5 marks)

Part 2: Advanced Programming (35 marks)

 OOP concepts: Inheritance and polymorphism (15 marks)

 Encapsulation and abstraction (10 marks)
 Exception handling and custom exceptions (10 marks)

Part 3: Advanced Databases (30 marks)

 Database normalization to 3NF (10 marks)

 Advanced SQL queries and stored procedures (10 marks)
 Database transactions and security (10 marks)