CPSC 225 Final Exam Review Information

The final exam will be during the registrar-assigned final exam timeslot in the regular classroom (Gearan 228). Take care of any necessary business before the exam so that you do not need to leave the room during the exam.

The exam will be closed book, but you may have two pages of notes which you will turn in with your exam. Important: "Two pages" means either both sides of one 8.5x11" piece of paper or two one-sided sheets — hardcopies only, you may not use a tablet or laptop or other device to access your notes during the exam. (It's fine to create your notes electronically if you want, just make sure you print them out before class!) In addition, your notes must be personally prepared by you — you may not use generative AI to produce a set of notes, copy another student's notes, or make copies of your own for others. (Creating your own notes is an essential part of the learning process — deciding what to include requires engagement with the material which reinforces understanding and improves long-term retention of the material, provides an opportunity for review in order to identify gaps in your knowledge in time to ask questions before the exam, increases confidence in what you do know, and encourages taking ownership of your own learning.)

The exam will have two parts. The first part, which will be approximately the same length as the midterm exams, is required and will primarily cover new material not on the previous exams. Specific topics are listed below. The second part is optional and will cover material from the first two exams. See the review guides for the midterm exams for specific topics. This is a second chance opportunity for things that you may not have been fully successful with on the midterms. There is no penalty for anything on the second part — your grade won't go down because you skipped a question or answered it incorrectly. It can, however, help your grade if you do better on a topic than you did on one of the midterms.

(Required) Topics

Binary Trees

• tree terminology e.g. root, leaf, internal node, external node, parent, child, sibling, proper binary tree, complete binary tree
• working with trees, including the different types of tree traversals and patterns of access
• binary search trees: what BSTs are; how to carry out insert, remove, find operations

You should be familiar with the idea of the TreeNode class used in class but you don't need to memorize it — you will be provided with a class definition and/or an API for any node types that you are expected to use.

Inheritance and Polymorphism

• terminology e.g. inheritance, polymorphism, superclass/subclasses, extending classes, overriding methods, concrete class, abstract class, interface
• inheritance: what it is, how to declare a subclass, what is inherited and what you need to write in a subclass, how to determine what version of a method is called, what public/private/protected mean in the context of subclasses, why inheritance is useful and when it is appropriate to use
• polymorphism: what it is, how it is used, why it is useful, instanceof
• abstract classes: what they are, what they are useful for, how to write them, when to make something abstract
• interfaces: what they are, what they are useful for, how to write them, how they are different from abstract classes, when to use them
• this and super: what they mean, how they are used, when to use them
• aspects of usage
  • for what types a statement of the form x = y is legal (think in terms of the relationship between the types x and y)
  • how to determine whether obj.func() is legal to write and what version of func() is called at runtime
  • what types (concrete class, abstract class, interface) are valid for declarations (variables, parameters, return types)
  • what types (concrete class, abstract class, interface) are valid for creating objects (with new)

Nested Classes

• terminology and concepts: static nested class, inner class — what these things are, what the difference between them is, why you'd make use of them
• syntax and semantics — defining and using static nested classes and inner classes

Recursion

• terminology: base case, recursive case
• the key ingredients in a recursive algorithm / what makes it work
• when to use recursion instead of loops (and vice versa)
• writing a recursive function given a recursive definition
• working with recursively-defined data structures (like trees)

Questions

Types of questions you might encounter include (but are not limited to):

• defining a term or explaining a concept
• reading and/or tracing code involving binary trees, polymorphism, and/or recursion to explain what happens or find bugs
• writing code or a method to manipulate a binary tree in some way, including handling special cases (use pictures to help you work it out!)
• writing code to search and/or manipulate binary search trees
• translating a description of a class hierarchy into code (similar to lab 9) — identifying what should be a concrete class, abstract class, or interface, where instance variables go, whether a method should be abstract and where the method body goes
• writing a subroutine or method which utilizes polymorphism
• writing or using a static nested or inner class
• writing code to implement a recursive definition or involving a recursively-defined structure (such as trees)

When asked to write code, you will be graded on syntax — while you won't lose points for occasional typo sorts of errors (like a missing semicolon) which would be easily caught by Eclipse, frequent or major mistakes which indicate that you don't know what the correct syntax should be or would get in the way of being able to produce a working program (even with the assistance of Eclipse) will lose points.