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