In this course, students will:

• Document code including precondition/postcondition contracts for functions and invariants for classes.
• Create and recognize appropriate test data for simple problems, including testing boundary conditions and creating/running test cases.
• 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, binary search trees, hash tables, graphs, and at least one balanced search tree.
• Identify the features and applications of common data structures, including records/structs, lists, stacks, queues, trees, graphs, and maps.
• Implement algorithms for standard operations on common data structures and discuss the complexity of the operations.
• Comment on the features of different traversal methods for trees and graphs, including pre-, post-, and in-order traversal of trees.
• Describe the implementation of hash tables, including algorithms for collision avoidance and resolution.
• Describe the principles of recursion and iteration, and implement recursive and iterative solutions for a problem.
• Formulate and implement solutions to problems using fundamental graph algorithms, including depth-first and breadth-first search and a shortest-path algorithm.
• Explain the features of at least one tree balancing algorithm and how tree balancing affects the efficiency of various binary search tree operations.
• Correctly use and manipulate pointer variables to change variables and build dynamic data structures.
• Explain the differences between dynamic and static data structure implementations, and justify the use of static and dynamic implementations in different applications.
• Practice explaining design choices and algorithm features in small-group settings.