CSPB 2270 - Computer Science 2: Data Structures

• Document code including precondition/postcondition contracts for functions and invariants for classes.
• Determine quadratic, linear and logarithmic running time behavior in simple algorithms, write big-O expressions to describe this behavior, and state the running time behaviors for all basic operations on the data structures presented in the course.
• Create and recognize appropriate test data for simple problems, including testing boundary conditions and creating/running test cases, and writing simple interactive test programs to test any newly implemented class.
• Define basic data types (vector, stack, queue, priority queue, map, list).
• Specify, design and test new classes using the principle of information hiding for the following data structures: array-based collections (including dynamic arrays), list-based collections (singly-linked lists, doubly-linked lists, circular-linked lists), stacks, queues, priority queues, binary search trees, heaps, hash tables, graphs (e.g. for depth-first and breadth-first search), and at least one balanced search tree.
• Be able to describe how basic data types are stored in memory (sequential or distributed), predict what may happen when they exceed those bounds.
• Correctly use and manipulate pointer variables to change variables and build dynamic data structures.
• Determine an appropriate data structure for given problems.
• Follow, explain, trace, and be able to implement standard computer science algorithms using standard data types, such as a stack-based evaluation of arithmetic expressions or a traversal of a graph.
• Recognize situations in which a subtask is nothing more than a simpler version of the larger problem and design recursive solutions for these problems.
• Follow, explain, trace, and be able to implement binary search and a variety of quadratic sorting algorithms including mergesort, quicksort and heapsort.

• Cost of algorithms and Big O notation.
• Memory and pointers, structs, and dynamic memory allocation.
• Linked lists, stacks and queues.
• Trees: Binary trees, binary search trees, tree traversal, recursion.
• Tree balancing: red-black trees.
• Graphs: graph traversal algorithms, depth-first and breadth-first search.
• Hash tables, hash functions, collision resolution algorithms
• Algorithms for sorting, such as insertion sort, bubble sort, quick sort, and merge sort.

Logarithms, Big O, Recursion, Trees, Graphs