CS 315: Study Guide for Midterm Exam
Date: Thursday, October 20, 2011, in class.
Reading:
Weiss, Data Structures and Algorithm Analysis in
Java, Chapters 2-4. Class lecture notes.
Material covered in class:
- Big O:
- Meaning of Big O; names of Big O classes (quadratic, etc.)
- Given a function for time vs. n, reduce it to Big O.
- Ranking of Big O: which is better
- Big O for common algorithms
- Estimate Big O for some given code
- log(n) grows slowly
- Estimate Big O from a log-log plot, from time ratios
- Linked List:
- cons, first, rest, setfirst,
setrest: be able to give the result of a call to these functions,
and the ones below.
- length, reverse, append, nconc,
nreverse, member, assoc
- intersection, union, set-difference
- merge, sort
- mapcar
- some, every, subset
- Stack: using linked list, using array. Order in which items come out: LIFO.
- Queue: using linked list, using array. Order in which items come out: FIFO.
- Java Collections:
- LinkedList
- ArrayList
- Iteration over a Collection
- Trees:
- Binary tree
- First-child / next-sibling tree
- Linked list tree
- Implicit tree
- Binary tree search
- Binary search of array
- Depth-first search: order of search, stack space used
- Preorder, inorder, postorder
Vocabulary
abstract data type |
ancestors |
array |
association list |
backtrack |
base case |
Big O |
binary tree |
binary search tree (BST) |
boxed number |
branching factor |
child |
circularly linked list |
circular queue |
class |
cons |
constructive |
depth |
depth-first search |
dereference |
descendants |
design pattern |
destructive |
DFS |
divide and conquer |
doubly linked list |
fair |
FIFO |
filter |
first-child/next-sibling |
garbage |
garbage collection |
gedanken |
goal |
grammar |
immutable |
inorder |
interior node |
intersection |
intractable |
leaf |
LIFO |
linear |
link |
linked list |
merge |
node |
null dereference |
object |
ontology |
operator |
parent |
pointer |
postorder |
preorder |
quadratic |
queue |
random access |
recursion |
recursive case |
reference |
reference type |
root |
runtime stack |
scope |
search |
sentinel |
set difference |
shadow |
side-effect |
sort |
stack frame |
stack space |
state |
structure sharing |
successor |
tail recursive |
taxonomy |
union |
well-founded ordering |
XML |