Lecture 20, Thu 03/13

Final Exam Logistics
* Final Exam next Wednesday 3/19 @ 12pm - 2pm in class
	* 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, you must present your Student ID
	and hand in your exam before exiting (it's your ticket out!)
* The final exam will be cummulative
* Types of Questions
    * True / False (if false, explain why)
    * Short answers
        * Briefly describe / define / state / ...
    * Given some code, write the output
    * Write code satisfying a certain specification
    * Given some algorithm we covered (or some variation),
    fill in the blank to make it work
    * Draw a diagram, write the state of something, ...
    * Multiple choice

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, append, ...)
    * Under-the-hood functionality of dictionaries vs. lists
    * List / String slicing [:]
    * Strings
        * Supporting methods (replace, split, find, ...)
    * Function definitions
    * Control structures
        * if, else, elif, for, while
* Testing
    * Test Driven Development (TDD) using pytests
* Python Errors
    * Syntax vs. Runtime
* Exceptions
    * Exception Types (NameError, TypeError, ZeroDivisionError, KeyError, ...)
    * Exception handling
        * try / except / raise
        * Flow of execution
        * Passing exceptions back to the function caller
        * Catching multiple exception types
        * Catching inherited type exceptions
* 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__, __gt__, __lt__, ...
    * Inheritance
        * Know the implementation and inheritance behvior of fields / methods
        and how to override inherited methods
        * Know the pattern on how to construct inherited classes
        * Know the hierarchy of types (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
    * 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
    * Able to write recursive solutions
* Linear Data Structures
    * Know implementations (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 implementation and O-notation analysis (best and worst-case
    scenarios) of various sorting algorithms
        * Bubble (optimized version), Selection, Insertion, Merge, Quick sort
* Trees
    * Terminology
    * Know min-heap / max-heap data structure (and underlying list
    representation)
    * Binary Trees
        * Know the nodes and references implementation
        * Tree traversals: pre, in, post order traversals
    * Binary Search Tree (BST)
        * Know BST property and how insertion order affects structure
        * Know various BST methods (put, get, deletion)
        * Know the behavior / implementation / performance