Algorithm Design

Algorithm Representation

An algorithm is a step-by-step set of instructions to solve a problem. Algorithms can be represented in three ways: flowcharts, pseudocode, and program code.

Flowchart Symbols

Pseudocode Keywords

INPUT, OUTPUT
IF-THEN-ELSE-ENDIF
WHILE-ENDWHILE
FOR-NEXT
REPEAT-UNTIL

Flowchart vs Pseudocode

Aspect	Flowchart	Pseudocode
Format	Visual diagram with symbols	Text-based structured English
Advantage	Easy to understand logic flow	Closer to actual code
Disadvantage	Complex for large programs	Less visual clarity

Sorting Concepts

Sorting is the process of arranging data in a specific order (ascending or descending). It enables faster searching and better data organization.

Key Terms

• In-place sorting: Doesn't require an additional array
• Stable sorting: Preserves the relative order of equal elements
• Time complexity: O(n²) means time grows quadratically with data size

Searching Concepts

Searching algorithms find specific data within a collection. The choice of algorithm depends on whether the data is sorted.

Aspect	Linear Search	Binary Search
Method	Check one by one	Divide and conquer
Requirement	Works on any data	Requires sorted data
Time Complexity	O(n)	O(log n)
Example (1000 items)	Up to 1000 comparisons	At most 10 comparisons

Sub-programs

Sub-programs are reusable blocks of code that perform specific tasks. They improve code modularity and maintainability.

Types of Sub-programs

• Function: Returns a value using the return statement
• Procedure: Performs an action but does NOT return a value

Benefits

• Code reuse
• Modularity
• Easier maintenance
• Improved readability

Key Terms

• Parameters: Values passed into a sub-program
• Local variables: Exist only within the sub-program
• Global variables: Accessible throughout the entire program
• Scope: The region where a variable is accessible

Bubble Sort

Bubble sort repeatedly compares adjacent elements and swaps them if they are in the wrong order. The largest element "bubbles" to the end after each complete pass.

How It Works

1. Compare adjacent pairs of elements
2. Swap if they are in the wrong order
3. After pass k, the last k elements are in their final positions
4. Optimization: use a swapped flag to exit early if already sorted

Python Implementation

def bubble_sort(data):
    n = len(data)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if data[j] > data[j + 1]:
                data[j], data[j + 1] = data[j + 1], data[j]
                swapped = True
        if not swapped:
            break

Trace Table Example: [5, 3, 8, 1, 2]

Pass	List State	Comparisons
Initial	[5, 3, 8, 1, 2]	-
Pass 1	[3, 5, 1, 2, 8]	4
Pass 2	[3, 1, 2, 5, 8]	3
Pass 3	[1, 2, 3, 5, 8]	2
Pass 4	[1, 2, 3, 5, 8]	No swaps - sorted!

Insertion Sort

Insertion sort builds the sorted portion one element at a time by inserting each element into its correct position. It works like sorting playing cards in your hand.

How It Works

1. Start with the second element (first element is already "sorted")
2. Compare it with elements in the sorted portion
3. Shift larger elements to the right
4. Insert the element in its correct position

Python Implementation

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

Trace Table Example: [5, 3, 8, 1, 2]

Iteration	Key	List State
Initial	-	[5, 3, 8, 1, 2]
i=1	3	[3, 5, 8, 1, 2]
i=2	8	[3, 5, 8, 1, 2]
i=3	1	[1, 3, 5, 8, 2]
i=4	2	[1, 2, 3, 5, 8]

Linear Search

Linear search checks each element one by one from start to end until the target is found or the end is reached.

Python Implementation

def linear_search(data, target):
    for i in range(len(data)):
        if data[i] == target:
            return i  # Return index if found
    return -1  # Return -1 if not found

Time Complexity: O(n) - worst case checks all elements

Binary Search

Binary search only works on sorted data. It repeatedly divides the search space in half, making it much faster than linear search.

How It Works

1. Find the middle element
2. If target equals middle element, found!
3. If target is less than middle, search left half
4. If target is greater than middle, search right half
5. Repeat until found or search space is empty

Python Implementation

def binary_search(data, target):
    low = 0
    high = len(data) - 1
    while low <= high:
        mid = (low + high) // 2
        if data[mid] == target:
            return mid
        elif target < data[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return -1

Trace Table: Search for 7 in [1, 3, 5, 7, 9, 11, 13]

Step	low	high	mid	data[mid]	Action
1	0	6	3	7	Found!

Time Complexity: O(log n) - much faster than linear search

Sub-program Examples

Function (Returns a Value)

def calculate_area(length, width):
    return length * width

result = calculate_area(5, 3)  # result = 15

Procedure (No Return Value)

def display_greeting(name):
    print("Hello, " + name + "!")

display_greeting("Alice")  # Prints: Hello, Alice!

Program Testing & Test Data

Testing verifies that a program produces correct output for various inputs. Different types of test data are used to ensure comprehensive coverage.

Types of Test Data

• Normal data: Typical expected inputs
• Boundary data: Edge cases (min/max values, empty input)
• Abnormal data: Invalid inputs (wrong type, out of range)

Test Plan Example

Test Case	Input	Expected Output	Actual Output	Pass/Fail
Normal	5	120	120	Pass
Boundary	0	1	1	Pass
Abnormal	-5	Error message	Error message	Pass

Error Types

1. Syntax Error

Violates language rules. Detected by the interpreter before/during execution.

# Example: Missing colon
if x > 5  # SyntaxError: invalid syntax
    print("Greater")

2. Runtime Error

Program crashes during execution due to invalid operations.

# Example: Division by zero
result = 10 / 0  # ZeroDivisionError

# Example: Index out of range
data = [1, 2, 3]
print(data[5])  # IndexError

3. Logic Error

Program runs but produces incorrect output. Hardest to find!

# Example: Wrong loop boundary
# Should print 1 to 10, but only prints 1 to 9
for i in range(1, 10):  # Should be range(1, 11)
    print(i)

Debugging Techniques

• Print statements to track variable values
• Trace tables to manually execute code
• Step-through debugging with IDE tools
• Test with different types of data

Trace Tables in Practice

Trace tables track variable values step by step during code execution. They are essential for understanding algorithm behavior and finding logic errors.

Example: Bubble Sort Pass

Complete trace of one pass of bubble sort on [5, 3, 8, 1]:

Comparison	j	Compare	Swap?	List
Initial	-	-	-	[5, 3, 8, 1]
1	0	5 vs 3	Yes	[3, 5, 8, 1]
2	1	5 vs 8	No	[3, 5, 8, 1]
3	2	8 vs 1	Yes	[3, 5, 1, 8]

Real-world Algorithm Applications

Greatest Common Divisor (GCD)

def gcd(a, b):
    while b != 0:
        temp = b
        b = a % b
        a = temp
    return a

result = gcd(48, 18)  # result = 6

Palindrome Checking

def is_palindrome(text):
    text = text.lower().replace(" ", "")
    return text == text[::-1]

print(is_palindrome("A man a plan a canal Panama"))  # True

Menu-driven Program

choice = 0
while choice != 4:
    print("1. Enter data")
    print("2. Sort data")
    print("3. Search data")
    print("4. Exit")
    choice = int(input("Choice: "))
    if choice == 1:
        # Enter data code
        pass
    elif choice == 2:
        # Sort data code
        pass
    elif choice == 3:
        # Search data code
        pass