15-122 Section G, Fall 2012


Note: due to issues with the server that normally hosts these handouts, I've had to temporarily re-host them here. I will post updates here and on Piazza if there are any changes.


Feedback is very important to me. If there's something I could do better or something I'm doing especially well, I want to know! I'm here to help you learn. If at any point this semester (Fall 2012) you have feedback (positive or negative) for me, please fill out this anonymous survey (or whatever parts of it are relevant to your feedback).

Recitation Handouts and Code

  1. Wed, Aug 29. Administrivia, C0 syntax, and setup. Handout
  2. Fri, Aug 31. Contracts and intro to correctness proofs. Handout (Solutions, Code)
  3. Wed, Sep 5. Hexadecimal, two's complement, ARGB images. Handout (Solutions)
  4. Fri, Sep 7. Bit manipulation and safe array access. Handout (Solutions, Code: addOne.c0, fib.c0, sieve.c0)
  5. Wed, Sep 12. Safe array access, linear search, and debugging. Handout (Solutions, Code: sieve.c0, linsearch.c0, isqrt.c0)
  6. Fri, Sep 14. Binary search and brief intro to complexity. Handout (Solutions, isqrt.c0 [with binary search version], find.c0)
  7. Wed, Sep 19. Big-O, unit testing, and selection sort. Handout (Solutions, selectsort.c0)
  8. Fri, Sept 21. Unit testing and quicksort. Handout (Solutions, qsort-fp.c0)
  9. Wed, Sept 26. Linked lists, pointers, structs, typedefs, and queues. Handout (Solutions)
  10. Fri, Sept 28. Stacks, interface vs. implementation, and clac. Handout (Solutions)
  11. Wed, Oct 3. Memory layout, reasoning about recursion. Handout (Solutions)
  12. A: Fri, Oct 5. Midterm review. Note that this is NOT a comprehensive review. You should also look at my old recitations to help you study, along with your own notes and lecture notes. Handout (Solutions, modpow.c0)
    B: Wed, Oct 10. Amortized analysis and unbounded arrays. Handout (Solutions)
  13. Fri, Oct 12. Programming assignment 4. Assignment handout
  14. Wed, Oct 17. Hash tables, a bit more on interface vs. implementation. Handout (Solutions, ht.c0)
  15. There was no recitation 15 due to midsemester break.
  16. Wed, Oct 24. Priority queues, heaps, and backtracking search. Handout (Solutions, heaps.c0)
  17. Fri, Oct 26. Binary search trees. Handout (Solutions NOTE: The proof in these solutions has a bug. Part of your homework is to fix it. bst.c0)
  18. Wed, Oct 31. AVL trees. Handout (Solutions)
  19. Fri, Nov 2. Function pointers, strings in C, ASSERT, REQUIRES, and ENSURES statements, and a brief bit of memory management. Handout (funcpoint.c, strcat.c)
  20. Wed, Nov 7. Some more C details, including the address-of operator, free, valgrind, memory, and common C mistakes. Handout (Solutions)
  21. A: Fri, Nov 9. This recitation was a NON-COMPREHENSIVE review for midterm 2. Handout (Solutions)
    B: Wed, Nov 14. This recitation was an overview of tries and a discussion of how to improve the interface presented in lecture. Handout.
  22. Fri, Nov 16. This recitation covered some more C details that will be useful for assignment 8 and in future classes when you use C, including switch statements, structs that aren't pointers, macros, and casting. Handout, (goodswitch.c, badswitch.c)
  23. There was no recitation 23 due to Thanksgiving break.
  24. Wed, Nov 28. This recitation covered generic graph search using priority queues, and talked a bit about edge weights and Dijkstra's algorithm. Handout.
  25. Fri, Nov 30. This recitation covered Kruskal's algorithm, minimum spanning trees, dfs_tree_distance, and recursive depth-first search. Handout (Solutions)
  26. This recitation covered the C0VM and some common mistakes on homework 7.
  27. Fri, Dec 7. This recitation covered the union-find algorithm. Handout (Solutions)