Chapter 0 modules¶

1. Data Structures and Algorithms
- 1.1. Data Structures and Algorithms
- 1.2. Some Software Engineering Topics
2. Spotlight: Carl Friedrich Gauss
- 2.1. Spotlight: Carl Friedrich Gauss
3. Spotlight: Francis Bacon
- 3.1. Spotlight: Francis Bacon
4. Command Line Basics
- 4.1. What’s A CLI?
5. Parsing Command Line Parameters In Your Program
- 5.1. Parameters In Programming
6. Using Parameters in Eclipse
- 6.1. Using Parameters in Eclipse
7. Installing the Web-CAT Submission Plug-in for Eclipse
- 7.1. Introduction
- 7.2. Installing the Plug-in
- 7.3. Installing student.jar
- 7.4. Installing formatting support
8. Common Debugging Methods
- 8.1. Common Debugging Methods
9. Debugging In Eclipse
- 9.1. Debugging In Eclipse
10. Reading Input (from Files or Otherwise)
- 10.1. The Scanner Class
11. Random Access Files In Java
- 11.1. Understanding File I/O
  - 11.1.1. Using RandomAccessFile Class
12. JUnit Testing And You
- 12.1. Getting Started
13. Writing JUnit Tests
- 13.1. Writing JUnit Tests
14. Code Coverage In JUnit
- 14.1. Code Coverage In JUnit
  - 14.1.1. Using EclEmma
15. Mutation Coverage In JUnit
- 15.1. Mutation Coverage In JUnit
16. Mutation Testing Examples
- 16.1. Types of Mutants
17. Mutation Coverage: FAQ
- 17.1. Frequently Asked Questions
18. Abstract Data Types
- 18.1. Abstract Data Types
19. Introduction to Object Oriented Programming
- 19.1. Introduction to Object Oriented Programming
20. The Unified Modeling Language
- 20.1. The Unified Modeling Language
  - 20.1.1. Static and Dynamic Diagrams
  - 20.1.2. Class Diagrams
21. Software Development Processes
- 21.1. Software Development Processes
22. Pointers Chapter Introduction
23. Basic References Part 1
- 23.1. Pointers and References
  - 23.1.1. What is a Pointer?
  - 23.1.2. What is a Reference?
- 23.2. Data Types in Java
- 23.3. Referencing and Dereferencing
- 23.4. changePointeeDataDirect
- 23.5. The Employee Class
- 23.6. Reference Assignments
- 23.7. circularList1
24. Basic References Part 2
- 24.1. Sharing
- 24.2. Shallow and Deep Copying
  - 24.2.1. What does it mean to copy?
- 24.3. Shallow and Deep Comparing
- 24.4. Bad References
  - 24.4.1. Why Are Bad Reference Bugs So Common?
25. Syntax of the Lambda Calculus
- 25.1. Lambda Calculus
- 25.2. Practice with Lambda Calculus Syntax
- 25.3. More Practice with Lambda Calculus Syntax
26. Local Memory
- 26.1. Local Memory
27. Heap Memory
- 27.1. Heap Memory
28. Link Nodes
- 28.1. Link Nodes
29. Link Nodes Practice Exercises
- 29.1. createList
- 29.2. iterateOverList
- 29.3. changePointeeNext1
- 29.4. addNodeAtHead
30. Additional Practice Exercises
- 30.1. changeHeadPointer2
- 30.2. changeQPointer
- 30.3. changeRPointer
- 30.4. changePointeeDataInDirect
- 30.5. circularList2
- 30.6. circularList3
- 30.7. changePointeeNext2
- 30.8. findValueInList
- 30.9. addNodeAtTail
- 30.10. changeNodesOrder1
- 30.11. changeNodesOrder2
31. Chapter Introduction
32. Sets and Relations
- 32.1. Set Notation
  - 32.1.1. Relations
- 32.2. Equivalence Relations
- 32.3. Partial Orders
33. Miscellaneous Notation
34. Logarithms
- 34.1. Logarithms
35. Summations
- 35.1. Summations
36. Recurrence Relations
- 36.1. Recurrence Relations
37. Mathematical Proof Techniques
- 37.1. Mathematical Proof Techniques
38. Estimation
39. Chapter Summary Questions
- 39.1. Chapter Summary Questions
40. Searching in an Array
- 40.1. Searching in an Array
  - 40.1.1. Sequential Search
  - 40.1.2. Binary Search
41. Chapter Introduction
42. Problems, Algorithms, and Programs
- 42.1. Problems, Algorithms, and Programs
43. Comparing Algorithms
- 43.1. Comparing Algorithms
- 43.2. Growth Rates Ordering Exercise
44. Best, Worst, and Average Cases
- 44.1. Best, Worst, and Average Cases
45. Faster Computer, or Faster Algorithm?
- 45.1. Faster Computer, or Faster Algorithm?
46. Asymptotic Analysis and Upper Bounds
- 46.1. Asymptotic Analysis and Upper Bounds
47. Lower Bounds and \(\Theta\) Notation
- 47.1. Lower Bounds and Theta Notation
48. Calculating Program Running Time
- 48.1. Calculating Program Running Time
- 48.2. Summary Exercise
49. Analyzing Problems
- 49.1. Analyzing Problems
50. Common Misunderstandings
- 50.1. Common Misunderstandings
51. Multiple Parameters
52. Space Bounds
53. Code Tuning and Empirical Analysis
- 53.1. Code Tuning and Empirical Analysis
  - 53.1.1. Empirical Analysis
54. Algorithm Analysis Summary Exercises
- 54.1. Summary Exercise: CS2
55. Algorithm Analysis Summary Exercises
- 55.1. Summary Exercise: CS3
56. Chapter Introduction: Lists
57. The List ADT
- 57.1. The List ADT
  - 57.1.1. Defining the ADT
- 57.2. List ADT Programming Exercise
58. Array-Based List Implementation
- 58.1. Array-Based List Implementation
  - 58.1.1. Insert
  - 58.1.2. Insert Practice Exericse
- 58.2. Append and Remove
  - 58.2.1. Remove Practice Exericise
