Übung 4 tutorial

Transcrição

Übung 4 tutorial

Informatik II (D-ITET)
Tutorial 4
TA: Hông-Ân Cao, E-mail: [email protected]
Distributed Systems Group, ETH Zürich
Informatik II - Hông-Ân Cao | 23.03.2016 |
1
Homework Submission

Exercise submission (please follow rigorously, copy-paste if necessary)
•
•
•
•
•
•
•

By email to [email protected] until the next Wednesday at 13:00
Use x as the exercise sheet’s number and y as your group number (1 to 18)
Subject: [Info2_2016] Exercise Ux_y_z
Attachments:
•
Theoretical Answers: Ux_y_z.pdf (Only one pdf and in English)
•
Source Code: Ux_y_z.zip (Do not change the original archive we provided and keep
its structure (i.e. ux/uxa1 etc.). Right click on the project from the IDE  Export 
General  Archive File) Comments in code should be made in English. Code has to
compile.
Body: Usual greetings
Non-compliant or late submissions will not be processed
Collaboration has to be stated on the submitted documents (names and groups)
For questions on (Lecture/Exercise)




All team members’ names should
appear
on every document!
Tutorial slides online: http://people.inf.ethz.ch/caoh/info2_2016
Google
Questions: Make an appointment during the office hours or send me an email (use [Info2_2016] in the subject
line, otherwise the email will not be processed)
Rudeness will not be tolerated and will be reported to the main assistant and Prof. Mattern.
2
Outlook
 Exercise 3 solution discussion
 Exercise 4 hints
3
Solution Ex3.Q1
/**
* Decrypts input text based on the CaesarChiffre (i.e.,
removing 3 from the
* ASCII code of each character). The decryption employs
StringBuffers
* (instead of Strings).
*
* @param s ciphertext to be decrypted
*/
public static String decrypt(String s) {
Never do as in the
StringBuffer ret = new StringBuffer();
handout classes!
for (int i = 0; i < s.length(); ++i) {
What if the you
ret.append((char) (s.charAt(i) - 3));
change the step
}
size?
return ret.toString();
}
Explicit type casting
4
Solution Ex3.Q1
 Run as Java Application
Starting encryption (using Strings)
Done - Duration: 4174 ms.
Starting decryption (using StringBuffers)
Done - Duration: 70 ms.
Decryption successful :-)
 String is immutable (remember String literals
created in memory)  modifiying a chain of characters is
more efficient with StringBuffer
5
Solution Ex3.Q1
 String is stored as a String literal due to its
immutable nature.
 StringBuffer are pre-allocated memory space in a
char array upon instantiation. As the StringBuffer's
capacity needs to expand, this is done with a new
(internally), which can still be expensive.
void expandCapacity(int minimumCapacity) {
int newCapacity = (value.length + 1) * 2;
if (newCapacity < 0) {
newCapacity = Integer.MAX_VALUE;
}
else if (minimumCapacity > newCapacity) {
newCapacity = minimumCapacity;
}
//shallow copy
value = Arrays.copyOf(value, newCapacity);
}
http://stackoverflow.com/questions/3983715/java-stringbuffer-append-allocation
6
Solution Ex3.Q2 – Syntax Analysis
Achievable
Non
Achievable
Expression
Type
𝑋2
Clause
(~𝑋1 )
Clause
~(𝑋1 𝑂𝑅 ~𝑋2 )
Clause

𝑋2 OR (~𝑋1 𝑂𝑅 𝑋2 )
Clause

𝑋1 𝑂𝑅 𝑋2 𝐴𝑁𝐷(~𝑋1 )
Expr

𝑋1 𝐴𝑁D ~𝑋1 𝑂𝑅 ~𝑋2 𝐴𝑁𝐷 (𝑋2 )
Expr



7
Solution Ex3.Q3 – Syntax Diagram
Successor
Tree
–
Tree
Subtree
,
Subtree
Node
A
Node
(
Successor
)
B
Z
8
Lukas Beyeler's solution
Solution Ex3.Q3 – Syntax Checker
parseEmptyOrSubTree()
Idea: int parseXY(lkd, pos)
Tree
 Parse XY at Position pos in
–
String lkd
Subtree
 Return value: Position in
String after processing XY
parseSubTree()
 If the string lkd is not correct,
