CS21: Quiz 5 Study Guide

In addition to the concepts below, you should also know the concepts from Quiz 1, Quiz 2, Quiz 3, and Quiz 4. Many of the earlier concepts -- especially functions -- are fundamental to what we've been studying recently.

You should understand the following terms and concepts:

• Searching: linear vs binary search
• Analysis of algorithms (number of steps)
• Big-O notation (O(N) vs O(logN), etc)
• Complexity (big O, number of steps) of searching algorithms
• string comparisons ("alice" < "zelda")
• list of lists

Practice problems:

1. True/False questions:
   • Linear search requires a number of steps proportional to the size of the list being searched (T/F)
   • The python in operator performs a binary search (T/F)
   • Binary search is an NlogN algorithm (T/F)
   • The number of times N can be divided by 2 (before reaching 1) is log base-two of N (T/F)
2. Approximately how many iterations will binary search need to find a value in a list of 1 million items?
3. Place these algorithm classes in order from best to worst: N, logN, N*N, NlogN
4. What is log(1024,2) in python? What about log(2048,2)?
5. How many steps are required for each of the following?

   #############################################
   for i in range(n):
     for j in range(n):
       print i, j
   #############################################
   while n > 1:
     print n
     n = n/2
   #############################################
   for i in range(n):
     for j in range(10):
       print i, j
   #############################################
   

6. Show the index values for low, high, and mid for each step in searching the list L for the value x using binary search.

   x = 99
   L = [-20, -12, -4, 1, 7, 44, 45, 46, 58, 67, 99, 145]     low   mid   high
          0    1   2  3  4   5   6   7   8   9  10   11      ----------------
   
   
   
   
   
   

7. Write a function to return the index of the smallest item in a given list.
8. Use top-down design to write a program that reads in a DNA strand comprised of the letters/nucleotides 'A', 'T', 'G', and 'C' and then displays frequency counts for each of the letters. Your program should define and use at least two functions in addition to main(). Here's what an example run might look like:

   Enter DNA strand: GATTACA
   
   Nucleotide frequencies:
   A: 3
   C: 1
   G: 1
   T: 2
   

   If this was really a quiz, we'd probably say that you can assume the user gives you valid input, but for extra practice try putting in code to validate the input:

   Enter DNA strand: $$$$
   DNA must be comprised of A, C, G, and T
   Enter DNA strand: GATTACa
   DNA must be comprised of A, C, G, and T
   Enter DNA strand: GATTACA
   
   Nucleotide frequencies:
   A: 3
   C: 1
   G: 1
   T: 2