- 58.3. Array-based List Practice Questions
59. Linked Lists
- 59.1. Linked Lists
- 59.2. Linked List Remove
60. Comparison of List Implementations
- 60.1. Space Comparison
- 60.2. Time Comparison
  - 60.2.1. Practice Questions
61. Doubly Linked Lists
- 61.1. Doubly Linked Lists
62. List Element Implementations
- 62.1. List Element Implementations
63. Stacks
- 63.1. Stack Terminology and Implementation
  - 63.1.1. Array-Based Stacks
- 63.2. Pop
64. Linked Stacks
- 64.1. Linked Stack Implementation
  - 64.1.1. Linked Stack Push
- 64.2. Linked Stack Pop
  - 64.2.1. Comparison of Array-Based and Linked Stacks
65. Freelists
- 65.1. Freelists
66. Implementing Recursion
67. Queues
- 67.1. Queue Terminology and Implementation
- 67.2. Array-based Dequeue Practice
68. Linked Queues
- 68.1. Linked Queues
- 68.2. Linked Dequeue
- 68.3. Comparison of Array-Based and Linked Queues
  - 68.3.1. Stack and Queue Summary Questions
69. Linear Structure Summary Exercises
- 69.1. Practice Questions
- 69.2. Chapter Review Questions
70. Introduction
- 70.1. Introduction
71. Writing a recursive function
- 71.1. Writing a recursive function
72. Code Completion Practice Exercises
- 72.1. Introduction
- 72.2. Recursion Programming Exercise: Largest
- 72.3. Recursion Programming Exercise: Multiply
- 72.4. Recursion Programming Exercise: GCD
- 72.5. Recursion Programming Exercise: log
- 72.6. Recursion Programming Exercise: Cummulative Sum
- 72.7. Recursion Programming Exercise: Add odd values
- 72.8. Recursion Programming Exercise: Sum Of the Digits
- 72.9. Recursion Programming Exercise: Count Characters
73. Writing More Sophisticated Recursive Functions
74. Harder Code Completion Practice Exercises
- 74.1. Recursion Programming Exercise: Minimum of array
- 74.2. Recursion Programming Exercise: Is Reverse
- 74.3. Recursion Programming Exercise: Decimal to Binary
75. Writing Practice Exercises
- 75.1. Recursion Programming Exercise: Cannonballs
- 75.2. Recursion Programming Exercise: Check Palindrome
- 75.3. Recursion Programming Exercise: Subset Sum
- 75.4. Recursion Programming Exercise: Pascal Triangle
76. Tracing Recursive Code
- 76.1. Tracing Recursive Code
  - 76.1.1. A Domino Analogy
  - 76.1.2. Towers of Hanoi
77. Tracing Practice Exercises
- 77.1. Forward Flow Tracing Exercises
- 77.2. Backward Flow Tracing Exercises
- 77.3. Find Error Tracing Exercises
- 77.4. Two Recursive Calls Tracing Exercises
- 77.5. How Many Times Tracing Exercises
- 77.6. Harder Tracing Exercises
78. Summary Exercises
- 78.1. Summary Questions
79. Design Patterns
- 79.1. Design Patterns
80. Alternative List ADT Designs
81. Comparing Records
- 81.1. Comparing Records
82. The Dictionary ADT
- 82.1. The Dictionary ADT
83. Binary Trees Chapter Introduction
84. Binary Trees
- 84.1. Definitions and Properties
- 84.2. Practice Questions
85. Binary Tree as a Recursive Data Structure
- 85.1. Binary Tree as a Recursive Data Structure
86. The Full Binary Tree Theorem
87. Binary Tree Traversals
- 87.1. Binary Tree Traversals
- 87.2. Postorder Traversal Practice
- 87.3. Inorder Traversal Practice
- 87.4. Summary Questions
88. Implementing Tree Traversals
- 88.1. Implementing Tree Traversals
  - 88.1.1. Base Case
  - 88.1.2. The Recursive Call
- 88.2. Binary Tree Increment By One Exercise
89. Information Flow in Recursive Functions
- 89.1. Information Flow in Recursive Functions
  - 89.1.1. Local
  - 89.1.2. Passing Down Information
- 89.2. Binary Tree Set Depth Exercise
- 89.3. Collect-and-return
- 89.4. Binary Tree Check Sum Exercise
- 89.5. Binary Tree Leaf Nodes Count Exercise
- 89.6. Binary Tree Sum Nodes Exercise
- 89.7. Combining Information Flows
- 89.8. Binary Tree Check Value Exercise
- 89.9. Combination Problems
- 89.10. Binary Tree Height Exercise
- 89.11. Binary Tree Get Difference Exercise
- 89.12. Binary Tree Has Path Sum Exercise
90. Binary Tree Node Implementations
- 90.1. Binary Tree Node Implementations
91. Composite-based Expression Tree
- 91.1. Composite-based Expression Tree
92. Binary Tree Space Requirements
- 92.1. Binary Tree Space Requirements
93. Binary Search Trees
- 93.1. Binary Search Tree Definition
  - 93.1.1. BST Search
