Transcript CS1101 Group1

CS1101 Group1
Discussion 5
Lek Hsiang Hui
lekhsian @ comp.nus.edu.sg
http://www.comp.nus.edu.sg/~lekhsian/cs1101
Debugging in Dr Java
Checklist
• Setting a breakpoint
– Before running program
– During the debugging process
• Step into a method
• Watches
Debugging in Dr Java
public class Dummy{
public static void main(String[] args){
int tmp = 0;
for (int i = 0 ; i < 10 ; i++){
tmp++;
}
dummyMethod();
}
public static void dummyMethod(){
System.out.println("do nothing1");
System.out.println("do nothing2");
System.out.println("do nothing3");
}
}
•
•
•
•
•
Ctrl+B (toggle breakpoints at current line)
F7 (Resume/Continue Run)
F11 (Step Over)
F12 (Step Into)
Shift + F12 (Step Out)
Search And Sorting
Searching
• Linear Search
– Go through all the items in an array
• Binary Search
– Search by “cutting” the possible solutions by
½ each time
Sorting
• Bubble Sort
• Insertion Sort
• Selection Sort
Stable Sorts
• A stable sort is one where the relative ordering of
elements with the same value is preserved after sorting.
– Two elements having the same key appear in the same order in
the sorted sequence as they did in the original sequence.
• Example:
– Stable sort:
Before sorting: 6
After sorting:
2
2 3a 8
3a 3b 5
3b 5
6 8
9
9
– Unstable sort:
Before sorting: 6
After sorting:
2
2 3a 8
3b 3a 5
3b 5
6 8
9
9
• Which of the three basic sorts – bubble sort, selection
sort, insertion sort – is/are stable?
Slide taken from cs1101x lecture notes
Sorting Algorithms Comparison
Name
Best Time
Worst Time
Stable
(in general)
Bubble sort
O(n)
O(n2)
Yes
Insertion sort
O(n)
O(n2)
Yes
Selection
sort
O(n2)
O(n2)
No
Sorting Algorithms Comparison
Name
Best Time
Worst Time
Stable
(in general)
Bubble sort
about
n comparisons
about
n2 comparisons
Yes
Insertion sort
about
n comparisons
about
n2 comparisons
Yes
Selection sort
about
n2 comparisons
about
n2 comparisons
No
Sorting Question
Which of the 3 algorithms is best for data
that is almost sorted?
Recursion
Recursion
• Base case
• Recursive case
n! = n * (n-1) * (n-2) * … * 2 * 1
for n > 0 (recursive case)
0! = 1 (base case)
int fac(int n){
if (n == 0) return 1;
else{ return n * fac(n-1); }
}
Recursion
• General approaches
• Think recursive
– Split the problem into simple cases
– Work in the opposite way
• Work from a base case
• See what you need to do for the 2nd last case
• etc
Recursion Practice
• Can you write a “while” method that does
what the while loop is doing
Recursion Practice
• Can you write a “while” method that does what
the while loop is doing
public static void While (int i){
if (cond){
//code of while body
While(i);
}
}
Recursion Practice
while(i > 0){
System.out.println(i);
i--;
}
public static void While (int i){
if (i > 0 ){
System.out.println(i);
i--;
While(i);
}
}
References
• Pass by Value
– Java is always pass by value!
• Pass by Reference
Pass by Value
public static void main (String args[]){
//a is an Integer Object
//you can just think of it as a
//integer value
Integer a = new Integer(13);
addOne(a);
System.out.println(a);
}
public static void addOne(Integer number){
number = new Integer(number.intValue() + 1);
System.out.println("number inside the method : " + number);
}
What do you think is the output?
Pass by Value
public static void main (String args[]){
//a is an Integer Object
//you can just think of it as a
//integer value
Integer a = new Integer(13);
addOne(a);
System.out.println(a);
}
public static void addOne(Integer number){
number = new Integer(number.intValue() + 1);
System.out.println("number inside the method : " + number);
}
What do you think is the output?
number inside the method : 14
13
Pass by Value
public static void main (String args[]){
Integer a = new Integer(13);
addOne(a);
System.out.println(a);
}
public static void addOne(Integer number){…}
What is really happening on the JVM?
13
0x0010
The value of a is at
memory location 0x0010
Note that this is really a simplified view of what’s happening
Pass by Value
public static void main (String args[]){
Integer a = new Integer(13);
addOne(a);
System.out.println(a);
}
public static void addOne(Integer number){…}
What is really happening on the JVM?
13
0x0010
0x0010
a
0x0020
To find the value of a,
just need to go to
memory location 0x0010
This information is stored at
memory location 0x0020
Pass by Value
public static void main (String args[]){
Integer a = new Integer(13);
addOne(a);
System.out.println(a);
}
public static void addOne(Integer number){…}
What is really happening on the JVM?
13
0x0010
0x0010
addOne(a)
a
0x0020
0x0010
Copy of a
0x0030
What happens when you
call a method is that another box
with the value 0x0010 is passed in
(both are pointing to 0x0010)
What this means is that you can,
only change the contents
at 0x0010, but you cannot define a
new totally new object for a
(You are allowed to modify 0x0010)
Pass by Reference
public static void main (String args[]){
Integer a = new Integer(13);
addOne(a);
System.out.println(a);
}
public static void addOne(Integer number){…}
What is really happening on the JVM?
13
0x0010
0x0010
a
0x0020
addOne(a)
In Pass by Reference,
what happens call a method
is that the first box on
the left is passed
to the method(0x0010)
What this means is that you can,
change the contents
at 0x0010, and you can also give
new pointer for Integer a
(You are allowed to modify both
0x0010, and 0x0020)
Java (Pass by value)
• When you are passing primitive data types
to methods (int, byte, double etc), you can
think of it as you are giving the method the
numerical value of the variable, not the
variable itself
Java (Pass by value)
• When you are passing in references…
– Objects, Arrays*
– Can really think of Arrays are Objects
• You are given access to the content of that
Object (but cannot modify the container)
Java (Pass by value)
int[] arr = new int[10];
method(arr);
public static void method(int[] a){
a = new int[20];
}
arr
contents
0x0010
0x0010
arr
0x0020
0x0010
Copy of arr
0x0030
Java (Pass by value)
int[] arr = new int[10];
method(arr);
public static void method(int[] a){
a = new int[20];
}
arr
contents
0x0010
new array
0x0010
arr
0x0020
0x0050
Copy of arr
0x0030
Java (Pass by value)
int[] arr = new int[10];
method(arr);
public static void method(int[] a){
a = new int[20];
}
When you comes out of the
method, you don’t really have the
previous box and 0x0050
arr
contents
0x0010
0x0010
arr
0x0020