Below is a study guide 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.

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

• 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 is static and where and why would it be used?
  • What is the difference between deep copy and shallow copy and what are the advantages and disadvantages of each?
  • What is inheritance, why is it useful, and how does it work?
  • What is an abstract class and why is it useful?
  • How are the terms extends, super, and implements used in Java?
  
  
  
• Big Oh
  • What does Big Oh mean informally? Why are we interested in a definition like this?
  • What is the formal definition of Big Oh?
  • You should be familiar with the properties of logarithms (those that we used in class and on the homework).
  • What is the height of a perfectly balanced binary tree with n nodes? Make sure that you can prove this formally.
  • Why does the height of a binary tree with n nodes remain O(log n) even if some large fixed fraction of the nodes (say 90%) always goes on one side of the tree and the remaining nodes go on the other? Be able to prove this.
  • Why are self-balancing trees important to us and what's the very general idea? (No need to know the specific rules for rotating, etc.)
  
  
  
• 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, Stacks, and Priority Queues? (What operations does each ADT support?)
  • How are function calls handled by the operating system using a stack? Why does this make recursion very simple to handle?
  • 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, bit vectors, linked lists, binary trees, and heaps 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 and inserting and extracting the maximum in a heap.
  • 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. For example, if we used an unsorted linked list to implement a Priority Queue, you should be able to explain why insert would take O(1) time but extracting the maximum would take O(n) time.
  • How does heapsort work? How can an array be used in place of a binary tree to implement a heap? Be able to derive the big Oh running time of this clever sorting algorithm. How does it compare to the running time of minsort?
  • How does a reference count garbage collector work? How does a mark and sweep garbage collector work? In what cases might they behave dirently?
  
  
  
• 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 on Assignments 7-8. 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, drop, any, some, ... . 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 are breadth-first search and reachability implemented in rex?
  • What is tail recursion and why is it important?
  • What is the "merge" technique for combining data from two sorted lists and what is its running time?
  
  
  
• 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?
  
  
  
• Grammars and Parsing
  • What is a grammar and why are grammars useful?
  • What is a parse tree?
  • How does the recursive descent parsing algorithm work? Be sure that you understand it well enough that you could explain each step of the algorithm for any given grammar. Remember that the algorithm returns a parse tree and the remaining tokens or "residue".
  
  
  
• 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?
  • How do S-R latches and D-latches work?
  • What is a RAM and how does it work?
  • How does a CPU work? Specifically, what is the IP (or PC), what is the IR, and what are registers? What are the five basic operations that occur for each instruction and how does the corresponding circuitry work?
  • 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 directives?
  
  
  
• Finite Automata
  • What is a deterministic finite automaton (DFA)? What does the name mean? What is the definition of a regular language?
  • 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?
  • What is a regular expression? Why are regular expressions useful? How can a regular expression be converted into an NFA and an NFA into a DFA?
  
  
  
• Computability and Turing Machines
  • Know the proofs that the "halting problem" and "autograder problem" are undecidable.
  • 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 Hypothesis?
  
  
  
• Algorithm Analysis
  • Two useful formulae for analyzing algorithms are the formula for the arithmetic progression

          1 + 2 + 3 + ... + n = n(n+1)/2 = O(N^2)
          

    and for the geometric progression

          x^0 + x^1 + ... + x^k = x^(k+1) - 1 / x-1 = O(x^k)
          

  • Make sure that you understand the algorithm analysis examples we saw in class.
  • How did we prove that every comparison-based sorting algorithm requires at least n log n running time (asymptotic worst-case running time)?
  • What is a recurrence relation? Be sure you can "unwind" recurrence relations to find big-Oh running times for recursive programs.
  • Also, be sure you can analyze the running time of nested loops to find asymptotic performance.