Transcript Compsci_201_Midterm_1_Reviewx

Compsci 201 Midterm 1 Review
Professor Peck
Jimmy Wei
10/1/2013
List of Topics
•
•
•
•
•
•
Data Structures
References
Big O
Hashing
Inheritance
LinkedLists
Data Structures
• Arrays: fixed-length, typed
• Lists: variable-length, ordered
• Sets: variable-length, unordered, unique
elements
• Maps: variable-length, unordered, keyvalue pairs
Data Structures
• In the following algorithms, what kind of data
structure would you use and why?
– An algorithm that takes a number and returns its
prime factors
– An algorithm that reads a file to create a data
representation of a family tree
– An algorithm that checks a string for invalid
characters and removes them from the string
– An algorithm that generates the first k numbers in
some given number pattern (e.g. Fibonacci)
References
• Objects in Java are stored in memory,
and are accessed through references—
Java doesn’t trust us coders with direct
memory access!
• The references themselves are stored in
a different part of memory
References
• Process of creating a new
Object:
1. Declare typed reference
•
Java Memory (Heap)
ArrayList<String>
ArrayList<String> list;
2. Create new Object
•
new ArrayList<String>();
3. Assign the reference to
the Object
•
myStringList = new
ArrayList<String>();
list
References
• How do we create another
reference to the same
object?
Java Memory (Heap)
ArrayList<String>
– ArrayList<String> otherList
= list;
• What happens if we
manipulate list?
list
list otherList
References
• Consider the following code:
public void firstMethod() {
ArrayList<String> firstList = new ArrayList<String>();
firstList.add(“Jimmy”);
ArrayList<String> secondList = firstList;
System.out.println(secondList);
secondList.add(“Andrew”);
System.out.println(firstList);
Output
secondList = new ArrayList<String>();
secondList.remove(“Jimmy”);
[“Jimmy”]
System.out.println(firstList);
[“Jimmy”, “Andrew”]
System.out.println(secondList);
[“Jimmy”, “Andrew”]
}
[]
• What’s the output?
References
public static void secondMethod(Set<Integer> set) {
Set<Integer> temp = new HashSet<Integer>(set);
for (Integer item : set) {
if (item % 2 == 0) {
temp.remove(item);
}
}
}
public static void main(String[] args) {
Set<Integer> nums = new HashSet<>();
nums.add(1); nums.add(2); …; nums.add(10);
secondMethod(nums);
System.out.println(nums);
}
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Output
Big O
• Used to measure scalability of performance
• Does not tell us how fast something runs in
terms of absolute runtime—rather, tells us
how performance of an algorithm scales as we
increase input!!!
Big O
• Consider the following example:
public void sum(int n) {
int sum = 0;
for (int i=0; i<n; i++) {
sum += I;
}
return sum;
}
• What is the input of the algorithm?
• How does performance scale as we increase
the input?
Big O
• Consider the following example:
public void count(int k) {
for (int i=0; i<k*k; i++) {
for (int j=0; j<k; j+=2) {
System.out.printf(“%d-%d\n”, j, i);
}
}
}
• What is the input of the algorithm?
• How does performance scale as we increase
the input?
Big O
public long bigMethod(List<Integer> listOfNums) {
long result = 0;
for (int i=0; i<5; i++) {
for (int k=0; k<listOfNums.size(); k*=2) {
result += helper(listOfNums, k);
}
}
return result;
}
public int helper(List<Integer> list, int firstK) {
int sum = 0;
for (int i=0; i<firstK; i++) {
sum += list.get(i);
}
return sum;
}
Big O
• Big Oh of common data structures operations:
Data Structure
Access
Add
Remove
Search
Array
O(1)
O(n)
O(n)
O(n)
ArrayList
O(1)
O(1)
O(n)
O(n)
LinkedList
O(n)
O(1)
O(n)
O(n)
HashMap
O(1)
O(1)
O(1)
O(n)
HashSet
O(1)
O(1)
O(1)
O(1)
• Note that add for arrays, ArrayLists, and
LinkedLists refers to adding to the end
• Access refers to grabbing a known element or
index; search refers to checking for the existence
of some element
Hashing
• Java variables are either primitives or objects
– Primitives: int, long, float, double, short, etc…
– Objects: Strings, Arrays, Lists, Sets, Maps, etc...
• Primitives are stored as values
• Objects are stored as references
Hashing
• The difference between “.equals()” and “==“:
– “.equals()” tests for EQUALITY
– “==“ tests for IDENTITY
• Also note:
– Above statements are a simplification of using
“.equals()” and “==“ for objects
– Primitives cannot invoke “.equals()”, but can be
passed in as parameters
Hashing
• The hashCode() method returns an integer
code for every object
• Rules:
– If a.equals(b), then a.hashCode() == b.hashCode()
– If !(a.equals(b)), then a.hashCode() ==
b.hashCode() || a.hashCode() != b.hashCode()
– Every object inherits .equals() and .hashCode(); if
you overwrite one you MUST overwrite the other!
Hashing
• HashTables provide us with
O(1) lookup/update
• Implemented as an array
representing a fixed
number of buckets
• Add keys to table based on
calculated hashcode
Index
Value
0
“Jimmy”
1
2
42
3
4
5
6
“CS201”
7
8
9
List<String>
Add the following values (with given hashcodes) to the table:
“Jimmy” (2510), 42 (42), List<String> (8509), “CS201” (5166)
Inheritance
• Java allows us to set up super/subclasses
which inherit behavior from each other
• Consider the following classes:
public class Sedan {
public void start();
public void move();
public void honk();
}
public class Bicycle {
public void start();
public void move();
public void ringBell();
}
public class Train {
public void start();
public void move();
public void board();
}
Inheritance
• We can set up a superclass for these:
public class Vehicle{
public void start();
public void move();
}
public class Sedan extends
Vehicle {
public void start();
public void move();
public void honk();
}
public class Bicycle
extends Vehicle {
public void start();
public void move();
public void ringBell();
}
public class Train extends
Vehicle {
public void start();
public void move();
public void board();
}
Inheritance
• How to use a superclass:
• Think back to the different parts of creating a
new variable in Java…
List<Integer> myList = new ArrayList<Integer>();
• [Type] [VarName] = new [Instantiation]
• Only methods declared in [Type] are available!
• However, the actual methods that are executed
are those in [Instantiation]!!
Inheritance
• Let’s look at an example:
public class Vehicle {
public void start() {
println(“Vehicle started”);
}
public void stop() {
println(“Vehicle stopped”);
}
public void move() {
println(“Vehicle moved”);
}
}
public class Plane extends Vehicle {
public void takeoff() {
println(“Plane takeoff”);
}
public void board() {
println(“Plane boarding”);
}
public void start() {
board();
takeoff();
}
}
• If I write “Vehicle myVehicle = new Plane();”…
Inheritance
• Sometimes you want to declare a method
without providing an implementation—such a
method is called an abstract method
• An abstract method can only exist in an
abstract class
• Abstract classes can be subclassed, but not
instantiated
• An interface is an abstract class with only
abstract methods
Inheritance
public abstract class Vehicle {
public void start() {
println(“Vehicle started”);
}
public void stop() {
println(“Vehicle stopped”);
}
public abstract void move();
}
public interface PublicTransit {
public abstract void board();
public abstract void unload();
}
public class Plane extends Vehicle implements PublicTransit {
public void move() { println(“Plane moving”); }
public void board() { println(“Plane boarding”); }
public void unload() { println(“Plane unloading”); }
}
Inheritance
• For every abstract method in a superclass, a
subclass must either declare it to be abstract
(thus making the subclass also abstract) or
implement it
• Note: no multiple inheritance in Java, i.e. can
only extend ONE class
– However, one class can implement MULTIPLE
interfaces
Inheritance
public interface ClassA {
public abstract void methodA();
}
public abstract class ClassB {
public abstract void methodB();
}
public class ClassC {
public void methodC() {
println(“ClassC MethodC!”);
}
}
Which are valid?
1) ClassA myClass = new ClassD();
myClass.methodC();
2) ClassB myClass = new ClassB();
3) ClassC myClass = new ClassD();
myClass.methodC();
public class ClassD extends ClassB
implements ClassA {
public void methodA() {
println(“ClassD MethodA!”);
}
public void methodB() {
println(“ClassD MethodB!”);
}
public void methodC() {
println(“ClassD MethodC!”);
}
}
4) ClassD myClass = new ClassD();
myClass.methodB();
5) ClassB myClass = new ClassD();
myClass.methodB();
Linked Lists
• How do we implement a LinkedList?
private class Node {
private int value;
private Node next;
private Node(int v, Node n) {
value = v;
next = n;
}
}
• Maintain a pointer to the HEAD of the list, and
have every node point to the NEXT node
Linked Lists
• Let’s do some practice with LinkedLists! Code is
available for snarfing…
• First the basics:
– Adding to the list
– Removing from the list
• Then we’ll try trickier things…
–
–
–
–
Removing every other element
Moving elements to end of list
Reversing the list
???
Linked Lists
• Adding an element to the list:
public void add(int value) {
if (head == null) {
head = new Node(value, null);
return;
}
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = new Node(value, null);
}
Linked Lists
• Removing an element from the list:
public void remove(int value) {
if (head == null) { return; }
Node first = null;
Node second = head;
while (second != null) {
if (second.value == value) {
if (first == null) {
head = second.next;
} else {
first.next = second.next;
}
return;
}
first = second;
second = second.next;
}
}
Linked Lists
• Extra practice!
• We will implement the following LinkedList
methods together:
– removeEveryOther();
– moveToEnd();
– reverse();
• If we don’t finish all these problems, please
feel free to practice them on your own!
Good luck!
“An iteration over a thousand-length
LinkedList begins with a single next call”
-Timothy Shih-