Lecture 20, Thu 12/05

Final Exam Logistics
* Final Exam next Thursday 12/12, in class 4 - 6pm
     * Closed book, closed notes, no electronic devices
     * Please write LEGIBLY (if we can't read it, we can't grade
     it)
     * When leaving the room, pack up your stuff, present your
     student ID when turning in your exam
* Final exam will be cummulative
* Types of Questions
    * True / False (if false, briefly explain why)
    * Short answer
        * Briefly describe / state / define ...
    * Given some code, write the output
    * Write code satisfying a certain specification
    * Given some algorithm we covered in class, fill in the
    blank to make it work
    * Draw diagrams
    * Multiple choice

Topics
* Python Basics
    * Types
        * int, float, boolean, strings, lists, sets, dict, ...
        * conversion functions (int(), float(), str())
        * Mutable vs. immutable
    * Relational / Logical operators (==, <=, >=, >, and, or, ...)
    * Python Lists
        * Supporting methods (count, pop, ...)
    * Understand under-the-hood functionality of dictionaries
    and lists
    * List / String slicing [:]
    * Strings
        Supporting methods (replace, split, find, ...)
    * Function definitions
    * Control structures
        * If, else, elif for, while
Testing
    * Test Driven Development (TDD)
    * pytest
Python Errors
    * Syntax vs. Runtime
Exceptions
    * Exception types (NameError, TypeError, ZeroDivisionError,...)
    * Exception handling
        * Try / except / raise
        * Flow of execution
        * Passing exceptions to function callers
        * Catching multiple exceptions
        * Catching inherited type exceptions
* Object Oriented Programming
    * Defining Python classes and methods
    * Class constructors
        * Definining and initializing default parameters
    * Shallow vs. Deep Equality
        * Overloading __eq__ method
    * Overloading operators
        * __str__, __add__, __le__, __ge__, __gt__, __lt__, ...
    * Know the implementation and inheritance behavior of
    fields / methods and how to override inheritence methods
    * Know the pattern on how to construct inherited classes
    * Know the hierarchy of types (how this affect exception
    handling)
    * Know how to explicitly call super / base class methods
    * Method lookup
* Algorithm Analysis and O-notation
    * Know how to derive O-notation for various data structures
    and code segments
* Binary Search
    * Search for items in a SORTED list
    * Know implementation and O-notation
* Recursion
    * Understand how recursive algorithms are managed by the call
    stack
    * Able to derive O-notation for various recursive functions
* Linear Data Structures
    * Know implentation (as covered in textbook/lecture) and
    O-notation for various functionality of data structures
        * Stacks, Queues, Deques, Linked lists, Ordered Linked
        Lists
* Sorting Algorithms
    * Know the implementation and O-notation (best and worst cases)
    of various sorting algorithms
        * Bubble (optimized version), Selection, Insertion, Merge,
        Quick
        * Know the mechanics of algorithms (or parts of).
* Trees
    * Terminology
    * Know min-heap / max-heap data structure implementation
    (and underlying list representation).
    * Binary Trees
        * Know the nodes and references implementation
            * Tree traversals: pre, in, post order traversals
    * Binary Search Trees
        * Know the BST property and how insertion order affects
        the structure
        * Know various BST methods (put, get, deletion).
            * Understand performance, behavior, implementation