Chapter 0 modules¶

0.1. Data Structures and Algorithms
- 0.1.1. Data Structures and Algorithms
- 0.1.2. Some Software Engineering Topics
0.2. Spotlight: Carl Friedrich Gauss
- 0.2.1. Spotlight: Carl Friedrich Gauss
0.3. Spotlight: Francis Bacon
- 0.3.1. Spotlight: Francis Bacon
0.4. Command Line Basics
- 0.4.1. What's A CLI?
0.5. Parsing Command Line Parameters In Your Progam
- 0.5.1. Parameters In Programming
0.6. Using Parameters in Eclipse
- 0.6.1. Using Parameters in Eclipse
0.7. Installing the Web-CAT Submission Plug-in for Eclipse
- 0.7.1. Introduction
- 0.7.2. Installing the Plug-in
  - 0.7.2.1. Un-Installing an Old Plug-in
  - 0.7.2.2. Installing the Plug-in
- 0.7.3. Installing student.jar
0.8. Common Debugging Methods
- 0.8.1. Common Debugging Methods
0.9. Debugging In Eclipse
- 0.9.1. Debugging In Eclipse
0.10. Reading Input (from Files or Otherwise)
- 0.10.1. The Scanner Class
0.11. Random Access Files In Java
- 0.11.1. Understanding File I/O
  - 0.11.1.1. Using RandomAccessFile Class
0.12. JUnit Testing And You
- 0.12.1. Getting Started
0.13. Writing JUnit Tests
- 0.13.1. Writing JUnit Tests
0.14. Code Coverage In JUnit
- 0.14.1. Code Coverage In JUnit
  - 0.14.1.1. Using EclEmma
0.15. Abstract Data Types
- 0.15.1. Abstract Data Types
0.16. Introduction to Object Oriented Programming
- 0.16.1. Introduction to Object Oriented Programming
0.17. The Unified Modeling Language
- 0.17.1. The Unified Modeling Language
  - 0.17.1.1. Static and Dynamic Diagrams
  - 0.17.1.2. Class Diagrams
0.18. Software Development Processes
- 0.18.1. Software Development Processes
0.19. Pointers Chapter Introduction
0.20. Basic References Part 1
- 0.20.1. Pointers and References
  - 0.20.1.1. What is a Pointer?
  - 0.20.1.2. What is a Reference?
- 0.20.2. Data Types in Java
- 0.20.3. Referencing and Dereferencing
- 0.20.4. changePointeeDataDirect
- 0.20.5. The Employee Class
- 0.20.6. Reference Assignments
- 0.20.7. circularList1
0.21. Basic References Part 2
- 0.21.1. Sharing
- 0.21.2. Shallow and Deep Copying
  - 0.21.2.1. What does it mean to copy?
- 0.21.3. Shallow and Deep Comparing
- 0.21.4. Bad References
  - 0.21.4.1. Why Are Bad Reference Bugs So Common?
0.243. Syntax of the Lambda Calculus
- 0.243.1. Lambda Calculus
- 0.243.2. Mastering Lambda Calculus Syntax (1)
- 0.243.3. Mastering Lambda Calculus Syntax (2)
0.23. Local Memory
- 0.23.1. Local Memory
0.24. Heap Memory
- 0.24.1. Heap Memory
0.25. Link Nodes
- 0.25.1. Link Nodes
0.26. Link Nodes Practice Exercises
- 0.26.1. createList
- 0.26.2. iterateOverList
- 0.26.3. changePointeeNext1
- 0.26.4. addNodeAtHead
0.27. Additional Practice Exercises
- 0.27.1. changeHeadPointer2
- 0.27.2. changeQPointer
- 0.27.3. changeRPointer
- 0.27.4. changePointeeDataInDirect
- 0.27.5. circularList2
- 0.27.6. circularList3
- 0.27.7. changePointeeNext2
- 0.27.8. findValueInList
- 0.27.9. addNodeAtTail
- 0.27.10. changeNodesOrder1
- 0.27.11. changeNodesOrder2
0.28. Chapter Introduction
0.29. Sets and Relations
- 0.29.1. Set Notation
  - 0.29.1.1. Relations
- 0.29.2. Equivalence Relations
- 0.29.3. Partial Orders
0.30. Miscellaneous Notation
0.31. Logarithms
- 0.31.1. Logarithms
0.32. Summations
- 0.32.1. Summations
0.33. Recurrence Relations
- 0.33.1. Recurrence Relations
0.34. Mathematical Proof Techniques
- 0.34.1. Mathematical Proof Techniques
0.35. Estimation
0.36. Chapter Summary Questions
- 0.36.1. Chapter Summary Questions
0.37. Searching in an Array
- 0.37.1. Searching in an Array
  - 0.37.1.1. Sequential Search
  - 0.37.1.2. Binary Search
