CS 314: Study Guide for Midterm Exam
Date: Tuesday, October 24, 2017, 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 |