Show Menu
Cheatography

CS201 Midterm 1 Cheat Sheet (DRAFT) by

This is a draft cheat sheet. It is a work in progress and is not finished yet.

Primitive Data Types

Type
Descri­ption
Default
Examples
Boolean
true/false
false
boolean b = true;
char
character
0
char c = 'A';
int- takes up less space than a double
integer
0
int i = 0;
double
floating point
0.0
double vel = 85.4;

Memory

Array: Length of array * memory of type it contains

Primitives vs Objects

- Java is an object oriented language --> object oriented mean organized in terms of classes
- Primitive: can create them without using the new word
int x= 5;
- Objects: repres­ented by a class and contain variables and methods
- Java has built-in objects, like String and ArrayList, but can also write your
own
- Objects are created by writing a class to represent them
String s = new String ("Hello world");
- Object versions of all the primitive types because many data types require
you to say what is inside them
ArrayL­ist­<In­teg­er> goodList = new ArrayL­ist­<In­teg­er>();
- One except are arrays. They are created by having the type the array
contains, followed by square brackets.

Static Methods

You can write code like Math.e­xp(-xx/2) / Math.s­qrt(2Math.PI) and Java knows what you mean. ) Static methods are associated
with the class. They can be called from static or dynamic methods.
No object
Static: associated with class
Dynamic: associated with instances of the class (objects) and have access to instance variables

Creating Data Types

NBody

Question 2: For what values of timeStep, does the simulation no longer behave correctly?
With a large totalTime and dt,the planets move in a spiral and some of the planets knock each other around during the simula­tion.
Large values don't work in the simulation because, the time step is too large. The planets don't
move fluidly and take large jumps from one position to the next.

Sets

s1.con­tai­nsA­ll(s2) — returns true if s2 is a subset of s1. (s2 is a subset of s1 if set s1 contains all of the elements in s2.)
 

Arrays

type [] name = new type[size]; 
    Student [] studentList = new Student[3]; 
Length 
   nameOfArray.length 
Access value at a specific index
   nameOfArray[index] 
Convert List to array: Arrays.asList(ArrayList)
Homogenous collections: once created, don't grow

Constr­uctors

A class contains constructors that are invoked to create objects from the class blueprint and have same name as class. Constructor declarations look like method declarations—except that they use the name of the class and have no return type. For example, Bicycle has one constructor:

public Bicycle(int startCadence, int startSpeed, int startGear) {
    gear = startGear;
    cadence = startCadence;
    speed = startSpeed;
}

Bicycle myBike = new Bicycle(30, 0, 8);
the call to new : 
- calls the constructor, reference to the object 
- all non primitive variables are pointers 
-Calling constructor creates new object
To create a new Bicycle object called myBike, a constructor is called by the new operator:

Scanner Example Code

nextInt(), nextDouble(), and next() methods in the Scanner

List<Set<String>> attendeeList(Scanner in) {
ArrayList<Set<String>> result = new ArrayList<Set<String>>();
while (in.hasNext()) {
TreeSet<String> words = new TreeSet<String>();
Scanner line = new Scanner(in.nextLine());
while (line.hasNext())
words.add(line.next());
result.add(words);
}
return result;
}

Trade-offs

Tree Maps and Tree Sets are slower but ordered
Hash Maps and Hash Sets are faster but unordered
ArrayList is slower and takes up more memory, but you can change the size
Array is faster and takes up less memory but you can't change the size

Comparing and Sorting

Arrays.sort
Collec­tio­ns.sort
Strings are comparable lexico­gra­phi­cally: zebra>­aar­dvark but Zebra<­aar­dvark
yak.co­mpa­reTo(s) returns <0, ==0, >0

Equals Method Example

compareTo method example

Markov

- Effici­ent­Markov based on using maps rather than rescanning the training text// Implement a new version of getFollows so that it's a constant time operation that uses myMap to return an ArrayList using the parameter to getFollows as a key. If the key isn't present in the map, throw a new NoSuch­Ele­men­tEx­ception with an approp­riate String.
- WordGram that will use a word-m­arkov model rather than the charac­ter­-markov model you start with
- Effici­ent­Wor­dMarkov, modeled on Effici­ent­Markov and with the same structure in terms of methods --- but using WordGram objects rather than String­s//This class uses a map (either a TreeMap or a HashMap) to create a more efficient version of WordMa­rko­vModel.
The order of the Markov Model, size of the N gram, does not have more impact than the size of the text on the run time.
 

Map Interface

A Map is an object that maps keys to values. A map cannot contain duplicate keys: Each key can map to at most one value. Keys in a map need to be comparable

Adding Values to Maps

Value is a counter
m.put(key, m.get(key) + 1)

value is arrayList// set 
if (map.get(key) == null) {
    map.put(key, new ArrayList<Integer>());
}
map.put(key, map.get(key).add(number));

Maps API

value = map.ge­t(key)
Collec­tio­ns.max

ArrayList

Does not have fixed sized/ no primitive types
ArrayList<String> list = new ArrayList<String>(); 
    add(Object o) - adds an object to the ArrayList, must be of the correct type
    remove(Object o) - removes that object from the ArrayList, if it exists
    get(int index) - returns object at that index
    contains(Object o) - returns true/false
    size() - returns the length of the ArrayList

Object Values and Variables

== is usually used for primitive types / do they point to the same location in memory
while .equals() is used for objects.

Strings

String name = "word"; 
String syntax 
   length() - returns length of String 
   charAt(int index) - returns character at that index 
   concat(String str) - cocatenates String str to the end of the String 
   compareTo(String stre) - compares the two Strings lexicographically 
   equals (Object obj) - compares the String to the object 
   indexOf(char c) - returns first index of the character c in the String

Hashing Markov Example

Instance of checks to see if the object is an instance of a class. Returns true if it is and returns false if it isn't. Hashing is important because it helps with efficiency (can access in O(1) time). While HashMaps already have a hash code, we overwrite it to make it more effective and so that ordering matters.

Inheri­tance: Implements vs. Etends.

Object-oriented programming allows classes to inherit commonly used state and behavior from other classes.Implements you have to override all the methods. Extends is you add some methods to existing class.

Hash Code Example

public int hashCode(){
int h = 0;
h += myState.hashCode() + myRegion.hashCode()*3;
for (int k=0, fact=9; k < myMembers.length; k++, fact *= 3) {
h += myMembers.hashCode()*fact;
return h;
}

Hashing

- Hashing is a search method: average case is O(1) search
- Associate a number with every key, use the number to store the key
- A hash function generates the number from the key
- Hash table is an array of fixed size with a key to each location and each key is mapped to an index in the table ArrayL­ist­<Ar­ray­Lis­t<T­ype­>>()
- Every object has a hashCode which is an integer value
- Two objects can have the same hashCode when two keys have the same value
- you can look for the next spot
- two equal objects should hash to the same place because they have the same hash code and key
- if x.equa­ls(y) then x.hash­Code() == y.hash­Code()