EECS 2011: Fundamentals of Data Structures (Summer 2017)

Summer 2017

EECS Department

Home

Course Syllabus

Lectures and Topics

Assignments (A3 is posted, monitor FAQs)

Additional Resources

Course Syllabus

Instructor

Instructor	Section	Contact
Andriy Pavlovych	A	LAS 2008 andriyp [at] cse [dot] yorku [dot] ca

Description

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.

Outcomes

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.

Prerequisites

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

Textbook

"Data Structures and Algorithms in Java", M. T. Goodrich, R. Tamassia, M. H. Goldwasser, Wiley, 2014, 6th Edition.

Format

3 hours of lectures per week.

Evaluation (this may change during the first two weeks of the course)

Assignments:	25%
Midterm Test:	30%
Final Exam:	45%

Students may view their grades using the ePost 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.

Click here for further details on the University's grading schemes.

Academic Honesty

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.