0.38. Chapter Introduction
0.39. Problems, Algorithms, and Programs
- 0.39.1. Problems, Algorithms, and Programs
0.40. Comparing Algorithms
- 0.40.1. Comparing Algorithms
- 0.40.2. Growth Rates Ordering Exercise
0.41. Best, Worst, and Average Cases
- 0.41.1. Best, Worst, and Average Cases
0.42. Faster Computer, or Faster Algorithm?
- 0.42.1. Faster Computer, or Faster Algorithm?
0.43. Asymptotic Analysis and Upper Bounds
- 0.43.1. Asymptotic Analysis and Upper Bounds
0.44. Lower Bounds and \(\Theta\) Notation
- 0.44.1. Lower Bounds and Theta Notation
0.45. Calculating Program Running Time
- 0.45.1. Calculating Program Running Time
- 0.45.2. Summary Exercise
0.46. Analyzing Problems
- 0.46.1. Analyzing Problems
0.47. Common Misunderstandings
- 0.47.1. Common Misunderstandings
0.48. Multiple Parameters
0.49. Space Bounds
0.50. Code Tuning and Empirical Analysis
- 0.50.1. Code Tuning and Empirical Analysis
  - 0.50.1.1. Empirical Analysis
0.51. Algorithm Analysis Summary Exercises
- 0.51.1. Summary Exercise: CS2
0.52. Algorithm Analysis Summary Exercises
- 0.52.1. Summary Exercise: CS3
0.53. Chapter Introduction: Lists
0.54. The List ADT
- 0.54.1. The List ADT
  - 0.54.1.1. Defining the ADT
- 0.54.2. List ADT Programming Exercise
0.55. Array-Based List Implementation
- 0.55.1. Array-Based List Implementation
  - 0.55.1.1. Insert
  - 0.55.1.2. Insert Practice Exericse
- 0.55.2. Append and Remove
  - 0.55.2.1. Remove Practice Exericise
- 0.55.3. Array-based List Practice Questions
0.56. Linked Lists
- 0.56.1. Linked Lists
- 0.56.2. Linked List Remove
0.57. Comparison of List Implementations
- 0.57.1. Space Comparison
- 0.57.2. Time Comparison
  - 0.57.2.1. Practice Questions
0.58. Doubly Linked Lists
- 0.58.1. Doubly Linked Lists
0.59. List Element Implementations
- 0.59.1. List Element Implementations
0.60. Stacks
- 0.60.1. Stack Terminology and Implementation
  - 0.60.1.1. Array-Based Stacks
- 0.60.2. Pop
0.61. Linked Stacks
- 0.61.1. Linked Stack Implementation
  - 0.61.1.1. Linked Stack Push
- 0.61.2. Linked Stack Pop
  - 0.61.2.1. Comparison of Array-Based and Linked Stacks
0.62. Freelists
- 0.62.1. Freelists
0.63. Implementing Recursion
0.64. Queues
- 0.64.1. Queue Terminology and Implementation
- 0.64.2. Array-based Dequeue Practice
0.65. Linked Queues
- 0.65.1. Linked Queues
- 0.65.2. Linked Dequeue
- 0.65.3. Comparison of Array-Based and Linked Queues
  - 0.65.3.1. Stack and Queue Summary Questions
0.66. Linear Structure Summary Exercises
- 0.66.1. Practice Questions
- 0.66.2. Chapter Review Questions
0.67. Introduction
- 0.67.1. Introduction
0.68. Writing a recursive function
- 0.68.1. Writing a recursive function
0.69. Code Completion Practice Exercises
- 0.69.1. Introduction
- 0.69.2. Recursion Programming Exercise: Largest
- 0.69.3. Recursion Programming Exercise: Multiply
- 0.69.4. Recursion Programming Exercise: GCD
- 0.69.5. Recursion Programming Exercise: log
- 0.69.6. Recursion Programming Exercise: Cummulative Sum
- 0.69.7. Recursion Programming Exercise: Add odd positions
- 0.69.8. Recursion Programming Exercise: Sum Of the Digits
- 0.69.9. Recursion Programming Exercise: Count Characters
0.70. Writing More Sophisticated Recursive Functions
0.71. Harder Code Completion Practice Exercises
- 0.71.1. Recursion Programming Exercise: Minimum of array
- 0.71.2. Recursion Programming Exercise: Is Reverse
- 0.71.3. Recursion Programming Exercise: Decimal to Binary
0.72. Writing Practice Exercises
- 0.72.1. Recursion Programming Exercise: Cannonballs
- 0.72.2. Recursion Programming Exercise: Check Palindrome
- 0.72.3. Recursion Programming Exercise: Subset Sum
- 0.72.4. Recursion Programming Exercise: Pascal Triangle
0.73. Tracing Recursive Code
- 0.73.1. Tracing Recursive Code
  - 0.73.1.1. A Domino Analogy
  - 0.73.1.2. Towers of Hanoi
