This course presents the fundamental data structures that are commonly used and that are the basis of other more advanced data structures and algorithms. The material covers: the classical data structures, the use of abstraction, API specification, basic search and sort algorithms, and asymptotic analysis. Also some graph representation, manipulation and algorithms are presented. Students must also demonstrate practical ability to apply the theory in building working Java classes that implement a given APIs given in the form of Java interfaces. The course reinforces programming techniques such as delegation and contracts, encapsulation and API programming, aggregation, inheritance, and polymorphism. By the end of the course, the students will be expected to be able to:

• Instantiate a range of standard abstract data types (ADT) as data structures
• Implement these data structures and associated operations and check that they satisfy the properties of the ADT
• Apply best practice software engineering principles in the design of new data structures
• Demonstrate the ability to reason about data structures using contracts, assertions, and invariants
• Analyse the asymptotic run times of standard operations for a broad range of common data structures
• Select the most appropriate data structures for novel applications

• Section A: Mondays, 7:00pm-10:00pm, LSB 105