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