- 93.2. BST Insert
- 93.3. BST Remove
- 93.4. BST Analysis
94. Dictionary Implementation Using a BST
95. Binary Tree Guided Information Flow
- 95.1. Binary Tree Guided Information Flow
- 95.2. Binary Search Tree Small Count Exercise
96. Multiple Binary Trees
- 96.1. Mirror Image Binary Trees Exercise
- 96.2. Same Binary Tree Exercise
- 96.3. Structurally Identical Binary Trees Exercise
97. A Hard Information Flow Problem
98. Array Implementation for Complete Binary Trees
- 98.1. Array Implementation for Complete Binary Trees
99. Heaps and Priority Queues
- 99.1. Heaps and Priority Queues
- 99.2. Building a Heap
- 99.3. Removing from the heap or updating an object’s priority
- 99.4. Priority Queues
100. Huffman Coding Trees
- 100.1. Huffman Coding Trees
101. Trees versus Tries
- 101.1. Trees versus Tries
102. Proof of Optimality for Huffman Coding
- 102.1. Proof of Optimality for Huffman Coding
103. Binary Tree Chapter Summary
- 103.1. Summary Questions
104. Chapter Introduction: Sorting
105. Sorting Terminology and Notation
- 105.1. Sorting Terminology and Notation
106. Insertion Sort
- 106.1. Insertion Sort
- 106.2. Insertion Sort Analysis
107. Bubble Sort
- 107.1. Bubble Sort
- 107.2. Bubble Sort Analysis
108. Selection Sort
- 108.1. Selection Sort
- 108.2. Selection Sort Analysis
109. The Cost of Exchange Sorting
- 109.1. The Cost of Exchange Sorting
- 109.2. Analysis
110. Optimizing Sort Algorithms with Code Tuning
- 110.1. Code Tuning for Simple Sorting Algorithms
111. Shellsort
- 111.1. Shellsort
- 111.2. Putting It Together
- 111.3. Shellsort Practice Exercise
- 111.4. Optimizing Shellsort
- 111.5. Shellsort Summary Questions
112. Mergesort Concepts
- 112.1. Mergesort Concepts
- 112.2. Mergesort Practice Exercise
113. Implementing Mergesort
- 113.1. Implementing Mergesort
114. Quicksort
- 114.1. Introduction
- 114.2. Partition
- 114.3. Putting It Together
- 114.4. Quicksort Analysis
115. Heapsort
- 115.1. Heapsort
- 115.2. Heapsort Proficiency Practice
- 115.3. Heapsort Analysis
116. Binsort
- 116.1. Binsort
117. Radix Sort
- 117.1. Radix Sort
- 117.2. Array-based Radix Sort
  - 117.2.1. Radix Sort Analysis
118. An Empirical Comparison of Sorting Algorithms
- 118.1. An Empirical Comparison of Sorting Algorithms
119. Lower Bounds for Sorting
- 119.1. Lower Bounds for Sorting
120. Sorting Summary Exercises
- 120.1. Sorting Summary Exercises
121. Chapter Introduction: File Processing
122. Primary versus Secondary Storage
123. Disk Drives
- 123.1. Disk Drives
124. Buffer Pools
- 124.1. Buffer Pools
125. The Programmer’s View of Files
126. External Sorting
- 126.1. External Sorting
- 126.2. Multiway Merging
  - 126.2.1. Empirical Results
  - 126.2.2. Summary
127. Introduction
- 127.1. Introduction
128. Hash Function Principles
- 128.1. Hash Function Principles
129. Sample Hash Functions
- 129.1. Sample Hash Functions
- 129.2. A Simple Hash Function for Strings
- 129.3. String Folding
- 129.4. Hash Function Practice
- 129.5. Hash Function Review Questions
130. Open Hashing
- 130.1. Open Hashing
131. Bucket Hashing
- 131.1. Bucket Hashing
- 131.2. An Alternate Approach
132. Collision Resolution
- 132.1. Collision Resolution
  - 132.1.1. The Problem with Linear Probing
133. Improved Collision Resolution
- 133.1. Linear Probing by Steps
- 133.2. Pseudo-Random Probing
- 133.3. Quadratic Probing
- 133.4. Double Hashing
134. Analysis of Closed Hashing
- 134.1. Analysis of Closed Hashing
135. Deletion
- 135.1. Deletion
- 135.2. Hashing Deletion Summary Questions
136. Hashing Chapter Summary Exercises
- 136.1. Hashing Review
137. Chapter Introduction: Memory Management
138. Dynamic Storage Allocation
- 138.1. Dynamic Storage Allocation
139. Sequential-Fit Methods
- 139.1. Sequential-Fit Methods
140. First Fit
- 140.1. First Fit
141. Circular First Fit
- 141.1. Circular First Fit
142. Best Fit
- 142.1. Best Fit
143. Worst Fit
- 143.1. Worst Fit
144. Sequential Fit Peformance
- 144.1. Sequential Fit Peformance
145. Other Memory Allocation Methods
- 145.1. Other Memory Allocation Methods
  - 145.1.1. Buddy Methods
  - 145.1.2. Other Methods
146. Failure Policies and Garbage Collection
147. Indexing Chapter Introduction
148. Linear Indexing
- 148.1. Linear Indexing
149. ISAM
150. Tree-based Indexing
- 150.1. Tree-based Indexing
151. 2-3 Trees
- 151.1. 2-3 Trees
152. B-Trees
- 152.1. B-Trees
  - 152.1.1. B+ Trees
  - 152.1.2. B-Tree Analysis
153. Indexing Summary Exercises
- 153.1. Indexing Summary
154. General Trees
- 154.1. General Trees
155. Union/Find and the Parent Pointer Implementation
- 155.1. The Union/Find Problem
156. Sequential Tree Representations
- 156.1. Sequential Tree Representations
- 156.2. Alternative Sequential Representation
- 156.3. Bit Vector Representation
- 156.4. General Tree Sequential Representation
157. Graphs Chapter Introduction
- 157.1. Graph Terminology and Implementation
  - 157.1.1. Graph Representations
- 157.2. Graph Terminology Questions
158. Graph Implementations
159. Graph Traversals
- 159.1. Graph Traversals
  - 159.1.1. Depth-First Search
- 159.2. Breadth-First Search
160. Topological Sort
- 160.1. Topological Sort
  - 160.1.1. Depth-first solution
  - 160.1.2. Queue-based Solution
161. Shortest-Paths Problems
- 161.1. Shortest-Paths Problems
  - 161.1.1. Single-Source Shortest Paths
162. Minimal Cost Spanning Trees
- 162.1. Minimal Cost Spanning Trees
  - 162.1.1. Prim’s Algorithm
  - 162.1.2. Prim’s Algorithm Alternative Implementation
163. Kruskal’s Algorithm
- 163.1. Kruskal’s Algorithm
164. All-Pairs Shortest Paths
165. Spatial Data Structures
- 165.1. Spatial Data Structures
  - 165.1.1. Multdimensional Keys
166. The PR Quadtree
- 166.1. The PR Quadtree
167. KD Trees
- 167.1. KD Trees
168. The Bintree
- 168.1. The Bintree
  - 168.1.1. Implementation Concerns
169. Other Spatial Data Structures
170. Data and Algorithm Analysis
- 170.1. Introduction
171. An Introduction to Problem Solving
- 171.1. An Introduction to Problem Solving
172. Semester Overview
- 172.1. Semester Overview
  - 172.1.1. Modeling Algorithm Cost
  - 172.1.2. Big Issues
