CSE 413 16au Final Exam Topics

This is a summary of topics that could appear on the final exam. The exam will focus more on things covered since the midterm, although earlier parts of the course will appear, particularly things not covered on 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 is closed book, closed notes. We will provide any necessary reference material on the exam, but you should know common Ruby programming idioms such as how to use each to iterate through a collection.

  • 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.
    • Modules and mixins, namespaces, important mixins: Enumerable and Comparable and how these interact with each and <=> methods in classes.
    • Duck typing: what do types mean in a dynamically typed language like Ruby? Tradeoffs compared to languages like Java.
    • Inheritance and overriding: defining subclasses, overriding methods, how a method call is resolved in Ruby.
  • 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, pros and cons of reference counting vs garbage collection algorithms like mark/sweep, basic concepts behind generational garbage collection and why it is effective.