Teaching Notes: Module 09

Key Learning Objectives

• Practical STL application
• Choosing appropriate containers
• File parsing
• Algorithm implementation
• Performance measurement

---

Container Strategy

Each exercise requires different container(s). Once used, cannot reuse!

Suggested allocation:

• ex00: map (date -> price lookup)
• ex01: stack (RPN evaluation)
• ex02: vector + deque (sorting comparison)

---

Exercise 00: Bitcoin Exchange

Key Concepts

• Parse CSV database
• Match dates (use closest earlier if exact not found)
• Validate input

Common Mistakes

1. Date matching

   // Use map::lower_bound for efficient lookup
   std::map<std::string, float>::iterator it = _db.lower_bound(date);
   if (it == _db.end() || it->first != date) {
       if (it == _db.begin())
           // No earlier date exists
       --it;  // Go to previous (earlier) date
   }

2. Input validation

   • Date format: YYYY-MM-DD
   • Value: 0 to 1000, positive
   • Handle leap years!

3. Error messages

   • “Error: bad input => [input]”
   • “Error: not a positive number.”
   • “Error: too large a number.”

---

Exercise 01: RPN (Reverse Polish Notation)

Algorithm

For each token:
  If number: push to stack
  If operator: pop 2, calculate, push result
Result is last item on stack

Common Mistakes

1. Operand order

   int b = stack.top(); stack.pop();
   int a = stack.top(); stack.pop();
   // a OP b, not b OP a!
   result = a - b;  // For "5 3 -" = 2

2. Division by zero

   • Handle gracefully

3. Single digit only

   • Numbers < 10 in input (result can be any size)

---

Exercise 02: PmergeMe (Ford-Johnson)

The Algorithm (Simplified)

1. Pair elements, put larger in “main chain”
2. Recursively sort main chain
3. Insert smaller elements using binary search
4. Use Jacobsthal sequence for optimal insertion order

Common Mistakes

1. Not implementing actual Ford-Johnson

   • Regular merge sort won’t pass

2. Timing issues

   clock_t start = clock();
   // ... sort ...
   clock_t end = clock();
   double us = (double)(end - start) / CLOCKS_PER_SEC * 1000000;

3. Same container for both

   • Must use TWO DIFFERENT containers
   • Compare performance between them

Jacobsthal Sequence

J(n) = J(n-1) + 2*J(n-2)
0, 1, 1, 3, 5, 11, 21, 43, ...

Insertion order: 1, 3, 2, 5, 4, 11, 10, 9, 8, 7, 6, ...

Guiding Questions

• “Why does Ford-Johnson use this specific insertion order?”
• “Why might vector be faster/slower than deque for this?”
• “How do you handle an odd number of elements?”

---

General Module 09 Tips

Performance Comparison

• vector: contiguous memory, fast random access
• deque: fast front/back, random access
• list: fast insertion anywhere, slow access

Debugging

• Print intermediate states
• Test with small inputs first
• Verify sorting correctness before timing