173. Introduction to Analyzing a Problem
- 173.1. Towers of Hanoi
174. Bounds Review
- 174.1. Bounds Review
  - 174.1.1. Analyzing Problems
  - 174.1.2. Modeling the Inputs
175. Growth Rates Review
- 175.1. Growth Rates Review
  - 175.1.1. Asymptotic Notation
176. Summation Techniques
177. Solving Recurrence Relations
- 177.1. Solving Recurrence Relations
178. Chapter Introduction: Search
179. Analyzing Search in Unsorted Lists
- 179.1. Analyzing Search in Unsorted Lists
  - 179.1.1. Lower Bounds Proofs
180. Search in Sorted Arrays
- 180.1. Analysis
181. Self-Organizing Lists
- 181.1. Introduction
  - 181.1.1. Frequency Count
- 181.2. Move to Front
- 181.3. Transpose
  - 181.3.1. An Example
182. Bit Vectors for Representing Sets
183. Perfect Hashing
- 183.1. Perfect Hashing
184. Finding the Maximum Value
- 184.1. Finding the Maximum Value
185. Adversarial Lower Bounds Proofs
186. State Space Lower Bounds Proofs
187. Finding the \(i\) th Best Element
188. Optimal Sorting
189. Number Problems
- 189.1. Number Problems
190. The Transformation Concept
- 190.1. The Transformation Concept: Integer Multiplication
- 190.2. Polynomial Multiplication
191. The Fast Fourier Transform
- 191.1. The Fast Fourier Transform
192. Introduction to Probabilistic Algorithms
- 192.1. Probabilistic Algorithms
193. Finding Prime Numbers
194. Random Numbers
- 194.1. Random Numbers
195. Skip Lists
- 195.1. Skip Lists
196. Balanced Trees
197. The AVL Tree
198. The Splay Tree
199. The Red-Black Tree
- 199.1. Exercise 1
- 199.2. Exercise 2
200. The Sparse Matrix
201. Dynamic Programming
- 201.1. Dynamic Programming
- 201.2. Computing Fibonacci Numbers
- 201.3. The Knapsack Problem
- 201.4. Chained Matrix Multiplication
202. Amortized Analysis
203. 0/1 Knapsack Problem
- 203.1. 0/1 Knapsack Problem
  - 203.1.1. Exercise 1
- 203.2. Exercise 2
- 203.3. Exercise 3
- 203.4. Exercise 4
204. Edit Distance
- 204.1. Edit Distance
- 204.2. Exercise 1
- 204.3. Exercise 2
205. KMP String Search Algorithm
- 205.1. KMP String Search Algorithm
206. Boyer-Moore String Search Algorithm
- 206.1. Boyer-Moore String Search Algorithm
207. Rabin-Karp String Search Algorithm [Draft]
- 207.1. Rabin-Karp String Search Algorithm [Draft]
208. General Tree Implementations
- 208.1. General Tree Implementations
209. K-ary Tree Implementations
- 209.1. K-ary Tree Implementations
210. Limits to Computing
- 210.1. Limits to Computing
211. Reductions
- 211.1. Reductions
212. NP-Completeness
- 212.1. NP-Completeness
  - 212.1.1. Hard Problems
  - 212.1.2. The Theory of NP-Completeness
213. Circuit Satisfiability
- 213.1. Circuit Satisfiability
214. Formula Satisfiability
- 214.1. Formula Satisfiability
215. 3-CNF Satisfiability
- 215.1. 3-CNF Satisfiability
216. The Clique Problem
- 216.1. The Clique Problem
217. The Independent Set Problem
- 217.1. Independent Set
218. The Vertex Cover Problem
- 218.1. Vertex Cover
219. The Hamiltonian Cycle Problem
- 219.1. Hamiltonian Cycle
220. The Traveling Salesman Problem
- 220.1. Traveling Salesman
221. NP-Completeness Proofs
- 221.1. NP-Completeness Proofs
222. Reduction of Circuit SAT to SAT
- 222.1. Reduction of Circuit SAT to SAT
223. Reduction of SAT to 3-SAT
- 223.1. Reduction of SAT to 3-SAT
224. Reduction of 3-SAT to Clique
- 224.1. Reduction of 3-SAT to Clique
225. Reduction of Clique to Independent Set
- 225.1. Clique to Independent Set
226. Reduction of Independent Set to Vertex Cover
- 226.1. Independent Set to Vertex Cover
227. Reduction of 3-SAT to Hamiltonian Cycle
- 227.1. 3-SAT to Hamiltonian Cycle
228. Reduction of Hamiltonian Cycle to Traveling Salesman
- 228.1. Hamiltonian Cycle to Traveling Salesman
229. Coping with NP-Complete Problems
230. Unsolveable Problems
- 230.1. Unsolveable Problems
231. Turing Machines
- 231.1. Turing Machines
232. Derivations and Parse Trees
- 232.1. Parse Trees
  - 232.1.1. First Sample Grammar
- 232.2. Strings Generated by a Grammar
- 232.3. Characterizing a Language: Example 1
- 232.4. Characterizing a Language: Example 2
233. Ambiguous Grammars
- 233.1. Second Sample Grammar
- 233.2. Ambiguity in Grammars
- 233.3. Ambiguous Grammar - Part 1
- 233.4. Ambiguous Grammar - Part 2
- 233.5. Ambiguous Grammar - Part 3
- 233.6. Discovering Ambiguity
234. Enforcing Order of Operations
- 234.1. Evaluation of Expressions
  - 234.1.1. Third Sample Grammar
