Lecture 19, Thu 12/04

Final Exam Logistics
* Final Exam next Wednesday 12/10, in class 12pm - 2pm
* Please write LEGIBLY
* When leaving the room, you must present your Student ID and hand
in your exam before leaving (it's your ticket out)
* Types of Questions
    * True / False (if False, explain why)
    * Short answer
        * Briefly describe / define / state / ...
    * Given some code, write the output
    * Write the code satisfying a certain specification
    * Given some algorithm we covered, fill in the blank to make it
    work
    * Draw a diagram / ...
    * Multiple choice

Topics
* Python Basics
    * Types
        * int, float, bool, strings, lists, sets, dictionaries, ...
        * coversion functions (int(), float(), str(), ...)
        * Mutable vs. Immutable
    * Relational / Logical Operators (==, <, <=, >=, and, or, ...)
    * Python Lists
        * (cout, pop, append, ...)
    * Dictionaries and lists (under-the-hood workings)
    * Strings
        * Supporting methods (replace, split, find, ...)
    * Function definitions
    * Control structures
        * if, else, elif, for, while
* Testing
    * 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 caller
    * Catching multiple exception types
    * Catching inherited type exceptions
* Object Oriented Programming
    * Define Python Classes and methods
    * Class constructors
        * Defining / initializing default parameters
    * Shallow vs. Deep Equality
        * Overload __eq__ method
    * Overload operators
        * __str__, __add__, __le__, __lt__, ...
    * Inheritance
        * Know the implementation and inheritance behavior of fields /
        methods and how to override inherited methods
        * Know the pattern on how to construct inherited classes
        * Know the hierarchy of types (and how this affects exception
        handling)
        * Know how to explicitly call super / base class(es) methods
* Algorithm Analysis and O-notation
    * Know how to derive the O-notation from a Time function for
    various data structures and code segments
* Binary Search
    * Search for items in a SORTED list
    * Knowing the implementation and O-notation
* Recursion
    * Understand how recursive algorithms are managed by the call stack
    * Able to derive O-notation for variour recursive functions
* Linear Data Structures
    * Know implementations (as covered in the 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-ntation (best and worst cases) of
    various sorting algorithms
        * Bubble Sort (including optimized version), Selection Sort,
        Insertion Sort, Merge Sort, and Quick Sort
* Tree Algorithms
    * Terminology
    * Know min-heap / max-heap data structures (and underlying list and
    conceptual binary complete tree)
    * Binary Trees
        * Know the nodes and references implementation
        * Tree traversals: pre, in, and post order
    * Binary SEARCH Trees (BST)
        * Know BST property and how insertion order affects the
        structure
        * Know various BST methods (put, get, deletion)
            * Note: The code for deletion wasn't covered in this quarter
            but put and get were covered