Exam Reminder

The final exam will be given Tuesday, Dec 14 from 2-5pm in the usual classroom.  

The exam is closed book, closed notes, etc.  You may not use any resources for the final except 
you may use up to two 8.5 by 11 sheets of paper with anything you want HANDWRITTEN on both sides of the sheets.

As on previous exams, you may use a computer to type your answers (subject to the same rules as previous exams).

We will spend part of class on Thursday for a review session. 

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 best way to study is to re-do the homework problems on paper.  This will simulate the exam experience.  The exam will be comprehensive.

Study Guide 

Object-oriented Programming in Python

• What is a constructor and when is it invoked?
• What does self (typically) refer to in a python class?
• What is inheritance, why is it useful, and how does it work?
• You should be comfortable with box-and-arrow diagrams to illustrate how Python organizes references and data in computer memory. What is the difference between the stack and the heap?
• How do reference counting and mark-and-sweep garbage-collection algorithms work? What are the advantages/disadvantages of each?  Which one does Python use?
• How do GUIs work, generally?  (and what is a GUI?)  What is event-driven programming?  What does the after function in tkinter do and when is it necessary in a Python GUI?
• What is the difference between Python's input and raw_input functions?
• You should be comfortable writing programs in Python similar to the complexity of your homework problems or quiz problems.  These programs might incldue loops (nested), 2D lists (lists of lists), files, input and output from the user, etc.

Abstract Data Types (ADT's), Data Structures

• What is an ADT ("abstract data type") and what is a data structure? How are these concepts different?
• What are the ADT's Queue and Stack (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 linked lists and binary trees work? What is a dictionary (in Python) and how do you use it?  In particular, make sure that you could write code for data structures such as these including the more challenging ones such as inserting, deleting, and finding data in a binary search tree.
• For each ADT above, which data structures could be used to implement it? Make sure that you can analyze the big-O running time of any operation for any given data structure above.

Searching, Sorting (and other algorithms) and Big-O

• 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 advantages of one over the other (and vice versa)?
• What is Big-O running time?  Make sure you can analyze the Big-O running time of an algorithm or a piece of code.
• 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)
  
  

  You might want to write these on your sheet...
• What is a recurrence relation and how can it be used to find Big-O running time?  Be sure that you could express and solve simple recurrences using the "tree" method described in class.
• You should be familiar with the lower-bound on the running time of comparison sorting algorithms.
• You should be able to analyze, implement and compare different sorting algorithms that we discussed in class including merge sort, insertion sort, CS5 sort, selection sort and "check sort".
• What is a Markov process?  How does the "order" of the process determine its output?  For what kinds of tasks are Markov processes reasonable models?
• What is the difference between "tractable" and "intractable" problems?  Why do we care?

Logic Programming in Prolog

• Prolog "programs" are a collection of facts and rules. Make sure that you understand all of the examples that we saw in class and on homework.
• Why does prolog sometimes produce multiple identical answers to a query?
• What is the fundamental algorithm that prolog uses in seeking bindings that satisfy predicates?
• What is "unification" ? What are the differences among prolog's =, =:=, ==, and is operators? Similarly, what are the differences between \+, \==, and =\=?
• Why does the order in which prolog clauses are placed sometimes matter to the inference of variable/value bindings?
• What types of problems is Prolog well-suited for?
• You should feel comfortable composing a Prolog solution to a (moderately-sized) problem similar to the ones we did in class and on the HW.
• What does it mean for a logical statement (that may include variables) to be satisfiable or unsatisfiable or a tautology?
• You should understand an algorithm that can determine which of the three categories above a particular logical statement falls under.

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.
• What types of problems is Racket well-suited for?
   

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?
  

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?
• 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? How can a DFA be converted to a Regular expression?
• What are some practical applications of DFAs?

Computability and Turing Machines

• Know the proofs that the "halting problem" and "autograder problem" are undecidable.  
• What does it mean to be countably infinite or uncountably infinite?  Know how to prove that a set is countably or uncountably infinite, and what implications this distinction has for computer programs (vs. the set of all problems).
• 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?
• Know how to prove a problem is undeciable via reduction from the Halting Problem (or any other undecidable problem)

High-level design and testing/debugging strategies

• Make sure you know what constitutes a good test case
• Be comfortable breaking a problem down to a level where implementation would be straightforward
• Given piece of (potentially complicated) code, be able to suggest checks that would reveal potential bugs in the code.