## Lecture 10- Hand Tracing

### Hand Tracing

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.

Lab Activity 1

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)


Lab Activity 2

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))


Lab Activity 3

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


Lab Activity 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


Lab Activity 5
#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]


Lab Activity 6
#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']


Lab Activity 7
#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']

Lab Activity 8
#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


#### Submission

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.