def crunchy(lst):
forwards = 0
for num in lst:
forwards = forwards + num
backwards = 0
for i in range(len(lst)-1, -1, -1):
# This loops over the list backwards!
backwards = backwards + lst[i]
even = 0
for i in range(0, len(lst), 2):
even = even + lst[i]
odd = 0
for i in range(1, len(lst), 2):
odd = odd + lst[i]
evenodd = even + odd
# check if all 3 equal each other
return forwards == backwards == evenoddFall 2025 Midterm 1 Practice Problems
CSCI 1913 – Introduction to Algorithms, Data Structures, and Program Development
1 Big-O
1.1 Question 1
Consider the following function:
Where \(N=len(lst)\), what is the worst case big-O runtime of this function?
▢ a) \(O(1)\)
▢ b) \(O(\log N)\)
▢ c) \(O(N)\)
▢ d) \(O(N \log N)\)
▢ e) \(O(N^2)\)
▢ f) \(O(N^3)\)
▢ g) \(O(N^4)\)
▢ h) \(O(2^N)\)
1.2 Question 2
Consider the following function:
def crunchy(lst):
out = 1
tracker = []
for idx in range(len(lst)-1):
for k in range(idx):
out += k
tracker.append(lst[idx])
return (out, tracker)Where \(N=len(lst)\), what is the worst case big-O runtime of this function? (You may assume append is constant time and tuple literal creation is constant time.
▢ a) \(O(1)\)
▢ b) \(O(\log N)\)
▢ c) \(O(N)\)
▢ d) \(O(N \log N)\)
▢ e) \(O(N^2)\)
▢ f) \(O(N^3)\)
▢ g) \(O(N^4)\)
▢ h) \(O(2^N)\)
1.3 Question 3
Consider the following function:
def mystery(data):
result = []
for i in range(len(data)):
temp = 0
for j in range(i, len(data)):
temp += data[j]
result.append(temp)
for x in data:
for y in data:
if x == y:
result.append(x * 2)
count = 0
for i in range(len(result)):
count += result[i]
return countWhere \(N=len(lst)\), what is the worst case big-O runtime of this function? (You may assume append is constant time and tuple literal creation is constant time.
▢ a) \(O(1)\)
▢ b) \(O(\log N)\)
▢ c) \(O(N)\)
▢ d) \(O(N \log N)\)
▢ e) \(O(N^2)\)
▢ f) \(O(N^3)\)
▢ g) \(O(N^4)\)
▢ h) \(O(2^N)\)
1.4 Question 4
Consider this function:
def find_max(numbers):
if not numbers:
return None
max_val = numbers[0]
for num in numbers:
if num > max_val:
max_val = num
return max_valWhere N is the length of the argument list, what is the worst case big-O runtime of this function?
▢ a) \(O(1)\)
▢ b) \(O(\log N)\)
▢ c) \(O(N)\)
▢ d) \(O(N \log N)\)
▢ e) \(O(N^2)\)
▢ f) \(O(N^3)\)
▢ g) \(O(N^4)\)
▢ h) \(O(2^N)\)
1.5 Question 5
Consider this function:
def has_duplicates(arr):
for i in range(len(arr)):
for j in range(i + 1, len(arr)):
if arr[i] == arr[j]:
return True
return FalseWhere N is the length of the argument list, what is the worst case big-O runtime of this function?
▢ a) \(O(1)\)
▢ b) \(O(\log N)\)
▢ c) \(O(N)\)
▢ d) \(O(N \log N)\)
▢ e) \(O(N^2)\)
▢ f) \(O(N^3)\)
▢ g) \(O(N^4)\)
▢ h) \(O(2^N)\)
1.6 Question 6
Consider the following function:
def print_pairs(arr):
n = len(arr)
for i in range(n):
for j in range(n):
for k in range(n):
print(f"({arr[i]}, {arr[j]}, {arr[k]})")Where N is the length of the argument list, what is the worst case big-O runtime of this function?
▢ a) \(O(1)\)
▢ b) \(O(\log N)\)
▢ c) \(O(N)\)
▢ d) \(O(N \log N)\)
▢ e) \(O(N^2)\)
▢ f) \(O(N^3)\)
▢ g) \(O(N^4)\)
▢ h) \(O(2^N)\)
1.7 Question 7
Consider the following function:
def foo(arr, target):
left = 0
right = len(arr) - 1
all_mid_values = []
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
all_mid_values.append(arr[mid])
else:
right = mid - 1
all_mid_values.append(arr[mid])
return -1Where N is the length of the argument list, what is the worst case big-O runtime of this function?
▢ a) \(O(1)\)
▢ b) \(O(\log N)\)
▢ c) \(O(N)\)
▢ d) \(O(N \log N)\)
▢ e) \(O(N^2)\)
▢ f) \(O(N^3)\)
▢ g) \(O(N^4)\)
▢ h) \(O(2^N)\)
1.8 Question 8
Consider the following functions:
def binary_search(arr, v):
low = 0
high = len(arr)-1
while low <= high:
mid = (low+high)//2
if v > arr[mid]:
low = mid + 1
elif v < arr[mid]:
high = mid - 1
else:
return mid
return -1
def foo(arr):
result = []
for value in arr:
index = binary_search(arr, value)
result.append(index)Where N is the length of the argument list, what is the worst case big-O runtime of the foo(arr) function?
▢ a) \(O(1)\)
▢ b) \(O(\log N)\)
▢ c) \(O(N)\)
▢ d) \(O(N \log N)\)
▢ e) \(O(N^2)\)
▢ f) \(O(N^3)\)
▢ g) \(O(N^4)\)
▢ h) \(O(2^N)\)
2 Code reading – output
2.1 Question 1
Consider the following code:
def foo(x):
new = ""
if x < 10:
new += "A"
elif x < 100:
new += "B"
elif x < 1000:
new += "C"
else:
new += "D"
if x < 10:
new += "E"
else:
new += "F"
return new
if __name__ == "__main__":
result = foo(22)
print(result)
result = foo(5)
print(result)What does the code print? For credit your answer must be EXACTLY correct, so a few hints: The question is case sensitive (lowercase vs. uppercase letters matter).
2.2 Question 2
Consider the following code:
def foo(count):
result = ""
while count > 0:
if count % 2 == 1:
result += "X"
else:
result += "Y"
count -= 1
if len(result) > 2:
result += "A"
else:
result += "B"
return result
if __name__ == "__main__":
result = foo(5)
print(result)What does the code print? For credit your answer must be EXACTLY correct, so a few hints: The question is case sensitive (lowercase vs. uppercase letters matter).
3 Loops and Python types
3.1 Question 1
This question tests your understanding of looping patterns and overall access-patterns for the various data structures. Consider the following function:
def lovely(something):
new = []
for heart in something:
new.append(something[heart])
return newFor each input below either indicate it would crash, or if it would run to completion, write out what would be printed. (if there are multiple possible correct printings, for example because dictionaries and sets are unordered, give one possible printed output)
my_list1=["N", "S", "E", "W", "north"]
result = lovely(my_list1)
print(result)var={"up":"down", "left":"right", "north":"south", "east":"west"}
result = lovely(var)
print(result)4 Write code
4.1 Question 1
Write a python function rotate that rotates a list in place by k elements left. This is a mutator function, that mutates the argument list. This function should take two argu- ments: a list and an integer k. For example [1,2,3,4,5,6] rotated by k = 2 becomes [3,4,5,6,1,2]
Test cases:
numbers = [1, 2, 3, 4, 5, 6]
rotate(numbers, 2)
assert numbers == [3, 4, 5, 6, 1, 2]
letters = ["a", "B", "c", "d"]
rotate(letters, 1)
assert letters == ["B", "c", "d", "a"]4.2 Question 2
Write a python function called get_average that takes a list of numbers are argument and returns the average (sum all numbers and divide by total number of items in list).
Test cases:
numbers = [1, 2, 3, 4, 5, 6]
assert get_average(numbers) == 3.5
assert get_average([]) == 0 # empty list4.3 Question 3
Write a python function adjust_grades that takes a list of grades and adjusts them according to the rules specified below. This is a mutator function, that mutates the argument list.
- Every student receives a grade in the inclusive range from 0 to 100. (no need to validate this)
- If the difference between the grade and the next multiple of 5 is less than 1, round the grade up to the next multiple of 5.
- If the value of grade is less than 60, no rounding occurs as the result will still be a failing grade.
fall_2025 = [59.7, 69.6, 64.5, 73, 79, 79.5, 84.1]
adjust_grades(fall_2025)
assert fall_2025 == [59.7, 70.0, 65.0, 73, 79, 80, 85]4.4 Question 4
Write a ptyhon function most_frequent that takes in a list (of any immutable type) and returns the most frequent element in the list.
things = ["apple", 0, 0, "apple", "pear", 0, "apple", "apple"]
assert most_frequent(things) == "apple"5 Sorting
- What is the main principle behind selection sort?
▢ a) Divide the array into sorted and unsorted portions, inserting elements one at a time
▢ b) Repeatedly find the minimum element from the unsorted portion and place it at the beginning
▢ c) Compare adjacent elements and swap them if they’re in the wrong order
▢ d) Use a pivot element to partition the array
- How does insertion sort build the final sorted array? By…
▢ a) searching which minimun value should go at each list position (starting at index 0), repeatedly selecting the smallest element
▢ b) comparing all adjacent pairs simultaneously, starting at the beginning of the list going to the end repeatedly
▢ c) building the sorted array one item at a time, inserting each new element into its proper position
▢ d) dividing the array in half recursively, sorting each array, and then combining back each sorted subarray
- When does insertion sort perform most efficiently?
▢ a) When the array is sorted in reverse order
▢ b) When the array is randomly shuffled
▢ c) When the array is already sorted or nearly sorted
▢ d) When the array contains many duplicate elements
- What does bubble sort do in each pass through the array?
▢ a) Finds the minimum element and places it at the front
▢ b) Inserts each element into its correct position
▢ c) Partitions the array around a pivot
▢ d) Compares adjacent elements and swaps them if they’re out of order
- After the first complete pass of bubble sort on an array of n elements, what is guaranteed?
▢ a) The largest element is in its correct position
▢ b) The smallest element is in its correct position
▢ c) Half the array is sorted
▢ d) All elements have been compared once
- How can bubble sort be optimized to detect when the array is already sorted?
▢ a) By using a flag to check if any swaps occurred during a pass
▢ b) By counting the number of comparisons
▢ c) By dividing the array into subarrays
▢ d) By sorting from both ends simultaneously
- After the first complete pass of selection sort on an array of n elements, what is guaranteed?
▢ a) The largest element is in its correct position
▢ b) The smallest element is in its correct position
▢ c) Half the array is sorted
▢ d) All elements have been compared once
- Selection, insertion, and bubble sort algorithms share which characteristic?
▢ a) They all have O(n) time complexity
▢ b)They all use divide-and-conquer
▢ c) They all have O(n²) time complexity
▢ d) They all require O(n) additional space
6 Key
6.1 Big-O Question 1
The answer is c) \(O(N)\) because the four for loops are not nested. The total time complexity is: \(O(1) + O(N) + O(N) + O(N) + O(N) = O(N)\)
6.2 Big-O Question 2
The answer is e) \(O(N^2)\)
Outer loop runs runs N times.
Inner loop runs 0 times for idx 0, 1 time for idx 1, 2 times for idx 2 – \(0 + 1 + 2 + ... + (N-2) = (N-2)(N-1)/2\).
\(\frac{(N-2)(N-1)}{2} = O(N^2)\)
tracker.append(lst[idx]) runs N times (\(O(N)\)).
\(O(N^2) + O(N) = O(N^2)\)
6.3 Big-O Question 3
The answer is e) \(O(N^2)\)
First loop is \(O(N^2)\).
Second loop is \(O(N^2)\).
Third loops runs \(2N\) for worst-case scenario, so \(O(N)\).
6.4 Big-O Question 4
The answer is c) \(O(N)\)
Best case is \(O(1)\) (empty list), worst case is \(O(N)\). Loop checks every value in argument list.
6.5 Big-O Question 5
The answer is e) \(O(N^2)\)
Because fo the nested loops comparing all pairs. For every item in list, it’s compared to every item in the (minus itself).
6.6 Big-O Question 6
The answer is f) \(O(N^3)\)
Three nested loops.
6.7 Big-O Question 7
The answer is b) \(O(\log N)\)
Boundaries of which values will be checked in the while loop change at every iteraction, halving the size of the sublist that is considered in each interaction.
- After 1 comparison: N/2 elements remain
- After 2 comparisons: N/4 elements remain
- After 3 comparisons: N/8 elements remain
- After 4 comparisons: N/16 elements remain
- After 5 comparisons: N/32 elements remain
- After
kcomparisons: N/2^k elements remain
After k comparisons: N/2^k elements remain.
What’s the value of k?
\(N = 2^k\)
\(k = log_2(N)\)
6.8 Big-O Question 8
The answer is d) \(O(N \log N)\)
Binary Search is performed for every element in the array. Binary Search is \(O(\log N)\) so running Binary Search for every array item is \(O(N \log N)\)
6.9 Read code – output Question 1
BF
AE6.10 Read code – Question 2
XYXYXA6.11 Loops and Python types Question 1
It crashes because items in a list are accessed by an index, so when it does
something[heart]it is indexing the list through its items (it can’t) so it crashes because a string does not index a list. The loop would need to befor i in range(len(something))and then we need to dosomething[i]Since
somethingis a dictionary, and the for loop retrieves each key in the dictionary,something[heart]works because heart is always a dictionary key. The standard output would look like this:
['down', 'right', 'south', 'west']6.12 Write code Question 1
Solution 1:
def rotate(my_list, k):
list_copy = my_list.copy()
for i in range(len(my_list)-k):
my_list[i] = list_copy[i+k]
for i in range(1, k+1):
index = (k-i+1) * -1
my_list[index] = list_copy[i-1]Solution 2:
def rotate(my_list, k):
for i in range(k):
my_list.append(my_list.pop(0))6.13 Write code Question 2
def get_average(my_list):
average = 0
for item in my_list:
average += item
return average/len(my_list)6.14 Write code Question 3
def adjust_grades(grades):
for i in range(len(grades)):
grade = grades[i]
round_up = (grade+5)//5 * 5
if round_up - grade < 1 and grade > 60:
grades[i] = round_up6.15 Write code Question 3
Solution 1:
def most_frequent(my_list):
# count first
counts = {}
for item in my_list:
counts[item] = counts.get(item, 0) + 1
return max(counts, key=counts.get)Solution 2:
def most_frequent(my_list):
# count first
counts = {}
for item in my_list:
counts[item] = counts.get(item, 0) + 1
highest = max(counts.values())
for key, value in counts.items():
if value == highest:
return key6.16 Sorting
- The main principle behind selection sort is b) Repeatedly find the minimum element from the unsorted portion and place it at the beginning
- Insertion sort builds the final sorted array by c) building the sorted array one item at a time, inserting each new element into its proper position
- Insertion sort perform most efficiently c) When the array is already sorted or nearly sorted
- Bubble sort do in each pass through the array d) Compares adjacent elements and swaps them if they’re out of order
- After the first complete pass of bubble sort on an array of n elements, a) The largest element is in its correct position
- Bubble sort cab be optimized to detect when the array is already sorted? a) By using a flag to check if any swaps occurred during a pass
- After the first complete pass of selection sort on an array of n elements, b) The smallest element is in its correct position
- Selection, insertion, and bubble sort algorithms c) all have O(n²) time complexity