CSE 413 23sp Final Exam Topic List

This is a summary of topics that could appear on the final exam. The exam will focus mosty on things we've done since the midterm, although earlier parts of the course may appear, particularly topics not included in the midterm. You are responsible for everything covered in lectures, notes, slides, sample code, and on the homework assignments.

As with the midterm, the exam will be closed book, except that you may have two 5x8 (or smaller) index cards with whatever notes you wish written on both sides for reference. The notes must be hand-written, i.e., no computer printouts, no scanned/reduced notes, and no electronic devices or other technology. You can use the notecard you had for the midterm as one of these cards or you can have two completely new cards. We will provide basic reference material on the exam as needed, but you should know common Ruby programming idioms such as how to use each to iterate through a collection.

• Racket & MUPL - some coverage is fair game since MUPL was due after the midterm and there were important concepts such as streams that were not included on the midterm to avoid making that exam too long. You should still know key Racket concepts, including use of memory and closures. Specific additional topics since the midterm:
  • Racket structs and how to use them.
  • Interpreters. What an interpreter does, interpretative evaluation of programs, maintaining environments and handling closures. You should be familiar with both the whiteboard discussions in class and the implementation in the MUPL assignment. (You don't need to memorize the MUPL data types like int, apair, call, etc.; if these are needed for a question a summary will be provided.)
• Ruby
  • Basic concepts: objects and messages (everything is an object), dynamic typing.
  • Containers: arrays and hashes.
  • Blocks and iterators: blocks, block parameters, using iterators (each) to sequence through a container, using times and upto/downto for repetition and counting.
  • Ruby class definitions: defining classes, initialize and other methods, creating instances with new, instance variables (syntax and use), accessors and mutators, attr_reader and attr_writer.
  • Blocks, procs, and closures: using a block, yield (with or without arguments), difference between blocks and first-class closures created with Proc.new or lambda.
  • Duck typing: what do types mean in a dynamically typed language like Ruby? Tradeoffs compared to statically typed languages like Java.
  • Inheritance and overriding: defining subclasses, overriding methods, how a method call is resolved in Ruby.
  • Modules and mixins, namespaces, important mixins: Enumerable and Comparable and how these interact with each and <=> methods in classes.
• Grammars
  • Specification of languages using context-free grammars and regular expressions.
  • Regular expressions: basic operations, using r.e.'s to specify lexical grammar of typical programming language tokens.
  • Context-free grammars: terminals vs. non-terminals, productions, derivations (leftmost and rightmost), ambiguities and ways to deal with them.
• Scanners, parsers, and interpreters
  • Interpreters vs compilers.
  • Scanners and parsers: why split the recognizer into these two parts? Tokens as scanner/parser interface.
  • Scanners: principle of longest match, using the grammar to design a scanner, DFAs (state diagrams) for describing the operation of a recognizer.
  • Parsing: reconstructing derivations, abstract vs. concrete syntax; recursive-descent parsers, dealing with issues like left recursion and common prefixes in productions.
• Garbage collection
  • Basic idea of reachable (live) data; root set of variables and other data that form the starting point for discovering the reachable data, then how to locate other live data from these.
  • Pros and cons of reference counting vs garbage collection algorithms like mark/sweep.
  • Tradeoffs between various kinds of gc algorithms like mark/sweep vs generational collectors.