0.74. Tracing Practice Exercises
- 0.74.1. Forward Flow Tracing Exercises
- 0.74.2. Backward Flow Tracing Exercises
- 0.74.3. Find Error Tracing Exercises
- 0.74.4. Two Recursive Calls Tracing Exercises
- 0.74.5. How Many Times Tracing Exercises
- 0.74.6. Harder Tracing Exercises
0.75. Summary Exercises
- 0.75.1. Summary Questions
0.76. Design Patterns
- 0.76.1. Design Patterns
0.77. Alternative List ADT Designs
0.78. Comparing Records
- 0.78.1. Comparing Records
0.79. The Dictionary ADT
- 0.79.1. The Dictionary ADT
0.80. Binary Trees Chapter Introduction
0.81. Binary Trees
- 0.81.1. Definitions and Properties
- 0.81.2. Practice Questions
0.82. Binary Tree as a Recursive Data Structure
- 0.82.1. Binary Tree as a Recursive Data Structure
0.83. The Full Binary Tree Theorem
0.84. Binary Tree Traversals
- 0.84.1. Binary Tree Traversals
- 0.84.2. Postorder Traversal Practice
- 0.84.3. Inorder Traversal Practice
- 0.84.4. Summary Questions
0.85. Implementing Tree Traversals
- 0.85.1. Implementing Tree Traversals
  - 0.85.1.1. Base Case
  - 0.85.1.2. The Recursive Call
- 0.85.2. Binary Tree Increment By One Exercise
0.86. Information Flow in Recursive Functions
- 0.86.1. Information Flow in Recursive Functions
  - 0.86.1.1. Local
  - 0.86.1.2. Passing Down Information
- 0.86.2. Binary Tree Set Depth Exercise
- 0.86.3. Collect-and-return
- 0.86.4. Binary Tree Check Sum Exercise
- 0.86.5. Binary Tree Leaf Nodes Count Exercise
- 0.86.6. Binary Tree Sum Nodes Exercise
- 0.86.7. Combining Information Flows
- 0.86.8. Binary Tree Check Value Exercise
- 0.86.9. Combination Problems
- 0.86.10. Binary Tree Height Exercise
- 0.86.11. Binary Tree Get Difference Exercise
- 0.86.12. Binary Tree Has Path Sum Exercise
0.87. Binary Tree Node Implementations
- 0.87.1. Binary Tree Node Implementations
0.88. Composite-based Expression Tree
- 0.88.1. Composite-based Expression Tree
0.89. Binary Tree Space Requirements
- 0.89.1. Binary Tree Space Requirements
0.90. Binary Search Trees
- 0.90.1. Binary Search Tree Definition
  - 0.90.1.1. BST Search
- 0.90.2. BST Insert
- 0.90.3. BST Remove
- 0.90.4. BST Analysis
0.91. Dictionary Implementation Using a BST
0.92. Binary Tree Guided Information Flow
- 0.92.1. Binary Tree Guided Information Flow
- 0.92.2. Binary Search Tree Small Count Exercise
0.93. Multiple Binary Trees
- 0.93.1. Mirror Image Binary Trees Exercise
- 0.93.2. Same Binary Tree Exercise
- 0.93.3. Structurally Identical Binary Trees Exercise
0.94. A Hard Information Flow Problem
0.95. Array Implementation for Complete Binary Trees
- 0.95.1. Array Implementation for Complete Binary Trees
0.96. Heaps and Priority Queues
- 0.96.1. Heaps and Priority Queues
- 0.96.2. Building a Heap
- 0.96.3. Removing from the heap or updating an object's priority
- 0.96.4. Priority Queues
0.97. Huffman Coding Trees
- 0.97.1. Huffman Coding Trees
0.98. Trees versus Tries
- 0.98.1. Trees versus Tries
0.99. Proof of Optimality for Huffman Coding
- 0.99.1. Proof of Optimality for Huffman Coding
0.100. Binary Tree Chapter Summary
- 0.100.1. Summary Questions
0.101. Chapter Introduction: Sorting
0.102. Sorting Terminology and Notation
- 0.102.1. Sorting Terminology and Notation
0.103. Insertion Sort
- 0.103.1. Insertion Sort
- 0.103.2. Insertion Sort Analysis
0.104. Bubble Sort
- 0.104.1. Bubble Sort
- 0.104.2. Bubble Sort Analysis
0.105. Selection Sort
- 0.105.1. Selection Sort
- 0.105.2. Selection Sort Analysis
0.106. The Cost of Exchange Sorting
- 0.106.1. The Cost of Exchange Sorting
- 0.106.2. Analysis
0.107. Optimizing Sort Algorithms with Code Tuning
- 0.107.1. Code Tuning for Simple Sorting Algorithms
0.108. Shellsort
- 0.108.1. Shellsort
- 0.108.2. Putting It Together
- 0.108.3. Shellsort Practice Exercise
- 0.108.4. Optimizing Shellsort
- 0.108.5. Shellsort Summary Questions
0.109. Mergesort Concepts
- 0.109.1. Mergesort Concepts
- 0.109.2. Mergesort Practice Exercise
0.110. Implementing Mergesort
- 0.110.1. Implementing Mergesort
0.111. Quicksort
- 0.111.1. Introduction
- 0.111.2. Partition
- 0.111.3. Putting It Together
- 0.111.4. Quicksort Analysis
0.112. Heapsort
- 0.112.1. Heapsort
- 0.112.2. Heapsort Proficiency Practice
- 0.112.3. Heapsort Analysis
0.113. Binsort
- 0.113.1. Binsort
0.114. Radix Sort
- 0.114.1. Radix Sort
- 0.114.2. Array-based Radix Sort
  - 0.114.2.1. Radix Sort Analysis
