CS-2852
Study Guide for Exam 1

Study the material according to the objectives below. If you can address these, you'll be prepared for Exam 1.

You can prepare and use a single sheet of notes for use during the Exam.

Bring a calculator to the exam.

Course outcomes to date:

• The Java Collections Framework (JCF)
  • Explain the basic behaviors exhibited by a container that implements the Collection interface
  • Explain the additional behaviors exhibited by containers that implement the List interface.
     
• Interfaces and Abstract Classes
  • Explain the concept of an Interface
  • Given a UML class diagram for an interface, write the equivalent Java code.
  • Given the Java code for an interface, draw the equivalent UML class diagram.
  • Explain the concept of an Abstract Class
  • Explain when it makes sense to provide some implementation in an Abstract class, even though the class is not instantiable, and that concrete (normal) classes must still be derived and (fully) implemented.
  • Explain why the JCF uses various Abstract Classes.
  • Be able to demonstrate how to derive a concrete class from an Interface or an Abstract class.
     
• Arrays, array-based lists and linked lists
  • Explain the performance differences between array-based and linked linked lists for various algorithmic operations, such as add(), add(index), contains(), remove(), and get().
  • Explain the situations in which you would choose an array-based list over a linked list, and vice-versa.
  • Given a specific situation describing how a software application would use a container, explain and justify why you would choose an array-based container or a linked list container
  • Draw diagrams that illustrate the layout and referencing of variables, arrays, and objects in memory
     
• Internal structure of the linked list and array-based list data structures.
  • Implement the basic methods, such as add(), get(), contains(), and remove(), of an array-based data structure (including manipulation of arrays)
  • Illustrate the rerouting of next and prev references when elements are added to or deleted from a linked list.
     
• Iterable container classes and nested Iterator-based inner classes
  • Implement the Iterable interface on a specified container class
  • Implement the Iterator interface on a container class's nested inner class.
  • Make use of the "for-each" to iterate containers that implement the Iterable/Iterator interfaces
  • Use the hasNext() and next() methods of the Iterator/Iterable interfaces to iterate through a container using a while or do-while loop
  • Explain why iterating through a linked list is faster than indexing through a linked list
     
• Algorithm Analysis
  • Derive analytical expressions (e.g. f(n) =3n + 2) for time complexity (i.e. number of instructions) of arbitrary algorithms, similar to those discussed in recent lectures and assignments.
  • Express the time complexity of an arbitrary algorithm using Big-O notation
  • Compute the time required to execute an algorithm whose time complexity behavior is known.
     
• Generic classes
  • Given a class and methods that operate on a specific datatype (e.g. double), rewrite the class using Generics such that the class and its methods can accommodate any datatype