Extra practice problems

Here are some extra practice problems that might be helpful when studying for Exam 3. Take the time to write out your solutions by hand before typing them to check your work.

Loops, lists and dictionaries, other review

  1. Do the Nested For Loops worksheet that Rachel created.
  2. Do the practice problems from the Runestone Chapter 10 assessment

Object-oriented programming

  1. Do the Understanding Classes worksheet that Rachel created.
  2. Do the practice problems from the Runestone Chapter 13 assessment
  3. Finish the last page of the worksheet from May 27 (Slowish Sorting Algorithms).

Recursion

  1. Write a recursive function that checks whether a string is a palindrome. A palindrome is a word that reads the same forwards and backwards, e.g., "anna" and "madam" are palindromes, while "dog", "nana", and "canal" are not palindromes.
  2. In class we discussed how to write a recursive function to sum the numbers in a nested list, assume that each sublist does not mix integers and more sublists. (For example, our code would have worked on the input [[1, 2, 3], [[3, 4], [5], [6, 7]]] but not on the input [[1, [2, 3], 4]].) Write a function that will recursively sum the numbers in a nested list, where each sublist may contain a mixture of integers and more sublists.
  3. Write a recursive program to compute the nth Fibonacci number. The nth fibonacci number Fn is defined as 1 if n=1, 1 if n=2, and F(n-2) + F(n-1) if n >= 3. For example, F3 = F2 + F1 = 3 and F4 = F3 + F2 = 5.

Searching and sorting

  1. Finish the last page of the worksheet from May 27 (Slowish Sorting Algorithms).
  2. Do the "Extra time" problems from the merge sort lab. Explain to yourself in your own words why the improvements lead to faster running time.
  3. Generate a random list of 8 integers (you can use the code from the Merge Sort lab in sortTiming.py). Show how this list will be sorted (at each iteration of the outer loop) for each of selection sort and insertion sort. Then diagram how it will be sorted for merge sort.
  4. Write code to implement sequential search and binary search. Then, modify the code from the Merge Sort lab to compare the time complexity of these algorithms for lists that have different lengths.