CISC 3130
Data Structures
Midterm Topics
The Structure of the Exam
- You are only responsible for topics and material in the lecture notes and the CodeLab exercises / labs.
- The labs are a great way for you to prepare yourself for the exam.
- The following topics will only be covered in the multiple choice questions; they are indicated in the lecture notes by topic on a grey background with the word 'Sidebar' at the top:
- Nested/Inner Classes
- Memory Management Issues in Java
- The material covered in the sidebar has to do with the why's, how's and gotcha's of memory management and in particular array resizing. You ARE responsible for
the handling of resizing in the context of container classes, i.e., the
checkCapacity
method and its integration
into the container class.
- Capacity-specifying constructors
- Autoboxing
- Down and upcasting
- The exam may contain some or all of the following: reading and writing code, answering questions about containers, and multiple choice questions
- I've posted a set of Sample Questions together with this topic list on the Class Calendar
- There will be 30-40 points (15-20 questions) of multiple choice questions taken directly from multiple choice questions in CodeLab
- Much of the coding will be directyl related to the lectures and labs, but you will probably be asked to code methods and/or classes you have not encountered in either
(but of course related to the exam topics).
The Exam Covers Lectures 1-6 and the corresponding Labs.
- Most of the coding will come from material covered in class and the labs
- I may ask you to code some simple tasks using a container, e.g, empty a queue of its elements, or print/search a stack leaving it intact afterwards.
Detailed Topics List
These are meant to list the primary topics; the notes themselves are the final say on whether something may be on the exam (subject to them not being in one of the
Sidebars). If you think something major is missing here, please let me know. Again, if it's in the Lecture Notes or Labs, it may appear on the exam.
Basic Concepts (Lecture 1)
- Basic container concepts: size, capacity, empty, full, underlying (implementing) container, underflow, overflow
- arrays, heterogeneous containers, homogeneous containers
- logical vs physical aspects of a container, interface (abstraction) vs implementation
- Abstract Data Type (interface) vs Data Structure (implementation)
More Robust Containers (Lecture 2)
- exception handling
- You should understand where and what sort of exceptions arise when working and implementing containers.
- memory (capacity) management
- you should be able to write the basic code to 'resize' an array
- generic containers
Interfaces and Implementations (Lecture 3)
- Behavior vs Internal Representation
- Changes of Representation
- Programming to the Interface
- Demo Apps: Interface-specific vs Implementation-Specific
- You should be able to code an interface-specific demo and have implementation-specific demo app
send it the implementation-specific container via dependency injection
- Abstract Data Types (ADT) vs Data Structures
- Interface vs Implementation in the Context of Vector/Set and the JCF
Algorithmic Analysis (Lecture 4)
- Complexity of an Algorithm
- Big O notation and the commonly used orders
- Amortized Time
The Classical Containers (Lecture 5)
- The classic containers: sequences and associatives; list/sequence, stack FIFO queue, deque, bag/associative, set, map (Lecture 2)
- Their API's (i.e., the set of public methods provided to users of each container), behavior, simple usage
- Simple usage (along the lines of the demos)
- For each of the containers you should be able to populate, empty, and check for membership (when appropriate)
- Introduction to the containers of JCF
Building Containers (Lecture 6)
- Independent, composition, inheritance based implementations