CS285 -- Detailed Objectives                                                                        Fall 2002

### Upon completion of this course, a student should be able to:

• Understand the meaning of asymptotic time complexity analysis. In particular:
• Describe the value of big-oh notation.
• Describe the limitations of big-oh notation.
• Provide a definition for big-oh notation.
• Describe the differences between the following time complexity notations: big-oh, omega, theta.
• Be able to analyze the time complexity of simple functions with loops and conditionals.
• Be able to analyze the time complexity of simple recursive functions.
• Be able to compare the time complexity of two alternate functions.
• Be able to analyze the time complexity of a program with multiple simple function calls with known time complexity.
• Be able to use induction to prove/disprove the suggested time complexity of a given function.
• Interpret and write templated generic algorithms.
• Interpret and write C++ code using the following STL container classes: vector, list, stack, deque, priority queue, queue, set, and map.
• Understand the underlying organzation of the following data structures: vector, double/singly-linked-list, deque, stack, queue, priority queue, hash table, binary search tree, set, and map.
• Describe and explain the time complexity for inserting, finding, and deleting items to/from the following data structures: vector, list, deque, stack, queue, priority queue, heap, hash table, binary tree, set, and map.
• Compare and contrast the following data structures: vector, double/singly-linked-list, deque, stack, queue, priority queue, binary search tree, set, hash table, and map.
• Describe the differences between the set and multiset data structures.
• Describe the differences between the map and multimap data structures.
• Define the term adaptor class and be able to implement a simple adaptor class, e.g., stack, queue.
• Demonstrate the use of binary tree traversals (inorder, preorder, postorder.
• Define a collision as it relates to hash tables and describe ways of coping with collisions.
• Interpret and develop simple hashing functions.
• Understand and apply recursion in algorithm development.
• Prove algorithm correctness using inductive assertions. © 2001-2002 Dr. Christopher C. Taylor Office: CC-27C Phone: 277-7339 Last Updated: Sat Jun 8 15:48:58 2002 I am responsible for all content posted on these pages; MSOE is welcome to share these opinions but may not want to.