- java file read by java compiler, and compiler generates byte codes, and processed by JVM, and process on operating systems
- program.java -> java compiler -> program.class ->jvm -> program
- java virtual machine is platform dependent on the operating systems and hardware
- any program you might want to write
- objects, methods, inheritance[^1],encapsulation[^2],polymorphism[^3]
- functions and modules
- graphics, sound, and image i/o
- arrays
- conditionals and loops
- math text i/o
- primitive data types and assignment statements
explanations: 1. creating new classes in existing class 2. integrate data and the code that acts upon them as a single unit, other classes cannot access to it 3. greek words many forms, the ability of objects take on many forms/ different objects respond to the same methond call in multiple ways
- Just start
- Work hard to learn code
- Concepts and topics build on one another so take your required classes as fast as possible, and back to back
- Brakes will break you
- Work smarter and efficiently
- Master the basics, dont move forward unless you understand something fully, this is always the case in AMCS
- Things worth having dont come easily
- Always come to your own conclusion, ppl said suck things often which disturbs you
- You can solve any problem w/ enough time and effort
- Doing is the best way to learn coding
- Train your ability to translate thoughts into code
- println() means start a new line but print will not add a new row
- sum += i means sum = sum + i
- t *= (x/i) means t = t *(x/i) which is used in Taylor expansion
- data type: a set of values and a set of operations on those values
eight primitive data types: byte,short,int,long,float, and double (bit increased in order) boolean (true or false) char(16 bit unicode)
string is not primitive but still built-in
- string: for input and output * Java like put things into string
- int: integers, for math calculations
- stored by binary number system; a bit is a single binary digit (0/1)
- This sequence of bits ( b_n 2^n + b_{n-1} 2^{n-1} + \dots + b_2 2^2 + b_1 2^1 + b_0 2^0 ) represents an integer.
- double: with floating points, for science and math apps
- boolean: true or false, for decision-making in program
java is statically typed programming check types at compile time while the dynamically typed one check at run-time
- a data type automatically converted into another data type at compile time
- destination type should be bigger than source type, as known as widening conversion
- Integer.parseInt()
- toString()
- conversion set by programmer
- destination is smaller than source, as known sa narrowing conversion
x = (int) a * b
arithmetic, comparison, logical, increment,conditional,assignment, compound assignment
- the sequance of statements that are actually executed in a program
- conditionals and loops enable us to choreograph control flow
execute certain statements depending on the values of variables
- evaluate a boolean expression
- if true, execute a statement
- if false, use else option
execute statements repeatedly until certain conditions are met
- boolean
- true, execute,repeat
- evaluate an initialization statement; eg: int a = 0
- boolean
- true, execute,increment repeat if satisfies boolean
// This demonstrates "every for loop has a while statement
// for loop is more compact obviously
public class PowerOfTwo {
public static void main(String[] args){
int v = 1;
int n = Integer.parseInt(args[0]);
for (int i = 0; 1<= n; i++){ // the difference lies in the initialization statement
System.out.println(i + " " + v);
v = 2*v;
}
}
}
public class PowerOfTwo {
public static void main(String[] args){
int v = 1;
int n = Integer.parseInt(args[0]);
int i = 0;
while (i<= n;){
System.out.println(i + " "+ v);
v = 2*v;
i++;
}
}
}- Any statement within a conditional or loop may ifself a conditional or loop
- enables complex control flow
- adds to challenge of debugging
- programming is primarily a process of finding and fixing mistakes
- is challenging because conditionals and loops increase the number of possible outcomes and most programs contain numerous conditionals and loops, with nesting
- Good news: conditionals and loops provide structure that helps us understand our programs
Step of Debugging a program
- syntax errors: java compiler can help you find out, eg: terminating semicolons
- semantic and runtime
- testing
- performance: fast enough to solve your problem, increasing problem sizes to find out
explanation time: compile time is the phase in a program's lifecycle when the source code is translated into machine code before the program is run run time is on the contrary, period of program actually executing When initialize an array with specific values as compile time,, it dirrectly provides source code the contents of the array
- store and process (manipulate) huge amounts of data
- my first data structure: an arrangement of data that enables efficient processing
- def: an indexed sequence of values of the same type
a computer's memory is an indexed sequence of memroy locations
- each primitive type value occupies a fixed number of locations
- array values are stored in contiguous locations
// if copying an array w the same values
double [] a = new double [n];
double[] b = new double [n];
for (int i = 0; i<n; i++)
b[i] = a[i];
// however if just denote b = a, it indicates b and a are the same arrays- doubly-indexed sequence of values of the same type
- declare: double [][] a;
- create an array of a given length: a = new double [1000] [1000];
- refer to an array entry by index
- refer to the number of rows: a.length;
- refer to the number of columns: a[i].length
- refer to row i: a[i];
// vector addition / 1D array
double [] c = new double [N];
for (int i = 0; i< N;i++)
c[i] = a[i] + b[i];
//Matrix addition / 2D array
double [] [] c = new double [N][N];
for (int i = 0; i<N; j++)
c[i][j]= a[i][j] + b[i][j];
// vector dot product
double sum = 0.0;
for (int i = 0; i<N; i++)
sum += a[i]*b[i];
// matrix multiplication
double [][] c = new double [N][N];
for (int i = 0; i<N; i++)
for (int j = 0; j < N; j++)
for (int k = 0; k < N; k++)
c[i][j]+= a[i][k]* b[k][j];public class Deck {
public static void main(String[] args) {
String[] SUITS = {
"Clubs", "Diamonds", "Hearts", "Spades"
};
String[] RANKS = {
"2", "3", "4", "5", "6", "7", "8", "9", "10",
"Jack", "Queen", "King", "Ace"
};
String[] deck = new String[52];
for (int i = 0; i < 13; i++) {
for (int j = 0; j < 4; j++) {
deck[4*i + j] = RANKS[i] + " of " + SUITS[j];
}
}
// print shuffled deck
for (int i = 0; i < n; i++) {
System.out.println(deck[i]);
}
}
}It seems that I got confused about some concepts when I had week 3 test1; here are some things i need to mention again:
- creating one-dimensional array of length n will also initialize n elements w/ default values
- two-dim arrays are not necessarily rectangular. In java, two-dim array is an array of arrays, so each row can have a different number of elements.
- int [] c = b seems equal to c = b which means change in c also = change in b
- i personally feel proud of myself when debugging this BinomialCoefficient.java; it includes jagged arrays and an error Arrayoutboundsindexexception that new to me
- jagged/ragged arrays in case you forget
- boolean checks whether an element in an array by using eg：birthdays[birthday]= true, another "milestone" problem I'm solving, proud of myself BirthdayParadox
to install std.jar into intellij
- Open your installed IntelliJ IDEA Project and.
- Go to the File > Project Structure.
- Select Modules at the left panel and select the Dependencies tab.
- Select the + icon and select 1 JARs or Directories option.
- select your JAR file or you can select the directories.
- Click on the OK button.
interact w/ outside world through manipulating text,image, and sound
-
input: command-line arguments
-
standard input stream: an abstraction(an opinion) for an infinite input sequence
-
standard output: some methods like System.out.print() and System.out.println()
-
interactive input: (1) prompt user to type inputs on standard input stream; (2) mix input stream and output stream
public class AddTwo{
public static void main(String [] args){
StdOut.print("Type the first integer");
int x = StdIn.readInt();
StdOut.print("Type the second");
int y = StdIn.readInt();
int sum = x+y;
StdOut.println("There sum is "+ sum);
}
}redirection: keep data in files on the computer
- redirect standard output to a file
- from a file to standard input
piping: avoid saving data
- connect standard output of one program to standard input of another
iterated function systems: simple iterative computations yield patterns that are similar to those found in the natural world
- clear the screen
- move the object
- draw the object
- display and pause briefly
modular programming: organize programs as independent modules that do a job together
- input--> output w/ side effects
- example: built-in functions(Math.random(), Math.abs()), I/O libraries
- library: a set of functions
- module: a .java file
- scope: a variable's scope is the code following its declaration, in the same block(keep scope low to better understand the code)
- put a copy of Gaussian.java in your working directory
- call Gaussian.pdf() or Gaussian.cdf() from any other module in that directory
- learn to use OS "classpath" mechanism if found w/ too many copies
fundamental abstractions:
- client: library's methods
- API (applications programming interface): defines signatures, describes methods
- implementation: module containing java code
- base case: return a value for small positive integer N
- reduction step
- save subproblem's answer to avoid exponential waste pitfalls
- performance
- sorting and searching
- stack and queue
-
binary logarithms:
- the number of bits in the binary representation of N is
$$1 + lg N$$ - bit (binary digit) is the smallest unit of data that a computer can process and store, a byte is a sequence of eight bits
- the number of bits in the binary representation of N is
-
doubling method
- to estimate the time of simulation
- for debugging?
- abstract data types:a data type whose representation is hidden from the client
- OOP
- create ur own data types (representation is hidden from the client)
- use them in ur programs
- clients can use ADTs w/o knowing implementation details
- a natural vehicle to study abstract models of the real world
- encapsulation
- separate client from implementation
- enable modular programming
- facilitate debugging
- clarify program code
- whitelist case: use of
compareTo()which is based on the unicode value of each character in the strings. return 0 is the string is equal to the other string - binary search
- sorting: rearrange items into ascending order
- Moore's law: the number of transistors in an integrated circuit doubles about every two years
- implications: memory size doubles
- processor speed doubles every two years
- scalability: an algorithm scales if its running time doubles when the problem size doubles
- bottom line: need algorithm scales to keep pace w/ Moore's law.
- mergesort:
- divide array into two halves
- recursively sort each half
- merge two halves to make sorted whole
- longest repeats in a string(LRS)
- form suffix strings (suffix of string: any substring of the string which includes the last letter)
- sort suffix strings
- find longest lcp among adjacent entries
- two data types for manipulating arbitrarily large collections of jects
- each is characterized by four operations:
create the collection,
insert an item,
remove an item,
test emptiness
- always remember the graph that shows stack and queue
- take in and out at the beginning
- add an item to the collection
- remove and return the item most recently added
- test if the collection is empty
- return the size of the collection
- postfix arithmetic expression evaluation
- value: push onto the stack
- operator: pop operands, apply operator, push the result
import java.util.Stack;
public class Postfix {
public static void main(String[] args) {
Stack<Double> stack = new Stack<Double>();
while (!StdIn.isEmpty()) {
String token = StdIn.readString();
if (token.equals("+")) {
double operand2 = stack.pop();
double operand1 = stack.pop();
double result = operand1 + operand2;
stack.push(result);
} else if (token.equals("-")) {
double operand2 = stack.pop();
double operand1 = stack.pop();
double result = operand1 - operand2;
stack.push(result);
} else if (token.equals("*")) {
double operand2 = stack.pop();
double operand1 = stack.pop();
double result = operand1 * operand2;
stack.push(result);
} else if (token.equals("/")) {
double operand2 = stack.pop();
double operand1 = stack.pop();
double result = operand1 / operand2;
stack.push(result);
} else {
// Assuming token is a numbber, push it onto the stack
double number = Double.parseDouble(token);
stack.push(number);
}
}
// The final result will be at the top of the stack
if (!stack.isEmpty()) {
double finalResult = stack.pop();
System.out.println("Result: " + finalResult);
} else {
System.out.println("No valid expression provided.");
}
}
}- PostScript: a virtual machine with stack application
- JVM(java virtual machine)
data structure: sequential vs. linked
- linked data structure
- associate with each object a link to another one
- machine: link is memory address of next object
- java: link is reference to next object
- linked list
- def: a linked list is null or a reference to a node
- def: a node is a data type that contains a reference to a node
- associative array abstraction: index of array is string value
- def: an ADT whose values are sets of key-value pairs
- operations:
- associate a key w a value(add the key if not in table)
- return the value
- test if a given key is in the table
- iterate through keys
- hash table: divide keys into m groups, keys in an linked list and use sequential search
- binary search tree(BST)
- def: a null/ a reference to a BST node
- a BST node: reference to a key, a value, and two BSTs, a left and right subtree
- abstract machines:
- mathematical model of computation
- defined by specific rules for transforming input to output
- deterministic finite automata (DFAs)
- solve pattern matching problem
- each defines a language that it can recognize
- formal language
- a set of strings
- each defined by specific rules that characterize it
- regular expression
- define and specify a language; recognize the string belongs to the concept or not
- three categories: expand the alphabet, shorthand notation, extension to closure operation
questions:
is a given string defined by a given RE or not
can a dfa help answer this question?
answer:
REs and DTAs are equivalent to define a set of strings
Equivalence theorem: given any RE, there exists a DFA that accepts the same sef of strings; vice versa
- def: an abstract model of computation
- reads and writes characters on the tape (x:x, if reads x, writes the latter x)
- move left or right
- halt and leave result of the computation
- pro: performing a single algorithm, are more like a software than hardware;
- con: need to build seperate TMs for each algorithm; which is highly impractical
Universal Turing Machine (UTM): consists both a program and its data
- interaction machines are natural generalizations of TMs that accept synchronous or asynchronous input streams
- solvable: algorithm exists to solve a particular problem