Exam and Review Reminders

The final exam is Thursday, December 14 2-5pm in the usual classroom.

There will be a review session in Jacobs B134 on Tuesday, December 12 at 6:30 PM.

You may bring up to two 8.5 by 11 sheets of paper to the exam with anything you want on both sides of the sheets.

Below is a study guide and some practice problems to help you prepare for the final exam. In addition to using this guide, we strongly recommend carefully reviewing the class homework assignments and your notes. The exam will be comprehensive.

Study Guide

• Object-oriented Programming in Java
  • What is a constructor and when is it invoked?
  • What does this refer to in a java class?
  • What do private and public mean and where is it appropriate to use each of them?
  • What are getters and setters and why are they important?
  • What is static and where and why would it be used?
  • What is inheritance, why is it useful, and how does it work?
  • What is polymorphism and why is it useful?
  • What is an abstract class and why is it useful?
  • How are the terms extends, super, and implements used in Java?
  
  
  
• Abstract Data Types (ADT's) and Data Structures
  • What is an ADT and what is a data structure?
  • How do Java interfaces facilitate the relationship between ADTs and data structures?
  • What are the ADT's Dictionaries, Queues, and Stacks (What operations does each ADT support?)
  • How do breadth-first search and depth-first search work? How are queues and stacks used in each of these algorithms? How can recursion be used to implement depth-first search without explicitly using a stack?
  • How do extendible arrays, linked lists, binary trees, and self-balancing binary trees work? In particular, make sure that you could write code for all of these data structures including the more challenging ones such as inserting, deleting, and finding data in a binary tree. (We won't ask details about AVL Trees, but you should understand how to insert and find in a B-tree.)
  • For each ADT above, which data structures could be used to implement it? Make sure that you can analyze the big-Oh running time of any operation for any given data structure above.
  
  
  
• Functional Programming in rex
  • Make sure that you understand and feel comfortable with rex's syntax.
  • Make sure that you can write basic rex functions like those developed in lecture and in the rex assignments. In particular, recursion is the secret to all happiness in functional programming. How can you take a problem and formulate it using recursion?
  • What is a function and what is a predicate? How can a function take a function as an argument? How can a function return a function as an output? What are anonymous functions and where are they useful?
  • You should be familiar with the rex higher-order functions such as map, reduce, keep, and drop. You certainly don't need to memorize them, but you should feel like you could implement them from a definition using recursion.
  • How can objects such as arrays, trees, and graphs be encoded as lists? Make sure that you feel comfortable writing rex functions to manipulate such objects.
  • How is delayed evaluation expressed syntactically in rex? How does it allow a programmer to compute with "infinite" lists?
  • What is "weirdo analysis" and how is it used?
  
  
  
• Logic Programming
  • Prolog "programs" are a collection of facts and rules. Make sure that you understand all of the examples that we saw in class.
  • Dynamic assertions: What are they and why do we need them?
  • Why does prolog sometimes produce multiple identical answers to a query? How can "marking" configurations make prolog's search more efficient?
  • What is the fundamental algorithm that prolog uses in seeking bindings that satisfy predicates?
  • What is "unification" ? What are the differences between prolog's =, =:=, ==, and is operators?
  • Why does the order in which prolog clauses are placed sometimes matter to the inference of variable/value bindings?
  
  
  
• Computer Architecture
  • Logic gates: What do they do?
  • How can the minterm expansion principle be used to design an arbitrary circuit? Why do AND, OR, and NOT gates suffice? Why does a NAND or NOR gate alone suffice to construct any logical function?
  • What is the von Neumann model?
  • How do latches and RAMs work?
  • Make sure that you can explain the inner-workings of a simple CPU.
  • What is an "assembly language"? How is it related to the computer's own "machine language"? What does an assembler actually do? What are "assembler directives"?
  • How are function calls and recursion implemented in assembly language using a stack?
  • What are the differences between ISCAL's copy, load, store, and lim commands?
  • Note that a reminder of any/all ISCAL directives will be provided, as needed, with the exam.
  
  
  
• Finite Automata
  • What is a deterministic finite automaton (DFA)? What does the name mean? What is the definition of a regular language?
  • You should feel comfortable building a DFA for a given regular language. Remember that the states can encode meaningful information about what the machine has seen so far.
  • What does "distinguishable" mean? What does "pairwise distinguishable" mean?
  • What does the Distinguishability Theorem state? How can it be used to prove that a specific DFA has the minimum possible number of states for the language that it accepts? How did we prove the Distinguishability Theorem?
  • What does the Nonregular Language Theorem state? How can it be used to prove that a given language is not regular? How did we prove this theorem?
  • What is an NFA? What does it mean for an NFA to accept a string? How can any NFA be converted to an equivalent DFA? What happens to the number of states?
  • What is a regular expression? How can regular expressions be converted into NFAs and then DFAs?
  • Make sure that you could design a simple digital lock as we did in class.
  
  
  
• Computability and Turing Machines
  • What is a Turing Machine? How does it operate? You should feel comfortable building a turing machine that will accept simple languages. What is the Church-Turing Thesis?
  • What does "countably infinite" mean and how are countably and uncountably infinite sets used to show that there exist uncomputable functions? Make sure that you understand all of the Cantor diagonalization arguments and why they are useful to us here.
  • Make sure that you know how to prove that a problem is uncomputable using the techniques described in class.
  
  
  

  Practice Problems

  1. Uncomputability Problems!

     You have been hired by Millisoft. Your boss, Gill Bates, drops by your spacious cubicle sipping a refreshing and stimulating Jolt Cola ("All the sugar, and twice the caffeine!"). Gill begins by reminding you that a decider is a program that takes an input and eventually halts and accepts (says "yes" to its inputs) or rejects (says "no" to its input). For example, a decider for the prime numbers would take a number (perhaps encoded in binary) as input and would eventually halt saying "yes" (it's prime) or "no" (it's not prime).

     1. "OK, so here's your first task," says Gill. "We're having a little programming competition in the company. The contestants are writing deciders which take as input a string of 0's and determine whether the number of 0's was a power of 2." You smirk, having written such a program in JFLAP just a short time ago yourself! "Here's what I need from you," says Gill. "I need a program which we'll call a Power of Two Decider Tester (POTDT). The POTDT takes as input a program. The POTDT then decides whether P is a legitimate decider for strings whose length is a power of 2. That is, the POTDT eventually halts and says yes if the program it received was a correct submission for this competition and otherwise the POTDT halts and says no. I need this POTDT program written by tomorrow at 6 AM." Prove to Gill that this cannot be done, not by 6 AM and not EVER! You may use diagrams to help explain your proof, but your proof must be clear, precise, and rigorous. Your submission on this and the following problem will be graded on clarity and precision of explanation.
        
     2. "Alright," says Gill. "Drats! In that case, I'd like you to write a program called a Regularity Checker (RC). The Regularity Checker takes as input a program P (e.g. a Turing Machine) and determines whether or not the set of strings accepted by P is a regular language. The RC must always halt with an answer of yes or no!" Prove to Gill that this too is impossible. Again, you may use pictures to help you explain your proof, but your proof must be clear, precise, and rigorous.
        
     
     
     
  2. DFAs The optional bonus problems from Assignment 12 are excellent review problems!
     
     
  3. ISCAL
     Write an ISCAL program that takes sorts an array of numbers from smallest to largest. You may assume that the array is placed immediately after the code in memory. You may assume that arg1 contains the address of the first element of the array and arg2 contains the address of the last element of the array.
     
     
  4. Prolog
     Write a prolog "rule" that takes as input a binary search tree of integers (represented as a list of the form [Root, LeftTree, RightTree] or []) and an integer X and says "yes" if X is in the tree and no otherwise.
     
     
  5. rex
     Write a rex function that takes as input a binary tree in which each leaf node is an integer and each non-leaf node is a function of two integers. Your function evaluates the the tree by recursively evaluating the left subtree, the right subtree, and then applying the function at the root to these two results. Thus, the output should always be a number.
     
     
  6. Java
     Consider a collection of nodes organized into a search tree. The search tree is not necessarily binary. In fact, each node can have up to MAXCHILDREN children.

        class Node
        {  
           public int key;    
           public Object data;
           public Object children[];
           public int num_children;
           public final int MAXCHILDREN = 100;
           
           Node(int key, Object data, Object children[])
           {
              this.key = key;
     	 this.data = data;
     	 children = new Object[MAXCHILDREN];
     	 num_children = 0;
           }
        }
        

     In this node class, key is a unique ID for the node, data is a reference to some Object and children is the array of the node's children.

     Consider a tree made of such of nodes in which the tree has no particular organization. That is, the tree is not sorted in any way. Write a method that takes as input the root of such a tree and reorganizes the tree so that every node has at most two children and for each node, its "left" subtree contains nodes with strictly smaller keys and its "right" subtree contains nodes with strictly larger keys. In addition, the tree must have height O(log n) where n is the number of nodes.

  
  
  Last modified December 2006