- 234.2. Expression Evaluation
- 234.3. Associativity
- 234.4. Precedence and Associativity
- 234.5. Characterizing a Language Given a BNF Grammar
- 234.6. Extended BNF
235. Parser Generators
- 235.1. Jison
- 235.2. More practice with Jison
236. Using Parser Generators to Interpret a Language
- 236.1. Annotating Jison Grammars
237. List Construction and Deconstruction
- 237.1. Constructing Lists with fp.cons
- 237.2. Deconstructing Lists with fp.hd and fp.tl
- 237.3. Practicing List Manipulations with the fp module
- 237.4. fp.isNull, fp.isEq, and fp.isZero
238. Developing Basic, Recursive List-processing Functions
- 238.1. Recursive List Processing Example: sum( list )
- 238.2. Recursive List Processing Example: isMember( num, list )
- 238.3. Recursive List Processing Example: subst( new, old, list )
239. Recurring On Lists That Aren’t Flat
- 239.1. Deep Recursion in FP
- 239.2. Deep Recursion on Binary Search Trees
- 239.3. Practice with Deep Recursion
- 239.4. More Practice with Deep Recursion
240. Using Helper Functions with Accumulators
- 240.1. Using Helpers to Write reverse and split Functions
- 240.2. Using the split Function to Develop a Sorting Function
- 240.3. Additional Practice with the Accumulator Pattern
241. Scope, Closures, Higher-order Functions, Static vs. Dynamic Binding
- 241.1. Scope, Closures, Higher-order Functions
- 241.2. Practice with Higher-order Functions and Anonymous Functions
- 241.3. More Practice with Higher-order Functions and Anonymous Functions
- 241.4. Practice with Static vs. Dynamic Binding Rules
242. Procedural Abstraction: Map, Curry, and Compose
- 242.1. The Mapping Pattern
- 242.2. Function Composition
- 242.3. Currying
- 242.4. More currying
243. Procedural Abstraction: The Filtering and Folding (or Reduce) Patterns
- 243.1. The Filtering Pattern
- 243.2. The Folding/Reduce Pattern
- 243.3. Practice with the Mapping and Reduce Patterns
- 243.4. More Practice with the Reduce Pattern
244. Combining Map and Reduce
- 244.1. The MapReduce Paradigm
245. Continuations and Continuation Passing
- 245.1. Tail recursive functions
- 245.2. Continuation-Passing Style
- 245.3. Continuation-Passing Style Practice Problem (Part 1)
- 245.4. Continuation-Passing Style Practice Problem (Part 2)
- 245.5. Continuation-Passing Style Practice Problem (Part 3)
- 245.6. More CPS Practice
25. Syntax of the Lambda Calculus
- 25.1. Lambda Calculus
- 25.2. Practice with Lambda Calculus Syntax
- 25.3. More Practice with Lambda Calculus Syntax
246. Semantics of the Lambda Calculus
- 246.1. Semantics of the Lambda Calculus
- 246.2. Practice with Lambda Calculus Semantics
247. Free and Bound Variables
- 247.1. Free and Bound Variables
- 247.2. Identifying Free Variables
- 247.3. Identifying Bound Variables
- 247.4. Formal Definition of Free Variables
248. Alpha-Conversion
- 248.1. Alpha-Conversion Rule
- 248.2. Practice with Alpha Conversion
249. The Substitution-Based Model of Evaluation
- 249.1. Substitution Algorithm
- 249.2. Identifying Substitution Subcases of Case 1
- 249.3. Identifying Substitution Subcases of Case 2
- 249.4. Identifying Substitution Case 3
- 249.5. Identifying Substitution Cases and Subcases
- 249.6. Performing the Substitution Algorithm
250. Beta-Reduction
- 250.1. Beta-Redexes
- 250.2. Identifying Beta-Redexes
- 250.3. Beta-Reduction is a Substitution
- 250.4. Some Beta-Reductions Require Alpha-Conversion
- 250.5. Performing Beta-Reductions
251. Reduction Strategies
- 251.1. Applicative Order
- 251.2. Normal Order
- 251.3. Beta-Reduction Order (1)
- 251.4. Beta-Reduction Order (2)
- 251.5. Applicative Order Proficiency Exercise
- 251.6. Normal Order Proficiency Exercise
252. Church Numerals and Booleans
- 252.1. Church Booleans
- 252.2. Encoding If-Then-Else
- 252.3. Encoding OR
- 252.4. Church Numerals
- 252.5. Church Numerals with Addition and Multiplication
253. Recursive Functions
- 253.1. Fixed-points of Functions
- 253.2. The Y Fixed-point Combinator
- 253.3. Using Y to Implement Factorial
- 253.4. Identifying Fixed Point Combinators
254. Defining SLang 1
- 254.1. Syntax of SLang 1
- 254.2. Concrete Syntax of SLang 1
- 254.3. More Practice with the Concrete Syntax of SLang 1
- 254.4. Abstract Syntax of SLang 1
- 254.5. Curry in SLang 1
- 254.6. Semantics of SLang 1
255. Environment-based Model of Evaluation
- 255.1. Environment Data Structure
- 255.2. Determining Values Bound to a Variable
- 255.3. Evaluation of Expression Within an Environment
- 255.4. Determining Denoted Values in SLang 1
256. Let Expressions
- 256.1. Let Blocks
- 256.2. Let Blocks As Syntactic Sugar
- 256.3. Nested Lets
- 256.4. Nested Lets with Closures
257. Defining SLang 2
- 257.1. SLang 2: An Imperative Language
- 257.2. Output of SLang 2 Program
258. Tying The Knot
- 258.1. Implementing Recursion Efficiently
- 258.2. Practice TTK
259. Parameter-Passing Mechanisms
- 259.1. Call By Value vs. Call By Reference
- 259.2. Copy-Restore
- 259.3. Macro Expansion
- 259.4. Call By Name
- 259.5. Comprehensive Review of the Five Methods Studied So Far
260. Lazy Lists
- 260.1. Infinite Sequences
- 260.2. Practice With Infinite Sequences
- 260.3. Practice With Infinite Sequences (2)
- 260.4. Practice With Infinite Sequences (3)
261. Types in Programming Languages
- 261.1. Motivating Examples
- 261.2. Type System: Definition
- 261.3. Type System: Static Versus Dynamic
- 261.4. Type System: Safe Versus Unsafe
- 261.5. Type System: Strong Versus Weak
- 261.6. Type System: Typed Variables or Values
- 261.7. Type System: Explicit Versus Implicit typing
- 261.8. The Many Uses of Type Systems
262. Type Inference
- 262.1. Type Environments
- 262.2. Typing Rules Expressed as Post Systems
- 262.3. Typing in a Scaled-down ML
- 262.4. Using Post System Rules to Describe Type Inferencing in ML
- 262.5. Parametric Polymorphism in ML
- 262.6. Type inferencing in ML
- 262.7. Type Inferencing Problem 1
- 262.8. Type Inferencing Problem 2
- 262.9. Type Inferencing Problem 3
- 262.10. Type Inferencing Problem 4
- 262.11. Type Inferencing Problem 5
- 262.12. Type Inferencing Problem 6
263. GLOSSARY
264. Formal Languages
- 264.1. Introduction
- 264.2. Prerequisites
- 264.3. What we will do
- 264.4. Process
265. Overview
- 265.1. Languages, Grammars, and Machines
- 265.2. Language Hierarchy
- 265.3. Power of Machines
- 265.4. Application: Compilers
  - 265.4.1. Stages of a Compiler
