Exam 1 information

The first exam will be given on:

• Mon 10/21, for section MY9
• Tue 10/22, for sections TY9 and TY2.

You must take the exam with the section the you are registered for on CUNYfirst, unless you have received special permission from me. There will be different exams for the different sections.

On Mon 10/14, at 3pm, there will be an optional Zoom meeting for Q&A about the exam. There may be an additional optional Q&A session if there is demand for one.

The exam will cover material from the beginning of the course through the topic of dynamic array-based lists.

The exam will be taken on paper. During the exam, you must not use anything except the exam sheets and a pen or pencil — no notes, computer, or calculator. You may not leave the room until you hand in your exam.

Types of questions

1. Write a basic class, like TimeSpan from HW 2.
2. Write equals and hashCode methods for a class, as in TimeSpan in HW 2.
3. Given a class, make the class implement Comparable, as in TimeSpan in HW 2.
4. Given an array or List, write code to sort it by writing a Comparator and passing it to a sort method of the Java library. Example: StudentSorter in HW 2.
5. Writing methods of BoundedList and ArrayBoundedList from HW 4 (partially based on HW 3).
6. Writing generic methods, including with wildcards and the extends and super keywords. Examples here.
7. Given a generic method and a list of potential arguments to the method, indicate which ones are legal and which aren't. Examples here.
8. Writing a method that uses an iterator, e.g. to remove some elements from a collection. Examples here.
9. Given a sorted array, trace the execution of binary search. (The code will not be provided to you.) Examples here.
10. Given an array, trace the execution of the following sorting algorithms: selection sort, bubble sort (the optimized version), insertion sort, merge sort, and quicksort. (The code will not be provided to you.) (For quicksort, always pick the first element of the subarray as the pivot.) Examples here.
11. Given a list of functions representing various running times, order them from best (fastest) to worst (slowest). If two functions are equal using big-Oh notation, indicate that. Example here.
12. Given a piece of code, write the running time as a function of n using big-Oh notation. Examples here.
13. Given code involving Lists, ArrayLists, or Iterators obtained from them, determine what gets printed. Examples here.
14. Given code involving a ArrayList, or an Iterator obtained from one, determine the running time as a function of n (where n is the size of the list) using big-Oh notation. Examples here.

Items to know from the Java Collections Framework

• Know the basic meaning of Iterable, Collection, SequencedCollection, List, and ArrayList, and know which inherits from which.
• Methods of the List<E> interface:
  • int size()
  • boolean isEmpty()
  • void add(int index, E element)
  • boolean add(E e)
  • default void addFirst(E e)
  • default void addLast(E e)
  • E get(int index)
  • default E getFirst()
  • default E getLast()
  • E set(int index, E element)
  • boolean contains(Object o)
  • int indexOf(Object o)
  • int lastIndexOf(Object o)
  • E remove(int index)
  • boolean remove(Object o)
  • default E removeFirst()
  • default E removeLast()
  • void clear()
  • default void sort(Comparator<? super E> c)
  • List<E> subList(int fromIndex, int toIndex)
  • default List<E> reversed()
  • static List<E> of(E... elements)
  • static List<E> copyOf(Collection<? extends E> coll)
  • Iterator<E> iterator()
• Methods of the Iterator<E> interface:
  • boolean hasNext()
  • E next()
  • default void remove()
• Constructors of ArrayList<E>:
  • public ArrayList()
  • public ArrayList(int initialCapacity)
  • public ArrayList(Collection<? extends E> c)
• The following method of the Arrays class:
  • public static <T> List<T> asList(T... a)
• The following method of the Collections class:
  • public static <T> List<T> unmodifiableList(List<? extends T> list)
• The following method of the Comparable<T> interface:
  • int compareTo(T o)
• The following methods of the Comparator<T> interface:
  • int compare(T o1, T o2)
  • default Comparator<T> reversed()
  • static <T extends Comparable<? super T>> Comparator<T> naturalOrder()
  • static <T extends Comparable<? super T>> Comparator<T> reverseOrder()