Data Types and Structures
UW
About This Course
This course introduces widely used and effective methods of data organization, focusing on data structures, their algorithms, and the performance of these algorithms.
Students learn how the choice of a data structure affects the performance and usability of applications, e.g., in web browsing and searching, computer databases, data analysis, text processing, etc. Specific topics include lists, stacks, queues, sets, maps, priority queues, trees, and graphs, together with general algorithmic techniques, such as sorting, searching, and other transformations on data. Students who successfully complete the course can use these tools to design and develop efficient programs for a wide variety of applications.
Requirements
At the start of the course, students should be able to
- Use and follow mathematical reasoning and notation; in particular, work comfortably with simple predicate logic, functions, and elementary probability.
- Describe basic quadratic sorting algorithms, such as Selection Sort or Insertion Sort.
- Given a simple, well-specified computational task, write a program in a high-level imperative language (e.g., Python, C, or Java) and generate appropriate test cases. Use as appropriate simple types, built-in compound types and control idioms, such as selection, iteration, and recursion. These programs should not require more than a single routine, possibly together with a small number of additional helper routines.
- Define and write programs that work with recursively defined structures, such as binary trees.