0.115. An Empirical Comparison of Sorting Algorithms
- 0.115.1. An Empirical Comparison of Sorting Algorithms
0.116. Lower Bounds for Sorting
- 0.116.1. Lower Bounds for Sorting
0.117. Sorting Summary Exercises
- 0.117.1. Sorting Summary Exercises
0.118. Chapter Introduction: File Processing
0.119. Primary versus Secondary Storage
0.120. Disk Drives
- 0.120.1. Disk Drives
0.121. Buffer Pools
- 0.121.1. Buffer Pools
0.122. The Programmer's View of Files
0.123. External Sorting
- 0.123.1. External Sorting
- 0.123.2. Multiway Merging
  - 0.123.2.1. Empirical Results
  - 0.123.2.2. Summary
0.124. Introduction
- 0.124.1. Introduction
0.125. Hash Function Principles
- 0.125.1. Hash Function Principles
0.126. Sample Hash Functions
- 0.126.1. Sample Hash Functions
- 0.126.2. A Simple Hash Function for Strings
- 0.126.3. String Folding
- 0.126.4. Hash Function Practice
- 0.126.5. Hash Function Review Questions
0.127. Open Hashing
- 0.127.1. Open Hashing
0.128. Bucket Hashing
- 0.128.1. Bucket Hashing
- 0.128.2. An Alternate Approach
0.129. Collision Resolution
- 0.129.1. Collision Resolution
  - 0.129.1.1. The Problem with Linear Probing
0.130. Improved Collision Resolution
- 0.130.1. Linear Probing by Steps
- 0.130.2. Pseudo-Random Probing
- 0.130.3. Quadratic Probing
- 0.130.4. Double Hashing
0.131. Analysis of Closed Hashing
- 0.131.1. Analysis of Closed Hashing
0.132. Deletion
- 0.132.1. Deletion
- 0.132.2. Hashing Deletion Summary Questions
0.133. Hashing Chapter Summary Exercises
- 0.133.1. Hashing Review
0.134. Chapter Introduction: Memory Management
0.135. Dynamic Storage Allocation
- 0.135.1. Dynamic Storage Allocation
0.136. Sequential-Fit Methods
- 0.136.1. Sequential-Fit Methods
0.137. First Fit
- 0.137.1. First Fit
0.138. Circular First Fit
- 0.138.1. Circular First Fit
0.139. Best Fit
- 0.139.1. Best Fit
0.140. Worst Fit
- 0.140.1. Worst Fit
0.141. Sequential Fit Peformance
- 0.141.1. Sequential Fit Peformance
0.142. Other Memory Allocation Methods
- 0.142.1. Other Memory Allocation Methods
  - 0.142.1.1. Buddy Methods
  - 0.142.1.2. Other Methods
0.143. Failure Policies and Garbage Collection
0.144. Indexing Chapter Introduction
0.145. Linear Indexing
- 0.145.1. Linear Indexing
0.146. ISAM
0.147. Tree-based Indexing
- 0.147.1. Tree-based Indexing
0.148. 2-3 Trees
- 0.148.1. 2-3 Trees
0.149. B-Trees
- 0.149.1. B-Trees
  - 0.149.1.1. B+ Trees
  - 0.149.1.2. B-Tree Analysis
