161 Midterm 1

Card Set Information

Author:
CMortty
ID:
293870
Filename:
161 Midterm 1
Updated:
2015-01-26 23:49:59
Tags:
161
Folders:

Description:
161 Midterm 1
Show Answers:

Home > Flashcards > Print Preview

The flashcards below were created by user CMortty on FreezingBlue Flashcards. What would you like to do?


  1. Sequential Search of an Ordered List
    • WC: 
    • AVG (x in list): 
    • AVG (x not in list): 
    • AVG (50% in 50% not): 
  2. Binary Search of an Ordered List
    • WC: 
    • AVG (x in list):  where 
    • AVG (x not in list):  where 
  3. Interpolation Search
    • Works well with data in order and uniformly distributed
    • Like looking in a phone book
    • WC: 
    • AVG: 
  4. Straight Insertion Sort
    • WC C: 
    • AVG C: 
    • M: 
    • T: 
    • S: 
  5. Binary Insertion Sort
    • WC C: 
    • AVG C: 
    • M: 
    • T: 
    • S: 
  6. Heapsort
    • C: 
    • M: 
    • S: 
    • T: 
  7. Bucket Sort
    • T: 
    • S: 
  8. Lexiographic (Radix) Sort
    • T: 
    • S: 
    • M is the base
  9. Shellsort
    • Uses tables to sort
    • Video showed decreasing tables over time to the items next to each other
    • Use straight insertion to sort each table
  10. Definition of Upper Bound (O notation)
    if  constants  and  s.t. 
  11. Definition of Lower Bound ( notation)
    if  constants  and  s.t. 
  12. Definition of Tight Bound ( notation)
    •  is  if  is both  and  
    • if  exists and is equal to some number c > 0 then 
  13. Definition of Domination (o notation)
     if 

What would you like to do?

Home > Flashcards > Print Preview