CMPT 255 course outline

At the end of CMPT 225 course, a student will be able to:
1. Software Development:
   • convert specifications into high-level design, apply software engineering and design concepts, and express OO design in UML class diagrams
   • write C++ code
   • encapsulate methods and variables for an ADT into a C++ class
   • develop, compile and test their programs using the standard unix/linux tool set (e.g., make/g++)
   • differentiate between memory declared globally, on the stack, and on the heap
   • implement functions/algorithms that pass pointers as parameters, perform pointer arithmetic and manipulate pointers
   • manage memory in C++, allocate and free arrays and individual elements in heap
   • design and use test cases
2. Abstract Data Types (ADTs):
   • define "abstract data type" and "data structure" and differentiate between the two
   • define the following ADTs in terms of their data and their operations (their public interface): stack, queue, priority queue
   • give examples of real-life applications of the above ADTs
   • define the following data structures, and demonstrate, simulate, and trace operations on them:
     • static array
     • dynamic array
     • circular array
     • linked list (singly/doubly headed, singly/doubly linked, etc...)
     • binary heap
     • [balanced] binary search tree (for example: AVL and B-trees)
     • [chained / open addressed] hash table
     • discuss tradeoffs in designing hash functions and describe collisions
   • given a set of requirements, select the most appropriate data collection ADT class, taking into account its time and space efficiency
   • implement and analyze basic sorting algorithms: insertion sort, selection sort, merge sort, quick sort, heap sort, tree sort, ...
3. Recursion:
   • describe tradeoffs between recursive and iterative solutions to problems
   • write recursive solutions to non-trivial problems, such as binary search tree traversals and recursive sorts
   • write recursive definitions of binary heap and BST
4. Complexity Analysis:
   • analyze the best, worst, and average case running time of various ADT operations implemented by various data structures
   • analyze the best, worst, and average case running time of basic sorting algorithms above
   • describe alternatives for measuring the performance of an algorithm implementation such as empirical measurement of running time, by counting the elementary operations and/or O notation
5. External Storage:
   • perform operations on data that are too large to fit in memory, e.g.:external mergesort, index files and data files