- 265.5. Some Mindbending Ideas
266. Major Concepts
- 266.1. Introduction
- 266.2. Languages
- 266.3. Grammars
- 266.4. Automata
267. Deterministic Finite Acceptors
- 267.1. DFA: Deterministic Finite Acceptor
268. Non-Deterministic Finite Automata
- 268.1. NFA: Non-Deterministic Finite Automata
- 268.2. NFA vs. DFA: Which is more powerful?
269. Minimizing the Number of States in a DFA
- 269.1. Minimizing the Number of States in a DFA
270. Regular Expressions
- 270.1. Regular Expressions
  - 270.1.1. Precedence Rules
  - 270.1.2. Examples of Regular Expressions
- 270.2. Regular Expressions vs. Regular Languages
- 270.3. Converting Regular Languages to Regular Expressions
271. Regular Grammars
- 271.1. Regular Grammars
272. Closure Properties of Regular Grammars
- 272.1. Closure Properties of Regular Grammars
273. Identifying Non-regular Languages
- 273.1. Identifying Non-regular Languages
274. Properties
- 274.1. Introduction
- 274.2. Properties and Proving: Problem 1
- 274.3. Properties and Proving - Problem 2
275. Context-Free Languages
- 275.1. Context-Free Languages
- 275.2. Ambiguity
- 275.3. Eliminating Grammar Ambiguity
- 275.4. Extended BNF
276. Transforming Grammars
- 276.1. Transforming Grammars
277. Pushdown Automata
- 277.1. Pushdown Automata
  - 277.1.1. Example of transitions
  - 277.1.2. Equivalence of Acceptance Definitions
278. PDAs and Context Free Languages
- 278.1. PDAs and Context Free Languages
279. Deterministic Pushdown Automata
- 279.1. Deterministic Pushdown Automata
- 279.2. Grammars for Deterministic Context-free Languages
280. Properties of Context-Free Languages
- 280.1. Properties of Context-Free Languages
  - 280.1.1. (Chap 8.2) Closure Properties of CFLs
281. Models of Computation
- 281.1. Models of Computation
231. Turing Machines
- 231.1. Turing Machines
282. Parsing Introduction
- 282.1. Introduction
283. LL Parsing
- 283.1. LL Parsing
284. LR Parsing
- 284.1. LR Parsing
285. CYK Parsing
- 285.1. CYK Parsing
  - 285.1.1. CYK Parsing Algorithm
  - 285.1.2. Algorithm
286. Structure of a Compiler
- 286.1. What is a compiler?
  - 286.1.1. Translator
- 286.2. Language Processing System
  - 286.2.1. Compiler
- 286.3. Overview of General Compiler
- 286.4. Phases of Compilation
287. Recursively Enumerable Languages
- 287.1. Recursively Enumerable Languages
  - 287.1.1. Enumeration procedure for recursive languages
  - 287.1.2. Enumeration procedure for recursively enumerable languages
288. Intro Exercises
- 288.1. Exercise 1
- 288.2. Exercise 2
- 288.3. Exercise 3
- 288.4. Exercise 4
- 288.5. Exercise 5
- 288.6. Exercise 6
- 288.7. Exercise 7
289. FA Exercises
- 289.1. Exercise 1
- 289.2. Exercise 2
- 289.3. Exercise 3
- 289.4. Exercise 4
290. Regular Language Exercises
- 290.1. Exercise 1
- 290.2. Exercise 2
- 290.3. Exercise 3
- 290.4. Exercise 4
- 290.5. Exercise 5
- 290.6. Exercise 6
291. Sheet 5
- 291.1. Exercise 1
- 291.2. Exercise 2
292. Sheet 6
- 292.1. Exercise 1
- 292.2. Exercise 2
- 292.3. Exercise 3
- 292.4. Exercise 4
293. Sheet 7
- 293.1. Exercise 1
- 293.2. Exercise 2
- 293.3. Exercise 3
- 293.4. Exercise 4
294. Intro Exercise Practice
- 294.1. Exercise 1
- 294.2. Exercise 2
- 294.3. Exercise 3
- 294.4. Exercise 4
- 294.5. Exercise 5
- 294.6. Exercise 6
- 294.7. Exercise 7
295. FA Exercise Practice
- 295.1. Exercise 1
- 295.2. Exercise 2
- 295.3. Exercise 3
- 295.4. Exercise 4
- 295.5. NFA to DFA 1
- 295.6. NFA to DFA 2
- 295.7. Create NFA
296. Regular Language Exercise Practice
- 296.1. Exercise 1
- 296.2. Exercise 2
- 296.3. Exercise 3
- 296.4. Exercise 2
- 296.5. Exercise 3
- 296.6. Exercise 4
297. Sheet 5 Practice
- 297.1. Exercise 1
- 297.2. Exercise 2
298. List Iteration
- 298.1. List Iteration
299. List Iteration Visualizations
- 299.1. List Iteration Visualizations
300. Classwork 8
- 300.1. List Exercise 1
301. Homework 8
- 301.1. List Exercise 2
302. Understanding this Course
- 302.1. Read the Course Syllabus
- 302.2. Who Is This Class For?
- 302.3. Students of Many Experience Levels
- 302.4. Online and Face-to-face Sections
- 302.5. Weekly Schedule
- 302.6. Reading Activities
- 302.7. Labs
- 302.8. Programming Assignments
- 302.9. Programming Language and Environment
- 302.10. Cheating and The Honor Code
- 302.11. Self-Check: Confirm Your Understanding
303. Getting Started
- 303.1. Installing BlueJ
- 303.2. Introducing LightBot
- 303.3. From LightBot to Micro Worlds
- 303.4. Self Check: Micro-Worlds
- 303.5. A Bit More LightBot
- 303.6. Textually Representing Programs
- 303.7. Self-Check: Turning Micro-Worlds into Code
- 303.8. What Does LightBot Say About Programming?
- 303.9. A Programmable LightBot in Java
- 303.10. Syntax Practice 1a
- 303.11. Creating New Objects
- 303.12. Calling Methods on an Object
- 303.13. Putting it All Together
- 303.14. A Word on Making Code Easy to Read
- 303.15. Syntax Practice 1b
- 303.16. Programming Practice 1
- 303.17. Check Your Understanding
304. Inheritance and Polymorphism: Subclasses and Methods
- 304.1. The Jeroos of Santong Island
- 304.2. Your Opinions on Course Grading Policies
- 304.3. Class Hierarchy and Inheritance
- 304.4. Summarizing: What is Inheritance?
- 304.5. Syntax Practice 2a: Jeroo Methods
- 304.6. Problem Solving and Algorithms
- 304.7. Creating and Using Jeroo Methods
- 304.8. What is Polymorphism?
- 304.9. Syntax Practice 2b: Subclass Constructors
- 304.10. Syntax Practice 2c: More Subclass Constructors
- 304.11. Programming Practice 2
- 304.12. Check Your Understanding
305. Conditional and Repeating Actions
- 305.1. Selection
- 305.2. Conditions Using Sensor Methods
- 305.3. An Overview of Conditional Statements
- 305.4. Java’s Syntax for the If-Then-Else Structure
  - 305.4.1. Example (if-then-else structure)
  - 305.4.2. Self-Check
