Transcript CS 101E – Exam 2 Review

CS 101E – Exam 2
Review
Spring 2007
Michele Co
Announcements
• Review Session
• Tonight, 7/7:30 p.m., OLS 009
• Will be announced via email
• In-class Exam
• Wednesday
• Lab Quiz 2
• Same time as Lab Quiz 1
• Quiz will become available on Sunday evening, 7:00
p.m.
• MUST electronically submit your solution by 8:30 p.m.
• Contact me by Wednesday noon if you need to take
the lab quiz in lab on Thursday. (Let me know which
section you’d like to attend.)
•
•
•
•
•
Textbook Chapters
Chapter 3 – Decision structures
Chapter 4 – Looping constructs
Halting problem
Chapter 5 - Methods
Chapter 6 – Classes
Chapter 3 – Decision
Structures
• logical expressions
•
•
•
•
•
logical and, logical or, logical not
DeMorgan’s Laws
truth tables
operator precedence
testing for object equality
• string comparison
• short circuit evaluation
Chapter 3 - Decisions
• if statements
• if, if-else, if-else-if
• nested if statements
if(Expression)
Action
• ? : notation
(x > y) ? x : y
Chapter 3 - Decisions
• switch statements
switch(Expression) {
case CaseExpression:
Action_1;
case CaseExpression:
Action_n;
default:
}
Action_n+1;
Chapter 3
• break statement
Chapter 4 - Loops
• while
• do-while
• for
break vs. continue
• loop indexing
• Syntax for each construct
• Components of each
• Differences between the constructs
• for vs. while vs. do-while
• How often, and when is the condition
expression evaluated?
• nested loops
Loop Design/Analysis
• Questions to consider in loop design and
analysis
• What initialization is necessary for the loop’s
test expression?
• What initialization is necessary for the loop’s
processing?
• What causes the loop to terminate?
• What actions should the loop perform?
• What actions are necessary to prepare for the
next iteration of the loop?
• What conditions are true and what conditions
are false when the loop is terminated?
• When the loop completes what actions are need
to prepare for subsequent program processing?
Halting Problem
• Given a Java program P, and input I
• Let P be a filename for a program file on a disk
somewhere
• Let I be a filename for a file that contains all the
input the program takes in
• Will the program P with input I ever
terminate?
• Meaning will program P with input I loop forever
or halt?
• Can a computer program determine this?
• Can a human?
• First shown by Alan Turing in 1936
• Before digital computers existed!
Halting Problem Proof
Idea
• Consider a program P with input I
• Suppose that a method
Oracle.CheckHalt(P,I) exists
• Tests if P(I) will either “loop forever” or
“halt”
• A program is a series of bits
• And thus can be considered data as well
• Thus, we can call CheckHalt(P,P)
• It’s using the bytes of program P as the
input to
program P
Halting Problem Proof
(cont’d)
• Consider a new program:
public class Test {
public static void main (String args[]) {
if ( Oracle.CheckHalt(“Test.java”, “Test.java”) )
// if Test.java loops
forever
System.exit();
// then halt
else
// else if Test.java
halts
while (true) { }
// then loop forever
}
}
Why is the Halting Problem
Important?
• It was the first algorithm that
was shown to not be able to
exist by a computer
• It’s much harder to prove that a
program can never exist
Chapter 5 - Methods
• Method syntax
• Trace method execution
• Refactoring
• benefits
• disadvantages
• return keyword
• return values
• returning primitive types vs.
returning objects
Chapter 5 - Methods
• Parameters
• How parameters are passed in
Java
• When can changes occur?
• Variable scoping
• static
• local variables
• parameters
Chapter 6 - Classes
• mutator
• accessor
• constructor
• specific
• default
• What set of actions occurs when
Circle c = new Circle();
is executed?
• What is the purpose of a
constructor?
Miscellaneous
• Using Scanner class to read in
from a file
• Object-oriented programming
benefits
• ++i vs. i++
• When are variables
automatically initialized in
Java?