# Order of operations (highest to lowest)
# 1. Parentheses: ()
# 2. Exponentiation: **
# 3. Unary operators: +x, -x
# 4. Multiplication/Division/Modulo: *, /, //, %
# 5. Addition/Subtraction: +, -
# 6. Comparison operators
# 7. Logical NOT: not
# 8. Logical AND: and
# 9. Logical OR: or
result = 5 + 3 * 2 ** 2 # 5 + 3 * 4 = 5 + 12 = 17
result = (5 + 3) * 2 ** 2 # 8 * 4 = 32
result = 10 / 2 * 3 # 5 * 3 = 15 (left to right for same precedence)
Assignment Operators
x = 5 # Basic assignment
x += 3 # x = x + 3 (now 8)
x -= 2 # x = x - 2 (now 6)
x *= 4 # x = x * 4 (now 24)
x /= 3 # x = x / 3 (now 8.0)
x //= 2 # x = x // 2 (now 4.0)
x %= 3 # x = x % 3 (now 1.0)
x **= 2 # x = x ** 2 (now 1.0)
1.3 Input and Output
Print Function
# Basic output
print("Hello, World!")
print(42)
print(3.14159)
# Multiple arguments (automatically space-separated)
print("The answer is", 42, "and pi is", 3.14)
# Custom separators
print("apple", "banana", "cherry", sep=", ") # apple, banana, cherry
# Custom end character (default is newline)
print("Loading", end="...")
print("Done!") # Loading...Done!
# Formatted strings (f-strings) - Python 3.6+
name = "Alice"
age = 17
print(f"Hello, {name}! You are {age} years old.")
print(f"Next year you will be {age + 1}.")
print(f"Pi is approximately {3.14159:.2f}") # Pi is approximately 3.14
# .format() method (older style)
print("Hello, {}! You are {} years old.".format(name, age))
# % formatting (oldest style)
print("Hello, %s! You are %d years old." % (name, age))
Input Function
# Input always returns a string
name = input("Enter your name: ")
print(f"Hello, {name}!")
# Convert input to other types
age = int(input("Enter your age: ")) # Convert to integer
height = float(input("Enter your height: ")) # Convert to float
is_student = input("Are you a student? (yes/no): ").lower() == "yes"
# Multiple inputs
x, y = input("Enter two numbers: ").split()
x, y = int(x), int(y)
print(f"Sum: {x + y}")
# Input validation
try:
age = int(input("Enter age: "))
if age < 0 or age > 150:
print("Invalid age!")
else:
print(f"Valid age: {age}")
except ValueError:
print("Please enter a valid number!")
1.4 Type Conversion (Casting)
# Implicit conversion (automatic)
x = 5 # int
y = 2.5 # float
z = x + y # float (8.5) - int promoted to float
# Explicit conversion
# To integer
int(3.14) # 3 (truncates)
int("42") # 42
int(True) # 1
int(False) # 0
int("101", 2) # 5 (binary to decimal)
# To float
float(5) # 5.0
float("3.14") # 3.14
float("inf") # infinity
float("nan") # Not a Number
# To string
str(42) # "42"
str(3.14) # "3.14"
str(True) # "True"
# To boolean
bool(0) # False
bool(1) # True
bool("") # False
bool("Hello") # True
bool([]) # False
bool([1,2]) # True
bool(None) # False
# Rounding
round(3.14159) # 3
round(3.14159, 2) # 3.14
round(2.5) # 2 (rounds to even - banker's rounding)
Unit 2: Using Objects
2.1 Object-Oriented Concepts in Python
Everything is an Object
# In Python, even primitive types are objects
x = 5
print(x.__class__) # <class 'int'>
print(dir(x)) # Shows all methods available
y = "Hello"
print(y.upper()) # HELLO
print(y.lower()) # hello
print(y.__len__()) # 5 (same as len(y))
Creating and Using Objects
# Creating instances of built-in classes
my_list = list() # Create a list object
my_dict = dict() # Create a dictionary object
my_str = str("Hello") # Create a string object
# Using object methods
my_list.append(10) # Call method on object
my_list.sort() # Another method
# Object attributes
class Person:
def __init__(self, name):
self.name = name # Instance attribute
p = Person("Alice")
print(p.name) # Access attribute
import random
# Basic random
random.random() # Random float [0.0, 1.0)
random.randint(1, 10) # Random integer [1, 10] (inclusive)
random.randrange(10) # Random integer [0, 9]
random.randrange(1, 10, 2) # Random odd number 1,3,5,7,9
# Sequence operations
my_list = [1, 2, 3, 4, 5]
random.choice(my_list) # Random element
random.choices(my_list, k=3) # 3 random elements (with replacement)
random.sample(my_list, k=3) # 3 unique random elements
random.shuffle(my_list) # Shuffle in place
# Random distributions
random.uniform(1, 10) # Random float [1, 10]
random.gauss(0, 1) # Gaussian distribution (mean, stddev)
random.expovariate(1) # Exponential distribution
# Setting seed for reproducibility
random.seed(42) # Same sequence each time
print(random.random()) # Will be same every run with seed 42
Unit 3: Boolean Expressions and if Statements
3.1 Boolean Expressions
Comparison Operators
# All comparison operators return True/False
x = 5
y = 10
x == y # False (equal to)
x != y # True (not equal to)
x < y # True (less than)
x > y # False (greater than)
x <= y # True (less than or equal)
x >= y # False (greater than or equal)
# Chained comparisons (Python unique feature)
1 < x < 10 # True (same as 1 < x and x < 10)
5 == x == 5 # True
Logical Operators
a = True
b = False
# AND - both must be True
a and b # False
a and True # True
# OR - at least one must be True
a or b # True
b or False # False
# NOT - reverses boolean value
not a # False
not b # True
# Short-circuit evaluation
def expensive_function():
print("Called!")
return True
# Second expression not evaluated if first is False
False and expensive_function() # expensive_function NOT called
True or expensive_function() # expensive_function NOT called
# Truth values - what's considered True/False?
# False values: False, 0, 0.0, "" (empty string), [], (), {}, None
# All other values are True
if "": # False
if "Hello": # True
if []: # False
if [1,2]: # True
if None: # False
3.2 if Statements
Basic if Statement
age = 18
if age >= 18:
print("You are an adult")
print("You can vote")
# Indentation is crucial! (typically 4 spaces)
if-else Statement
temperature = 25
if temperature > 30:
print("It's hot!")
print("Stay hydrated")
else:
print("It's not too hot")
print("Enjoy the weather")
if-elif-else Chain
score = 85
if score >= 90:
grade = "A"
print("Excellent!")
elif score >= 80:
grade = "B"
print("Good job!")
elif score >= 70:
grade = "C"
print("Satisfactory")
elif score >= 60:
grade = "D"
print("Needs improvement")
else:
grade = "F"
print("Failed")
print(f"Grade: {grade}")
# Note: elif is else + if in one word
Nested Conditionals
age = 25
has_license = True
if age >= 18:
if has_license:
print("You can drive")
else:
print("Get a license first")
else:
print("Too young to drive")
# Better to use logical operators:
if age >= 18 and has_license:
print("You can drive")
elif age >= 18 and not has_license:
print("Get a license first")
else:
print("Too young to drive")
3.3 Conditional Expressions (Ternary Operator)
# Traditional if-else
if age >= 18:
status = "adult"
else:
status = "minor"
# Ternary operator (conditional expression)
status = "adult" if age >= 18 else "minor"
# Multiple conditions
category = "senior" if age >= 65 else "adult" if age >= 18 else "minor"
# Using with assignment
x = 5
y = 10
max_value = x if x > y else y
3.4 Common Patterns and Examples
Input Validation
# Validate numeric input
user_input = input("Enter a positive number: ")
if user_input.isdigit():
number = int(user_input)
if number > 0:
print(f"Valid input: {number}")
else:
print("Number must be positive")
else:
print("Please enter a valid number")
# Menu selection
print("1. Start game")
print("2. Load game")
print("3. Settings")
print("4. Quit")
choice = input("Choose option: ")
if choice == "1":
start_game()
elif choice == "2":
load_game()
elif choice == "3":
show_settings()
elif choice == "4":
quit_game()
else:
print("Invalid choice")
Leap Year Detection
year = 2024
# Leap year rules:
# Divisible by 4
# But not divisible by 100, unless also divisible by 400
is_leap = (year % 4 == 0) and (year % 100 != 0 or year % 400 == 0)
if is_leap:
print(f"{year} is a leap year")
else:
print(f"{year} is not a leap year")
Character Type Checking
char = "A"
if char.isupper():
print("Uppercase letter")
elif char.islower():
print("Lowercase letter")
elif char.isdigit():
print("Digit")
elif char.isspace():
print("Whitespace")
else:
print("Special character or punctuation")
Unit 4: Iteration (Loops)
4.1 while Loops
Basic while Loop
# Basic while loop
count = 0
while count < 5:
print(f"Count: {count}")
count += 1
# Infinite loop (be careful!)
# while True:
# print("This will run forever")
# while loop with break
while True:
user_input = input("Enter 'quit' to exit: ")
if user_input == "quit":
break
print(f"You entered: {user_input}")
# while loop with continue
number = 0
while number < 10:
number += 1
if number % 2 == 0:
continue # Skip even numbers
print(f"Odd number: {number}")
Common while Loop Patterns
# Input validation with while
while True:
age = input("Enter your age (must be 0-120): ")
if age.isdigit():
age = int(age)
if 0 <= age <= 120:
break
print("Invalid input, try again")
print(f"Valid age: {age}")
# Menu loop
choice = ""
while choice != "4":
print("\n1. Option 1")
print("2. Option 2")
print("3. Option 3")
print("4. Exit")
choice = input("Choose option: ")
if choice == "1":
print("Option 1 selected")
elif choice == "2":
print("Option 2 selected")
elif choice == "3":
print("Option 3 selected")
elif choice == "4":
print("Goodbye!")
else:
print("Invalid choice")
# Sentinel-controlled loop
total = 0
count = 0
number = float(input("Enter a number (negative to stop): "))
while number >= 0:
total += number
count += 1
number = float(input("Enter another number (negative to stop): "))
if count > 0:
average = total / count
print(f"Average: {average}")
else:
print("No numbers entered")
4.2 for Loops
for Loop with range()
# range(stop) - from 0 to stop-1
for i in range(5):
print(i) # 0, 1, 2, 3, 4
# range(start, stop) - from start to stop-1
for i in range(2, 7):
print(i) # 2, 3, 4, 5, 6
# range(start, stop, step) - with step
for i in range(0, 10, 2):
print(i) # 0, 2, 4, 6, 8
# Negative step
for i in range(10, 0, -2):
print(i) # 10, 8, 6, 4, 2
# Common patterns
# Sum of numbers 1 to 100
total = 0
for i in range(1, 101):
total += i
print(f"Sum: {total}")
# Factorial
n = 5
factorial = 1
for i in range(1, n + 1):
factorial *= i
print(f"{n}! = {factorial}")
for Loop with Sequences
# Iterating through strings
word = "Hello"
for char in word:
print(char) # H, e, l, l, o
# With index
for i, char in enumerate(word):
print(f"Index {i}: {char}")
# Iterating through lists
fruits = ["apple", "banana", "cherry"]
for fruit in fruits:
print(fruit)
# With index
for i, fruit in enumerate(fruits):
print(f"{i}: {fruit}")
# Iterating through dictionaries
person = {"name": "Alice", "age": 17, "city": "New York"}
for key in person:
print(f"{key}: {person[key]}")
for value in person.values():
print(value)
for key, value in person.items():
print(f"{key}: {value}")
4.3 Nested Loops
# Multiplication table
for i in range(1, 6):
for j in range(1, 6):
print(f"{i * j:4}", end="")
print() # New line after each row
# Output:
# 1 2 3 4 5
# 2 4 6 8 10
# 3 6 9 12 15
# 4 8 12 16 20
# 5 10 15 20 25
# Drawing patterns
for i in range(1, 6):
print("*" * i)
# *
# **
# ***
# ****
# *****
# More complex pattern
for i in range(5):
for j in range(5 - i - 1):
print(" ", end="")
for j in range(2 * i + 1):
print("*", end="")
print()
# *
# ***
# *****
# *******
# *********
# Nested loops with lists
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
for row in matrix:
for element in row:
print(element, end=" ")
print()
# 1 2 3
# 4 5 6
# 7 8 9
4.4 Loop Control Statements
break Statement
# Exit loop immediately
for i in range(10):
if i == 5:
break
print(i) # Prints 0, 1, 2, 3, 4
# Find first occurrence
numbers = [3, 7, 2, 9, 4, 1]
target = 9
for i, num in enumerate(numbers):
if num == target:
print(f"Found at index {i}")
break
else:
print("Not found") # Executes if loop completes without break
# Break in nested loops (only breaks inner loop)
for i in range(3):
for j in range(3):
if j == 1:
break
print(f"({i}, {j})") # Only prints when j=0
continue Statement
# Skip current iteration
for i in range(10):
if i % 2 == 0:
continue
print(i) # Prints odd numbers: 1, 3, 5, 7, 9
# Process only valid items
data = [5, -2, 10, -8, 0, 3]
for value in data:
if value <= 0:
continue
print(f"Processing: {value}")
else Clause with Loops
# else executes if loop completes without break
for i in range(5):
print(i)
else:
print("Loop completed normally") # Executes
for i in range(5):
if i == 3:
break
print(i)
else:
print("Loop completed normally") # Doesn't execute (break occurred)
# Common use: search loops
numbers = [2, 4, 6, 8, 9, 10]
for num in numbers:
if num % 2 != 0:
print(f"Found odd number: {num}")
break
else:
print("No odd numbers found")
4.5 Loop Examples and Patterns
Accumulator Pattern
# Sum of squares
numbers = [1, 2, 3, 4, 5]
sum_squares = 0
for n in numbers:
sum_squares += n ** 2
print(f"Sum of squares: {sum_squares}")
# Building a string
words = ["hello", "world", "python"]
result = ""
for word in words:
result += word + " "
print(result.strip()) # "hello world python"
# List comprehension (Pythonic alternative)
sum_squares = sum(n ** 2 for n in numbers)
Maximum/Minimum Pattern
numbers = [45, 23, 89, 12, 67, 34]
# Find maximum
max_value = numbers[0] # Start with first element
for num in numbers[1:]:
if num > max_value:
max_value = num
print(f"Maximum: {max_value}")
# Using built-in functions
print(f"Max: {max(numbers)}")
print(f"Min: {min(numbers)}")
# Find index of maximum
max_index = 0
for i in range(1, len(numbers)):
if numbers[i] > numbers[max_index]:
max_index = i
print(f"Index of max: {max_index}, value: {numbers[max_index]}")
Filter Pattern
# Filter even numbers
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
evens = []
for num in numbers:
if num % 2 == 0:
evens.append(num)
print(f"Even numbers: {evens}")
# List comprehension alternative
evens = [num for num in numbers if num % 2 == 0]
# Filter strings by length
words = ["cat", "elephant", "dog", "butterfly", "ant"]
long_words = []
for word in words:
if len(word) > 4:
long_words.append(word)
print(f"Long words: {long_words}")
Count Pattern
# Count occurrences
text = "hello world"
count_e = 0
for char in text:
if char == 'e':
count_e += 1
print(f"Number of 'e's: {count_e}")
# Count vowels
vowels = "aeiou"
text = "Hello, how are you today?"
count = 0
for char in text.lower():
if char in vowels:
count += 1
print(f"Number of vowels: {count}")
Unit 5: Writing Classes
5.1 Class Definition Basics
Class Syntax
class ClassName:
"""Class docstring - describes what this class does"""
# Class variable (shared by all instances)
class_variable = "shared value"
# Constructor - initializes new instances
def __init__(self, param1, param2):
"""Initialize instance attributes"""
# Instance variables (unique to each instance)
self.instance_var1 = param1
self.instance_var2 = param2
self._private_var = None # Convention: private starts with _
self.__really_private = None # Name mangling (more private)
# Instance method
def method_name(self, parameter):
"""Method docstring"""
# Access instance variables using self
return f"{self.instance_var1} {parameter}"
# Special methods (__str__, __repr__, etc.)
def __str__(self):
"""String representation for users"""
return f"ClassName({self.instance_var1})"
def __repr__(self):
"""String representation for developers"""
return f"ClassName('{self.instance_var1}', '{self.instance_var2}')"
Simple Class Example
class Dog:
"""A simple Dog class"""
# Class variable (same for all dogs)
species = "Canis familiaris"
dog_count = 0
def __init__(self, name, age):
"""Initialize dog with name and age"""
self.name = name
self.age = age
Dog.dog_count += 1 # Increment class variable
def bark(self):
"""Make the dog bark"""
return f"{self.name} says Woof!"
def get_human_years(self):
"""Convert dog years to human years"""
return self.age * 7
def __str__(self):
return f"{self.name} ({self.age} years old)"
def __repr__(self):
return f"Dog('{self.name}', {self.age})"
# Creating instances
my_dog = Dog("Buddy", 3)
your_dog = Dog("Max", 5)
# Using methods
print(my_dog.bark()) # Buddy says Woof!
print(my_dog.get_human_years()) # 21
print(my_dog) # Buddy (3 years old)
# Accessing attributes
print(my_dog.name) # Buddy
print(my_dog.age) # 3
print(Dog.species) # Canis familiaris
print(Dog.dog_count) # 2
print(my_dog.dog_count) # 2 (also accessible through instance)
5.2 Instance Variables and Methods
Instance Variables
class Student:
def __init__(self, name, age):
# Instance variables created here
self.name = name
self.age = age
self.grades = [] # Empty list for grades
self._id = None # "Protected" (by convention)
self.__ssn = None # "Private" (name mangling)
# Instance method
def add_grade(self, grade):
"""Add a grade to student's record"""
if 0 <= grade <= 100:
self.grades.append(grade)
return True
return False
def average(self):
"""Calculate average grade"""
if self.grades:
return sum(self.grades) / len(self.grades)
return 0
# Creating and using
s = Student("Alice", 17)
s.add_grade(85)
s.add_grade(92)
s.add_grade(78)
print(s.average()) # 85.0
# Dynamic attributes (can add anytime - but be careful!)
s.address = "123 Main St" # Creates new attribute
print(s.address) # 123 Main St
# Access control (by convention, not enforced)
# s._id = "12345" # Works, but indicates "protected"
# s.__ssn = "123-45-6789" # Actually stored as _Student__ssn
5.3 Class Variables and Methods
class BankAccount:
# Class variables
bank_name = "Python Bank"
interest_rate = 0.02
account_count = 0
def __init__(self, owner, balance=0):
self.owner = owner
self.balance = balance
BankAccount.account_count += 1
self.account_number = BankAccount.account_count
# Instance method
def deposit(self, amount):
self.balance += amount
return self.balance
# Class method (operates on class, not instance)
@classmethod
def set_interest_rate(cls, new_rate):
"""Set interest rate for all accounts"""
cls.interest_rate = new_rate
@classmethod
def from_string(cls, account_string):
"""Alternative constructor - creates account from string"""
owner, balance = account_string.split("-")
return cls(owner, float(balance))
# Static method (utility function related to class)
@staticmethod
def validate_amount(amount):
"""Check if amount is valid for transaction"""
return amount > 0 and amount < 1000000
def apply_interest(self):
"""Apply interest to this account"""
interest = self.balance * BankAccount.interest_rate
self.balance += interest
return interest
# Using class methods
BankAccount.set_interest_rate(0.025) # Change for all accounts
print(BankAccount.interest_rate) # 0.025
# Alternative constructor
acc = BankAccount.from_string("John-500")
print(acc.owner) # John
print(acc.balance) # 500.0
# Static method
print(BankAccount.validate_amount(1000)) # True
print(BankAccount.validate_amount(-50)) # False
# Instance methods
acc1 = BankAccount("Alice", 1000)
acc2 = BankAccount("Bob", 2000)
print(BankAccount.account_count) # 3 (including John)
5.4 Properties (Getters and Setters)
class Person:
def __init__(self, name, age):
self._name = name
self._age = age
self._email = None
# Getter for name
@property
def name(self):
"""Get the person's name"""
return self._name.title() # Format nicely
# Setter for name
@name.setter
def name(self, value):
"""Set the person's name"""
if not isinstance(value, str):
raise TypeError("Name must be a string")
if len(value) < 2:
raise ValueError("Name must be at least 2 characters")
self._name = value
# Deleter for name
@name.deleter
def name(self):
print(f"Deleting {self._name}")
self._name = None
# Property for age with validation
@property
def age(self):
return self._age
@age.setter
def age(self, value):
if not isinstance(value, (int, float)):
raise TypeError("Age must be a number")
if value < 0 or value > 150:
raise ValueError("Age must be between 0 and 150")
self._age = value
# Computed property
@property
def email(self):
if self._email:
return self._email
return f"{self._name.lower()}@example.com"
@email.setter
def email(self, value):
if "@" not in value:
raise ValueError("Invalid email address")
self._email = value
# Property with no setter (read-only)
@property
def is_adult(self):
return self._age >= 18
# Using properties
p = Person("alice", 25)
print(p.name) # Alice (automatically titled)
p.name = "bob" # Works with setter
# p.name = "a" # ValueError: Name must be at least 2 characters
print(p.age) # 25
p.age = 30
# p.age = 200 # ValueError: Age must be between 0 and 150
print(p.email) # bob@example.com
p.email = "bob@gmail.com"
print(p.email) # bob@gmail.com
print(p.is_adult) # True (read-only property)
a = [1, 2, 3]
b = [4, 5, 6]
# Concatenation
c = a + b # [1, 2, 3, 4, 5, 6]
# Repetition
d = a * 3 # [1, 2, 3, 1, 2, 3, 1, 2, 3]
# Membership
print(2 in a) # True
print(7 not in a) # True
# Length
len(a) # 3
# Minimum and maximum (if all elements comparable)
min(a) # 1
max(a) # 3
# Sum (if all numeric)
sum(a) # 6
List Methods
numbers = [5, 2, 8, 1, 9]
# Adding elements
numbers.append(3) # [5, 2, 8, 1, 9, 3] (add at end)
numbers.insert(2, 7) # [5, 2, 7, 8, 1, 9, 3] (insert at index)
numbers.extend([4, 6]) # [5, 2, 7, 8, 1, 9, 3, 4, 6] (add multiple)
# Removing elements
numbers.pop() # Removes and returns last element (6)
numbers.pop(2) # Removes and returns element at index 2 (7)
numbers.remove(8) # Removes first occurrence of 8
numbers.clear() # Removes all elements
# Finding elements
numbers = [5, 2, 8, 1, 9, 2]
numbers.index(8) # 2 (index of first occurrence)
numbers.index(2) # 1 (first occurrence)
numbers.count(2) # 2 (number of occurrences)
# Sorting
numbers.sort() # [1, 2, 2, 5, 8, 9] (in-place)
numbers.sort(reverse=True) # [9, 8, 5, 2, 2, 1]
sorted(numbers) # Returns new sorted list (original unchanged)
# Reversing
numbers.reverse() # Reverse in-place
# Copying
new_list = numbers.copy() # Shallow copy
new_list = numbers[:] # Also makes a copy
6.3 Iterating Through Lists
fruits = ["apple", "banana", "cherry"]
# Basic for loop
for fruit in fruits:
print(fruit)
# With index using range
for i in range(len(fruits)):
print(f"{i}: {fruits[i]}")
# Using enumerate (most Pythonic)
for i, fruit in enumerate(fruits):
print(f"{i}: {fruit}")
# enumerate with start index
for i, fruit in enumerate(fruits, start=1):
print(f"{i}. {fruit}")
# While loop
i = 0
while i < len(fruits):
print(fruits[i])
i += 1
# List comprehension
upper_fruits = [fruit.upper() for fruit in fruits]
# ['APPLE', 'BANANA', 'CHERRY']
# Conditional list comprehension
long_fruits = [fruit for fruit in fruits if len(fruit) > 5]
# ['banana', 'cherry']
# Nested loops with 2D lists
matrix = [[1, 2], [3, 4], [5, 6]]
for row in matrix:
for element in row:
print(element, end=" ")
print()
# 1 2
# 3 4
# 5 6
6.4 Common List Patterns
# Sum of elements
numbers = [1, 2, 3, 4, 5]
total = 0
for num in numbers:
total += num
print(total) # 15
# Using built-in sum
total = sum(numbers)
# Average
average = sum(numbers) / len(numbers)
# Filter even numbers
evens = [num for num in numbers if num % 2 == 0]
# Transform all elements
doubled = [num * 2 for num in numbers]
# Find maximum
max_value = numbers[0]
for num in numbers[1:]:
if num > max_value:
max_value = num
# Using built-in
max_value = max(numbers)
min_value = min(numbers)
# Check if all elements satisfy condition
all_positive = all(num > 0 for num in numbers)
any_even = any(num % 2 == 0 for num in numbers)
# Join list elements to string
words = ["Hello", "World"]
sentence = " ".join(words) # "Hello World"
# Flatten nested list
nested = [[1, 2], [3, 4], [5, 6]]
flat = [num for row in nested for num in row]
# [1, 2, 3, 4, 5, 6]
# Remove duplicates
items = [1, 2, 2, 3, 3, 3, 4]
unique = list(set(items)) # [1, 2, 3, 4] (order not preserved)
# Preserve order while removing duplicates
seen = set()
unique = []
for item in items:
if item not in seen:
unique.append(item)
seen.add(item)
6.5 List Algorithms
Linear Search
def linear_search(arr, target):
"""Find index of target in list"""
for i in range(len(arr)):
if arr[i] == target:
return i
return -1 # Not found
# With index built-in
def linear_search_builtin(arr, target):
try:
return arr.index(target)
except ValueError:
return -1
# Test
numbers = [5, 2, 8, 1, 9, 3]
print(linear_search(numbers, 8)) # 2
print(linear_search(numbers, 10)) # -1
Bubble Sort
def bubble_sort(arr):
"""Sort list using bubble sort algorithm"""
n = len(arr)
# Make a copy to avoid modifying original
result = arr.copy()
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if result[j] > result[j + 1]:
# Swap elements
result[j], result[j + 1] = result[j + 1], result[j]
swapped = True
if not swapped:
break # List is already sorted
return result
# Test
numbers = [64, 34, 25, 12, 22, 11, 90]
sorted_numbers = bubble_sort(numbers)
print(f"Original: {numbers}")
print(f"Sorted: {sorted_numbers}")
Binary Search (on sorted list)
def binary_search(arr, target):
"""Find target in sorted list using binary search"""
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # Not found
# Test
numbers = [11, 12, 22, 25, 34, 64, 90]
print(binary_search(numbers, 25)) # 3
print(binary_search(numbers, 30)) # -1
Finding Duplicates
def find_duplicates(arr):
"""Find all duplicate elements in list"""
seen = set()
duplicates = []
for item in arr:
if item in seen and item not in duplicates:
duplicates.append(item)
else:
seen.add(item)
return duplicates
# Test
numbers = [1, 2, 3, 2, 4, 3, 5, 6, 3]
print(find_duplicates(numbers)) # [2, 3]
Unit 7: ArrayList (Python Lists – Dynamic)
7.1 List as Dynamic Array
Python lists are already dynamic arrays – they automatically grow and shrink.
# Lists are dynamic - no fixed size
dynamic_list = []
print(len(dynamic_list)) # 0
# Add elements - list grows automatically
dynamic_list.append(10)
dynamic_list.append(20)
dynamic_list.append(30)
print(len(dynamic_list)) # 3
print(dynamic_list) # [10, 20, 30]
# Remove elements - list shrinks
dynamic_list.pop() # Remove last
print(len(dynamic_list)) # 2
print(dynamic_list) # [10, 20]
# Lists can hold any type
dynamic_list.append("hello")
dynamic_list.append(True)
dynamic_list.append([1, 2])
print(dynamic_list) # [10, 20, 'hello', True, [1, 2]]
7.2 List Capacity and Performance
import sys
import time
# Lists have internal capacity that may be larger than length
my_list = []
for i in range(10):
my_list.append(i)
print(f"Length: {len(my_list):2}, Size: {sys.getsizeof(my_list):4} bytes")
# Output shows list size increases in chunks (not every append)
# Time complexity of list operations
# - Append: O(1) amortized
# - Insert: O(n)
# - Remove: O(n)
# - Get by index: O(1)
# - Search: O(n)
# Demonstrate performance difference
def test_list_performance():
n = 100000
# Append at end (fast)
start = time.time()
lst = []
for i in range(n):
lst.append(i)
end = time.time()
print(f"Append at end: {end - start:.4f} seconds")
# Insert at beginning (slow)
start = time.time()
lst = []
for i in range(n):
lst.insert(0, i)
end = time.time()
print(f"Insert at beginning: {end - start:.4f} seconds")
# test_list_performance()
7.3 List vs Array (if needed)
# For numerical work, array module provides typed arrays
from array import array
# Array with type code 'i' for signed integers
int_array = array('i', [1, 2, 3, 4, 5])
# Array with type code 'f' for floats
float_array = array('f', [1.5, 2.7, 3.2])
# Arrays are more memory efficient for same type
import sys
list_int = [1, 2, 3, 4, 5]
array_int = array('i', [1, 2, 3, 4, 5])
print(f"List size: {sys.getsizeof(list_int)} bytes")
print(f"Array size: {sys.getsizeof(array_int)} bytes")
# Arrays support similar operations
array_int.append(6)
array_int.insert(2, 10)
print(array_int[0]) # 1
# But all elements must be same type
# array_int.append(3.14) # TypeError
Unit 8: 2D Arrays (Nested Lists)
8.1 Creating 2D Lists
# Method 1: Direct initialization
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
# Method 2: Create empty and fill
rows, cols = 3, 4
matrix = [[0] * cols for _ in range(rows)]
# [[0, 0, 0, 0],
# [0, 0, 0, 0],
# [0, 0, 0, 0]]
# WRONG way - creates references to same row
wrong_matrix = [[0] * cols] * rows
# Modifying one row affects all!
# wrong_matrix[0][0] = 1 # Changes all rows!
# Method 3: Using nested list comprehension
matrix = [[i * j for j in range(1, 4)] for i in range(1, 4)]
# [[1, 2, 3],
# [2, 4, 6],
# [3, 6, 9]]
# Method 4: From user input
def create_matrix_from_input(rows, cols):
matrix = []
for i in range(rows):
row = []
for j in range(cols):
value = int(input(f"Enter value for [{i}][{j}]: "))
row.append(value)
matrix.append(row)
return matrix
8.2 Accessing and Modifying 2D Lists
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
# Access individual elements
element = matrix[1][2] # Row 1, Column 2 = 6
print(element)
# Modify element
matrix[2][1] = 10 # Change 8 to 10
# Get number of rows
rows = len(matrix)
# Get number of columns (assuming rectangular)
cols = len(matrix[0])
# Access entire row
second_row = matrix[1] # [4, 5, 6]
# Access column (using list comprehension)
col_2 = [row[2] for row in matrix] # [3, 6, 9]
8.3 Iterating Through 2D Lists
matrix = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
]
# Method 1: Nested for loops with indices
for i in range(len(matrix)):
for j in range(len(matrix[i])):
print(f"matrix[{i}][{j}] = {matrix[i][j]}")
# Method 2: Nested for loops with elements
for row in matrix:
for element in row:
print(element, end=" ")
print() # New line after each row
# Output:
# 1 2 3
# 4 5 6
# 7 8 9
# Method 3: Using enumerate
for i, row in enumerate(matrix):
for j, value in enumerate(row):
print(f"({i},{j}): {value}")
# Method 4: List comprehension for flattened view
flattened = [value for row in matrix for value in row]
# [1, 2, 3, 4, 5, 6, 7, 8, 9]
# Method 5: While loops
i = 0
while i < len(matrix):
j = 0
while j < len(matrix[i]):
print(matrix[i][j], end=" ")
j += 1
print()
i += 1
8.4 Common 2D Array Operations
Matrix Addition
def add_matrices(A, B):
"""Add two matrices"""
if len(A) != len(B) or len(A[0]) != len(B[0]):
raise ValueError("Matrices must have same dimensions")
rows, cols = len(A), len(A[0])
result = [[0] * cols for _ in range(rows)]
for i in range(rows):
for j in range(cols):
result[i][j] = A[i][j] + B[i][j]
return result
# Test
A = [[1, 2], [3, 4]]
B = [[5, 6], [7, 8]]
C = add_matrices(A, B)
print(C) # [[6, 8], [10, 12]]
Matrix Multiplication
def multiply_matrices(A, B):
"""Multiply two matrices"""
rows_A, cols_A = len(A), len(A[0])
rows_B, cols_B = len(B), len(B[0])
if cols_A != rows_B:
raise ValueError("Cannot multiply: incompatible dimensions")
# Initialize result matrix
result = [[0] * cols_B for _ in range(rows_A)]
# Multiply
for i in range(rows_A):
for j in range(cols_B):
for k in range(cols_A):
result[i][j] += A[i][k] * B[k][j]
return result
# Test
A = [[1, 2], [3, 4]]
B = [[5, 6], [7, 8]]
C = multiply_matrices(A, B)
print(C) # [[19, 22], [43, 50]]
Transpose Matrix
def transpose(matrix):
"""Return transpose of matrix"""
rows, cols = len(matrix), len(matrix[0])
# Create new matrix with swapped dimensions
result = [[0] * rows for _ in range(cols)]
for i in range(rows):
for j in range(cols):
result[j][i] = matrix[i][j]
return result
# Using list comprehension (more concise)
def transpose_zip(matrix):
return [list(row) for row in zip(*matrix)]
# Test
matrix = [[1, 2, 3], [4, 5, 6]]
print(transpose(matrix)) # [[1, 4], [2, 5], [3, 6]]
Find Maximum in 2D Array
def find_max(matrix):
"""Find maximum element in 2D array"""
if not matrix or not matrix[0]:
return None
max_val = matrix[0][0]
max_pos = (0, 0)
for i, row in enumerate(matrix):
for j, value in enumerate(row):
if value > max_val:
max_val = value
max_pos = (i, j)
return max_val, max_pos
# Test
matrix = [[1, 5, 3], [7, 2, 8], [4, 6, 9]]
max_val, (row, col) = find_max(matrix)
print(f"Max: {max_val} at [{row}][{col}]") # Max: 9 at [2][2]
Sum Each Row and Column
def row_sums(matrix):
"""Calculate sum of each row"""
return [sum(row) for row in matrix]
def col_sums(matrix):
"""Calculate sum of each column"""
rows, cols = len(matrix), len(matrix[0])
return [sum(matrix[i][j] for i in range(rows)) for j in range(cols)]
# Test
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(f"Row sums: {row_sums(matrix)}") # [6, 15, 24]
print(f"Col sums: {col_sums(matrix)}") # [12, 15, 18]
Rotate Matrix 90 Degrees
def rotate_clockwise(matrix):
"""Rotate matrix 90 degrees clockwise"""
n = len(matrix)
result = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
result[j][n - 1 - i] = matrix[i][j]
return result
# Using zip (more Pythonic)
def rotate_clockwise_zip(matrix):
return [list(row)[::-1] for row in zip(*matrix)]
# Test
matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotated = rotate_clockwise(matrix)
for row in rotated:
print(row)
# [7, 4, 1]
# [8, 5, 2]
# [9, 6, 3]
Check if Matrix is Symmetric
def is_symmetric(matrix):
"""Check if matrix is symmetric (equal to its transpose)"""
n = len(matrix)
for i in range(n):
for j in range(i + 1, n): # Only check upper triangle
if matrix[i][j] != matrix[j][i]:
return False
return True
# Test
symmetric = [[1, 2, 3], [2, 4, 5], [3, 5, 6]]
asymmetric = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(is_symmetric(symmetric)) # True
print(is_symmetric(asymmetric)) # False
8.5 Jagged Arrays (Rows of Different Lengths)
# Python supports jagged arrays (rows can have different lengths)
jagged = [
[1, 2, 3],
[4, 5],
[6, 7, 8, 9]
]
# Process jagged array
for i, row in enumerate(jagged):
print(f"Row {i} has {len(row)} elements: {row}")
# Sum all elements in jagged array
total = sum(sum(row) for row in jagged)
print(f"Total: {total}")
# Find maximum element
max_val = max(max(row) for row in jagged)
print(f"Max: {max_val}")
# Check if jagged array contains value
def contains(jagged, target):
for row in jagged:
if target in row:
return True
return False
print(contains(jagged, 5)) # True
print(contains(jagged, 10)) # False
Unit 9: Inheritance
9.1 Basic Inheritance
# Base class (parent)
class Animal:
"""Base class for all animals"""
def __init__(self, name, age):
self.name = name
self.age = age
self._alive = True
def speak(self):
"""Generic animal sound"""
return f"{self.name} makes a sound"
def eat(self, food):
"""Animal eats food"""
return f"{self.name} eats {food}"
def sleep(self):
"""Animal sleeps"""
return f"{self.name} is sleeping"
def __str__(self):
return f"{self.name} ({self.age} years old)"
# Derived class (child)
class Dog(Animal):
"""Dog class inherits from Animal"""
def __init__(self, name, age, breed):
# Call parent class constructor
super().__init__(name, age)
self.breed = breed
# Override parent method
def speak(self):
return f"{self.name} says Woof!"
# Add new method
def fetch(self, item):
return f"{self.name} fetches the {item}"
# Override __str__
def __str__(self):
return f"{self.name} is a {self.breed} ({self.age} years old)"
# Another derived class
class Cat(Animal):
"""Cat class inherits from Animal"""
def __init__(self, name, age, color):
super().__init__(name, age)
self.color = color
def speak(self):
return f"{self.name} says Meow!"
def purr(self):
return f"{self.name} is purring"
def __str__(self):
return f"{self.name} is a {self.color} cat ({self.age} years old)"
# Using the classes
dog = Dog("Buddy", 3, "Golden Retriever")
cat = Cat("Whiskers", 5, "orange")
# Inherited methods
print(dog.eat("bone")) # Buddy eats bone
print(cat.sleep()) # Whiskers is sleeping
# Overridden methods
print(dog.speak()) # Buddy says Woof!
print(cat.speak()) # Whiskers says Meow!
# New methods
print(dog.fetch("ball")) # Buddy fetches the ball
print(cat.purr()) # Whiskers is purring
# Polymorphism - same interface, different behavior
animals = [dog, cat]
for animal in animals:
print(animal) # Calls appropriate __str__
print(animal.speak()) # Calls appropriate speak method
9.2 Inheritance Hierarchy
# Multi-level inheritance
class Vehicle:
"""Base class for all vehicles"""
def __init__(self, make, model, year):
self.make = make
self.model = model
self.year = year
self._speed = 0
def start(self):
return f"{self.make} {self.model} is starting"
def stop(self):
self._speed = 0
return f"{self.make} {self.model} is stopping"
def accelerate(self, amount):
self._speed += amount
return f"Speed: {self._speed} mph"
class Car(Vehicle):
"""Car inherits from Vehicle"""
def __init__(self, make, model, year, doors):
super().__init__(make, model, year)
self.doors = doors
def honk(self):
return "Beep beep!"
class ElectricCar(Car):
"""ElectricCar inherits from Car"""
def __init__(self, make, model, year, doors, battery_capacity):
super().__init__(make, model, year, doors)
self.battery_capacity = battery_capacity
self._charge = 100
def charge(self):
self._charge = 100
return f"Battery charged to {self._charge}%"
def accelerate(self, amount):
# Override with electric-specific behavior
self._speed += amount * 1.2 # Electric cars accelerate faster
self._charge -= amount * 0.5
return f"Speed: {self._speed} mph, Charge: {self._charge}%"
# Test hierarchy
tesla = ElectricCar("Tesla", "Model 3", 2023, 4, 75)
# Methods from all levels
print(tesla.start()) # Vehicle method
print(tesla.honk()) # Car method
print(tesla.charge()) # ElectricCar method
print(tesla.accelerate(10)) # Overridden method
# Check inheritance
print(isinstance(tesla, ElectricCar)) # True
print(isinstance(tesla, Car)) # True
print(isinstance(tesla, Vehicle)) # True
print(issubclass(ElectricCar, Car)) # True
9.3 Method Resolution Order (MRO)
class A:
def method(self):
return "A"
class B(A):
def method(self):
return "B"
class C(A):
def method(self):
return "C"
class D(B, C):
pass
# Check MRO
print(D.__mro__)
# (<class '__main__.D'>, <class '__main__.B'>,
# <class '__main__.C'>, <class '__main__.A'>, <class 'object'>)
d = D()
print(d.method()) # "B" (follows MRO)
# Multiple inheritance example
class Flyer:
def fly(self):
return "Flying"
class Swimmer:
def swim(self):
return "Swimming"
class Duck(Flyer, Swimmer):
def quack(self):
return "Quack!"
duck = Duck()
print(duck.fly()) # Flying
print(duck.swim()) # Swimming
print(duck.quack()) # Quack!
9.4 Abstract Base Classes
from abc import ABC, abstractmethod
import math
class Shape(ABC):
"""Abstract base class for shapes"""
@abstractmethod
def area(self):
"""Calculate area - must be implemented by subclasses"""
pass
@abstractmethod
def perimeter(self):
"""Calculate perimeter - must be implemented"""
pass
def description(self):
"""Concrete method - available to all subclasses"""
return f"I am a {self.__class__.__name__}"
class Circle(Shape):
def __init__(self, radius):
self.radius = radius
def area(self):
return math.pi * self.radius ** 2
def perimeter(self):
return 2 * math.pi * self.radius
class Rectangle(Shape):
def __init__(self, width, height):
self.width = width
self.height = height
def area(self):
return self.width * self.height
def perimeter(self):
return 2 * (self.width + self.height)
# Cannot instantiate abstract class
# s = Shape() # TypeError!
# Can instantiate concrete subclasses
circle = Circle(5)
rect = Rectangle(4, 6)
print(circle.description()) # I am a Circle
print(f"Circle area: {circle.area():.2f}")
print(f"Rectangle area: {rect.area()}")
9.5 Polymorphism
class Payment(ABC):
"""Abstract payment class"""
@abstractmethod
def pay(self, amount):
pass
class CreditCard(Payment):
def __init__(self, number, expiry):
self.number = number
self.expiry = expiry
def pay(self, amount):
return f"Paid ${amount} with Credit Card ending in {self.number[-4:]}"
class PayPal(Payment):
def __init__(self, email):
self.email = email
def pay(self, amount):
return f"Paid ${amount} with PayPal account {self.email}"
class Cash(Payment):
def pay(self, amount):
return f"Paid ${amount} in cash"
# Polymorphic function
def process_payment(payment_method, amount):
"""Process payment regardless of method type"""
print(payment_method.pay(amount))
# Could add logging, receipt generation, etc.
# Test polymorphism
payments = [
CreditCard("1234-5678-9012-3456", "12/25"),
PayPal("user@example.com"),
Cash()
]
for payment in payments:
process_payment(payment, 100)
# Each calls its own pay method
9.6 super() and Method Chaining
class Person:
def __init__(self, name, age):
self.name = name
self.age = age
def introduce(self):
return f"Hi, I'm {self.name}, {self.age} years old"
class Employee(Person):
def __init__(self, name, age, employee_id, department):
super().__init__(name, age) # Call parent constructor
self.employee_id = employee_id
self.department = department
def introduce(self):
# Extend parent method
base_intro = super().introduce()
return f"{base_intro}. I work in {self.department} (ID: {self.employee_id})"
class Manager(Employee):
def __init__(self, name, age, employee_id, department, team_size):
super().__init__(name, age, employee_id, department)
self.team_size = team_size
def introduce(self):
# Chain to parent's introduce
base_intro = super().introduce()
return f"{base_intro} and manage a team of {self.team_size} people"
# Demonstrate method chaining
mgr = Manager("Alice", 35, "E123", "Engineering", 8)
print(mgr.introduce())
# Hi, I'm Alice, 35 years old. I work in Engineering (ID: E123) and manage a team of 8 people
Unit 10: Recursion
10.1 Introduction to Recursion
# Recursion is a function that calls itself
def countdown(n):
"""Simple recursive countdown"""
if n <= 0:
print("Blastoff!")
else:
print(n)
countdown(n - 1) # Recursive call
countdown(5)
# 5
# 4
# 3
# 2
# 1
# Blastoff!
# Every recursive function needs:
# 1. Base case - condition to stop recursion
# 2. Recursive case - function calls itself with modified parameters
10.2 Factorial
# Iterative factorial
def factorial_iterative(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
# Recursive factorial
def factorial_recursive(n):
# Base case
if n <= 1:
return 1
# Recursive case
return n * factorial_recursive(n - 1)
# Trace factorial_recursive(5):
# factorial_recursive(5) = 5 * factorial_recursive(4)
# = 5 * (4 * factorial_recursive(3))
# = 5 * (4 * (3 * factorial_recursive(2)))
# = 5 * (4 * (3 * (2 * factorial_recursive(1))))
# = 5 * (4 * (3 * (2 * 1)))
# = 5 * (4 * (3 * 2))
# = 5 * (4 * 6)
# = 5 * 24
# = 120
print(factorial_recursive(5)) # 120
10.3 Fibonacci Sequence
# Recursive Fibonacci (inefficient)
def fib_recursive(n):
"""Return nth Fibonacci number"""
if n <= 1:
return n
return fib_recursive(n - 1) + fib_recursive(n - 2)
# Trace fib_recursive(5):
# fib(5) = fib(4) + fib(3)
# = (fib(3) + fib(2)) + (fib(2) + fib(1))
# = ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + 1)
# = etc.
# This recalculates same values many times - inefficient for large n
# Memoized Fibonacci (with caching)
def fib_memoized(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memoized(n - 1, memo) + fib_memoized(n - 2, memo)
return memo[n]
# Iterative Fibonacci (most efficient for single values)
def fib_iterative(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
# Performance comparison
import time
def time_function(func, n):
start = time.time()
result = func(n)
end = time.time()
return result, end - start
n = 35
# rec_result, rec_time = time_function(fib_recursive, n) # Very slow!
memo_result, memo_time = time_function(fib_memoized, n)
iter_result, iter_time = time_function(fib_iterative, n)
print(f"Fib({n}) = {iter_result}")
# print(f"Recursive time: {rec_time:.4f}s") # Very slow for n=35
print(f"Memoized time: {memo_time:.4f}s")
print(f"Iterative time: {iter_time:.4f}s")
10.4 Power Function
# Recursive power function
def power(base, exponent):
"""Calculate base^exponent recursively"""
# Base case
if exponent == 0:
return 1
# Recursive case
return base * power(base, exponent - 1)
# More efficient: divide and conquer
def power_fast(base, exponent):
"""More efficient power using divide and conquer"""
if exponent == 0:
return 1
if exponent % 2 == 0:
# If exponent is even: base^exp = (base^(exp/2))^2
half = power_fast(base, exponent // 2)
return half * half
else:
# If exponent is odd: base^exp = base * base^(exp-1)
return base * power_fast(base, exponent - 1)
print(power(2, 10)) # 1024
print(power_fast(2, 10)) # 1024
10.5 Sum of Digits
def sum_digits(n):
"""Sum digits of a number recursively"""
# Base case
if n < 10:
return n
# Recursive case
return n % 10 + sum_digits(n // 10)
# Alternative: convert to string
def sum_digits_str(n):
return sum(int(digit) for digit in str(n))
print(sum_digits(12345)) # 15 (1+2+3+4+5)
print(sum_digits_str(12345)) # 15
10.6 Palindrome Check
def is_palindrome(s):
"""Check if string is palindrome recursively"""
# Clean string
s = s.lower().replace(" ", "")
# Base cases
if len(s) <= 1:
return True
# Check first and last characters
if s[0] != s[-1]:
return False
# Recursive case
return is_palindrome(s[1:-1])
print(is_palindrome("racecar")) # True
print(is_palindrome("A man a plan a canal Panama")) # True
print(is_palindrome("hello")) # False
10.7 Binary Search (Recursive)
def binary_search_recursive(arr, target, left, right):
"""Recursive binary search"""
# Base case - not found
if left > right:
return -1
# Calculate middle
mid = (left + right) // 2
# Base case - found
if arr[mid] == target:
return mid
# Recursive cases
if arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, right)
else:
return binary_search_recursive(arr, target, left, mid - 1)
# Wrapper function
def search(arr, target):
return binary_search_recursive(arr, target, 0, len(arr) - 1)
# Test
numbers = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72]
print(search(numbers, 23)) # 5
print(search(numbers, 10)) # -1
10.8 Tower of Hanoi
def tower_of_hanoi(n, source, target, auxiliary):
"""
Solve Tower of Hanoi puzzle recursively
Move n disks from source to target using auxiliary
"""
if n == 1:
print(f"Move disk 1 from {source} to {target}")
return
# Move n-1 disks from source to auxiliary
tower_of_hanoi(n - 1, source, auxiliary, target)
# Move largest disk from source to target
print(f"Move disk {n} from {source} to {target}")
# Move n-1 disks from auxiliary to target
tower_of_hanoi(n - 1, auxiliary, target, source)
# Solve for 3 disks
tower_of_hanoi(3, 'A', 'C', 'B')
# Output shows steps to move all disks from A to C
10.9 Recursion vs Iteration Comparison
import sys
# Recursion depth limit
print(f"Recursion limit: {sys.getrecursionlimit()}") # Usually 1000
# Pros of recursion:
# - Elegant for problems with recursive structure (trees, fractals)
# - Code can be shorter and clearer
# - Natural for divide-and-conquer algorithms
# Cons of recursion:
# - Function call overhead
# - Risk of stack overflow
# - May be less efficient (though memoization helps)
# Example: Tree traversal (natural for recursion)
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def inorder_traversal(node):
"""Inorder tree traversal - naturally recursive"""
if node:
inorder_traversal(node.left)
print(node.value, end=" ")
inorder_traversal(node.right)
# Create tree
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
inorder_traversal(root) # 1 3 4 5 8
10.10 Common Recursion Patterns
# Pattern 1: Linear recursion (one recursive call)
def linear_recursion(n):
"""Single recursive call"""
if n <= 0:
return
print(n)
linear_recursion(n - 1)
# Pattern 2: Binary recursion (two recursive calls)
def binary_recursion(n):
"""Two recursive calls (like binary tree)"""
if n <= 0:
return
print(n)
binary_recursion(n - 1)
binary_recursion(n - 2)
# Pattern 3: Tail recursion (recursive call at end)
def tail_recursion(n, accumulator=1):
"""Recursive call is the last operation"""
if n <= 1:
return accumulator
return tail_recursion(n - 1, n * accumulator)
# Pattern 4: Mutual recursion
def is_even(n):
if n == 0:
return True
return is_odd(n - 1)
def is_odd(n):
if n == 0:
return False
return is_even(n - 1)
print(is_even(4)) # True
print(is_odd(4)) # False
Summary: Python Topics Overview
Unit
Topic
Key Concepts
1
Primitive Types
int, float, bool, str, operators, input/output
2
Using Objects
string methods, math library, random, object references
