CS214 theory must know questions

Python makes use of duck typing. Explain what type hints are in Python, and what shortcoming of duck typing they attempt to alleviate.

Type hints are optional annotations that indicate the expected types of variables, function parameters, and return values. They help alleviate the drawback of duck typing that type errors are often only detected at runtime by allowing static analysis tools to catch type related errors before runtime

Explain why we must use an immutable type for a symbol table's keys.

Keys must be immutable so their hash value and equality do not change after insertion. If a key changes, it may no longer be found in the symbol table.

Advantages and Disadvantages of Immutability

adv: Immutability provides safety & predictability as the objects cannot change unexpectedly.

disadv: Immutability leads to an increase in memory usage and slower performance.

magnitude formula

math.sqrt(self.dot(self))

plotting formula

log(T) = mlog(N) + c

6 dunder methods

gt,ge,eq,ne,lt,le

recursion relation formula

T(N) = 2T(N/2) + O(N)

best complexity for merge sort

O(N log N)

BST rule

smaller: left, bigger: right

OOP principle of encapsulation naming convention

leading underscore: indicates that the field is meant to be private. Signals to the developer that the field is internal to the class and must be treated as private

advantages of OOP principle of encapsulation

improved code maintainability and enhanced data integrity