- 305.5. Syntax Practice 3a: If-Then-Else
- 305.6. Creating Optional Statements With If-then
- 305.7. Java’s Syntax for the If-then Structure
  - 305.7.1. Example (if-then structure)
  - 305.7.2. Self-Check
- 305.8. Syntax Practice 3b: If-Then
- 305.9. Java’s Syntax for the Multi-way Selection Structure (a cascaded if)
  - 305.9.1. Example (multi-way selection structure)
  - 305.9.2. Self-Check
- 305.10. Syntax Practice 3c: Multi-way If
- 305.11. Compound Conditions
  - 305.11.1. Examples (compound conditions)
  - 305.11.2. Self-Check
- 305.12. Syntax Practice 3d: Compound Conditions
- 305.13. Repeating Actions
- 305.14. Generic Repetition Structures
- 305.15. Java’s Syntax for the While Loop
  - 305.15.1. Example (pretest while structure)
  - 305.15.2. Self-Check
- 305.16. Syntax Practice 3e: While Loops
- 305.17. Programming Practice 3
- 305.18. Check Your Understanding
306. Software Testing
- 306.1. What Is Software Testing?
- 306.2. Writing Your First Software Test
- 306.3. Check Your Understanding: Software Testing Concepts
- 306.4. More About Methods
- 306.5. Check Your Understanding: Method Signatures
  - 306.5.1. Passing Information using Parameters
  - 306.5.2. Using Multiple Parameters
- 306.6. Check Your Understanding: Methods with Parameters
- 306.7. Good Habits for Conditionals
- 306.8. A Different Type of Complex If-Statement
- 306.9. Short Circuit Evaluation
- 306.10. Check Your Understanding: Logical Equivalence
  - 306.10.1. Relational Operators with Primitive Data Types
- 306.11. Syntax Practice 4a: Compound Conditionals
- 306.12. Syntax Practice 4b: Conditionals and Relational Operators
- 306.13. Programming Practice 4
- 306.14. Module Review
307. Variables, Fields, and Parameters
- 307.1. Variables
- 307.2. Check Your Understanding: Variables
- 307.3. Fields Versus Local Variables
- 307.4. Changing Private Variables: Mutator Methods
  - 307.4.1. A Note on Scope
- 307.5. Check your Understanding: Scope
- 307.6. Accessor Methods
- 307.7. Check Your Understanding: Fields, Getters and Setters
- 307.8. Syntax Practice 5a: Fields and Accessors
- 307.9. The Return Keyword
- 307.10. Check your Understanding: Typed Methods and Return Statements
- 307.11. Syntax Practice 5b: Mutators and Return Statements
- 307.12. Using Fields in Testing
- 307.13. Programming Practice 5a
- 307.14. Programming Practice 5b
308. Pictures and For-each Loops
- 308.1. First, the Basics
- 308.2. For Each Loops
  - 308.2.1. The For-Each Loop Syntax
  - 308.2.2. Using Outside Variables in Loops
- 308.3. Check Your Understanding: For-Each Loops
  - 308.3.1. Methods on Pictures
- 308.4. Check Your Understanding
- 308.5. Syntax Practice 6a: Pixel Loops
- 308.6. Syntax Practice 6b: More For-Each Loops
- 308.7. Programming Practice 6a
- 308.8. Programming Practice 6b
309. Aggregation, Strings and More Loops
- 309.1. Object-Oriented Design: Aggregation, Composition, and Delegation
- 309.2. Strings and Characters
- 309.3. Check Your Understanding: Strings
- 309.4. Counter-controlled Loops
  - 309.4.1. Traversing Strings
- 309.5. Check Your Understanding: Counter Controlled Loops
- 309.6. Tips on Random Numbers
  - 309.6.1. Generating Random Numbers
  - 309.6.2. Testing Random Behaviors
- 309.7. Check Your Understanding: Random Numbers
- 309.8. Method Overriding
  - 309.8.1. Overriding the toString() Method
- 309.9. Check Your Understanding: Method Overriding
- 309.10. Syntax Practice 7a: For Loops and OO Design
- 309.11. Syntax Practice 7b: toString and Returning Values
- 309.12. Programming Practice 7a
- 309.13. Programming Practice 7b
310. Grouping Objects Using Lists and Nested For Loops
- 310.1. Collections of Objects
- 310.2. Interfaces
- 310.3. Check Your Understanding: Interfaces
- 310.4. Syntax Practice 8a: Strings
- 310.5. The List Interface
- 310.6. Generics
- 310.7. ArrayList
  - 310.7.1. Programming with ArrayLists