a ParseException is thrown
Subtree
during execution
Node
(
parseChildren()
Successor
Tree
,
Successor
)
parseNode()
Node
A
B
Z
9
Solution Ex3.Q3 – Class LKD
public class LKD {
// string parsing
public static void parse(String lkd) throws ParseException;
// parse helpers (entity parsing)
private static int parseEmptyOrSubTree(String lkd, int position) throws
ParseException;
private static int parseSubTree(String lkd, int position) throws
ParseException;
private static int parseChildren(String lkd, int position) throws
ParseException;
private static int parseNode(String lkd, int position) throws ParseException;
// atomic helpers (single character parsing)
private static boolean isCharAt(String lkd, int position, char expected);
private static int parseChar(String lkd, int position, char expected) throws
ParseException;
}
Informatik II - Hông-Ân Cao | 23.03.2016 | 10
Solution Ex3.Q3 – LKD.parse(String)
 Parse a "Linksklammerdarstellung" (LKD) tree
 An empty tree is coded as "-"
 A node is coded with a block letter: A,B,C, ….
 Successors following a father are separated by "," in a bracket:
V(C1,C2)
 Empty subtree leaf at the end of the list of successors
 Omit empty list
public static void parse( String lkd ) throws ParseException {
int position = parseEmptyOrSubTree( lkd, 0 );
if( position != lkd.length() ) {
throw new ParseException( "expected end of string", position );
}
}
Solution Ex3.Q3 – LKD.parseChar() &
LKD.isCharAt()
boolean isCharAt( String lkd, int position, char expected ){
return ( position < lkd.length() ) &&
( lkd.charAt( position ) == expected );
}
int parseChar( String lkd, int position, char expected )
throws ParseException {
if( !isCharAt( lkd, position, expected ) ){
throw new ParseException( "expected character " +
expected, position );
}
return position + 1;
}
Solution Ex3.Q3 LKD.parseEmptyOrSubTree(String)
parseEmptyOrSubTree()
Tree
–
Subtree
int parseEmptyOrSubTree( String lkd, int position ) throws ParseException {
if( isCharAt( lkd, position, '-' ) ) {
return parseChar( lkd, position, '-' );
}
return parseSubTree( lkd, position );
}
Solution Ex3.Q3 - LKD.parseSubTree()
parseSubTree()
Subtree
Node
(
Successor
)
int parseSubTree( String lkd, int position ) throws ParseException {
position = parseNode( lkd, position );
if( isCharAt(
position =
position =
position =
}
lkd, position, "(" ) ){
parseChar( lkd, position, "(" );
parseChildren( lkd, position);
parseChar( lkd, position, ")" );
return position;
}
Solution Ex3.Q3 - LKD.parseChildren()
parseChildren()
Successor
Tree
,
int parseChildren(String lkd, int position) throws ParseException {
while(true) {
position = parseEmptyOrSubTree( lkd, position );
if(!isCharAt parseChar( lkd, position, ',' )){
break;
}
position = parseChar( lkd, position, ',');
}
return position;
}
Solution Ex3.Q3 - LKD.parseNode()
parseNode()
Node
A
B
Z
int parseNode( String lkd, int position ) throws ParseException {
if( position >= lkd.length() ) {
throw new ParseException( "expected a node", position );
}
char ch = lkd.charAt( position );
if( !Character.isUpperCase( ch ) ) {
throw new ParseException( "invalid character " + ch, position );
}
return position + 1;
}
Outlook
 Exercise 3 solution discussion
 Exercise 4 hints
Hints Ex4
1. A growing stack


A possible implementation using arrays
Interface is known but how it works is hidden in the background,
depends on the programmer. We will see a better implementation
with lists later.
2. Ackermann Function

Recursion explodes – compiler is used for benchmarking/testing
3. Java Bytecode
Hints Ex4.Q1 - Stack



Data structure
Only the last element is accessed
 Last-In-First-Out queue (LIFO queue)
Always use: function stack for local variables and function parameters
Hints Ex4.Q1a-c

Constructor


Initializes internal array
 Capacity is an argument to the constructor
toString() with StringBuffer

Expected Output: "[e0, e1, e2, …]"

Concatenation

String: str += "bar";
StringBuffer: buf.append("bar");
grow()



Capacity doubled, copy old values
Hints Ex4.Q1d
 push(), pop(), peek(), empty()
 Standard stack functions
 Arguments are of type int
 If necessary, call grow()
 size()
 Number of elements currently on the stack
 capacity()
 Total number of elements which fit on the current stack until the next
