Homework

14.4.3. Homework#

  • Use these questions after class to check your understanding of the chapter concepts and coding skills.

  • Sign in from the account menu before you start working on the homework.

  • Complete all true/false and coding questions before you submit the homework.

  • Launch Live Code (the rocket) to write and run code in the coding cells.

  • Multiple submissions are allowed. The highest score is kept.

1. Algorithm Design

Before coding, a team can compare two possible step-by-step procedures for the same task and choose the clearer or faster algorithm.

Hide code cell source

 
### Solution
# True
# An algorithm is a step-by-step procedure, so you can describe and compare two procedures
# for the same task before writing code. Comparing their clarity and growth in work helps
# you choose one.

2. Big O

Big O notation describes how work grows as input size grows, not the exact number of seconds on one laptop.

Hide code cell source

 
### Solution
# True
# Big O describes how the number of steps grows as the input size n grows, such as O(n) or
# O(log n). Actual run time in seconds depends on the machine, so Big O ignores it.

3. Linear Search

Linear search requires sorted input before it can check each value one at a time.

Hide code cell source

 
### Solution
# False
# Linear search checks each item in order until it finds the target or reaches the end. It
# works on unsorted data; binary search is the one that requires sorted input.

4. Binary Search

Binary search relies on sorted data so each comparison can discard about half of the remaining search space.

Hide code cell source

 
### Solution
# True
# Binary search compares the target with the middle item of a sorted list. Because the
# data is sorted, each comparison rules out about half of the remaining items, giving
# O(log n) time.

5. Sorting

A sorting algorithm can be evaluated only by whether it changes the original list in place.

Hide code cell source

 
### Solution
# False
# Sorting algorithms are evaluated mainly on correctness, time complexity, and properties
# such as stability and extra memory use. Sorting in place is only one property; sorted()
# returns a new list and is still a valid sort.

### 6. Handle linear search edge cases
# Write linear_search(items, target) that scans items from left to right
# and returns the index of the first match, or -1 if target is absent.
# Call it for a duplicated value (22), the first item (14), the last
# item (59), an absent value (40), and an empty list (search [] for 22).
# Print exactly these five lines:
# # Duplicate 22: 1
# # First item 14: 0
# # Last item 59: 4
# # Absent 40: -1
# # Empty list: -1
values = [14, 22, 31, 22, 59]

### Your code starts here.



### Your code ends here.

Hide code cell source

 
### Solution
values = [14, 22, 31, 22, 59]

def linear_search(items, target):
    for i, value in enumerate(items):
        if value == target:
            return i
    return -1

print("Duplicate 22:", linear_search(values, 22))
print("First item 14:", linear_search(values, 14))
print("Last item 59:", linear_search(values, 59))
print("Absent 40:", linear_search(values, 40))
print("Empty list:", linear_search([], 22))

Duplicate 22: 1
First item 14: 0
Last item 59: 4
Absent 40: -1
Empty list: -1

### 7. Find the leftmost match with binary search
# Write binary_search_first(sorted_items, target) that uses a while loop
# with left, right, and mid to return the index of the leftmost occurrence
# of target, or -1 if target is absent. When you find a match, record it
# and keep searching left. Call it for a duplicated value (8), the first
# item (3), the last item (31), an absent value (10), and an empty list
# (search [] for 8). Print exactly these five lines:
# # First 8: 1
# # First item 3: 0
# # Last item 31: 7
# # Absent 10: -1
# # Empty list: -1
values = [3, 8, 8, 8, 12, 19, 25, 31]

### Your code starts here.



### Your code ends here.

Hide code cell source

 
### Solution
values = [3, 8, 8, 8, 12, 19, 25, 31]

