Competency Demo #1 - Study Guide

Searching, Sorting, Recursion

Desired Outcomes

• Searching and Sorting
  • Understand the concept of searching data— i.e., discuss the rationale for searching and accurately describe various search techniques (e.g., linear, binary)
  • Understand the concept of sorting data— i.e., discuss the rationale for sorting and accurately describe various sort techniques (e.g., insertion, selection, quick, merge)
• Algorithm Complexity
  • Given a code segment, indicate its general complexity
  • Know the common complexity classes/categories
  • Be able to identify the complexity class/category of a

Competency Demo Items

While not guaranteed to be complete, the following is the types of questions we consider to be essential for demonstrating competency over the material from the first portion of the DSA Course.

1. Understanding/Identifying the complexity of a segment of code.
2. Explaining the basic algorithm or functionality of a given search/sort algorithm.
3. Identifying what a provided search/sort code segment will do.
4. Modifying a provided code segment to do a different but related operation.

Examples of specific questions include:

1. Complexity knowledge
   1. Counting

      Examine the following code segment and indicate its time complexity.

      1. N = int(input("range value?"))
         sum = 0
         for  i in range(N):
             sum = sum + 1
         print(sum)
         

      2. N = int(input("range value?"))
         sum = 0
         for  i in range (N):
             sum = sum + 1
         for  j in range(N, 0, -1):
             sum = sum + 1
         print(sum)
         

      3. N = int(input("range value?"))
         sum = 0
         for  i in range (N):
             sum = sum + 1
             for  j in range(N):
                 sum = sum + 1
         print(sum)
         

      4. N = int(input("range value?"))
         sum = 0
         for  i in range (N):
             for  j in range(N):
                 sum = sum + 1
         print(sum)
         

      5. N = int(input("range value?"))
         sum = 0
         j = 1
         while  j <= N:
             sum = sum + 1
             j = j * 2
         print(sum)
         

      6. N = int(input("range value?"))
         j = N
         sum = 0
         while  j > 0:
             for  k in range(N, 1, -1):
                 sum = sum + 1
             j =  int(j / 2)
         print(sum)
         

      7. N = int(input("range value?::"))
         sum = 0
         for  i in range(N):
             for  j in range(5):
                 sum = sum + 1
         print(sum)
         

      8. N = int(input("range value?::"))
         sum = 0
         for  i in range(N):
             j = 1
             while  j < N:
                 sum = sum + 1
                 j = j * 2
         print(sum)
         

      9. N = int(input("range value?::"))
         sum = 0
         while  sum <= N:
             while  sum <=  N:
                 sum = sum + 1
         print(sum)
         

      10. def factorial( n ):
              if n == 1:
                  return  1 
              else:
                  return n * factorial(n-1)
          

   2. Overall knowledge
      1. Identify the common complexity classes in order from least to greatest
      2. Identify the common complexity classes in order from greatest to least

2. Search and Sort Understanding
   1. Describe how the indicated search/sort works? Also, indicate it's average time complexity.
      1. Linear search
      2. Binary search
      3. Selection sort
      4. Insertion sort
      5. Bubble sort
      6. Quick sort
      7. Merge sort

3. Identify what the following code segment does. Your response should be a one-sentence description.
   1. Iteration

      1. t = 0
         for  i in range(1, len(values)):
             if  values[i] < values[t]:
                 t = i
         print(t)
         

      
      

      2. t = values[0]
         for  i in range(1, len(values)):
             if  values[i] >= t:
                 t = values[i]
         print(t)
         

      
      

      3. t = int(input("value? ::"))
         L = 0
         h = len(values) - 1
         while l < h:
             m = int( (h + L)/2 )
             if values[m] == t:
                 break
             elif t < values[m]:
                 h = m - 1
             else:
                 L = m + 1
         if values[m] == t:
             print( "at " + str(m) )
         else:
             print( "?" )
         

      
      

      4. t = int(input("value? ::"))
         i = 0
         while  i < len(values):
             if  values[i] == t:
                 break
             else:
                 i = i + 1
         if  i < len(values):
             print(i)
         else:
             print("?")
         

      
      

      5. for  s in range( len(values) ):
             l = s
             for  i in range( s, len(values) ):
                 if  values[i] < values[l]:
                     l = i
             temp = values[s]
             values[s] = values[l]
             values[l] = temp
         

      
      

      6. copy = []
         
         copy.append(orig[0])
         for  s in range( 1, len(orig) ):
             t = s
             copy.append(orig[s])
             while t > 0  and orig[s] < copy[t-1]:
                 print(t)
                 copy[t] = copy[t-1]
                 t = t - 1
             copy[t] = orig[s]
         

   2. Recursion

      1. def  myResult(values, t):
             if  len(values) == 0:
                 return  t
             else:
                 if  values[0] < t:
                     return  myResult(values[1: ], values[0])
                 else:
                     return  myResult(values[1: ], t)
         
         # called with  result = myResult( values[1: ], values[0] )
         

      
      

      2. def  myResult(values, t):
             if  len(values) == 0:
                 return  t
             else:
                 if  values[0] > t:
                     return  myResult(values[1: ], values[0])
                 else:
                     return  myResult(values[1: ], t)
         
         # called with  result = myResult( values[1: ], values[0] )
         

      
      

      3. def  myResult(values, t):
             if  len(values) == 0:
                 return  "?"
             else:
                 m = int( len(values) / 2 )
                 if  values[m] == t:
                     return  m
                 else:
                     if  t < values[m]:
                         return  myResult(values[ :m], t)
                     else:
                         return  myResult(values[m+1: ], t)
         
         # called with:
         #    t = int(input("value? :: "))
         #    result = myResult( values, t )
         

      
      

      4. def  myResult(values, t):
             if  len(values) == 0:
                 return  "?"
             else:
                 if  values[0] == t:
                     return  "!"
                 else:
                     return  myResult(values[1: ], t)
         
         # called with:
         #    t = int(input("value? :: "))
         #    result = myResult( values, t )
         



4. Modify the following code so that it:
   1. identifies the largest value in a collection and indicates the position of the last such value in the collection

      t = values[0]
      for  i in range(1, len(values)):
          if  values[i] < t:
              t = values[i]
      print(t)
      

   2. identifies the smallest value in a collection

      t = 0
      for  i in range(1, len(values)):
          if  values[i] > values[t]:
              t = i
      print(t)
      

   3. sorts a collection of values in ascending order

      for  s in range( len(values) ):
          l = s
          for  i in range( s, len(values) ):
              if  values[i] < values[l]:
                  l = i
          temp = values[s]
          values[s] = values[l]
          values[l] = temp