There are three things in life that are a certainty. Death, Taxes, and programming bugs. Being able to debug a program is one of the best skills a programmer can have. However, it's also one of the most difficult things to learn. Especially early in a computer science career. With practice, you will be able to find errors as quickly as myself (or your TA's). However, for now the best course of action to find programming bugs will be hand tracing code.
I am going to perform a hand trace of a slightly modified selection sort on the board today. You will exercise these skills on the programs written below. If there are no errors in the code, then you just need to identify the output. If there are errors in the code, you should identify the error, and write the corrected statement. Then hand trace your corrections.
This is a simplistic hand trace utilizing for loops. This code should print the first 10 odd positive integers.
for i in range(10):
print(2 * i + 1)
This is a simplistic hand trace utilizing functions. This program should print the sums of the first 10 pairs of positive integers.
def foo(a, b):
return a + b
for i in range(10):
print(foo(i, i + 1))
This function should print the greatest common divisor(GCD) of the two input parameters. remember the GCD of two numbers is the largest number that divides both numbers.
#Pre: a and b are positive integers
#Post: Returns an integer, the GCD of a and b
def GCD(a, b):
while b != 0:
temp = a
a = b
b = temp % b
return a
print(GCD(4, 2)) # 2
print(GCD(8, 2)) # 2
print(GCD(8, 4)) # 4
#Pre: a_list is a non-empty list of integers
#Post: Returns an integer, the minimum value from the list
def find_min(a_list):
min_so_far = 0
for item in a_list:
if item < min_so_far:
min_so_far = item
return min_so_far
print(find_min([0, 1, 2, 3, 4])) # 0
print(find_min([1, 0, 2, 3, 4])) # 0
print(find_min([1, 2, 0, 3, 4])) # 0
print(find_min([1, 2, 2, 3, 4])) # 1
print(find_min([2, 2, 2, 1, 1])) # 1
#Pre: a_list is a non-empty list
#Post: Returns a new list, all of the unique items from a_list
def compute_unique(a_list):
unique = []
for item in a_list:
if item not in unique:
unique.append(item)
print(unique)
print(compute_unique([0, 1, 2, 3, 4])) # [0, 1, 2, 3, 4]
print(compute_unique([1, 0, 2, 3, 4])) # [1, 0, 2, 3, 4]
print(compute_unique([1, 2, 0, 3, 4])) # [1, 2, 0, 3, 4]
print(compute_unique([1, 2, 2, 3, 4])) # [1, 2, 3, 4]
print(compute_unique([2, 2, 2, 1, 1])) # [2, 1]
#Pre: a_list is a non-empty list of items,
# len(a_list) = n
# first, second are integers, 0 <= first < second < n
#Post: Swaps the items at the indices first and second in a_list
def swap(a_list, first, second):
temp = a_list[first]
a_list[first] = a_list[second]
a_list[second] = a_list[first]
#Pre: a_list is a non-empty list of comparable items
#Post: Returns a sorted copy of a_list
# Uses the bubble sort algorithm
def bubble_sort(a_list):
for end_index in range(len(a_list) - 1, 0, -1):
for curr_index in range(1, end_index):
left_item = a_list[curr_index - 1]
right_item = a_list[curr_index]
if left_item > right_item:
swap(a_list, curr_index - 1, curr_index)
return a_list
print(bubble_sort([5, 4, 3, 2, 1])) # [1, 2, 3, 4, 5]
print(bubble_sort([5, 1, 2, 4, 3])) # [1, 2, 3, 4, 5]
print(bubble_sort(['f', 'd', 'c', 'b', 'a']) # ['a', 'b', 'c', 'd', 'f']
#Pre: a_list is a non-empty list of items,
# len(a_list) = n
# first, second are integers, 0 <= first < second < n
#Post: Swaps the items at the indices first and second in a_list
def swap(a_list, first, second):
temp = a_list[first]
a_list[first] = a_list[second]
a_list[second] = temp
#Pre: a_list is a non-empty list of comparable items
#Post: Returns a sorted copy of a_list
# Uses the insertion sort algorithm
def insertion_sort(a_list):
for start_index in range(len(a_list)):
for curr_index in range(start_index, -1, -1):
left_item = a_list[curr_index - 1]
right_item = a_list[curr_index]
if left_item > right_item:
swap(a_list, curr_index - 1, curr_index)
return a_list
print(insertion_sort([5, 4, 3, 2, 1])) # [1, 2, 3, 4, 5]
print(insertion_sort([5, 1, 2, 4, 3])) # [1, 2, 3, 4, 5]
print(insertion_sort(['f', 'd', 'c', 'b', 'a']) # ['a', 'b', 'c', 'd', 'f']
#Pre: a_2d_list is a non-empty n x n 2-dimensional list of integers
# index is an integer, 0 <= index < n
#Post: Returns an integer, the sum of the column at index 'index' from a_2d_list
def sum_column(a_2d_list, index):
col_sum = 0
for row in range(len(a_2d_list)):
col_sum += a_2d_list[row][index]
return col_sum
#Pre: a_2d_list is a non-empty n x n 2-dimensional list of integers
#Post: Returns True if all of the columns sum to the same values,
# False otherwise.
def col_sums(a_2d_list):
col_sum = sum_column(a_2d_list, 0)
valid = True
for col_index in len(a_2d_list):
if row_sum != sum_column(a_2d_list, col_index):
valid = False
return valid
#Pre: a_2d_list is a non-empty n x n 2-dimensional list of integers
#Post: Returns True if all of the rows sum to the same values,
# False otherwise.
def row_sums(a_2d_list):
row_sum = sum(a_2d_list[0])
valid = True
for row in a_2d_list:
if row_sum != sum(row):
valid = False
return valid
#Pre: a_2d_list is an non-empty n x n 2-dimensional list of integers
#Post: Returns True if a_2d_list is a magic square, False otherwise
# Note:a magic square is one where all of the rows and columns
# sum to the same value
def is_magic(a_2d_list):
rows_valid = row_sums(a_2d_list)
cols_valid = col_sums(a_2d_list)
return rows_valid and cols_valid
print(is_magic([[1, 1], [1, 1]]) # True
print(is_magic([[1, 2], [1, 2]]) # False
print(is_magic([[2, 1], [1, 2]]) # True
print(is_magic([[2, 2], [1, 3]]) # False
Make sure, before you leave, that either myself, Christian, or Natalie have checked you off. Your paper work are yours for future reference. We will go through some of these in class before you leave.