CS 314: Study Guide for Midterm Exam
Date: Tuesday, October 20, 2015, in class.
Reading:
Weiss, Data Structures & Problem Solving Using
Java, Sections 1, 5 - 5.2, 2 - 2.4, 17.1, 7 - 7.3.4, 17.3, 17.4,
11 - 11.1, 6 - 6.6, 16, 18 - 18.4, 19 - 19.1, 19.3.
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: be able to give the
result of a call to these functions, and the ones below.
- length, reverse, append,
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 |
ASCII |
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 |
interpreter |
intersection |
intractable |
Java Virtual Machine |
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 |
Unicode |
union |
virtual machine |
well-founded ordering |
word |
XML |