Lectures and Topics
Assignments (A3 is posted, monitor FAQs)
andriyp [at] cse [dot] yorku [dot] ca
This course introduces fundamental data structures and the underlying widely-used algorithms. They include various implementations of arrays, lists, maps, hash tables, priority queues, search trees, graphs, and their algorithmic applications. We express these structures in an Object-Oriented Programming (OOP) context and use the Java Programming Language for this purpose.
The course discusses a number of key concepts in OOP. Abstraction and encapsulation are two such concepts. Abstraction at the data level gives rise to expressing a data structure as an Abstract Data Type (ADT). The concept of data abstraction (ADT) predates OOP. OOP adopts a higher level of abstraction, namely objects. A data structure, like any other abstracted entity, is encapsulated as an object with state (data) and behaviour (functionality). An object is an instance of its class type. This facilitates a higher level of procedural abstraction: hierarchical inheritance & polymorphism. Parameters in method calls can now be objects of any specified type, possessing not only pure data, but also specified functional behaviour.
An ADT's client is any (user application) class that accesses and invokes the ADT. Through encapsulation, a client can directly access only externally visible members of the ADT, namely its Application Programming Interface (API), and is oblivious to the internal details, hence to any particular implementation, of the ADT. The interaction between the client and the ADT implementation is through this API which acts as a contract between them. This contract is expressed by public & protected class member signatures, pre/post conditions, and invariants. Implementing an API means implementing the corresponding ADT that respects the API contract. An important benefit is code flexibility: the ADT implementation can be changed and improved over time without changing its API, and hence, without breaking any client code.
The relationship between this course and your previous courses is as follows:
- EECS 1020: students are clients who use a given API (reading API specs & creating client programs that use them).
- EECS 1030: students are asked to implement a given API.
- EECS 2011: students are asked to design & build a correct & efficient implementation of an ADT to be used by its clientele.
By the end of the course, students will be familiar with the more prevalent data structure patterns, and will be able to design and implement variations on these patterns, and then use them as clients to solve a broad range of real-world problems.
General prerequisites; LE/EECS1030 3.00 or LE/EECS2030 3.00; LE/EECS1028 3.00 or SC/MATH1028 3.00 or LE/EECS1019 3.00 or SC/MATH1019 3.00
"Data Structures and Algorithms in Java", M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Wiley, 2014, 6th Edition.
3 hours of lectures per week.
Evaluation (this may change during the first two weeks of the course)
Students may view their grades using the
system. All grades distributed via ePost are unoffical and are subject to
review by the Department of Computer Science and Engineering.
A student's final grade will be expressed as a letter grade.
for further details on the University's grading schemes.
Students are expected to understand and follow the guidelines for
academic honesty described in this document.
Counselling and Disability Services (CDS)
Students requiring accommodation for the written midterm or exam should
follow the normal procedure for accommodated alternative tests and exams.