This course will:
• introduce two fundamental programming concepts: abstract data types and recursion;
• examine and apply these concepts within the context of an object-oriented approach to programming;
• introduce techniques for reasoning about the efficiency of algorithms and data structures;
• study foundational approaches to organizing data and computations.
Upon successful completion of the course, students will have:
• an understanding of how to use a modern object-oriented programming language to define and manipulate lists, stacks, queues, trees and tables of data;
• an appreciation of why it is important to use abstraction and encapsulation in the design of programs;
• the ability to recognize when a particular choice of data structure is appropriate or ill-advised by reasoning about its efficiency in relation to a problem domain;
• the ability to uncover and reason about repetitive aspects of a computing problem, and to develop appropriate recursive or iterative solutions;
• the ability to understand the specification of a program and its implementation as separate, but related design problems.
The course will cover the following topics:
• A review of programming in Java
• The design, definition and manipulation of simple data objects
• The implementation of lists, including both sequential (linked) and random access (array) variations
• The implementation of stacks, queues, binary trees, and hash tables; with applications
• An introduction to polymorphism: class hierarchies, interfaces, and generic types
• Problem decomposition using recursion and divide-and-conquer strategies
• Techniques for describing the time and space requirements of data structures and their operations
• The efficiency of common searching and sorting approaches