Python Basics
Not a "focus" of the exam per se, but you definitely need to be able to write correct code. We won't be testing things like deep vs shallow copy as we did in midterm 1, for example -- but it will be hard to answer questions if you are not able to read and write python code fluently.
Asymptotic Analysis
Again, not a main focus point, but you will need to understand asymptotic analysis (Big-Oh and friends) to be able to answer questions. For example, we may ask you to implement something to run in $$O(n)$$ (or linear time)
Dynamic Arrays
Again, much of what we've done since midterm 1 builds on the ideas from this topic (e.g., implementations of Stack and Queue) so you will need to be familiar with them.
Recursion
We've been using recursion quite a bit (e.g., with linked lists and binary trees), so you will need to be very comfortable with recursion for the exam.
Abstraction: Interface vs Implementation
You need to be comfortable with the idea that the interface (methods/operations it provides) of an Abstract Data Type are separate from the implementation of that ADT.
There may be multiple ways to implement a given ADT.
The running times of an ADT's operations depends on the implementation.
Stacks
The Stack ADT
The Stack data model (LIFO)
Operations on a stack
Ways to implement a Stack
Dynamic Array Implementation (done in class, as ArrayStack) and the running times of the operations in this implementation
Linked List Implementation, using a Doubly LL (done in lab) and the running times of the operations in this implementation
Queues
The Queue ADT
First-in First-out (FIFO) data model
Operations on a queue
Implementing a Queue with a "circular array"
Understand the concept of circular arrays and how the mod operation helps achieve the "circular" part
Linked Lists
Motivations for Linked Lists as opposed to Dynamic Arrays
The tradeoffs of using linked lists vs arrays
singly vs doubly linked list
The DoublyLinkedList class we wrote in lecture
Running times of the DoublyLinkedList operations
How we can use linked lists (specifically, doubly LLs) to implement data structures such as stacks and queues
Rooted Trees
Definitions of properties in trees
Child, parent, descendant, ancestor
Subtree
Edge, Path
"Level" of a node, height of a tree
Binary Tree, Full binary tree, complete binary tree
Implementing methods for trees. Examples include:
Counting the number of nodes in the tree
Computing the sum of the values in the nodes
Computing the height of a tree
Traversing a tree with recursion (variants of "depth-first" traversal):
Preorder
Inorder
Postorder
Traversing a tree "breadth-first"
Use a Queue!
Recursion, Recursion, Recursion!
Map ADT
Operations of a Map
Key/Value association (the Map data model)
Implementing a Map
With an unsorted array
inefficient: O(n) running time for operations
We implemented this in lecture, as UnsortedArrayMap
Actual (real-world) implementations of the Map ADT don't do this -- it's too inefficient!
With a sorted array
inefficient: find is O(log n) but insert/delete are O(n)
We didn't implement this, but understand the idea of how it would work and why it's still inefficient
Again, this is not done in real-world implementations of Map ADT
With a linked list: inefficient
O(n) running time for operations, for both sorted and unsorted
We didn't implement this, but understand the idea of how it would work and why it's still inefficient
Real world implementations of Map ADT don't do this -- it's too inefficient
With a Binary Search Tree -- more efficient
We are implementing this in lecture now
Will not be tested on the implementation details (for this exam, anyway)
Just know what the "Binary Search Tree" property is
We haven't gone over the running times of the operations for this implementation yet. Won't be tested on Midterm 2.