CS 315: Algorithms & Data Structures: Lecture Notes


Copyright © 2008 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 Netscape or Firefox will.

Contents

abstract syntax tree 90

acyclic 188

adjacency list 192

adjacency matrix 193

adjacent 192

alist 59, 139

arc 188

array 63

assoc 59, 139

association list 59, 139

ast 90

avl tree 131

b tree 133

backtrack 115

bag 150

balanced tree 130

base case 32, 33

big o 11

bijective 197

binary heap 169

binary tree 130

binding 139

binding list 139

boolean matrix 193

boxed integer 25

branching factor 115

bucket 160

cache 163

cambridge polish 125

cartesian product 188

child 88

circular queue 77

circularly linked list 47

clustering 156

collection 79

collision 159

comparison 176

complete 169

complexity 11

cycle 188

dag 190

depth-first search 115

deque 85

design pattern 34, 110

destructive 41

dfs 115

dijkstra algorithm 195

directed 190

directed acyclic graph 190

divide and conquer 52

domain 151, 197

doubly linked list 47

edge 188

efficiency 11

equal 142

euclidean distance 201

exclusive or 157

extendible hashing 164

fair 75

fifo 75

filter 81

garbage 26

grammar 73

graph 188

greedy 195

half-adder 157

hash function 155

hash with buckets 160

hashing 155

immutable 26

in-place 178

infinite loop 32

infix 125

injective 197

inorder 125

insertion sort 177

interior node 88

intersection 45

inversion 178

language translation 147

leaf 88

lifo 60

linear probing 159

link 27, 88, 188

linked list 27

load factor 159

map 151

mapping 197

matching 144

merge 48

node 188

null dereference 60

object 25

on-line 178

one-to-one 197

onto 197

ontology 95

optimization 147

order 12

parse tree 91

partition 182

path 188

pattern matching 144

pattern-pair 146

percolate up 171

performance 11

pivot 182

pointer 25

polish 125

pop 60

postfix 125

priority queue 167

push 60

queue 75

quicksort 182

radix sort 185

random access 22, 63

range 151, 197

record 25

recursion 32

recursive case 33

red-black tree 130

reference 25

reference type 25

rehash 159, 162

root 88

routing 194

runtime stack 66

search 115

self balancing tree 130

sentinel 61

separate chaining 160

set 44, 150

set difference 46

shadow 67

shortest path 194

side effect 61

simple path 188

sparse 137, 192

splay tree 130

stable 178

stack 60

stack frame 66

state 115

structure sharing 41

substitution 140

surjective 197

symbol table 165

symmetric 193

syntax 73

tail recursive 37

taxonomy 94

transform 146

transformation 147

tree 88

tree recursion 110

tree rotation 132

undirected 190

union 46

vertex 188

well-founded ordering 32

xml 74


CS 315