Computer Science 60
Study Guide for the Final Exam
Fall 2001

Below is study guide to help you prepare for the final exam. In addition to using this guide, we strongly recommend carefully reviewing your class notes and homework assignments.

You may bring an 8.5 by 11 sheet of paper to the exam with anything you want written on both sides of the sheet.

Object-oriented Programming in Java

• What is a constructor and when is it invoked?
• What does this refer to in a java method?
• 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 a Java interface? How are interfaces implemented?
• What is inheritance and why is it useful?
• Why are inner classes useful?

• Data Structures
• How are lists implemented?
• What is the difference between open and closed lists?
• What are Queues and Stacks? For what is each used?
• 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?
• What are the comparative advantages of lists vs. arrays.
• How can trees be implemented using lists and vice-versa?
• What are some ways of implementing directed graphs?

• 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 assignments.
• How can you formulate the solution to a problem 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 argument? What are anonymous functions and where are they useful?
• 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 breadth-first search implemented in rex?
• What is tail recursion and why is it important?
• What is an accumulator argument and why are they used?

• Logic & Logic Programming
• What is switching function? What are some ways to represent switching functions?
• What is a truth-table?
• What is a Boole-Shannon expansion?
• 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 can logic circuits be simplified, e.g. using Karnaugh maps?
• What is the difference between predicate logic and propositional logic?
• How can Prolog be used to query a database?
• What is unification?
• What is "backtracking"? How does it work in Prolog?
• What are some uses of setof in Prolog?
• What is the connection between backtracking and search?
• What is the connection between Prolog and functional programming?

• Grammars and Languages
• What is an inductive definition and why are they important?
• What are the purposes of a grammar?
• What is the relationship between a garmmar and parsing?
  
  
  
  
• Finite-State Machines
• What is the difference between a combinational circuit and a sequential one?
• What is a deterministic finite-state acceptor (DFA)? What does the name mean? What do the states in a DFA attempt to model in a real computer? What does the input tape in a DFA attempt to model? What is the definition of a regular language?
• How can you build a DFA for a given regular language? Remember that the states can encode meaningful information about what the machine has seen so far.
• Are all finite languages (languages with a finite number of strings) regular? Why?
• What is an NFA? What does it mean for an NFA to accept a string?
• We showed that NFA's are no more powerful than DFA's in the sense that any NFA can be automatically converted into a DFA that accepts the same language. Be able to explain how this works and make sure that you can perform this conversion process.
• What is a regular expression? Why are regular expressions useful? How can a regular expression be converted into an epsilon-NFA?
• How can you use DFA's to build circuits with memory (such as a digital lock)?

• Computability and Turing Machines
• What is a Turing Machine? What is the Church-Turing Hypothesis?
• Which model of computation more closely models a real computer: A DFA or a Turing Machine? Why?

• Computer Architecture
• How does a processor work? Specifically, what is the IP, what is the IR, and what are general registers?
• 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?