CS 315: Algorithms & Data Structures: Lecture Notes

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 Netscape or 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. Finding Big O: Log-log Graph

18. Log-log Example

19. Computation Model

20. Big O from Code

21. Beware the Bermuda Triangle

22. Big O for Arrays

23. Average Case vs. Worst Case

24. Familiarity with Big O

25. Pointer / Reference

26. Boxed Number

27. Linked List

28. Constructing a Linked List

29. Access to Parts of a List

30. Iterative Processing of List

31. Iterative List Design Pattern

32. Recursion

33. Designing Recursive Functions

34. Design Pattern for Recursive Functions

35. Recursive Processing of List

36. Recursive List Design Pattern

37. Tail Recursive Processing of List

38. Tail Recursive List Design Pattern

39. Constructive Linked List: Reverse

40. Append

41. Destructive Linked List Functions

42. Nconc

43. Nreverse

44. Set as Linked List

45. Intersection

46. Union and Set Difference

47. Circularly Linked List

48. Merge

49. Constructive Merge

50. Destructive Merge Function

51. Java Destructive Merge Function

52. Divide and Conquer

53. Dividing a List

54. Sorting by Merge

55. Tracing Sort and Merge

56. Divide and Conquer Design Pattern

57. Intersection by Merge

58. Remember to Merge

59. Association List

60. Stack using Linked List

61. Sentinel Node

62. Other Uses of Linked Lists

63. Arrays

64. Stack using Array

65. Uses of Stacks

66. Recursion and Runtime Stack

67. Recursive Function Execution

68. Recursive Execution ...

69. Recursive Length Function Execution

70. Balancing Parentheses

71. Balance Test Using Stack

72. Linked List Stack

73. Tree Traversal and Stack

74. XML

75. Queues

76. Two Pointer Queue using Linked List

77. Circular Queue using Array

78. Circular Queue Code

79. Java Collections API

80. Java Collections Iteration

81. Filter Pattern

82. Using Library Packages

83. Java List Interface

84. ArrayList

85. LinkedList

86. ListIterator

87. Comparing ArrayList and LinkedList

88. Trees

89. Arithmetic Expressions as Trees

90. Computer Programs as Trees

91. English Sentences as Trees

92. File Systems as Trees

93. Phylogenetic Trees

94. Taxonomies as Trees

95. Ontologies as Trees

96. Organizations as Trees

97. Nerves

98. Representations of Trees

99. Binary Tree

100. First-Child / Next-Sibling Tree

101. First-Child / Next-Sibling Example

102. Linked List Tree

103. Implicit Tree

104. Ordered Binary Tree

105. Binary Tree Search

106. Binary Search of Array

107. Binary Tree Array Search

108. Binary Array Search Example

109. Binary Tree Recursion

110. Design Pattern: Binary Tree Recursion

111. Design Pattern: Binary Tree Recursion

112. Searching Directories for a File

113. Searching Directories Example

114. Searching Directories Example ...

115. Depth First Search

116. Depth First Search Order

117. Robot Mouse in Maze

118. Robot Mouse Program

119. Robot Mouse Example

120. Tracing the Robot Mouse

121. Tracing the Robot Mouse ...

122. Tree Traversal

123. Preorder

124. Preorder Example

125. Inorder

126. Inorder Printing of Binary Tree

127. Flattening Binary Tree

128. Tracing Flattening Binary Tree

129. Postorder

130. Balanced Binary Trees

131. AVL Tree

132. Tree Rotation

133. B-Tree

134. B-Tree Implementation

135. Advantages of B-Trees

136. Be Extreme!

137. Sparse Arrays

138. Copy Tree and Substitute

139. Binding Lists

140. Multiple Substitutions

141. Instantiating Design Patterns

142. Tree Equality

143. Tracing Equal

144. Pattern Matching

145. Pattern Matching

146. Transformation by Patterns

147. Transformation Patterns

148. Program Transformation using Lisp

149. Programs and Trees

150. {\tt Set} API in Java

151. {\tt Map} API in Java

152. Iteration over a {\tt Map}

153. Array as a {\tt Map}

154. Key of a {\tt Map}

155. Hashing

156. Hash Function

157. Exclusive OR

158. Hash Function for Strings

159. Collisions

160. Hashing with Buckets

161. Hashing with Buckets: Code

162. Rehashing

163. Hash Tables in Java

164. Extendible Hashing

165. Uses of Hashing

166. Randomization

167. Priority Queue

168. Priority Queue with Binary Tree

169. Binary Heap

170. Mapping to Array

171. Insertion into Heap

172. Removal from Heap

173. Uses of Priority Queues

174. {\tt PriorityQueue} in Java

175. Sorting

176. Comparison in Java

177. Insertion Sort

178. Insertion Sort Performance

179. Heapsort

180. Merge Sort

181. Merge Sort Performance

182. Quicksort

183. Quicksort Code

184. Quicksort Performance

185. Radix Sort

186. Radix Sort Example

187. Sorting in Java Library

188. Graphs

189. Examples of Graphs

190. Directed Acyclic Graph

191. Graph Representations

192. Adjacency List

193. Adjacency Matrix

194. Shortest Path Problem

195. Dijkstra's Algorithm

196. Dijkstra's Algorithm

197. Mapping

198. Implementation of Mapping

199. Mapping in Lisp

200. Reduce in Lisp

201. Combining Map and Reduce

202. MapReduce and Massive Data

203. Simplified MapReduce

204. Mapreduce in Lisp

205. MapReduce Example

CS 375