0.150. Indexing Summary Exercises
- 0.150.1. Indexing Summary
0.151. General Trees
- 0.151.1. General Trees
0.152. Union/Find and the Parent Pointer Implementation
- 0.152.1. The Union/Find Problem
0.153. Sequential Tree Representations
- 0.153.1. Sequential Tree Representations
- 0.153.2. Alternative Sequential Representation
- 0.153.3. Bit Vector Representation
- 0.153.4. General Tree Sequential Representation
0.154. Graphs Chapter Introduction
- 0.154.1. Graph Terminology and Implementation
  - 0.154.1.1. Graph Representations
- 0.154.2. Graph Terminology Questions
0.155. Graph Implementations
0.156. Graph Traversals
- 0.156.1. Graph Traversals
  - 0.156.1.1. Depth-First Search
- 0.156.2. Breadth-First Search
0.157. Topological Sort
- 0.157.1. Topological Sort
  - 0.157.1.1. Depth-first solution
  - 0.157.1.2. Queue-based Solution
0.158. Shortest-Paths Problems
- 0.158.1. Shortest-Paths Problems
  - 0.158.1.1. Single-Source Shortest Paths
0.159. Minimal Cost Spanning Trees
- 0.159.1. Minimal Cost Spanning Trees
  - 0.159.1.1. Prim's Algorithm
  - 0.159.1.2. Prim's Algorithm Alternative Implementation
0.160. Kruskal's Algorithm
- 0.160.1. Kruskal's Algorithm
0.161. All-Pairs Shortest Paths
0.162. Spatial Data Structures
- 0.162.1. Spatial Data Structures
  - 0.162.1.1. Multdimensional Keys
0.163. The PR Quadtree
- 0.163.1. The PR Quadtree
0.164. KD Trees
- 0.164.1. KD Trees
0.165. The Bintree
- 0.165.1. The Bintree
  - 0.165.1.1. Implementation Concerns
0.166. Other Spatial Data Structures
0.167. Data and Algorithm Analysis
- 0.167.1. Introduction
0.168. An Introduction to Problem Solving
- 0.168.1. An Introduction to Problem Solving
0.169. Semester Overview
- 0.169.1. Semester Overview
  - 0.169.1.1. Modeling Algorithm Cost
  - 0.169.1.2. Big Issues
0.170. Introduction to Analyzing a Problem
- 0.170.1. Towers of Hanoi
0.171. Bounds Review
- 0.171.1. Bounds Review
  - 0.171.1.1. Analyzing Problems
  - 0.171.1.2. Modeling the Inputs
0.172. Growth Rates Review
- 0.172.1. Growth Rates Review
  - 0.172.1.1. Asymptotic Notation
0.173. Summation Techniques
0.174. Solving Recurrence Relations
- 0.174.1. Solving Recurrence Relations
0.175. Chapter Introduction: Search
0.176. Analyzing Search in Unsorted Lists
- 0.176.1. Analyzing Search in Unsorted Lists
  - 0.176.1.1. Lower Bounds Proofs
0.177. Search in Sorted Arrays
- 0.177.1. Analysis
0.178. Self-Organizing Lists
- 0.178.1. Introduction
  - 0.178.1.1. Frequency Count
- 0.178.2. Move to Front
- 0.178.3. Transpose
  - 0.178.3.1. An Example
0.179. Bit Vectors for Representing Sets
0.180. Perfect Hashing
- 0.180.1. Perfect Hashing
0.181. Finding the Maximum Value
- 0.181.1. Finding the Maximum Value
0.182. Adversarial Lower Bounds Proofs
0.183. State Space Lower Bounds Proofs
0.184. Finding the \(i\) th Best Element
0.185. Optimal Sorting
0.186. Number Problems
- 0.186.1. Number Problems
0.187. The Transformation Concept
- 0.187.1. The Transformation Concept: Integer Multiplication
- 0.187.2. Polynomial Multiplication
0.188. The Fast Fourier Transform
- 0.188.1. The Fast Fourier Transform
0.189. Introduction to Probabilistic Algorithms
- 0.189.1. Probabilistic Algorithms
0.190. Finding Prime Numbers
0.191. Random Numbers
- 0.191.1. Random Numbers
0.192. Skip Lists
- 0.192.1. Skip Lists
0.193. Balanced Trees
0.194. The AVL Tree
0.195. The Splay Tree
0.196. The Red-Black Tree
- 0.196.1. Exercise 1
- 0.196.2. Exercise 2
0.197. The Sparse Matrix
0.198. Dynamic Programming
- 0.198.1. Dynamic Programming
  - 0.198.1.1. Computing Fibonacci Numbers
  - 0.198.1.2. The Knapsack Problem
0.199. Amortized Analysis
0.200. 0/1 Knapsack Problem
- 0.200.1. 0/1 Knapsack Problem
  - 0.200.1.1. Exercise 1
