Transcript ppt

CS 177 Week 12 Recitation Slides
Running Time and Performance
1
Announcements


Project 4 is due on Nov. 19th 9pm
There will be an office hour next week in case
that you have any question about your grade
of project 3.
2
QUESTIONS???
3
Exam 2 Review


Question 10 and 25’s correctness rates are less than
25%.
Question 1, 3, 9, 15’s are less than 50%.
10. Consider the following method:
public static int changeItUp(int x, int[] y)
{
int z;
x *= x;
y[0] /= 3;
z = x - y[1];
return z;
}
Given the method call below, what does the code print?
int x = 5;
int[] y = {12, 7};
int z = changeItUp(x, y);
System.out.println("(x, y0, y1, z) are (" + x + ", " + y[0] + ", " +
y[1] + ", " + z + ")");
(a) (x, y0, y1, z) are (25, 12, 8, 18)
(b) (x, y0, y1, z) are (25, 4, 7, 18)
(c) (x, y0, y1, z) are (5, 12, 7, 18)
(d) (x, y0, y1, z) are (5, 4, 7, 18)
25. Let char[][] board = new char[3][3]; represent the tic tac toe game board.
Given the following code fragment that prints out the winning message when
’X’ wins, which pair of board content and print out message is NOT correct.
for( int i = 0; i < board.length; i++) {
if((board[i][0] == ’X’) && (board[i][1] == ’X’) && (board[i][2] == ’X’)) {
System.out.println("\’X\’ wins with the " + (i+1) + "th row!");
} else if((board[0][i] == ’X’) && (board[1][i] == ’X’) && (board[2][i] == ’X’)) {
System.out.println("\’X\’ wins with the " + (i+1) + "th column!");
}
}
if( (board[0][0] == ’X’) && (board[1][1] == ’X’) && (board[2][2] == ’X’)) {
System.out.println("\’X\’ wins with the \\ cross");
} else if ( (board[0][2] == ’X’) && (board[1][1] == ’X’) && (board[2][0] == ’X’)) {
System.out.println("\’X\’ wins with the / cross");
}
(a) Board:
X-OXO
--X
Winning message: ’X’ wins with the \\ cross
(b) Board:
XXX
O--OWinning message: ’X’ wins with the 1th row!
(c) Board:
-XO
-XOXWinning message: ’X’ wins with the 2th column!
(d) All are correct
1. Consider the following code:
String[] rand_days = {"Monday", "Friday", "Sunday"};
for(int i = 0; i < rand_days.length(); i++)
{
System.out.print(rand_days.length + ", ");
}
Output will be:
(a) 3, 3, 3,
(b) There is no output due to run time error
(c) There is no output due to compile time error
(d) 6, 6, 6,
3. Why does the code below cause compile time error?
int[] list = {1, 2, 3, 4};
int sum = 0;
for (int i = 0; i < list.length; i++);
sum += list[i];
System.out.println(sum);
(a) The variable list is reference outside its scope
(b) The variable i is referenced outside its scope
(c) The variable list should have been initialized using the new operator
(d) All of the above
9. Given the method, mystery(), defined below, what does the integer b contain
if we assign mystery(36) to it?
public static int mystery(int n) {
int i = 0;
for (int j = 2; j <= n/2; j++) {
if (n != j && n%j == 0) {
i++;
}
}
return i;
}
(a) 0
(b) 5
(c) 7
(d) 6
15. Given the code below:
public class Person {
String name;
}
Which of the following is correct about the variable name?
(a) name is a local variable and an instance of the String class.
(b) name is a local variable and a primitive data type String.
(c) name is a member of the Person class and a primitive data type String.
(d) name is a member of the Person class and an instance of the String class.
Algorithm Design

Get the right answer


Use a reasonable amount of memory



Obviously, the most important thing
Not so important because of the rapidly growing memory sizes
But we still only have limited resources, esp. small electronic
devices like cell phones have very limited memory
Run as quickly as possible



0.1 sec and 0.3 sec make little difference
What about 10 min and 30 min?
10 years and 30 years?
Data Structure





In early days, algorithm + data structure = program
Although not really these days, they are still the most
important parts of programs
The graph is a typical and extremely useful data
structure
Actually data structures are everywhere: strings, arrays,
linked lists, classes
There are more complicated data structures like trees
and hash tables which you will learn later
O



Big Oh analysis is not precise estimation
It only gives an idea how slow the program will become
when n is larger and larger
A simple way to determine the Big Oh value is to check
the number of embedded loops
for x = 1..n
for y = 1..n
O(n2)
for x = 1..100
for y = 1..100
O(1)
for x = 1..n3
for y = 1..n0.5
for z = 1..n
O(n4.5)
Sorting



In general, sorting algorithms are O(n2) because they
typically involve comparing each value to each other
value (a loop inside a loop) to get each value into the
proper position. (like bubble sort)
But the best sorting algorithms are O(n logn). (like quick
sort)
It makes difference when n is large enough. For
example, 1 million.
Runtime Analysis


It’s also possible to test your program’s performance by
running it many times.
It’s hard to get the exact Big Oh value (why?) but you
can get a curve about how rapidly your program slows
down when the data size increases


Because Big Oh is not precise, especially when n is not big
enough
You can learn more sophisticated ways to do run time
analysis in algorithm courses
Space Analysis


Usually, the memory sizes nowadays are sufficient for
you program.
However, sometimes, the space cost is extremely large.




What about sorting all bytes in your hard drive?
Before you start designing “fast” algorithms, please
consider the space cost first
Java is convenient for its garbage collector, which saves
you a lot of effort by helping clean useless objects,
arrays, etc.
Sometimes, there’s a tradeoff between time and space.
Example for Algorithm Design


Search an integer in a sorted array of integers with
ascending order
Obvious solution: check the integers one by one until
you find the wanted one



Time cost: O(n)
Space cost: O(n)
Better solution: binary search


Time cost: O(log n) (why?)
Space cost: O(n)
Final QUESTIONS???
19