growth
Hints Ex4.Q2
 Ackermann Function
 Recursive Definition
 𝐴 0, 𝑚 = 𝑚 + 1
 𝐴 𝑛 + 1,0 = 𝐴 𝑛, 1
 𝐴 𝑛 + 1, 𝑚 + 1 = 𝐴(𝑛, 𝐴 𝑛 + 1, 𝑚 )
 Grows extremely quickly:
Wilhelm Ackermann
Mathematician
(1986 – 1962, Germany)
 𝐴 3,3 = 6!
 𝐴 4,2 = 265536 − 3 has already 19729 decimal
digits!!
Hints Ex4.Q2a – Trick
 𝐴(2,1) calculated by hand


𝐴 2,1 = 𝐴 1 + 1,0 + 1 = 𝐴 1, 𝐴 2,0
…
Write down ALL steps!
Hints Ex4.Q2b - Pseudocode



Specify the algorithm using the usual two stack operations:

push(x)

x = pop()
Pseudo-code:

No language-specific syntax

Pseudo-code is self-explanatory

Based on comments
func bubblesort( var a as array )
for i from 1 to N
for j from 0 to N - 1
if a[j] > a[j + 1]
swap( a[j], a[j + 1] )
end func
Source: http://www.algorithmist.com/index.php/Bubble_sort
The function has the property that one cannot say in advance how deep the
recursion is  use while instead of for-loop using!!
Hints U4 - Iterative Approach Q2c

Ackermann’s function always requires (exactly) two values:
 The currently required values should be at the top of the stack…
 What does it means when there is one item left in the stack?
Stack stack = new Stack();
stack.push(4);
stack.push(7);
while(stack.size()!=1){
…
}
7
4
stack
Hints Ex4.Q2c – Implementation
stack.push(m)
stack.push(n)
m
n
m = stack.pop()
n = stack.pop()
stack
if n == 0  result = m+1
else if m == 0  push(n-1), push(1)
else push(n-1), push(n), push(m-1)
Hints Ex4.Q2c – Implementation

Stack
 The stack of part 1
 The interface should NOT be modified

"Snapshots"
 With toString() method of the stack

I cannot do part 1
 Use java.util.Stack<Integer>
you just need push(), pop(), size() und toString()
 If necessary: send me an email
Hints Ex4.Q3 – Java Bytecode
"Write once, run
everywhere"
- Sun Microsystems, 1996
Source: https://da2i.univ-lille1.fr/doc/tutorial-java/getStarted/intro/definition.html
public class SmallFunction {
public static void main(String [] args){
System.out.println(g(1,2));
}
/**
* A small f function
*/
private static int f(int a, int b, int c){
return (a + b) / c;
}
/**
* A small g function
*/
public static int g(int a, int b) {
return f(a,b,3);
}
}
private static int f(int, int, int);
Code:
0: iload_0
1: iload_1
2: iadd
3: iload_2
4: idiv
5: ireturn
private static int g(int, int);
Code:
0: iload_0
1: iload_1
2: iconst_3
3: invokestatic #5
// Method f:(III)I
6: ireturn
private static int f(int, int, int);
Code:
0: iload_0
a
1: iload_1
b
2: iadd
a + b
3: iload_2
c
4: idiv
(a + b) / c
5: ireturn
http://docs.oracle.com/javase/specs/jvms/se8/html/jvms-6.html
http://en.wikipedia.org/wiki/Java_bytecode_instruction_listings
C:\Some Path\DisassemblerDemo>
javac //compiler
java JavaTipJavaTip.java
//run
javap –c –private JavaTip //disassembler
Common mistake: "javap is not recognized as an internal or external command,
operable program or batch file"
Reason: java binaries are not defined in System environment variable PATH
Solution: RClick on Computer  Properties  Advanced System Settings 
Environment Variables  PATH  add (where you installed the Java JDK) and
restart Windows (prior to Windows 10)
;C:\Program Files\Java\jdk1.8.0_74\bin (prior to Windows 10)
(Depends on your java version. Do java –version to get the right value)
Have fun!
Source: http://xkcd.com/1636/

Übung 4 tutorial

Transcrição

Documentos relacionados

Auction Catalogue HAJI BUNDER/CENTRAL RLY HBHR291215