[CS61B] Notes for class 5-Linked lists

Array-based lists
Advantage: very fast access of each item
2 disadvantages:
    (1) Insert item at beginning or middle takes time proportional to length of array.
    (2) Array has a fixed length.                        

Linked lists (a recursively data type)
Made up of nodes. Each node has:
(1) an item
(2) a reference to next node in list

Linked lists vs. Array lists
Advantages of linked lists:
(1) Inserting item into middle of linked lists takes constant time, if you have a ref to previous node.
(2) List can keep growing until memory runs out.

Disadvantage of linked lists: Finding n-th item of a linked list takes time proportional to n. (Start at head, walk n-1 nodes.)

The "public" and "private" keywords
Private method or field: invisible and inaccessible to other classes.
Why?
(1) To prevent data form being corrupted by other classes.
(2) You can improve the implementation without causing other classes to fail.


The interface of a class: prototypes for public methods, plus description of their behaviours.

Abstract Data Type (ADT): A class with well-defined interface, but implementation details are hidden from other classes.

Invariant: A fact about a data structure that is always true. "A Date object always stores a valid date." Enforced by allowing access only through method calls.
If we don't have any restriction of a field, than we could declare this filed to "public"; Otherwise, we should declare it as "private."

Not all classes are ADTs! Some classes are data storage units, no invariants; field can be public.

Double-Linked Lists
Insert and delete items at both ends in constant running time.

Sentinel: A special node that does not represent an item. It points to the first and last nodes.

[CS61B] Notes for class 6-Stack frames

The heap stores all objects, including all arrays and all class variables.

The stack stores all local variables, including parameters.

When a method is called, Java creates a stack frame (aka activation record); stores the parameters and local variables.

Stack of tack frame.

Garbage collection only performs on heap.

When a method finishes, its stack frame is erased.

Method "Thread.dumpStack()": Prints a stack trace of the current thread to the standard error stream. This method is used only for debugging.

Parameter Passing
Java passes all parameters by value: copied.
When parameter is a reference, the reference is copied, but the object is shared.

[CS61B] Notes for class 4-Iteration and array

Declare arraies:
int[] a, b[]; //a is 1D array, b is 2D array

Constant:
"final" keyword: value that can never be changed.
BAD: if (month == 2)
GOOD: public final static int FEBRUARY = 2;
              if (month == FEBRUARY)

Output data to csv files

There is a little difference between the code implemented in Python 2 and 3.

[CS61B] Notes for class 3-types, conditionals, iteration and arrays

Primitive types: (don't have to create an object to store it)
byte : 8-bit integer    => -128~127
short:16-bit integer   => -32,768~32,767
int    : 32-bit integer  => -2,147,483,648 ~ 2,147483647
long : 64-bit
float : 32-bit
double: a 64-bit floating-point number
boolean: "true" or "false" ("True" or "False" in Python)
char: a character, 2byte, non-signed

e.g.
long x = 43L;

double & float values must have a decimal point:
double x = 10.0;
float x = 43.9f;

                               Object types                            Primitive types
-------------------------------------------------------------------------------------------
Contains a              reference                                   value
How defined?        class definition                          built into Java
How created?         "new"                                        "6", "3.4", "true", etc.
How initialized?    constructor                                default (usually zero)
How used?            method                                      operators("+", "*",...)


Function: methods declared to return a non-void type.

char c = new char[4];
c[4] = 'x'; //Run-Time error

The size of an array cannot be changed once it has been created.

[ML] Precision / Recall

For classification problem

Precision:
    True positives                            True positives
------------------------   =   ---------------------------------------
#predicted positives         True positives + False positives

Recall:
    True positives                            True positives
------------------------   =   ---------------------------------------
  #actual positives            True positives + False negative


There is a tradeoff between precision and recall.
One way to compute the precision and recall is using F_1 score
                           precision * recall
F_1 score = 2 * -----------------------
                           precision + recall

Reference: https://www.coursera.org/learn/machine-learning/lecture/tKMWX/error-metrics-for-skewed-classes