CSE 413 Autumn 2012 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.
  • Inheritance, implementing objects and dynamic dispatch
    • Implementing message send: this or self implicit parameters, implementing objects on top of non-OO languages
    • Multiple inheritance, interfaces, and mixins: tradeoffs, issues.
    • Type systems for object-oriented languages (Java, C++).
    • Dynamic dispatch: method lookup in dynamic languages like Ruby; differences in statically-typed languages like Java, C++; how inheritance works in both kinds of systems, what self is all about.