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.