| Home | Tech Talk | Team Github | Replit | Exam Review | About Me |
Tech Talk Notes
** Notes and Plans for Tech Talks and AP Exam Here **
Go to tutorial for any help and also make sure to ask scrum team and other coders as well
Take good notes to make sure to understand topics
Make sure to rewatch any AP videos for practice or to re-learn different topics
Look back at AP CSA Notes for more practice
AP Computer Science Notes: Notes
__________________________________________________________
Table of Contents
| TT0 | TT1 | TT2 | TT3 | TT4 | TT5 | TT6 | TT7 | TT8 | TT9 | TT10 |
TT0
Imperative vs. Object Oriented Paradigms
Imperative Paradigms are more step-by-step than Object Oriented Paradigms. OOP relies on classes and objects, although the methods have Imperative Paradigms.
Java Arrays
public static Animal[] animalData() {
return new Animal[]{
new Animal("Lion", 8, "Gold"),
new Animal("Pig", 3, "Pink"),
new Animal("Robin", 7, "Red"),
new Animal("Cat", 10, "Black"),
new Animal("Kitty", 1, "Calico"),
new Animal("Dog", 14, "Brown")
};
}
Java Dictionaries
private final Map<String, Integer> OPERATORS = new HashMap<>();
{
// Map<"token", precedence>
OPERATORS.put("*", 3);
OPERATORS.put("/", 3);
OPERATORS.put("%", 3);
OPERATORS.put("+", 4);
OPERATORS.put("-", 4);
}
TT1
Linked Lists
-Linked Lists. The objective is to build your own, not the ones in java like arrays. -A linked list class in Java is an order collection that contains many objects of the same type. -Once this data is stored in a sequence of containers, it holds a reference to the first container and each container will have a link to the next one in the sequence. -It’s like what we did with holding on to each other’s shoulders in tri 2 activities on sorting.
-Java Generic T allows us to pass any data type into a data structure. We’ve already done this through an arraylist. -For all of these, we must define what is iterable. Queues only need to know the tail. For example, seven slimy snakes. Seven is the head, snakes is the tail. -Anything in between is not too important. However, a stack doesn’t necessarily need to be iterable because you only need to know the head. -A Generic class simply means that the items or functions in that class can be generalized with the parameter(example T) to specify that we can add any type as a parameter in place of T like Integer, Character, String, Double or any other user-defined type.
-Insertion and deletion in queues takes place from the opposite ends of the list. -The insertion takes place at the rear of the list and the deletion takes place from the front of the list. Insert operation is called push operation. —-Insert operation is called enqueue operation.
-Queue merging takes two queues of sorteditems as arguments and returns a queue that results from merging the queues into sorted order. -While both queues aren’t empty, dequeue an item from A and enqueue it to a new queue. Then dequeue an item off of queue B. If either of the queues (A or B) are empty, dequeue the rest of the other queue and enqueue each element onto the new queue.
-A queue can be reversed by using a stack:
- Remove all the elements from the queue and push them to a stack.
- Pop-out all the elements from the stack and push them back to the queue.
- The queue is revered, print the elements of the queue.
public class LinkedList
{
private Object opaqueObject; // opaqueObject means specific type is not known, as LinkedList are not specific to a data type
private LinkedList prevNode;
private LinkedList nextNode;
/**
* Constructs a new element with object objValue,
* followed by object address
*
* @param opaqueObject Address of Object
*/
public LinkedList(Object opaqueObject, LinkedList node)
{
this.setObject(opaqueObject);
this.setPrevNode(node);
this.setNextNode(null);
}
TT2
When using a calculator, it is difficult to calculate with precedence rules. The reverse polish notation is used because the format that the equation is in is easier for machines to interpret rather than the notation we are used to, infix notation, where the operator is in between the numbers.
Example:
Reverse Polish Notation is a way of expressing arithmetic expressions that avoids the use of brackets to define priorities for evaluation of operators. In ordinary notation, one might write
(3 + 5) * (7 – 2)
and the brackets tell us that we have to add 3 to 5, then subtract 2 from 7, and multiply the two results together. In RPN, the numbers and operators are listed one after another, and an operator always acts on the most recent numbers in the list. The numbers can be thought of as forming a stack, like a pile of plates. The most recent number goes on the top of the stack. An operator takes the appropriate number of arguments from the top of the stack and replaces them by the result of the operation.
In this notation the above expression would be
3 5 + 7 2 – *
Reading from left to right, this is interpreted as follows:
- Push 3 onto the stack.
- Push 5 onto the stack. Reading from the top, the stack now contains (5, 3).
- Apply the + operation: take the top two numbers off the stack, add them together, and put the result back on the stack. The stack now contains just the number 8.
- Push 7 onto the stack.
- Push 2 onto the stack. It now contains (2, 7, 8).
- Apply the – operation: take the top two numbers off the stack, subtract the top one from the one below, and put the result back on the stack. The stack now contains (5, 8).
- Apply the * operation: take the top two numbers off the stack, multiply them together, and put the result back on the stack. The stack now contains just the number 40, which is the mathematically correct answer.
- How we can use a public static void main method to print the answer, 40, out.
Below are some code snippets where the procedure is impelmented
Below is an example formatted constructor to implement such a calculator:
// Create a 1 argument constructor expecting a mathematical expression
public Calculator(String expression) {
// original input
this.expression = expression;
// parse expression into terms
this.termTokenizer();
// place terms into reverse polish notation
this.tokensToReversePolishNotation();
// calculate reverse polish notation
this.rpnToResult();
}
Here is where precedence is established after operators and seperators are separated
// Test if token is an operator
private boolean isOperator(String token) {
// find the token in the hash map
return OPERATORS.containsKey(token);
}
// Test if token is an seperator
private boolean isSeperator(String token) {
// find the token in the hash map
return SEPARATORS.containsKey(token);
}
// Compare precedence of operators.
private Boolean isPrecedent(String token1, String token2) {
// token 1 is precedent if it is greater than token 2
return (OPERATORS.get(token1) - OPERATORS.get(token2) >= 0) ;
}
Now the expression is converted into an Arraylist and implements each operator and separator in one-by-one.
// Term Tokenizer takes original expression and converts it to ArrayList of tokens
private void termTokenizer() {
// contains final list of tokens
this.tokens = new ArrayList<>();
int start = 0; // term split starting index
StringBuilder multiCharTerm = new StringBuilder(); // term holder
for (int i = 0; i < this.expression.length(); i++) {
Character c = this.expression.charAt(i);
if ( isOperator(c.toString() ) || isSeperator(c.toString()) ) {
// 1st check for working term and add if it exists
if (multiCharTerm.length() > 0) {
tokens.add(this.expression.substring(start, i));
}
// Add operator or parenthesis term to list
if (c != ' ') {
tokens.add(c.toString());
}
// Get ready for next term
start = i + 1;
multiCharTerm = new StringBuilder();
} else {
// multi character terms: numbers, functions, perhaps non-supported elements
// Add next character to working term
multiCharTerm.append(c);
}
}
// Add last term
if (multiCharTerm.length() > 0) {
tokens.add(this.expression.substring(start));
}
}
**A tester method is built to print the final answer.
// Tester method
public static void main(String[] args) {
// Random set of test cases
Calculator simpleMath = new Calculator("100 + 200 * 3");
System.out.println("Simple Math\n" + simpleMath);
System.out.println();
Calculator parenthesisMath = new Calculator("(100 + 200) * 3");
System.out.println("Parenthesis Math\n" + parenthesisMath);
System.out.println();
Calculator fractionMath = new Calculator("100.2 - 99.3");
System.out.println("Fraction Math\n" + fractionMath);
System.out.println();
Calculator moduloMath = new Calculator("300 % 200");
System.out.println("Modulo Math\n" + moduloMath);
System.out.println();
Calculator divisionMath = new Calculator("300/200");
System.out.println("Division Math\n" + divisionMath);
System.out.println();
Calculator multiplicationMath = new Calculator("300 * 200");
System.out.println("Multiplication Math\n" + multiplicationMath);
System.out.println();
Calculator allMath = new Calculator("200 % 300 + 5 + 300 / 200 + 1 * 100");
System.out.println("All Math\n" + allMath);
System.out.println();
Calculator allMath2 = new Calculator("200 % (300 + 5 + 300) / 200 + 1 * 100");
System.out.println("All Math2\n" + allMath2);
System.out.println();
Calculator allMath3 = new Calculator("200%(300+5+300)/200+1*100");
System.out.println("All Math3\n" + allMath3);
System.out.println();
Calculator expMath = new Calculator("8 ^ 4");
System.out.println("Exponential Math\n" + expMath);
System.out.println();
Calculator sqrtMath = new Calculator("sqrt9");
System.out.println("Square Root Math\n" + sqrtMath);
System.out.println();
}
}
TT3
**A Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.
Example:
for (int x = 0; x < array.size(); x++) {
for (int y = 0; y < array.size() - 1; y++) {
if (array.get(y) > array.get(y + 1)) {
int temporary = array.get(y);
array.set(y, array.get(y + 1));
array.set(y + 1, temporary);
}
}
}
Example:
First Pass: ( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1. ( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ), Swap since 5 > 4 ( 1 4 5 2 8 ) –> ( 1 4 2 5 8 ), Swap since 5 > 2 ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them. Second Pass: ( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ) ( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2 ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted. Third Pass: ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) ( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
It has an average complexity of n^2, with an best possible complexity of n.
The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning. The algorithm maintains two subarrays in a given array.
1) The subarray which is already sorted. 2) Remaining subarray which is unsorted. In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray. Following example explains the above steps:
It has a complexity of n^2, always.
Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.
Example:
public static void insertSort(ArrayList<Integer> array) {
int n = array.size();
for (int i = 1; i < n; ++i) {
int key = array.get(i);
int j = i - 1;
while (j >= 0 && array.get(j) > key) {
array.set(j + 1, array.get(j));
j = j - 1;
}
array.set(j + 1, key);
}
}
To sort an array of size n in ascending order: 1: Iterate from arr[1] to arr[n] over the array. 2: Compare the current element (key) to its predecessor. 3: If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element. Example: 12, 11, 13, 5, 6 Let us loop for i = 1 (second element of the array) to 4 (last element of the array) i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12 11, 12, 13, 5, 6 i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13 11, 12, 13, 5, 6 i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position. 5, 11, 12, 13, 6 i = 4. 6 will move to position after 5, and elements from 11 to 13 will move one position ahead of their current position. 5, 6, 11, 12, 13
It has an average complexity of n^2, with an best possible complexity of n.
Merge Sort is a Divide and Conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is a key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one. See the following C implementation for details.
In the case of linked lists, the case is different mainly due to the difference in memory allocation of arrays and linked lists. Unlike arrays, linked list nodes may not be adjacent in memory. Unlike an array, in the linked list, we can insert items in the middle in O(1) extra space and O(1) time. Therefore, the merge operation of merge sort can be implemented without extra space for linked lists. In arrays, we can do random access as elements are contiguous in memory. Let us say we have an integer (4-byte) array A and let the address of A[0] be x then to access A[i], we can directly access the memory at (x + i*4). Unlike arrays, we can not do random access in the linked list. Quick Sort requires a lot of this kind of access. In a linked list to access i’th index, we have to travel each and every node from the head to i’th node as we don’t have a continuous block of memory. Therefore, the overhead increases for quicksort. Merge sort accesses data sequentially and the need of random access is low.
It has a complexity of nlog(n), always.