Chapter 0 modules¶
- 0.1. Data Structures and Algorithms
- 0.2. Spotlight: Carl Friedrich Gauss
- 0.3. Spotlight: Francis Bacon
- 0.4. Command Line Basics
- 0.5. Parsing Command Line Parameters In Your Progam
- 0.6. Using Parameters in Eclipse
- 0.7. Installing the Web-CAT Submission Plug-in for Eclipse
- 0.8. Common Debugging Methods
- 0.9. Debugging In Eclipse
- 0.10. Reading Input (from Files or Otherwise)
- 0.11. Random Access Files In Java
- 0.12. JUnit Testing And You
- 0.13. Writing JUnit Tests
- 0.14. Code Coverage In JUnit
- 0.15. Abstract Data Types
- 0.16. Introduction to Object Oriented Programming
- 0.17. The Unified Modeling Language
- 0.18. Software Development Processes
- 0.19. Pointers Chapter Introduction
- 0.20. Basic References Part 1
- 0.21. Basic References Part 2
- 0.22. Syntax of the Lambda Calculus
- 0.23. Local Memory
- 0.24. Heap Memory
- 0.25. Link Nodes
- 0.26. Link Nodes Practice Exercises
- 0.27. Additional Practice Exercises
- 0.28. Chapter Introduction
- 0.29. Sets and Relations
- 0.30. Miscellaneous Notation
- 0.31. Logarithms
- 0.32. Summations
- 0.33. Recurrence Relations
- 0.34. Mathematical Proof Techniques
- 0.35. Estimation
- 0.36. Chapter Summary Questions
- 0.37. Searching in an Array
- 0.38. Chapter Introduction
- 0.39. Problems, Algorithms, and Programs
- 0.40. Comparing Algorithms
- 0.41. Best, Worst, and Average Cases
- 0.42. Faster Computer, or Faster Algorithm?
- 0.43. Asymptotic Analysis and Upper Bounds
- 0.44. Lower Bounds and \(\Theta\) Notation
- 0.45. Analyzing Problems
- 0.46. Common Misunderstandings
- 0.47. Multiple Parameters
- 0.48. Space Bounds
- 0.49. Code Tuning and Empirical Analysis
- 0.50. Algorithm Analysis Summary Exercises
- 0.51. Algorithm Analysis Summary Exercises
- 0.52. Chapter Introduction: Lists
- 0.53. The List ADT
- 0.54. Array-Based List Implementation
- 0.55. Linked Lists
- 0.56. Comparison of List Implementations
- 0.57. Doubly Linked Lists
- 0.58. List Element Implementations
- 0.59. Stacks
- 0.60. Linked Stacks
- 0.61. Freelists
- 0.62. Implementing Recursion
- 0.63. Queues
- 0.64. Linked Queues
- 0.65. Linear Structure Summary Exercises
- 0.66. Introduction
- 0.67. Writing a recursive function
- 0.68. Code Completion Practice Exercises
- 0.68.1. Introduction
- 0.68.2. Recursion Programming Exercise: Largest
- 0.68.3. Recursion Programming Exercise: Multiply
- 0.68.4. Recursion Programming Exercise: GCD
- 0.68.5. Recursion Programming Exercise: log
- 0.68.6. Recursion Programming Exercise: Cummulative Sum
- 0.68.7. Recursion Programming Exercise: Add odd values
- 0.68.8. Recursion Programming Exercise: Sum Of the Digits
- 0.68.9. Recursion Programming Exercise: Count Characters
- 0.69. Writing More Sophisticated Recursive Functions
- 0.70. Harder Code Completion Practice Exercises
- 0.71. Writing Practice Exercises
- 0.72. Tracing Recursive Code
- 0.73. Tracing Practice Exercises
- 0.74. Summary Exercises
- 0.75. Design Patterns
- 0.76. Alternative List ADT Designs
- 0.77. Comparing Records
- 0.78. The Dictionary ADT
- 0.79. Binary Trees Chapter Introduction
- 0.80. Binary Trees
- 0.81. Binary Tree as a Recursive Data Structure
- 0.82. The Full Binary Tree Theorem
- 0.83. Binary Tree Traversals
- 0.84. Implementing Tree Traversals
- 0.85. Information Flow in Recursive Functions
- 0.85.1. Information Flow in Recursive Functions
- 0.85.2. Binary Tree Set Depth Exercise
- 0.85.3. Collect-and-return
- 0.85.4. Binary Tree Check Sum Exercise
- 0.85.5. Binary Tree Leaf Nodes Count Exercise
- 0.85.6. Binary Tree Sum Nodes Exercise
- 0.85.7. Combining Information Flows
- 0.85.8. Binary Tree Check Value Exercise
- 0.85.9. Combination Problems
- 0.85.10. Binary Tree Height Exercise
- 0.85.11. Binary Tree Get Difference Exercise
- 0.85.12. Binary Tree Has Path Sum Exercise
- 0.86. Binary Tree Node Implementations
- 0.87. Composite-based Expression Tree
- 0.88. Binary Tree Space Requirements
- 0.89. Binary Search Trees
- 0.90. Dictionary Implementation Using a BST
- 0.91. Binary Tree Guided Information Flow
- 0.92. Multiple Binary Trees
- 0.93. A Hard Information Flow Problem
- 0.94. Array Implementation for Complete Binary Trees
- 0.95. Heaps and Priority Queues
- 0.96. Huffman Coding Trees
- 0.97. Trees versus Tries
- 0.98. Proof of Optimality for Huffman Coding
- 0.99. Binary Tree Chapter Summary
- 0.100. Chapter Introduction: Sorting
- 0.101. Sorting Terminology and Notation
- 0.102. Insertion Sort
- 0.103. Bubble Sort
- 0.104. Selection Sort
- 0.105. The Cost of Exchange Sorting
- 0.106. Optimizing Sort Algorithms with Code Tuning
- 0.107. Shellsort
- 0.108. Mergesort Concepts
- 0.109. Implementing Mergesort
- 0.110. Quicksort
- 0.111. Heapsort
- 0.112. Binsort
- 0.113. Radix Sort
- 0.114. An Empirical Comparison of Sorting Algorithms
- 0.115. Lower Bounds for Sorting
- 0.116. Sorting Summary Exercises
- 0.117. Chapter Introduction: File Processing
- 0.118. Primary versus Secondary Storage
- 0.119. Disk Drives
- 0.120. Buffer Pools
- 0.121. The Programmer’s View of Files
- 0.122. External Sorting
- 0.123. Introduction
- 0.124. Hash Function Principles
- 0.125. Sample Hash Functions
- 0.126. Open Hashing
- 0.127. Bucket Hashing
- 0.128. Collision Resolution
- 0.129. Improved Collision Resolution
- 0.130. Analysis of Closed Hashing
- 0.131. Deletion
- 0.132. Hashing Chapter Summary Exercises
- 0.133. Chapter Introduction: Memory Management
- 0.134. Dynamic Storage Allocation
- 0.135. Sequential-Fit Methods
- 0.136. First Fit
- 0.137. Circular First Fit
- 0.138. Best Fit
- 0.139. Worst Fit
- 0.140. Sequential Fit Peformance
- 0.141. Other Memory Allocation Methods
- 0.142. Failure Policies and Garbage Collection
- 0.143. Indexing Chapter Introduction
- 0.144. Linear Indexing
- 0.145. ISAM
- 0.146. Tree-based Indexing
- 0.147. 2-3 Trees
- 0.148. B-Trees
- 0.149. Indexing Summary Exercises
- 0.150. General Trees
- 0.151. Union/Find and the Parent Pointer Implementation
- 0.152. Sequential Tree Representations
- 0.153. Graphs Chapter Introduction
- 0.154. Graph Implementations
- 0.155. Graph Traversals
- 0.156. Topological Sort
- 0.157. Shortest-Paths Problems
- 0.158. Minimal Cost Spanning Trees
- 0.159. Kruskal’s Algorithm
- 0.160. All-Pairs Shortest Paths
- 0.161. Spatial Data Structures
- 0.162. The PR Quadtree
- 0.163. KD Trees
- 0.164. The Bintree
- 0.165. Other Spatial Data Structures
- 0.166. Data and Algorithm Analysis
- 0.167. An Introduction to Problem Solving
- 0.168. Semester Overview
- 0.169. Introduction to Analyzing a Problem
- 0.170. Bounds Review
- 0.171. Growth Rates Review
- 0.172. Summation Techniques
- 0.173. Solving Recurrence Relations
- 0.174. Chapter Introduction: Search
- 0.175. Analyzing Search in Unsorted Lists
- 0.176. Search in Sorted Arrays
- 0.177. Self-Organizing Lists
- 0.178. Bit Vectors for Representing Sets
- 0.179. Perfect Hashing
- 0.180. Finding the Maximum Value
- 0.181. Adversarial Lower Bounds Proofs
- 0.182. State Space Lower Bounds Proofs
- 0.183. Finding the \(i\) th Best Element
- 0.184. Optimal Sorting
- 0.185. Number Problems
- 0.186. The Transformation Concept
- 0.187. The Fast Fourier Transform
- 0.188. Introduction to Probabilistic Algorithms
- 0.189. Finding Prime Numbers
- 0.190. Random Numbers
- 0.191. Skip Lists
- 0.192. Balanced Trees
- 0.193. The AVL Tree
- 0.194. The Splay Tree
- 0.195. The Red-Black Tree
- 0.196. The Sparse Matrix
- 0.197. Dynamic Programming
- 0.198. Amortized Analysis
- 0.199. 0/1 Knapsack Problem
- 0.200. Edit Distance
- 0.201. KMP String Search Algorithm
- 0.202. Boyer-Moore String Search Algorithm
- 0.203. Rabin-Karp String Search Algorithm [Draft]
- 0.204. General Tree Implementations
- 0.205. K-ary Tree Implementations
- 0.206. Limits to Computing
- 0.207. Reductions
- 0.208. NP-Completeness
- 0.209. Circuit Satisfiability
- 0.210. Formula Satisfiability
- 0.211. 3-CNF Satisfiability
- 0.212. The Clique Problem
- 0.213. The Independent Set Problem
- 0.214. The Vertex Cover Problem
- 0.215. The Hamiltonian Cycle Problem
- 0.216. The Traveling Salesman Problem
- 0.217. NP-Completeness Proofs
- 0.218. Reduction of Circuit SAT to SAT
- 0.219. Reduction of SAT to 3-SAT
- 0.220. Reduction of 3-SAT to Clique
- 0.221. Reduction of Clique to Independent Set
- 0.222. Reduction of Independent Set to Vertex Cover
- 0.223. Reduction of 3-SAT to Hamiltonian Cycle
- 0.224. Reduction of Hamiltonian Cycle to Traveling Salesman
- 0.225. Coping with NP-Complete Problems
- 0.226. Unsolveable Problems
- 0.227. Turing Machines
- 0.228. Derivations and Parse Trees
- 0.229. Ambiguous Grammars
- 0.230. Enforcing Order of Operations
- 0.231. Parser Generators
- 0.232. Using Parser Generators to Interpret a Language
- 0.233. List Construction and Deconstruction
- 0.234. Developing Basic, Recursive List-processing Functions
- 0.235. Recurring On Lists That Aren’t Flat
- 0.236. Using Helper Functions with Accumulators
- 0.237. Scope, Closures, Higher-order Functions, Static vs. Dynamic Binding
- 0.238. Procedural Abstraction: Map, Curry, and Compose
- 0.239. Procedural Abstraction: The Filtering and Folding (or Reduce) Patterns
- 0.240. Combining Map and Reduce
- 0.241. Continuations and Continuation Passing
- 0.22. Syntax of the Lambda Calculus
- 0.242. Semantics of the Lambda Calculus
- 0.243. Free and Bound Variables
- 0.244. Alpha-Conversion
- 0.245. The Substitution-Based Model of Evaluation
- 0.246. Beta-Reduction
- 0.247. Reduction Strategies
- 0.248. Church Numerals and Booleans
- 0.249. Recursive Functions
- 0.250. Defining SLang 1
- 0.251. Environment-based Model of Evaluation
- 0.252. Let Expressions
- 0.253. Defining SLang 2
- 0.254. Tying The Knot
- 0.255. Parameter-Passing Mechanisms
- 0.256. Lazy Lists
- 0.257. Types in Programming Languages
- 0.257.1. Motivating Examples
- 0.257.2. Type System: Definition
- 0.257.3. Type System: Static Versus Dynamic
- 0.257.4. Type System: Safe Versus Unsafe
- 0.257.5. Type System: Strong Versus Weak
- 0.257.6. Type System: Typed Variables or Values
- 0.257.7. Type System: Explicit Versus Implicit typing
- 0.257.8. The Many Uses of Type Systems
- 0.258. Type Inference
- 0.258.1. Type Environments
- 0.258.2. Typing Rules Expressed as Post Systems
- 0.258.3. Typing in a Scaled-down ML
- 0.258.4. Using Post System Rules to Describe Type Inferencing in ML
- 0.258.5. Parametric Polymorphism in ML
- 0.258.6. Type inferencing in ML
- 0.258.7. Type Inferencing Problem 1
- 0.258.8. Type Inferencing Problem 2
- 0.258.9. Type Inferencing Problem 3
- 0.258.10. Type Inferencing Problem 4
- 0.258.11. Type Inferencing Problem 5
- 0.258.12. Type Inferencing Problem 6
- 0.259. GLOSSARY
- 0.260. Formal Languages
- 0.261. Overview
- 0.262. Major Concepts
- 0.263. Deterministic Finite Acceptors
- 0.264. Non-Deterministic Finite Automata
- 0.265. Minimizing the Number of States in a DFA
- 0.266. Regular Expressions
- 0.267. Regular Grammars
- 0.268. Closure Properties of Regular Grammars
- 0.269. Identifying Non-regular Languages
- 0.270. Properties
- 0.271. Context-Free Languages
- 0.272. Transforming Grammars
- 0.273. Pushdown Automata
- 0.274. PDAs and Context Free Languages
- 0.275. Deterministic Pushdown Automata
- 0.276. Properties of Context-Free Languages
- 0.277. Models of Computation
- 0.227. Turing Machines
- 0.278. Parsing Introduction
- 0.279. LL Parsing
- 0.280. LR Parsing
- 0.281. CYK Parsing
- 0.282. Structure of a Compiler
- 0.283. Recursively Enumerable Languages
- 0.284. Sheet 1
- 0.285. Sheet 2
- 0.286. Sheet 3
- 0.287. Sheet 5
- 0.288. Sheet 6
- 0.289. Sheet 7
- 0.290. Sheet 1
- 0.291. Sheet 2 Practice
- 0.292. Sheet 3 Practice
- 0.293. Sheet 5 Practice
- 0.294. List Iteration
- 0.295. List Iteration Visualizations
- 0.296. Classwork 8
- 0.297. Homework 8