Lecture 20, Thu 06/03

Final Exam Logistics
* The final exam will be on Gradescope as an online assignment. The window to take
the final exam will start at 4pm PST and close at 6pm PST on Tuesday 6/8.
* The final exam will be cummulative (with an emphasis on latter topics).
* The final exam will be in a similar format as the homeworks and quizzes on
Gradescope (except it will be longer and cover more material).
    * True / False
    * Multiple Choice
    * Write code satisfying a certain specification
    * Short Answers (briefly define, explain, etc)
    * ...
* We will be monitoring Piazza during the final exam time.
    * For any CLARIFYING questions, you may post a PRIVATE question on Piazza where
    we will answer them.
    * If there needs to be a change / modification in any question, then we will
    post any clarifications publicly on Piazza (Piazza will send everyone an email)

Topics
* Python Basics
    * Types
        * int, float, boolean, strings, lists, sets, dictionaries, ...
        * conversion functions (int(), float(), str(), ...)
        * Mutable vs. Immutable
    * Relational / Logical Operators (==, <, <=, >=, >, and, or, ...)
    * Python Lists
        * Supporting methods (count, pop, ...)
    * Understand under-the-hood workings of dictionaries vs. lists
    * List / String slicing [:]
    * Strings
        * Supporting methods (replace, split, find, ...)
    * Function definitions
    * Control structures
        * if, else, elif, for, while
* Testing
    * TDD
    * pytests
* Python Errors
    * Syntax vs. Runtime
* Exceptions
    * Exception types (NameError, TypeError, ZeroDivisionError, ...)
    * Exception handling
        * try / except / raise
        * Flow of execution
        * pass exceptions to the function / method caller
        * Catching multiple exception types
        * Catching inherited exception types
* Object Oriented Programming
    * Defining Python Classes and methods
    * Class constructors
        * Defining / initializing default parameters
    * Shallow vs. Deep Equality
        * overloading __eq__ method
    * Overloading operators
        * __str__, __add__, __le__, __ge__, ...
    * Inheritance
        * Know the implementation and inheritance of fields and methods, and how
        to override inherited methods
        * Know the pattern on how to construct inherited classes
        * Understand the hierarchy of types (and also how this affects exception
        handling)
        * Understand how to explicitly call super / base class(es)' methods
* Algorithm analysis and O-notation
    * Know how to derive the O-notation for various data structures and code
    segments
* Binary Search
    * Search for items in a SORTED list
    * Know implementations 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 implementation (as discussed in textbook / lecture) and O-notation for
    various functionality of data structures
        * Stacks, Queues, Deques, Linked Lists, and Ordered Linked Lists
* Sorting Algorithms
    * Know the implementation and O-notation analysis (best and worst-case scenarios)
    of various sorting algorithms
        * Bubble Sort (including optimized version), Selection Sort, Insertion Sort,
        Merge Sort, and Quick Sort
* Trees
    * Terminology
    * Know min / max heap data structure implementation (and underlying Python
    list representation)
    * Binary Trees
        * Know the nodes and references implementation
        * Tree traversals: pre, in, post order traversals
    * Binary Search Tree
        * Understanding the implementation, BST property, and how insertion order
        affects the structure
        * Understanding how various BST methods work (and its implementation) (put,
        get, deletion)