- 0.200.2. Exercise 2
- 0.200.3. Exercise 3
- 0.200.4. Exercise 4
0.201. Edit Distance
- 0.201.1. Edit Distance
- 0.201.2. Exercise 1
- 0.201.3. Exercise 2
0.202. KMP String Search Algorithm
- 0.202.1. KMP String Search Algorithm
0.203. Boyer-Moore String Search Algorithm
- 0.203.1. Boyer-Moore String Search Algorithm
0.204. Rabin-Karp String Search Algorithm [Draft]
- 0.204.1. Rabin-Karp String Search Algorithm [Draft]
0.205. General Tree Implementations
- 0.205.1. General Tree Implementations
0.206. K-ary Tree Implementations
- 0.206.1. K-ary Tree Implementations
0.207. Limits to Computing
- 0.207.1. Limits to Computing
0.208. Reductions
- 0.208.1. Reductions
0.209. NP-Completeness
- 0.209.1. NP-Completeness
  - 0.209.1.1. Hard Problems
  - 0.209.1.2. The Theory of NP-Completeness
0.210. Circuit Satisfiability
- 0.210.1. Circuit Satisfiability
0.211. Formula Satisfiability
- 0.211.1. Formula Satisfiability
0.212. 3-CNF Satisfiability
- 0.212.1. 3-CNF Satisfiability
0.213. The Clique Problem
- 0.213.1. The Clique Problem
0.214. The Independent Set Problem
- 0.214.1. Independent Set
0.215. The Vertex Cover Problem
- 0.215.1. Vertex Cover
0.216. The Hamiltonian Cycle Problem
- 0.216.1. Hamiltonian Cycle
0.217. The Traveling Salesman Problem
- 0.217.1. Traveling Salesman
0.218. NP-Completeness Proofs
- 0.218.1. NP-Completeness Proofs
0.219. Reduction of Circuit SAT to SAT
- 0.219.1. Reduction of Circuit SAT to SAT
0.220. Reduction of SAT to 3-SAT
- 0.220.1. Reduction of SAT to 3-SAT
0.221. Reduction of 3-SAT to Clique
- 0.221.1. Reduction of 3-SAT to Clique
0.222. Reduction of Clique to Independent Set
- 0.222.1. Clique to Independent Set
0.223. Reduction of Independent Set to Vertex Cover
- 0.223.1. Independent Set to Vertex Cover
0.224. Reduction of 3-SAT to Hamiltonian Cycle
- 0.224.1. 3-SAT to Hamiltonian Cycle
0.225. Reduction of Hamiltonian Cycle to Traveling Salesman
- 0.225.1. Hamiltonian Cycle to Traveling Salesman
0.226. Coping with NP-Complete Problems
0.227. Unsolveable Problems
- 0.227.1. Unsolveable Problems
0.228. Turing Machines
- 0.228.1. Turing Machines
0.229. Grammars - Part 1 - Derivations and Parse Trees
- 0.229.1. Parse Trees
  - 0.229.1.1. Example Grammar 1
- 0.229.2. Strings Generated by a Grammar
- 0.229.3. Characterizing a Language (1)
- 0.229.4. Characterizing a Language (2)
0.230. Grammars - Part 2 - Ambiguous Grammars
- 0.230.1. Ambiguous Grammars
  - 0.230.1.1. Example Grammar 2
- 0.230.2. Ambiguous Grammars (2)
- 0.230.3. Ambiguous Grammars (3)
- 0.230.4. Ambiguous Grammars (4)
0.231. Grammars - Part 3 - Establishing Order of Operations
- 0.231.1. Evaluation of Expressions
  - 0.231.1.1. Example Grammar 3
