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.

Index

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. {\tt ==} 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. Comparison in Java
71. Comparator in Java
72. Complex Comparator
73. Divide and Conquer
74. Dividing a List
75. Sorting by Merge
76. Tracing Sort and Merge
77. On Not Dropping the Ball
78. Divide and Conquer Design Pattern
79. Intersection by Merge
80. Merge Technique
81. Sort, then Merge
82. Association List
83. Stack using Linked List
84. Sentinel Node
85. Other Uses of Linked Lists
86. Arrays
87. Stack using Array
88. Uses of Stacks
89. Recursion and Runtime Stack
90. Recursive Function Execution
91. Recursive Execution ...
92. Recursive Length Function Execution
93. Balancing Parentheses
94. Balance Test Using Stack
95. Linked List Stack
96. Tree Traversal and Stack
97. XML
98. Stack in Plain Code
99. Queues
100. Two Pointer Queue using Linked List
101. Circular Queue using Array
102. Circular Queue Code
103. Java Collection API
104. Java Collections Iteration
105. Filter Pattern
106. Using Library Packages
107. Java List Interface
108. ArrayList
109. LinkedList
110. ListIterator
111. Comparing ArrayList and LinkedList
112. Trees
113. Arithmetic Expressions as Trees
114. Computer Programs as Trees
115. English Sentences as Trees
116. File Systems as Trees
117. Phylogenetic Trees
118. Taxonomies as Trees
119. Ontologies as Trees
120. Organizations as Trees
121. Nerves
122. Representations of Trees
123. Binary Tree
124. First-Child / Next-Sibling Tree
125. First-Child / Next-Sibling Example
126. Linked List Tree
127. Implicit Tree
128. Binary Search Tree (BST)
129. Binary Tree Search
130. Binary Search of Array
131. Binary Tree Array Search
132. Binary Array Search Example
133. Binary Tree Recursion
134. Binary Tree Recursion
135. Design Pattern: Binary Tree Recursion
136. Binary Tree Recursion Pattern in Java
137. Design Pattern: Binary Tree Recursion
138. Searching Directories for a File
139. Findpath Example
140. Findpath Representation
141. Java Version of Findpath
142. Lisp Version of Findpath
143. Searching Directories Example
144. Searching Directories Example ...
145. Big O for Trees
146. Depth First Search
147. Depth First Search Order
148. Robot Mouse in Maze
149. Robot Mouse in Java
150. Robot Mouse Program
151. Robot Mouse Example
152. Tracing the Robot Mouse
153. Tracing the Robot Mouse ...
154. Tree Traversal
155. Preorder
156. Preorder Example
157. Preorder Example in Java
158. Inorder
159. Inorder Printing of Binary Tree
160. Flattening Binary Tree
161. Tracing Flattening Binary Tree
162. Flattening Binary Tree in Java
163. Postorder
164. Balanced Binary Trees
165. AVL Tree
166. Tree Rotation
167. B-Tree
168. B-Tree Implementation
169. Advantages of B-Trees
170. Quadtree
171. Image Quadtree
172. Intersection of Quadtrees
173. Aggregate Data in Quadtrees
174. Uses of Quadtrees
175. Be Extreme!
176. Sparse Arrays
177. Solving Equations
178. Solving an Equation by Search
179. Examples: Base Cases
180. Recursive Cases: Operators
181. Recursive Tree Search
182. Big O and Termination
185. Solving a Set of Equations by Search
186. Solving Physics Story Problems
187. Pattern Matching Overview
188. Copy Tree and Substitute
189. Copy Tree and Substitute in Java
190. Binding Lists
191. Multiple Substitutions
192. Sublis in Java
193. Instantiating Design Patterns
194. Tree Equality
195. Tree Equality in Java
196. Tracing Equal
197. Design Pattern: Nested Tree Recursion
198. Tracing Nested Tree Recursion
199. Pattern Matching
200. Specifications of Match
201. Match Function
202. Match Function in Java
203. Transformation by Patterns
204. Transformation Patterns
205. Program Transformation using Lisp
206. Programs and Trees
207. Set API in Java
208. Map API in Java
209. Iteration over a Map
210. Array as a Map
211. Avoid Repeated Code
212. Initializing Array
213. Key of a Map
214. Hashing
215. Hash Function
216. Java .hashCode()
217. Exclusive OR
218. Uses of Exclusive OR
219. Hash Function for Strings
220. Hash Function for Application Types
221. Collisions
222. Hashing with Buckets
223. Hashing with Buckets: Code
224. Rehashing
225. Hash Tables in Java
226. Extendible Hashing
227. Uses of Hashing
228. Randomization
229. Priority Queue
230. Priority Queue with Array or Binary Tree
231. Binary Heap
232. Mapping to Array
233. Insertion into Heap
234. Removal from Heap
235. Uses of Priority Queues
236. PriorityQueue in Java
237. Example Discrete Event Simulation
238. Sorting
239. Insertion Sort
240. Insertion Sort Performance
241. Heapsort
242. Merge Sort
243. Merge Sort Performance
244. Memory Hierarchy and Locality
245. Does Array Index Order Matter?
246. Array Storage and Indexing
247. Quicksort
248. Quicksort Code
249. Partitioning
250. Quicksort Example
251. Quicksort Performance
252. Radix Sort
253. Radix Sort Example
254. Sorting in Java Library
255. Graphs
256. Examples of Graphs
257. Directed Acyclic Graph
258. Graph Representations
259. Adjacency List
260. Adjacency Matrix
261. Implicit Graphs
262. Topological Sort
263. Uses of Topological Sort
264. PERT Chart
265. PERT Chart: Calculating Times
266. Shortest Path Problem
267. Dijkstra's Algorithm
268. Dijkstra's Algorithm
269. Dijkstra's Algorithm Example
270. Minimum Spanning Tree
271. Prim's Algorithm
272. Prim's Algorithm
273. Prim's Algorithm Example
274. Directed Search
275. Hill Climbing
276. Heuristic Search: A*
277. A* Algorithm
278. Ordered Search for Route Finding
279. Effect of Heuristic Function
280. Heuristic Search Handles Local Maxima
281. A* Algorithm Example
282. Graph Search Algorithm Summary
283. Microcontrollers
284. Arduino Programming
285. Resources
286. Mapping
287. Implementation of Mapping
288. Functional Programming
289. Associative and Commutative
290. Computation as Simulation
291. Mapping in Lisp
292. Mapcan
293. Input Filtering and Mapping
294. Reduce in Lisp
295. Combining Map and Reduce
296. MapReduce and Massive Data
297. Distributed Programming is Hard!
298. What MapReduce Does for Us
299. Map Sort Reduce
300. Simplified MapReduce
301. Mapreduce in Lisp
302. Simple MapReduce Example
303. MapReduce Example
304. Hamburger Example
305. How MapReduce Works
306. Map Worker
307. Buffering
308. Load Balancing
309. Reduce Worker
310. PageRank
311. PageRank Example
312. Running PageRank Example
313. Advanced Performance
314. Performance Techniques in MapReduce
315. Algorithm Failure
316. Atomic Commit


CS 314