CS 301 (Clancy)                                                              Homework 2
Fall 2002

Groups will be formed in class on September 23. With your group members, design a class activity around one of the topics below that minimizes information that you tell to the students in favor of information that students figure out on their own. In class on September 30, demonstrate your activity.

Here are the topics. Each group should choose one.

·      Help students learn how a feature of the hardware, programming environment, or programming language works—i.e. predict its effect, predict the error state that results from applying it incorrectly, and where possible determine how it was applied to achieve a given result or state. Examples: higher-order procedures from CS 3 (if they’re covered before recursion); virtual-to-physical memory translation from CS 61C; a network protocol; public key encryption.

·      Get the students to understand a proof—i.e. produce a given step, identify the rationale for that step, and evaluate the result of a slightly different induction hypothesis. Examples: correctness of Huffman encoding; amortized running time analysis of balanced tree insertion and deletion; proof and runtime analysis of Dijkstra’s shortest path algorithm; reduction of 3-SAT to vertex covering.

·      Familiarize the students with a programming technique or algorithm—i.e. predict the result of applying it to a given input, predict the error state that results from applying it incorrectly, and where possible determine how it was applied to achieve a given result. Examples: the Scheme evaluator; permutation generation; alpha-beta pruning; Fast Fourier Transform.