- 0.231.2. Associativity
- 0.231.3. Precedence and Associativity
- 0.231.4. Characterizing a Language Given the BNF
- 0.231.5. Extended BNF
0.232. Grammars - Part 4 - Parser Generators
- 0.232.1. Jison (1)
- 0.232.2. Jison (2)
0.233. Grammars - Part 5 - Using Parser Generators to Interpret a Language
- 0.233.1. Annotating Jison Grammars
0.234. Introduction to Functional Programming - List Construction and Deconstruction
- 0.234.1. FP - Constructing Lists with cons
- 0.234.2. FP - Deconstructing Lists with fp.hd and fp.tl
- 0.234.3. FP - Deconstructing Lists with fp.hd and fp.tl (2)
- 0.234.4. FP - fp.isNull, fp.isEq, fp.isZero
0.235. Functional Programming - Developing basic, recursive list-processing functions
- 0.235.1. Recursive List Processing (1)
- 0.235.2. Recursive List Processing (2)
- 0.235.3. Recursive List Processing (3)
0.236. Functional Programming - Recurring On Lists That Aren't Flat
- 0.236.1. Deep Recursion in FP (1)
- 0.236.2. Deep Recursion 2
- 0.236.3. Deep Recursion 3
- 0.236.4. Deep Recursion 4
0.237. Functional Programming - Using Helper Functions with Accumulators
- 0.237.1. Using helpers to write reverse and split functions
- 0.237.2. Using the split function to develop a sort function
- 0.237.3. Additional Practice with the Accumulator Pattern
0.238. Functional Programming - Scope, Closures, Higher-order Functions, Static vs. Dynamic Binding
- 0.238.1. Scope, Closures, Higher-order Functions (1)
- 0.238.2. Scope, Closures, Higher-order Functions (2)
- 0.238.3. Scope, Closures, Higher-order Functions (3)
- 0.238.4. Static vs. Dynamic Binding
0.239. Functional Programming - Procedural Abstraction: Map, Curry, and Compose
- 0.239.1. The Mapping Pattern
- 0.239.2. Function Composition
- 0.239.3. Currying
- 0.239.4. More currying
0.240. Functional Programming - Procedural Abstraction: The Filtering and Folding (Reduce) Patterns
- 0.240.1. The Filtering Pattern
- 0.240.2. Folding/Reducing
- 0.240.3. Folding/Reducing (2)
- 0.240.4. Folding/Reducing (3)
0.241. Functional Programming - Combining Map and Reduce
- 0.241.1. The MapReduce Paradigm
0.242. Functional Programming - Continuations and Continuation Passing
- 0.242.1. Tail recursive functions
- 0.242.2. Continuation-Passing Style
- 0.242.3. Continuation-Passing Style (2)
- 0.242.4. Continuation-Passing Style (3)
- 0.242.5. More CPS Practice
0.243. Syntax of the Lambda Calculus
- 0.243.1. Lambda Calculus
- 0.243.2. Mastering Lambda Calculus Syntax (1)
- 0.243.3. Mastering Lambda Calculus Syntax (2)
0.244. Semantics of the Lambda Calculus
- 0.244.1. Semantics of the Lambda Calculus
- 0.244.2. Mastering Lambda Calculus Semantics
0.245. Free and Bound Variables
- 0.245.1. Free and Bound Variables
- 0.245.2. Identifying Free Variables
- 0.245.3. Identifying Bound Variables
- 0.245.4. Formal Definition of Free Variables
0.246. Alpha-Conversion
- 0.246.1. Alpha-Conversion Rule
- 0.246.2. Mastering Alpha Conversion
0.247. The Substitution-Based Model of Evaluation
- 0.247.1. Substitution Algorithm
- 0.247.2. Identifying Substitution Cases
- 0.247.3. Performing the Substitution Algorithm
0.248. Beta-Reduction
- 0.248.1. Beta-Redexes
- 0.248.2. Identifying Beta-Redexes
- 0.248.3. Beta-Reduction is a Substitution
- 0.248.4. Some Beta-Reductions Require Alpha-Conversion
- 0.248.5. Performing Beta-Reductions
0.249. Reduction Strategies
- 0.249.1. Applicative Order
- 0.249.2. Normal Order
- 0.249.3. Beta-Reduction Order (1)
- 0.249.4. Beta-Reduction Order (2)
- 0.249.5. Applicative Order Proficiency Exercise
- 0.249.6. Normal Order Proficiency Exercise
0.250. Church Numerals and Booleans
- 0.250.1. Church Booleans
- 0.250.2. Encoding If-Then-Else
- 0.250.3. Encoding OR
- 0.250.4. Church Numerals
- 0.250.5. Church numerals with addition and multiplication
0.251. Recursive Functions
- 0.251.1. Fixed-points of Functions
- 0.251.2. The Y Fixed-point Combinator
- 0.251.3. Using Y to Implement Factorial
- 0.251.4. Identifying Fixed Point Combinators
0.252. Defining SLang1
- 0.252.1. Syntax of SLang1
- 0.252.2. Concrete Syntax SLang1
- 0.252.3. Abstract Syntax SLang1
- 0.252.4. Curry in SLang1
- 0.252.5. Semantics of SLang1
0.253. Environment-based Model of Evaluation
- 0.253.1. Environment Data Structure
- 0.253.2. Determining Values Bound to a Variable
- 0.253.3. Evaluation of Expression Within an Environment
- 0.253.4. Determining Denoted Values in SLang1
0.254. Let Expressions
- 0.254.1. Let Blocks
- 0.254.2. Let Blocks As Syntactic Sugar
- 0.254.3. Nested Lets
- 0.254.4. Nested Lets with Closures
0.255. Defining SLang2
- 0.255.1. SLang2: An Imperative Language
- 0.255.2. Output of SLang2 Program
0.256. Tying The Knot
- 0.256.1. Implementing Recursion Efficiently
- 0.256.2. Practice TTK
0.257. Parameter-Passing Mechanisms
- 0.257.1. Call By Value vs. Call By Reference
- 0.257.2. Copy-Restore
- 0.257.3. Macro Expansion
- 0.257.4. Call By Name
- 0.257.5. Comprehensive review of the five methods studied so far
0.258. Lazy Lists
- 0.258.1. Infinite Sequences
- 0.258.2. Practice With Infinite Sequences
- 0.258.3. Practice With Infinite Sequences (2)
- 0.258.4. Practice With Infinite Sequences (3)
0.259. Variations on how Languages Think about Types
- 0.259.1. Examples of Type-related Considerations in Programming Languages
- 0.259.2. Type Environments and Typing Rules Expressed as Post Systems
- 0.259.3. Type Inferencing Problem 1
- 0.259.4. Type Inferencing Problem 2
- 0.259.5. Type Inferencing Problem 3
- 0.259.6. Type Inferencing Problem 4
- 0.259.7. Type Inferencing Problem 5
- 0.259.8. Type Inferencing Problem 6
0.260. GLOSSARY
0.261. Formal Languages
- 0.261.1. Introduction
- 0.261.2. Prerequisites
- 0.261.3. What we will do
- 0.261.4. Process
0.262. Overview
- 0.262.1. Language Hierarchy
- 0.262.2. Power of Machines
- 0.262.3. Application: Compilers
  - 0.262.3.1. Stages of a Compiler