- 310.8. Check Your Understanding: ArrayLists
- 310.9. Syntax Practice 8b: Lists
- 310.10. Nested For Loops
- 310.11. Check Your Understanding: Nested For Loops
- 310.12. Syntax Practice 8c: Nested Loops
- 310.13. Check Your Understanding
- 310.14. Programming Practice 8a
- 310.15. Programming Practice 8b
311. Lists, Loop Idioms, Generics, and the Null Keyword
- 311.1. Modelling the Contents of a Library
- 311.2. Looping Idioms
- 311.3. Check Your Understanding: Loop Idioms
- 311.4. Syntax Practice 9a: Loop Idioms
- 311.5. Generics Revisited
- 311.6. Check Your Understanding: Generics
- 311.7. Syntax Practice 9b: Generics
- 311.8. The Null Keyword
- 311.9. Diagnosing a Null Pointer Exception
- 311.10. Check Your Understanding: Null
- 311.11. Using BlueJ’s Debugger
- 311.12. Using BlueJ’s Code Pad
- 311.13. Programming Practice 9a: Loop Idioms
- 311.14. Programming Practice 9b: Loops and Generics
312. Arrays
- 312.1. Creating An Array
- 312.2. Accessing Items in Arrays
- 312.3. Setting Items in an Array
- 312.4. Arrays Compared to Lists (or ArrayList)
- 312.5. Putting It All Together
- 312.6. Check Your Understanding: Arrays
- 312.7. Syntax Practice 10a
- 312.8. Iterating Over Arrays
  - 312.8.1. Counter-Controlled Loops Over Arrays
  - 312.8.2. For-Each Loops Over Arrays
- 312.9. Check Your Understanding: Iterating with Arrays
- 312.10. Syntax Practice 10b
- 312.11. Initializing Array Contents
- 312.12. Printing Arrays
- 312.13. Copying Array Variables
- 312.14. Naming Array Variables
- 312.15. Writing Test Assertions Involving Arrays
- 312.16. Applying Arrays in a Problem
- 312.17. Syntax Practice 10c
- 312.18. Check Your Understanding
- 312.19. Programming Practice 10a
- 312.20. Programming Practice 10b
313. Multi-dimensional Arrays
- 313.1. Dimensions in an Array
- 313.2. Check Your Understanding: 2D Arrays
- 313.3. Syntax Practice: 2D Array Basics
- 313.4. Iterating through a 2D Array
- 313.5. Check Your Understanding: Iterating with 2D Arrays
- 313.6. Syntax Practice: Looping Over 2D Arrays
- 313.7. Multi-Dimensional Arrays
  - 313.7.1. Initializing a Multi-Dimensional Array
  - 313.7.2. Jagged (or Ragged) Arrays
- 313.8. Syntax Practice: 3D Arrays
- 313.9. But Can You Have Multi-dimensional Lists?
- 313.10. Integer Division and Modulus
- 313.11. Check Your Understanding: Modulus
- 313.12. Syntax Practice: Modulus
- 313.13. Programming Practice: Multi-dimensional Arrays
- 313.14. Programming Practice: Mod
314. Variable Scoping, Input, and Output
- 314.1. Variable Scoping
- 314.2. Summarizing Scope Concepts
- 314.3. Check Your Understanding: Scope
- 314.4. Syntax Practice: Scoping
- 314.5. Java Input and Output
  - 314.5.1. Basic Input and Output Concepts
- 314.6. Output Using PrintWriters
- 314.7. Check Your Understanding: Output
- 314.8. Input Using Scanners
  - 314.8.1. Opening a Stream for Input
  - 314.8.2. Reading from an Input Stream
- 314.9. A Complete Input Example
- 314.10. Check Your Understanding: Input
- 314.11. A Complete Input/Output Example
- 314.12. Testing I/O-based Operations
- 314.13. Check Your Understanding: Testing
315. Maps and Sets
- 315.1. The Map and Set Interfaces
- 315.2. The Map Interface
  - 315.2.1. Classes that Implement Map
  - 315.2.2. Using a Map
- 315.3. Syntax Practice: Making Maps
- 315.4. Adding and Accessing Pairs in a Map
- 315.5. Syntax Practice: Adding to Maps
- 315.6. Checking for and Removing Pairs in a Map
- 315.7. A Visual Summary of Using Map and HashMap
- 315.8. Syntax Practice: Map Contains and Remove
- 315.9. Looping Over Map Contents
- 315.10. Check Your Understanding: Maps
- 315.11. The Set Interface
  - 315.11.1. Classes that Implement Set
  - 315.11.2. Using a Set
- 315.12. Syntax Practice: Making A Set
- 315.13. Adding Values to a Set
- 315.14. Syntax Practice: Adding to a Set
- 315.15. Checking Values in a Set
- 315.16. Syntax Practice: Set Contains
- 315.17. Removing Values from a Set
- 315.18. Syntax Practice: Set Remove
- 315.19. Looping Over Sets
- 315.20. Check Your Understanding: Sets
- 315.21. Programming Practice: Maps
316. Static, Main, and Exceptions
- 316.1. The Main Method
- 316.2. Check Your Understanding: Main Methods
- 316.3. The Static Keyword
  - 316.3.1. A Common Pitfall
- 316.4. Check Your Understanding: The Static Keyword
- 316.5. Your Opinions on Course Grading Policies
- 316.6. Errors
  - 316.6.1. Compile-Time errors
  - 316.6.2. Run-Time Errors
- 316.7. Throwing Exceptions
- 316.8. Check Your Understanding: Throwing Exceptions
- 316.9. Syntax Practice: Throwing Exceptions
- 316.10. Try/Catch Blocks
  - 316.10.1. Try/Catch/Finally Syntax
- 316.11. Check Your Understanding: Try/Catch Blocks
- 316.12. Syntax Practice: Try-Catch Blocks

TODO List

Index
Search Page

OpenDSA Stand-alone Modules

Table Of Contents

Search the book

Chapter 0 modules¶