This review sheet is intended to help you study for the midterm exam. It is not intended to be an exhaustive list of everything we've covered, but it should help you identify the "big ideas". You should also review your lecture notes and the solutions to your homework problems.  The lecture "quizzes" are especially useful in helping you study for the exam.

You may bring to the exam a 8.5 by 11 sheet with your own writing (only) on both sides.

Study Topics

Foundations of functional programming with Racket!

• Be sure that you feel comfortable using the basics of Racket. You don't need to memorize all Racket's built-in functions, but if we give you a list of built-in functions that were used in class or on a homework assignment, you should feel comfortable using them.
• Be sure that you feel comfortable with higher order functions (e.g. filter, map, foldr), both how to write them from scratch, and how to use them.
• What are anonymous functions and how do you use them?
• What is tail recursion and how can it improve performance?
• How can objects such as trees and graphs be represented as lists? Make sure that you feel comfortable writing Racket functions to manipulate such objects, e.g., by reviewing those we looked at in class.
• How does sort work in Racket?  You should be comfortable using this built-in function.
• Given a high-level specification for a function (e.g., Unicalc), be sure you can implement the function in Racket.
   

Parsing and Evaluating a Language

• How do tokenizing, parsing, and evaluation each contribute to the interpretation and execution of a computer program?
• What is a parse tree? You should be able to build a parse tree that gives rise to a particular sequence of tokens for a provided grammar, as we did in class.
• How does recursive descent parsing work? You should feel comfortable writing a parser for a small grammar and explaining how it works.
• How is the "environment" used during evaluation?
• Be sure you understand how to implement an evaluator for a language (e.g. a subset of Racket or an extension to Unilang).

Program Design

• What is an API and why is it useful?
• Why is data abstraction important?
• What are "magic numbers/string/symbols" and why and how do we avoid them?
• Be sure you can identify well designed and poorly designed code, considering issues such as function names, variable names, line length, indentation, etc.

Data Structures and Algorithms

• What are trees, graphs, cyclic graphs, directed graphs, and DAGS?
• Be sure you are familiar with Dijkstra's algorithm for finding the shortest path between pairs of nodes in a graph.
• How do Binary Search Trees work?  In particular, make sure that you could write code (in Racket) for all of the BST operations we discussed such as inserting, deleting, and finding data.
• What is Big-O analysis?  Given an algorithm or a snippet of code, make sure you're comfortable finding its Big-O running time.

Digital Logic and Computer Architecture

• Be comfortable writing truth tables from function descriptions as well designing circuits to implement those function based on the minterm expansion principle.
• What is the VonNeumann architecture?
• What do we mean by the following: Instruction Registrer, fetch-execute cycle, Program Counter?
• What is the relationship between machine language and assembly language.  Given a small set of instructions in assembly language, you should be comfortable devising a reasonable representation for these instructions in machine language.
• What is the relationship between machine language and hardware?  (Note: I will not ask you details here, just general ideas).
• What are DeMoragn's laws?
• You should be able to prove that the NAND gate is universal.
• What is the difference between combinational logic (logic that implements functions) and sequential logic (logic that implements "memory")?
• What are registers?  How do they differ from memory?
• What is a pseudoinstruction?  What distinguishes it from a "normal" instruction?

Assembly Language Programming

• Be sure you are comfortable reading and reasoning about Hmmm code (we will provide the instruction set)
• Be sure you are comfortable translating Racket programs into Hmmm, including recursive programs.
• What is the stack?  How is it used during program execution?
• How does the computer know which memory locations contain instructions and which contain data?

Some Practice Problems

