CS 315: Algorithms & Data Structures: Lecture Notes


Copyright © 2011 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

a* 252

abstract syntax tree 105, 181

acyclic 231

adjacency list 235

adjacency matrix 236

adjacent 235

alist 74, 165

amortize 25

arc 231

array 78

array performance 221

assoc 74, 165

association list 74, 165

associative 261

ast 105, 181

avl tree 150

b tree 152

backtrack 131

bag 182

balanced tree 149

base case 37, 38

big o 11

bijective 258

binary heap 206

binary tree 149

binding 165

binding list 165

boolean matrix 236

boxed integer 28

branching factor 131

bucket 197

cache 200, 220

cambridge polish 143

cartesian product 231

child 103

circular queue 92

circularly linked list 58

clustering 190

collection 94, 182

collision 196

commutative 261

comparator 214

comparison 214

complete 206

complexity 11

critical path 240

cycle 231

dag 233

dense 234

depth-first search 131

deque 100

design pattern 39, 125

destructive 50

dfs 131

digraph 233

dijkstra algorithm 243

directed 233

directed acyclic graph 233

divide and conquer 66

divide-and-conquer 223

domain 183, 258

doubly linked list 58

edge 231

efficiency 11

emit 272

equal 169

euclidean distance 267

exclusive or 192

extendible hashing 201

external sort 213

fair 90

fifo 90

filter 96

functional program 260

garbage 29

geometric series 203

grammar 88

graph 231

greedy 243

half-adder 192

hash function 189

hash with buckets 197

hashing 189

hashset 182

heapsort 217, 227

heuristic 250

heuristic function 252

hill climbing 251

immutable 29

in-place 216

infinite loop 37

infix 143

injective 258

inorder 143

insertion sort 215, 227

interior node 103

internal sort 213

intersection 54

introsort 227

introspective sort 227

inversion 216

isomorphism 262

language translation 179

leaf 103

lifo 75

linear probing 196

link 32, 103, 231

linked list 32

load factor 196

local maximum 251

map 183

mapcar 263

mapping 258, 263

mapreduce 268

match 176, 177

matching 174

member 53

memoization 202

memory hierarchy 220

memory locality 219, 220

merge 59

merge sort 218

minimum spanning tree 246

nested tree recursion 172

node 231

null dereference 75

object 28

on-line 216

one-to-one 258

onto 258

ontology 110

optimization 179

order 12

pagerank 277

parse tree 106

parsing 181

partition 223

path 231

pattern matching 174

pattern-pair 178

percolate 208

performance 11

pert chart 240

pivot 223

pointer 28

polish 143

pop 75

postfix 143

predicate 53

prims algorithm 247

priority queue 204

push 75

quadtree 155, 155

queue 90

quicksort 223

radix sort 228

random access 25, 78

randomization 203

range 183, 258

record 28

recursion 37

recursive case 38

red-black tree 149

reduce 266

reference 28

reference type 28

rehash 196, 199

relaxation 277

root 103

routing 242

row-major order 222

runtime stack 81

search 131

self balancing tree 149

sentinel 76

separate chaining 197

set 53, 182

set difference 57

shadow 82

shortest path 242

side effect 76

side-effect 260

simple path 231

simulation 262

sorting 213

sparse 161, 234, 235

splay tree 149

stable 216

stack 75

stack frame 81

state 131

structure sharing 50

substitution 166

surjective 258

symbol table 202

symmetric 236

syntax 88

tail recursive 42

taxonomy 109

topological sort 238

transform 178, 181

transformation 179

tree 103

tree recursion 125

tree rotation 151

treeset 182

undirected 233

union 57

unparsing 181

vertex 231

well-founded ordering 37

xml 89

xor 192


CS 315