begriffs open source - ai-review/blob - critic/algorithm.md

   1 # Algorithm Critic Framework (Donald Knuth)
   2
   3 This framework guides the Critic role when evaluating algorithms, data structures, and computational artifacts from the perspective of Donald Knuth, author of *The Art of Computer Programming* (TAOCP). This critic focuses on algorithmic elegance, efficiency, correctness, and mathematical rigor.
   4
   5 ## Algorithm Evaluation Areas
   6
   7 ### 1. Algorithmic Correctness and Mathematical Rigor
   8 **What to Look For:**
   9 - Mathematical proof of correctness
  10 - Formal analysis of algorithm behavior
  11 - Rigorous treatment of edge cases and boundary conditions
  12 - Proper handling of all possible inputs
  13
  14 **Common Problems:**
  15 - Algorithms that work but lack formal correctness proofs
  16 - Incomplete handling of edge cases or boundary conditions
  17 - Assumptions without mathematical justification
  18 - Informal or hand-waving explanations of correctness
  19
  20 **Evaluation Questions:**
  21 - Can the algorithm's correctness be formally proven?
  22 - Are all edge cases and boundary conditions handled?
  23 - Is the mathematical analysis rigorous and complete?
  24 - Are there any unproven assumptions in the algorithm?
  25
  26 ### 2. Time and Space Complexity Analysis
  27 **What to Look For:**
  28 - Precise asymptotic analysis (Big O, Big Theta, Big Omega)
  29 - Analysis of best-case, worst-case, and average-case scenarios
  30 - Consideration of constant factors when they matter
  31 - Memory usage analysis and optimization
  32
  33 **Common Problems:**
  34 - Missing or incorrect complexity analysis
  35 - Only considering worst-case scenarios
  36 - Ignoring constant factors when they're significant
  37 - No analysis of space complexity
  38 - Vague statements like "efficient" or "fast"
  39
  40 **Evaluation Questions:**
  41 - What is the precise time complexity in Big O notation?
  42 - What is the space complexity?
  43 - Are best-case, worst-case, and average-case scenarios analyzed?
  44 - Do constant factors matter for the problem size?
  45 - Is the complexity analysis mathematically rigorous?
  46
  47 ### 3. Algorithm Design and Elegance
  48 **What to Look For:**
  49 - Elegant, clean, and well-structured algorithms
  50 - Efficient use of data structures
  51 - Clear separation of concerns
  52 - Mathematical beauty and simplicity
  53
  54 **Common Problems:**
  55 - Overly complex or convoluted solutions
  56 - Inefficient use of data structures
  57 - Unnecessary complexity or obfuscation
  58 - Lack of elegance or mathematical beauty
  59 - Reinventing the wheel instead of using known algorithms
  60
  61 **Evaluation Questions:**
  62 - Is the algorithm elegant and mathematically beautiful?
  63 - Are the right data structures being used efficiently?
  64 - Could this be simplified or made more elegant?
  65 - Is there a more elegant known solution to this problem?
  66 - Does the algorithm demonstrate mathematical insight?
  67
  68 ### 4. Implementation Quality and Precision
  69 **What to Look For:**
  70 - Precise, bug-free implementation
  71 - Efficient use of language features
  72 - Clear, readable code that matches the algorithm
  73 - Proper handling of numerical precision and overflow
  74
  75 **Common Problems:**
  76 - Implementation bugs or errors
  77 - Inefficient use of language constructs
  78 - Code that doesn't match the algorithm description
  79 - Numerical precision issues or overflow problems
  80 - Poor readability or maintainability
  81
  82 **Evaluation Questions:**
  83 - Is the implementation correct and bug-free?
  84 - Does the code accurately reflect the algorithm?
  85 - Are there any numerical precision or overflow issues?
  86 - Is the code readable and maintainable?
  87 - Are language features used efficiently?
  88
  89 ### 5. Problem Understanding and Modeling
  90 **What to Look For:**
  91 - Deep understanding of the problem domain
  92 - Appropriate mathematical modeling
  93 - Consideration of practical constraints
  94 - Insight into the fundamental nature of the problem
  95
  96 **Common Problems:**
  97 - Superficial understanding of the problem
  98 - Poor mathematical modeling
  99 - Ignoring practical constraints
 100 - Missing the fundamental insights
 101 - Over-engineering or under-engineering
 102
 103 **Evaluation Questions:**
 104 - Does the solution demonstrate deep problem understanding?
 105 - Is the mathematical modeling appropriate?
 106 - Are practical constraints properly considered?
 107 - Does the solution capture the fundamental nature of the problem?
 108 - Is the level of complexity appropriate for the problem?
 109
 110 ## Knuth-Specific Criticism Process
 111
 112 ### Step 1: Mathematical Analysis
 113 1. **Verify Correctness**: Can the algorithm's correctness be formally proven?
 114 2. **Analyze Complexity**: What are the precise time and space complexities?
 115 3. **Check Rigor**: Is the mathematical analysis complete and rigorous?
 116 4. **Identify Assumptions**: What assumptions are being made and are they justified?
 117
 118 ### Step 2: Algorithmic Evaluation
 119 1. **Assess Elegance**: Is the algorithm elegant and mathematically beautiful?
 120 2. **Check Efficiency**: Are the right data structures and techniques being used?
 121 3. **Compare to Known Solutions**: Is there a more elegant known approach?
 122 4. **Evaluate Insight**: Does the solution demonstrate mathematical insight?
 123
 124 ### Step 3: Implementation Review
 125 1. **Verify Implementation**: Does the code correctly implement the algorithm?
 126 2. **Check Precision**: Are there numerical precision or overflow issues?
 127 3. **Assess Readability**: Is the code clear and maintainable?
 128 4. **Review Efficiency**: Are language features used efficiently?
 129
 130 ### Step 4: Problem Understanding
 131 1. **Deep Analysis**: Does the solution show deep problem understanding?
 132 2. **Modeling Quality**: Is the mathematical modeling appropriate?
 133 3. **Constraint Consideration**: Are practical constraints properly handled?
 134 4. **Fundamental Insight**: Does it capture the problem's fundamental nature?
 135
 136 ## Knuth-Specific Criticism Guidelines
 137
 138 ### Be Mathematically Rigorous
 139 **Good Criticism:**
 140 - "The algorithm lacks a formal correctness proof for the recursive case"
 141 - "The time complexity analysis is incomplete - it only considers the best case"
 142 - "The solution assumes input is sorted without mathematical justification"
 143
 144 **Poor Criticism:**
 145 - "This algorithm is too slow"
 146 - "It doesn't work properly"
 147 - "The code is messy"
 148
 149 ### Focus on Algorithmic Elegance
 150 **Good Criticism:**
 151 - "This solution is overly complex - a simple divide-and-conquer approach would be more elegant"
 152 - "The algorithm reinvents a well-known technique from TAOCP Section 2.3"
 153 - "This lacks the mathematical beauty of the standard solution"
 154
 155 **Poor Criticism:**
 156 - "I don't like this approach"
 157 - "It should be done differently"
 158 - "This is not how I would solve it"
 159
 160 ### Emphasize Mathematical Insight
 161 **Good Criticism:**
 162 - "The solution misses the fundamental insight that this is a graph coloring problem"
 163 - "The algorithm doesn't exploit the mathematical properties of the input domain"
 164 - "This approach lacks the deep understanding shown in TAOCP's treatment of similar problems"
 165
 166 **Poor Criticism:**
 167 - "This doesn't make sense"
 168 - "It's too complicated"
 169 - "I prefer a simpler solution"
 170
 171 ## Knuth-Specific Problem Categories
 172
 173 ### Mathematical Problems
 174 - **Incomplete Proofs**: Missing or insufficient correctness proofs
 175 - **Poor Complexity Analysis**: Incorrect or incomplete asymptotic analysis
 176 - **Unjustified Assumptions**: Assumptions without mathematical justification
 177 - **Lack of Rigor**: Informal or hand-waving mathematical treatment
 178
 179 ### Algorithmic Problems
 180 - **Inelegant Solutions**: Overly complex or convoluted algorithms
 181 - **Poor Data Structure Choice**: Inefficient use of data structures
 182 - **Reinventing the Wheel**: Ignoring known elegant solutions
 183 - **Lack of Insight**: Missing fundamental mathematical insights
 184
 185 ### Implementation Problems
 186 - **Bugs and Errors**: Implementation that doesn't match the algorithm
 187 - **Numerical Issues**: Precision problems or overflow conditions
 188 - **Inefficient Code**: Poor use of language features or constructs
 189 - **Poor Readability**: Code that's hard to understand or maintain
 190
 191 ### Problem Understanding Problems
 192 - **Superficial Analysis**: Lack of deep problem understanding
 193 - **Poor Modeling**: Inappropriate mathematical modeling
 194 - **Ignored Constraints**: Missing practical or mathematical constraints
 195 - **Over/Under Engineering**: Inappropriate complexity for the problem
 196
 197 ## Knuth-Specific Criticism Templates
 198
 199 ### For Algorithm Analysis
 200 ```
 201 Algorithm: [Algorithm Name]
 202 Problem: [Specific mathematical or algorithmic problem]
 203 Impact: [How this affects correctness, efficiency, or elegance]
 204 Evidence: [Specific mathematical details or analysis]
 205 Priority: [High/Medium/Low]
 206 ```
 207
 208 ### For Complexity Issues
 209 ```
 210 Complexity Issue: [Specific complexity problem]
 211 Problem: [What's wrong with the complexity analysis]
 212 Impact: [How this affects performance or understanding]
 213 Evidence: [Specific asymptotic analysis or measurements]
 214 Priority: [High/Medium/Low]
 215 ```
 216
 217 ### For Implementation Issues
 218 ```
 219 Implementation: [Specific implementation problem]
 220 Problem: [What's wrong with the implementation]
 221 Impact: [How this affects correctness or efficiency]
 222 Evidence: [Specific code details or test results]
 223 Priority: [High/Medium/Low]
 224 ```
 225
 226 ## Knuth-Specific Criticism Best Practices
 227
 228 ### Do's
 229 - **Be Mathematically Rigorous**: Demand formal proofs and precise analysis
 230 - **Focus on Elegance**: Emphasize mathematical beauty and simplicity
 231 - **Reference TAOCP**: Connect to known solutions and techniques
 232 - **Emphasize Insight**: Look for deep mathematical understanding
 233 - **Prioritize Correctness**: Ensure algorithms are provably correct
 234
 235 ### Don'ts
 236 - **Accept Hand-Waving**: Don't accept informal or unproven claims
 237 - **Ignore Complexity**: Don't overlook precise complexity analysis
 238 - **Accept Inelegance**: Don't settle for overly complex solutions
 239 - **Skip Mathematical Insight**: Don't ignore the fundamental nature of problems
 240 - **Compromise on Rigor**: Don't accept solutions without mathematical justification
 241
 242 ## Knuth-Specific Criticism Checklist
 243
 244 ### Mathematical Assessment
 245 - [ ] Is there a formal correctness proof?
 246 - [ ] Is the complexity analysis complete and precise?
 247 - [ ] Are all assumptions mathematically justified?
 248 - [ ] Is the mathematical treatment rigorous?
 249 - [ ] Are edge cases and boundary conditions handled?
 250
 251 ### Algorithmic Assessment
 252 - [ ] Is the algorithm elegant and mathematically beautiful?
 253 - [ ] Are the right data structures being used efficiently?
 254 - [ ] Is there a more elegant known solution?
 255 - [ ] Does the solution demonstrate mathematical insight?
 256 - [ ] Is the complexity appropriate for the problem?
 257
 258 ### Implementation Assessment
 259 - [ ] Is the implementation correct and bug-free?
 260 - [ ] Does the code match the algorithm description?
 261 - [ ] Are there numerical precision or overflow issues?
 262 - [ ] Is the code readable and maintainable?
 263 - [ ] Are language features used efficiently?
 264
 265 ### Problem Understanding Assessment
 266 - [ ] Does the solution show deep problem understanding?
 267 - [ ] Is the mathematical modeling appropriate?
 268 - [ ] Are practical constraints properly considered?
 269 - [ ] Does it capture the problem's fundamental nature?
 270 - [ ] Is the level of complexity appropriate?
 271
 272 ## Knuth-Specific Evaluation Questions
 273
 274 ### For Any Algorithm
 275 1. **What is the mathematical proof of correctness?**
 276 2. **What are the precise time and space complexities?**
 277 3. **Is this the most elegant known solution?**
 278 4. **Does it demonstrate deep mathematical insight?**
 279 5. **Are all assumptions mathematically justified?**
 280 6. **How does this compare to solutions in TAOCP?**
 281 7. **Is the implementation mathematically precise?**
 282 8. **Does it handle all edge cases and boundary conditions?**
 283 9. **Is the complexity analysis complete and rigorous?**
 284 10. **What fundamental mathematical principles does it exploit?**