1. Writing reduce in Racket! Recall the the foldr function in Racket takes as input three arguments: A function f of two variables, a unit (such that (f X unit) => X), and a list L. The foldr function returns the result of repeatedly applying the function f to the elements in L until to reduce them to a single value. For example,

    Scheme> (foldr (lambda (X, Y) (+ X Y)) 0 '(1, 2, 3, 4))
    10
    

   You should assume that foldr "associates" (orders operations) like this: 1 + 2 + 3 + 4 = 1 + (2 + (3 + (4 + 0))). (Notice that the 0 at the end is the unit for addition.) Write the foldr function from scratch. That is, your implementation my use Scheme's list notation and recursion, but no built-in functions. Notice that foldr should not be written exclusively to handle addition! It's first argument can be any function of two variables, its second argument is the unit for that function, and its third argument is a list of elements of the type operated on by the given function.
   
   
2. Graph algorithms in Racket!

   You have been hired by Napquest, a company specializing in finding shortest paths between given cities. (It's called Napquest, because their algorithms tend to be inefficient, causing the users to nap while they wait for the answer!)

   A map is a list of "triplets", where each triplet is a list of the form [City1, City2, Distance]. City1 and City2 are just names of cities (e.g. they might be numbers or strings) and Distance is a positive real number indicating the length of the one-way road from City1 to City2. For example, here is a valid map: [ ["Claremont", "Spamville", 1], ["Spamville", "Claremont", 2], ["Spamville", "Foobarsburg", 2], ["Foobarsburg", "Claremont", 4] ]. Notice that the map may contain cycles and that there may be funny things like a one-way road from Claremont to Spamville which is shorter than the one-way road from Spamville to Claremont.

   Your job is write a program called tour which takes as input two things: The name of the start city, and an entire map. The function returns a boolean that indicates whether there is a path starting in the start city that tours all of the cities (it does not need to return to the start city).  
   
   The program need not be fast, but it must compute the right answer. For full credit, keep your code very short.  However you may find it easier to write a helper function.
   

3. BTrees
   
   A BTree is a generalized form of a binary search tree that, similar to BSTs, allows fast (logarithmic time) access to data. In a BTree, each node stores a variable number of values--at least 1 and at most m-1, where m is said to be the "order" of the BTree, and the number of children that node has is determined by the number of values stored in that node.   The elements in each node have the following properties: 
1. The items in each node are sorted.
2. The items in each non-leaf node act as separators for the subtrees that originate at that node.  If a non-leaf node holds k items, it will have k+1 subtrees, all of which contain at least one non-empty node.
3. All items in each subtree lie between the values of their separators.  E.g., if a subtree originates between the values 3 and 15, all values in that subtree will be greater than 3 and less than 15.  Subtrees to the far left (right) (separated only by a value on the right (left)) will contain values strictly less than (greater than) their separator.  

See the Wikipedia page on BTrees for an example of a BTree with order 3.   http://en.wikipedia.org/wiki/B-tree.

Your jobs here is to: (1) Devise a method of reprsenting BTrees of order m in Racket.  Be sure to clearly describe your representation and give an example of how your representation would represent the tree given in the example on Wikipedia and (2) using your representation, write a function in Racket for finding an element in a BTree of some order m.  Your function find(item, tree) should return #t if the element is in the BTree and #f if it is not.

As a bonus challenge, consider implementing a function to insert an item into the tree.  Note, this is fairly difficult and much harder than what we would ask you  to do on an exam.  You'll find the algorithm for inserting into a BTree on the Wikipedia page above.


4. Hmmmm
   
   Write a Hmmm program that faithfully implements the following Racket function.  (Note that we would provide you with a complete Hmmm instruction set if we were to ask you this problem).  
   
   

   
   (define (main)
    (let* ((x (get input from user))
           (y (get input from user))
           (result (foo x y)))
      (display result)))
   
   (define (foo x y)
      (let* (
             (z 2)
    	  (a (smallestfactor x z))
    	  (b (smallestfactor y z)))
       (if (> a b) 
           x
    	y)))
   
   (define (smallestfactor n f)
      (if (= 0 (mod n f))
          f
          (smallestfactor n (+ f 1))))
   

   In addition to being able to translate into Hmmm, make sure you can also answer questions about provided Hmmm code such as:
1. Values in the registers as the code runs
2. The maximum (minimum) value of the stack pointer
3. The function of specific lines of code
4. etc.