Copyright © 2012 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.
1. CS 314: Data Structures
2. Course Topics
3. Introduction
4. eine kleine LispMusik
5. Fibonacci Numbers
6. Fibonacci Functions
7. Testing Fibonacci
8. Rates of Growth
9. Exponential Growth
10. Goals of the Course
11. Big O and Performance
12. Big O
13. Big O: An Upper Bound
14. Rules for Big O
15. Classes of Algorithms
16. Log n Grows Slowly
17. Log n Is Almost the Same as 1
18. Powers of 10: SI Prefixes
19. A Scientist Should Be Careful, Skeptical
20. Finding Big O: Log-log Graph
21. Log-log Example
22. Finding Big O: Semi-Log Graph
23. Big O from Timing Ratio
24. Computation Model
25. Big O from Code
26. Big O of Loops
27. Beware the Bermuda Triangle
28. Big O for Arrays
29. Average Case vs. Worst Case
30. Familiarity with Big O
31. Pointer / Reference
32. Boxed Number
33. References and ==
34. == vs. .equals()
35. Linked List
36. Constructing a Linked List
37. Access to Parts of a List
38. List Access Functions
39. Iterative Processing of List
40. Iterative List Design Pattern
41. Recursion
42. Designing Recursive Functions
43. Design Pattern for Recursive Functions
44. Recursive Processing of List
45. Recursive List Design Pattern
46. Tail Recursive Processing of List
47. Tail Recursive List Design Pattern
48. Constructive Linked List: Reverse
49. Tail Recursive Reverse
50. Tail Recursive Reverse in Java
51. Copying a List
52. Append
53. Iterative Append
54. Destructive Linked List Functions
55. Nconc
56. Nreverse
57. Set as Linked List
58. Intersection
59. Tail-Recursive Intersection
60. Tail-Recursive Intersection in Java
61. Union and Set Difference
62. Circularly Linked List
63. Merge
64. Constructive Merge
65. Tail Recursive Merge
66. Tail Recursive Merge in Java
67. Destructive Merge Function
68. Iterative Destructive Merge
69. Java Iterative Destructive Merge
70. Divide and Conquer
71. Dividing a List
72. Sorting by Merge
73. Tracing Sort and Merge
74. On Not Dropping the Ball
75. Divide and Conquer Design Pattern
76. Intersection by Merge
77. Sort, then Merge
78. Association List
79. Stack using Linked List
80. Sentinel Node
81. Other Uses of Linked Lists
82. Arrays
83. Stack using Array
84. Uses of Stacks
85. Recursion and Runtime Stack
86. Recursive Function Execution
87. Recursive Execution ...
88. Recursive Length Function Execution
89. Balancing Parentheses
90. Balance Test Using Stack
91. Linked List Stack
92. Tree Traversal and Stack
93. XML
94. Queues
95. Two Pointer Queue using Linked List
96. Circular Queue using Array
97. Circular Queue Code
98. Java Collection API
99. Java Collections Iteration
100. Filter Pattern
101. Using Library Packages
102. Java List Interface
103. ArrayList
104. LinkedList
105. ListIterator
106. Comparing ArrayList and LinkedList
107. Trees
108. Arithmetic Expressions as Trees
109. Computer Programs as Trees
110. English Sentences as Trees
111. File Systems as Trees
112. Phylogenetic Trees
113. Taxonomies as Trees
114. Ontologies as Trees
115. Organizations as Trees
116. Nerves
117. Representations of Trees
118. Binary Tree
119. First-Child / Next-Sibling Tree
120. First-Child / Next-Sibling Example
121. Linked List Tree
122. Implicit Tree
123. Binary Search Tree (BST)
124. Binary Tree Search
125. Binary Search of Array
126. Binary Tree Array Search
127. Binary Array Search Example
128. Binary Tree Recursion
129. Binary Tree Recursion
130. Design Pattern: Binary Tree Recursion
131. Binary Tree Recursion Pattern in Java
132. Design Pattern: Binary Tree Recursion
133. Searching Directories for a File
134. Findpath Example
135. Findpath Representation
136. Java Version of Findpath
137. Lisp Version of Findpath
138. Searching Directories Example
139. Searching Directories Example ...
140. Big O for Trees
141. Depth First Search
142. Depth First Search Order
143. Robot Mouse in Maze
144. Robot Mouse in Java
145. Robot Mouse Program
146. Robot Mouse Example
147. Tracing the Robot Mouse
148. Tracing the Robot Mouse ...
149. Tree Traversal
150. Preorder
151. Preorder Example
152. Preorder Example in Java
153. Inorder
154. Inorder Printing of Binary Tree
155. Flattening Binary Tree
156. Tracing Flattening Binary Tree
157. Flattening Binary Tree in Java
158. Postorder
159. Balanced Binary Trees
160. AVL Tree
161. Tree Rotation
162. B-Tree
163. B-Tree Implementation
164. Advantages of B-Trees
165. Quadtree
166. Image Quadtree
167. Intersection of Quadtrees
168. Aggregate Data in Quadtrees
169. Uses of Quadtrees
170. Be Extreme!
171. Sparse Arrays
172. Pattern Matching Overview
173. Copy Tree and Substitute
174. Copy Tree and Substitute in Java
175. Binding Lists
176. Multiple Substitutions
177. Sublis in Java
178. Instantiating Design Patterns
179. Tree Equality
180. Tree Equality in Java
181. Tracing Equal
182. Design Pattern: Nested Tree Recursion
183. Tracing Nested Tree Recursion
184. Pattern Matching
185. Specifications of Match
186. Match Function
187. Match Function in Java
188. Transformation by Patterns
189. Transformation Patterns
190. Program Transformation using Lisp
191. Programs and Trees
192. Set API in Java
193. Map API in Java
194. Iteration over a Map
195. Array as a Map
196. Avoid Repeated Code
197. Initializing Array
198. Key of a Map
199. Hashing
200. Hash Function
201. Java .hashCode()
202. Exclusive OR
203. Uses of Exclusive OR
204. Hash Function for Strings
205. Hash Function for Application Types
206. Collisions
207. Hashing with Buckets
208. Hashing with Buckets: Code
209. Rehashing
210. Hash Tables in Java
211. Extendible Hashing
212. Uses of Hashing
213. Randomization
214. Priority Queue
215. Priority Queue with Array or Binary Tree
216. Binary Heap
217. Mapping to Array
218. Insertion into Heap
219. Removal from Heap
220. Uses of Priority Queues
221. PriorityQueue in Java
222. Example Discrete Event Simulation
223. Sorting
224. Comparison in Java
225. Insertion Sort
226. Insertion Sort Performance
227. Heapsort
228. Merge Sort
229. Merge Sort Performance
230. Memory Hierarchy and Locality
231. Does Array Index Order Matter?
232. Array Storage and Indexing
233. Quicksort
234. Quicksort Code
235. Partitioning
236. Quicksort Example
237. Quicksort Performance
238. Radix Sort
239. Radix Sort Example
240. Sorting in Java Library
241. Graphs
242. Examples of Graphs
243. Directed Acyclic Graph
244. Graph Representations
245. Adjacency List
246. Adjacency Matrix
247. Implicit Graphs
248. Topological Sort
249. Uses of Topological Sort
250. PERT Chart
251. PERT Chart: Calculating Times
252. Shortest Path Problem
253. Dijkstra's Algorithm
254. Dijkstra's Algorithm
255. Dijkstra's Algorithm Example
256. Minimum Spanning Tree
257. Prim's Algorithm
258. Prim's Algorithm
259. Prim's Algorithm Example
260. Directed Search
261. Hill Climbing
262. Heuristic Search: A*
263. A* Algorithm
264. Ordered Search for Route Finding
265. Effect of Heuristic Function
266. Heuristic Search Handles Local Maxima
267. A* Algorithm Example
268. Graph Search Algorithm Summary
269. Mapping
270. Implementation of Mapping
271. Functional Programming
272. Associative and Commutative
273. Computation as Simulation
274. Mapping in Lisp
275. Mapcan
276. Input Filtering and Mapping
277. Reduce in Lisp
278. Combining Map and Reduce
279. MapReduce and Massive Data
280. Distributed Programming is Hard!
281. What MapReduce Does for Us
282. Map Sort Reduce
283. Simplified MapReduce
284. Mapreduce in Lisp
285. Simple MapReduce Example
286. MapReduce Example
287. Hamburger Example
288. PageRank
289. PageRank Example
290. Running PageRank Example
291. Advanced Performance
292. Performance Techniques in MapReduce
293. Buffering
294. Load Balancing
295. Algorithm Failure
296. Atomic Commit