CS 314: Data Structures: Lecture Notes


Copyright © by Gordon S. Novak Jr.

Permission is granted for individuals to make copies of these notes for personal use, or for instructors to make copies for classroom use.

Note: Some of these pages use math symbols. Microsoft Internet Explorer will not display the math symbols, but Firefox will.

Contents

== vs. .equals 34

a* 276

abstract syntax tree 114, 206

acyclic 255

adjacency list 259

adjacency matrix 260

adjacent 259

alist 82, 190

amortize 28

api 103

append 52

arc 255

array 86

array performance 245

arraylist 108

assoc 82, 190

association list 82, 190

associative 289

ast 114, 206

atomic 316

avl tree 165

b tree 167

backtrack 146

bag 207

balanced parentheses 93

balanced tree 164

base case 41, 42

big o 11

bijective 286

binary heap 231

binary tree 164

binding 190

binding list 190

boolean matrix 260

boxed integer 31

boxed number 32

branching factor 146

bucket 222

buffer 307

buffering 307

cache 225, 244

cambridge polish 158

car 37

cartesian product 255

cdr 37

child 112

circular linked list 62

circular queue 101

circularly linked list 62

clustering 215

collection 103, 207

collision 221

commutative 289

comparator 70, 71

comparison 70

complete 231

complexity 11

cons 36

constructive 54

critical path 264

cycle 255

dag 257

dense 258

depth-first search 146

deque 109

design pattern 43, 47, 78, 135

destructive 54

dfs 146

digraph 257

dijkstra algorithm 267

directed 257

directed acyclic graph 257

disk access 307

divide and conquer 73, 78

divide-and-conquer 247

domain 208, 286

doubly linked list 62

drop the ball 77

edge 255

efficiency 11

emit 300, 306

equal 194

euclidean distance 295

exclusive or 217

extendible hashing 226

external sort 238

fair 99

fifo 99

filter 105, 293

first 37, 38

functional program 288

functor 71

garbage 32

geometric series 228

grammar 96

graph 255

greedy 267

half-adder 217

hash function 214

hash with buckets 222

hashing 214

hashset 207

heapsort 241, 251

heuristic 274

heuristic function 276

hill climbing 275

i/o buffer 307

immutable 32

in-place 240

infinite loop 41

infix 158

injective 286

inorder 158

insertion sort 239, 251

integer vs. int 32

interior node 112

internal sort 238

intersection 58, 79

introsort 251

introspective sort 251

inversion 240

isomorphism 290

language translation 204

leaf 112

length 39

lifo 83

linear probing 221

link 35, 112, 255

linked list 35, 95

linkedlist 109

list interface 107

list iteration 40

list recursion 44

list tail recursion 46

listiterator 110

load balancing 306, 308

load factor 221

local maximum 275

locality 243, 244, 246

map 208

mapcan 292

mapcar 291

mapping 286, 291

mapreduce 296

mapreduce key 299

master 305

match 201, 202

matching 199

member 57

memoization 227

memory hierarchy 244

memory locality 243, 244, 246

merge 63, 79

merge sort 75, 242

minimum spanning tree 270

nconc 55

nested tree recursion 197

node 255

nreverse 56

null dereference 83

object 31

on-line 240

one-to-one 286

onto 286

ontology 119

optimization 204

order 12

pagerank 310

parentheses 93

parse tree 115

parsing 206

partition 247

path 255

pattern matching 199

pattern-pair 203

percolate 233

performance 11

pert chart 264

pivot 247

pointer 31

pointer equality 34

polish 158

pop 83

postfix 158

predicate 57

prims algorithm 271

priority queue 229

push 83

quadtree 170, 170

queue 99

quicksort 247

radix sort 252

random access 28, 86

randomization 228

range 208, 286

record 31

recursion 41, 41

recursive case 42

red-black tree 164

reduce 294

reference 31

reference type 31

rehash 221, 224

relaxation 310

repeated code 211

rest 37, 38

reverse 48

root 112

routing 266

row-major order 246

runtime stack 89

search 146

self balancing tree 164

sentinel 84

separate chaining 222

set 57, 207

set difference 61

shadow 90

shortest path 266

side effect 84

side-effect 288

simple path 255

simulation 290

sort 75

sorting 238

sparse 176, 258, 259

splay tree 164

stable 240

stack 83, 95

stack frame 89

state 146

structure sharing 52, 54

substitution 191

surjective 286

switch 211

symbol table 227

symmetric 260

syntax 96

table lookup 211

tail recursion 47

tail recursive 46

taxonomy 118

topological sort 262

transform 203, 206

transformation 204

tree 112

tree recursion 135

tree rotation 166

treeset 207

two pointer queue 100

undirected 257

union 61

unparsing 206

vertex 255

well-founded ordering 41

worker 305

xml 97

xor 217


CS 314