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