CS-2852
Study Guide for Exam 2
You may bring a sheet of notes to the exam.
Bring a calculator to the exam.
Study the material according to the objectives below. If
you can address these, you'll be prepared for Exam 2
Material covered / course outcomes since Exam 1:
- Be familiar with the internal structure and algorithms that implement a
Doubly-linked list class.
- Understand the behavioral differences (from a user's
perspective) between a List, a Stack, and a Queue.
- Explain what operations are supported by a (pure) Queue
- Explain the merits of implementing a Queue using a LinkedList vs. an
ArrayList as the underlying structure
- Explain what operations are supported by a (pure) Stack
- Explain the merits of implementing a Stack using a LinkedList vs. an
ArrayList as the underlying structure
- Explain what operations are supported by a List or a Collection that
don't belong in a "pure" Queue.
- Explain what operations are supported by a List or a Collection that
don't belong in a "pure" Stack.
- Derive analytical expressions for worst-time complexity of
arbitrary algorithms, similar to those discussed in recent lectures and the
recent quizzes.
- Express the worst-time complexity of an arbitrary algorithm using Big-O
notation
- Compute the time required to execute an algorithm whose Big-O behavior
is known.
- Explain how a binary search algorithm that uses the "splitting rule" achieves O(log2 N) behavior.
- Implement a binary search algorithm.
- Implement a class using generic types.
- Understand the
use of recursion in problem solving
- Write recursive methods to perform specific algorithms
- Identify the behavior of a recursive algorithm as it executes
- Distinguish a Binary Search Tree from a Binary Tree
- Identify the height of a Binary Tree
- Identify the depth of an element of a Binary Tree
- Cloneable classes
- Implement the clone() method for a given
class
- Explain the
difference between deep
and shallow
cloning
- Explain the
function of the clone()
method of the Object class