0.263. Major Concepts
- 0.263.1. Introduction
- 0.263.2. Languages
- 0.263.3. Grammars
- 0.263.4. Automata
0.264. Deterministic Finite Acceptors
- 0.264.1. DFA: Deterministic Finite Acceptor
0.265. Non-Deterministic Finite Automata
- 0.265.1. NFA: Non-Deterministic Finite Automata
- 0.265.2. NFA vs. DFA: Which is more powerful?
0.266. Minimizing the Number of States in a DFA
- 0.266.1. Minimizing the Number of States in a DFA
0.267. Regular Expressions
- 0.267.1. Regular Expressions
  - 0.267.1.1. Precedence Rules
  - 0.267.1.2. Examples
- 0.267.2. Regular Expressions vs. Regular Languages
0.268. Regular Grammars
- 0.268.1. Regular Grammars
0.269. Closure Properties of Regular Grammars
- 0.269.1. Closure Properties of Regular Grammars
0.270. Identifying Non-regular Languages
- 0.270.1. Identifying Non-regular Languages
0.271. Properties
- 0.271.1. Properties and Proving: Problem 1
- 0.271.2. Properties and Proving - Problem 2
0.272. Context-Free Languages
- 0.272.1. Context-Free Languages
  - 0.272.1.1. Ambiguity
0.273. Transforming Grammars
- 0.273.1. Transforming Grammars
0.274. Pushdown Automata
- 0.274.1. Pushdown Automata
  - 0.274.1.1. Example of transitions
  - 0.274.1.2. Equivalence of Acceptance Definitions
0.275. PDAs and Context Free Languages
- 0.275.1. PDAs and Context Free Languages
0.276. Deterministic Pushdown Automata
- 0.276.1. Deterministic Pushdown Automata
- 0.276.2. Grammars for Deterministic Context-free Languages
0.277. Properties of Context-Free Languages
- 0.277.1. Properties of Context-Free Languages
  - 0.277.1.1. (Chap 8.2) Closure Properties of CFLs
0.278. Parsing Introduction
- 0.278.1. Introduction
0.279. LL Parsing
- 0.279.1. LL Parsing
0.280. LR Parsing
- 0.280.1. LR Parsing
0.281. CYK Parsing
- 0.281.1. CYK Parsing
  - 0.281.1.1. CYK Parsing Algorithm
  - 0.281.1.2. Algorithm
0.282. Structure of a Compiler
- 0.282.1. What is a compiler?
  - 0.282.1.1. Translator
- 0.282.2. Language Processing System
  - 0.282.2.1. Compiler
- 0.282.3. Overview of General Compiler
- 0.282.4. Phases of Compilation
0.283. Recursively Enumerable Languages
- 0.283.1. Recursively Enumerable Languages
  - 0.283.1.1. Enumeration procedure for recursive languages
  - 0.283.1.2. Enumeration procedure for recursively enumerable languages
0.284. List Iteration
- 0.284.1. List Iteration
0.285. List Iteration Visualizations
- 0.285.1. List Iteration Visualizations
0.286. Classwork 8
- 0.286.1. List Exercise 1
0.287. Homework 8
- 0.287.1. List Exercise 2

TODO List

Index
Search Page

OpenDSA Stand-alone Modules

Table Of Contents

Search the book

Chapter 0 modules¶