ICS 33 – Assignment 2: Sorting, Searching, and Software Testing
Due Date: July 27, 2025
Submission Type: File Upload (.py and .pdf files)
Points: 100 total
Overview
This assignment explores sorting and searching algorithms, their complexity, and their validation using testing and mutation. You will implement two sort+search programs, evaluate their time complexities, and explore how program correctness is verified and undermined.
You will submit your algorithm analysis and mutation documentation in a single PDF file: complexity_and_mutants.pdf.
Changelog
● Fixed incorrect deadline
○ Changed from August 27, 2025 to July 27, 2025
Problem 1: sort and search
Points: 30
Filename(s): bubble_search.py, quick_search.py
Write two Python programs that follow this structure:
1. Sort the input list using:
- Bubble Sort in bubble_search.py
- Quick Sort in quick_search.py
2. Search the sorted list using binary search
3. Return the index of the target if found, or None if not found
The binary_search() function should be included in each file as a placeholder — implement your own logic inside it. Do not use Python's built-in in keyword, index() method, or external libraries.
File Contents: bubble_search.py
Python
def bubble_search(arr, target):
"""Sorts arr using bubble sort, then performs binary search for target."""
def bubble_sort(lst):
n = len(lst)
result = lst.copy()
for i in range(n):
for j in range(0, n - i - 1):
if result[j] > result[j + 1]:
result[j], result[j + 1] = result[j + 1], result[j]
return result
def binary_search(sorted_arr, target):
# TODO: Implement binary search here
return None
sorted_arr = bubble_sort(arr)
return binary_search(sorted_arr, target)
File Contents: quick_search.py
Python
def quick_search(arr, target):
"""Sorts arr using quick sort, then performs binary search for target."""
def quick_sort(lst):
if len(lst) <= 1:
return lst
pivot = lst[0]
left = [x for x in lst[1:] if x <= pivot]
right = [x for x in lst[1:] if x > pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
def binary_search(sorted_arr, target):
# TODO: Implement binary search here
return None
sorted_arr = quick_sort(arr)
return binary_search(sorted_arr, target)
Your Tasks:
1. Implement both bubble_sort() and quick_sort() in their respective files.
2. Implement a working binary_search() in each file that returns:
- The index of target if found
- None if the target is not present
3. In complexity_and_mutants.pdf, explain:
- The time complexity of the full operation (sort + search)
- Your reasoning for both programs
- To determine the complexity, you may try the following steps:
1. Annotate the complexity of each line of the algorithm (e.g., O(1), O(n), O(n2))
2. Express the running time using a mathematical expression—like in class, the supplied book chapters, and Alex's notes and examples:
- For example, 3n
2+n+7 or c1 * n
2 + c2 * n + c3
3. Drop the lowest terms and lower-term constants.
Example Usage:
Python
from bubble_search import bubble_search
from quick_search import quick_search
print(bubble_search([5, 3, 8, 4, 2], 4)) # → 2 or similar valid index
print(bubble_search([5, 3, 8, 4, 2], 10)) # → None
print(quick_search([9, 1, 6, 3], 1)) # → valid index
print(quick_search([9, 1, 6, 3], 7)) # → None
Constraints:
- Do not use sorted() or list.sort()
- Do not use bisect or built-in search methods
- Implement sorting and searching manually
- binary_search() is initially a placeholder — you must fill it in
Problem 2: unit testing and mutation testing
Points: 40
Filename(s): test_search.py, bubble_search_mutant.py, quick_search_mutant.py
Part A – Unit Testing
Write a test file test_search.py that includes two unit tests, using the unittest built-in Python module (https://docs.python.org/3/library/unittest.html):
- Each test provides the same input list and target to both bubble_search() and quick_search()
- The tests should assert that both functions return the correct index
Part B – Mutation Testing
1. Create mutant versions of each function:
- bubble_search_mutant.py
- quick_search_mutant.py
2. Inject bugs (e.g., off-by-one errors, broken comparisons) that cause the test to fail
3. Document the mutation in a section of complexity_and_mutants.pdf under the heading "Mutation Explanation"
Constraints:
- Mutants must fail when run with your unit tests
- Use the unittest built-in Python module and appropriate assert statements
- Keep the tests clean, readable, and reproducible
Problem 3: Analyzing a worklist algorithm's complexity
Points: 30
Reported in: complexity_and_mutants.pdf
A worklist algorithm maintains a list of items that need to be worked on continuously until the list is empty. Often, worklist algorithms keep executing until a fixed point is reached, i.e., tracked data or state no longer changes. Worklist algorithms operate like recursive algorithms, as they maintain information being worked on that would normally be stored on a stack, allowing a program to operate using loops instead of recursion. Recursion can suffer from potentially high memory consumption, making worklist algorithms with loops more preferable for such problems.
Analyze the time complexity of the following worklist algorithm.Python
In your complexity_and_mutants.pdf file, include:
def worklist_algorithm(matrix):
"""A worklist-based matrix update algorithm."""
n = len(matrix)
worklist = [(i, j) for i in range(n) for j in range(n)]
while worklist:
i, j = worklist.pop()
for k in range(n):
new_val = matrix[i][k] + matrix[k][j]
if new_val < matrix[i][j]:
matrix[i][j] = new_val
for m in range(n):
worklist.append((i, m))
worklist.append((m, j))
This algorithm simulates a propagating update over a matrix using a worklist. Your job is to analyze the runtime complexity of this algorithm based on input size n.
- A description or pseudocode of the algorithm
- The Big-O complexity in terms of input size ( n )
- Prove your program's Big-O complexity by solving for constants c and n0
that satisfy the formal definition of Big-O
- Annotate the complexity of each line of the algorithm (e.g., O(1), O(n), O(n
2
))
- Express the running time using a mathematical expression—like in class, the supplied book chapters, and Alex's notes and examples:
- For example, 3n
2+n+7 or c1 * n
2 + c2 * n + c3
- Choose an f(n) and g(n) and solve for c and n0
- A paragraph explaining how you derived your answer
Formatting:
Include each section in the PDF using clear headings:
- “Bubble Sort Complexity”
- “Quick Sort Complexity”
- “Worklist Algorithm Analysis”
- “Mutation Explanation”
Submission Instructions
Submit the following files in a zip file:
- bubble_search.py
- quick_search.py
- test_search.py
- bubble_search_mutant.py
- quick_search_mutant.py
- complexity_and_mutants.pdf
Ensure:
- Original programs pass all tests
- Mutant programs fail as expected
- complexity_and_mutants.pdf is well formatted, complete, and includes all required explanations