def binary_search_first(sorted_items, target):
    left = 0
    right = len(sorted_items) - 1
    result = -1
    while left <= right:
        mid = (left + right) // 2
        if sorted_items[mid] == target:
            result = mid
            right = mid - 1
        elif sorted_items[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result

print("First 8:", binary_search_first(values, 8))
print("First item 3:", binary_search_first(values, 3))
print("Last item 31:", binary_search_first(values, 31))
print("Absent 10:", binary_search_first(values, 10))
print("Empty list:", binary_search_first([], 8))

First 8: 1
First item 3: 0
Last item 31: 7
Absent 10: -1
Empty list: -1

### 8. Use insertion-sort logic
# Insert 74 into the sorted list. Print exactly this line:
# # Scores: [61, 68, 74, 80, 92]
scores = [61, 68, 80, 92]
new_score = 74

### Your code starts here.



### Your code ends here.

Hide code cell source

 
### Solution
scores = [61, 68, 80, 92]
new_score = 74
position = 0

while position < len(scores) and scores[position] < new_score:
    position += 1

scores.insert(position, new_score)
print("Scores:", scores)

Scores: [61, 68, 74, 80, 92]

### 9. Implement merge sort
# Write merge(left, right) that uses two pointers to combine two sorted
# lists into one sorted list, then write merge_sort(items) that splits
# the list in half at mid = len(items) // 2, sorts each half recursively,
# and merges the results. A list with one element or fewer is already sorted.
# Do not call sorted() or .sort() inside your functions.
# Print the sorted left and right halves of values, the full sorted list,
# and whether it matches sorted(values). Print exactly these four lines:
# # Left half: [27, 38, 43]
# # Right half: [3, 9, 10, 82]
# # Sorted: [3, 9, 10, 27, 38, 43, 82]
# # Matches sorted(): True
values = [38, 27, 43, 3, 9, 82, 10]

### Your code starts here.



### Your code ends here.

Hide code cell source

 
### Solution
values = [38, 27, 43, 3, 9, 82, 10]

def merge(left, right):
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

def merge_sort(items):
    if len(items) <= 1:
        return items[:]
    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    return merge(left, right)

mid = len(values) // 2
print("Left half:", merge_sort(values[:mid]))
print("Right half:", merge_sort(values[mid:]))
result = merge_sort(values)
print("Sorted:", result)
print("Matches sorted():", result == sorted(values))

Left half: [27, 38, 43]
Right half: [3, 9, 10, 82]
Sorted: [3, 9, 10, 27, 38, 43, 82]
Matches sorted(): True

### 10. Compare linear and binary search comparisons
# Write linear_count(items, target), which returns how many items linear
# search checks before it finds target or reaches the end, and
# binary_count(sorted_items, target), which returns how many midpoint
# comparisons binary search makes (count one per loop iteration).
# Report both counts for the last item (88) and an absent value (5).
# Then print the worst case for n = len(values): n for linear search and
# floor(log2 n) + 1 for binary search. Print exactly these three lines:
# # Target 88: linear 10, binary 4
# # Target 5: linear 10, binary 3
# # Worst case for n = 10: linear 10, binary 4
values = [4, 8, 15, 16, 23, 42, 57, 61, 75, 88]

### Your code starts here.



### Your code ends here.

Hide code cell source

 
### Solution
import math

values = [4, 8, 15, 16, 23, 42, 57, 61, 75, 88]

def linear_count(items, target):
    comparisons = 0
    for value in items:
        comparisons += 1
        if value == target:
            break
    return comparisons

def binary_count(sorted_items, target):
    left = 0
    right = len(sorted_items) - 1
    comparisons = 0
    while left <= right:
        comparisons += 1
        mid = (left + right) // 2
        if sorted_items[mid] == target:
            break
        if sorted_items[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return comparisons

for target in [88, 5]:
    print(f"Target {target}: linear {linear_count(values, target)}, binary {binary_count(values, target)}")

n = len(values)
print(f"Worst case for n = {n}: linear {n}, binary {math.floor(math.log2(n)) + 1}")

Target 88: linear 10, binary 4
Target 5: linear 10, binary 3
Worst case for n = 10: linear 10, binary 4