1) Programming Basics 1
a)
Java and the Java Virtual Machine 3 1.1 Computers and Their Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 The computer programs in your machine . . . . . . . . . . . . . . . . . . . . 3
1.1.2 Java Virtual Machines - JVM . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.3 Code editing and code compiling . . . . . . . . . . . . . . . . . . . . . . . . . 6
b) Our First Programs 13
2.1 The First Program, Hello, World! . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.1.1 Method declaration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.2 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1.3 System.out.println and System.out.print . . . . . . . . . . . . . . . . . . 17
2.1.4 Spacing in the source code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2 Commenting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3 Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.4 Using Multiple Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
* println versus print revisited . . . . . . . . . . . . . . . . . . . . . . . . . . 23
* Printing multiple-line texts on the screen . . . . . . . . . . . . . . . . . . . . 25
2.4.3 Escaping characters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.4 Printing shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
c) Using Data for Computation 39
3.1 Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.1.1 Data and their taxonomy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.1.2 Literals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.1.3 Variable declarations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.1.4 Naming variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.1.5 Value assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2 The primitive data types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2.1 Quarterbacks program again . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3 Using Variables for Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.3.1 Number arithmetics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.3.2 Formula evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.3.3 Our first calculation program . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3.4 Mixing different number types . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.3.5 Computing the Body-Mass Index . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.3.6 Sum of integers from 1 to 100 `a la Gauss . . . . . . . . . . . . . . . . . . . . 61
3.3.7 Simplified expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
3.4 An Introduction to String Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.4.1 String objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.4.2 String additions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
3.4.3 Escaping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
3.4.4 Connection with other types . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4 Reading Keyboard Input 83
4.1 The Class Scanner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.2 Reading input with a Scanner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5 Decomposing Code into Components 99
5.1 Code Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5.1.1 Printing rectangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5.1.2 Quadrangle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
5.1.3 Old MacDonald Had a Farm . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
5.1.4 The benefits of code decomposition . . . . . . . . . . . . . . . . . . . . . . . . 114
5.2 Using Multiple Program Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
6 Passing Values to and from Methods 123
6.1 Passing Values to Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
6.1.1 Methods that work with parameters . . . . . . . . . . . . . . . . . . . . . . . 123
6.1.2 Method overloading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
6.2 Receiving a Value from a Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
6.3 Class Math . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
6.3.1 Mathematical functions in Java . . . . . . . . . . . . . . . . . . . . . . . . . . 137
6.3.2 Application using Math methods . . . . . . . . . . . . . . . . . . . . . . . . . 146
2) Loops and Conditional Execution 157
7 For-Loops 159
7.1 Repetitive Code Execution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
7.2 Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
7.2.1 Simple iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
7.2.2 Iteration with an auxiliary variable . . . . . . . . . . . . . . . . . . . . . . . . 173
7.3 Double For-Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
8 Using Conditions to Control the Flow 187
8.1 Condition and its evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
8.2 The If Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
8.2.1 If . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
8.2.2 Else . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201
8.2.3 Special conditional evaluation rules . . . . . . . . . . . . . . . . . . . . . . . . 209
8.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
8.3.1 Computing max and min in a series of numbers . . . . . . . . . . . . . . . . . 211
8.3.2 A betting game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214
9 Formatted Printing using printf 225
9.1 Formatted Printing of Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
9.2 Formatted Printing of Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
9.3 Formatted Printing of Floating Point Numbers . . . . . . . . . . . . . . . . . . . . . 229
10 String Methods for Text Processing 237
10.1 String Methods for Information Extraction . . . . . . . . . . . . . . . . . . . . . . . 237
10.2 String Methods for Comparison . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
10.3 String methods for Pattern Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
10.4 String methods for creating new String objects . . . . . . . . . . . . . . . . . . . . 246
10.5 Class StringBuilder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
11 Branching Using Switch Statements 259
11.1 Switch Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
11.2 Switching on a Char or a String Value . . . . . . . . . . . . . . . . . . . . . . . . . . 266
12 While and Do-while Loops 277
12.1 The While Loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
12.1.1 What is a while-loop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
12.1.2 Collect numbers until the total reaches a target . . . . . . . . . . . . . . . . . 279
12.1.3 Integer overflow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
12.1.4 Vending machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283
12.1.5 The Collatz Conjecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285
12.1.6 From decimal to binary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
12.2 Do-while statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
12.2.1 Do-while versus while . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293
12.2.2 Waiting for Godot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 294
12.2.3 Converting to binary, again . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295
12.3 Terminating a Scanner of Keyboard . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
12.4 Approximating the Square Root . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
III Arrays 311
13 Arrays 313
13.1 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
13.1.1 What is an array? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
13.1.2 Counting the number of occurrences . . . . . . . . . . . . . . . . . . . . . . . 314
13.2 Offset Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
13.2.1 Offset indexing to avoid wasteful use of array elements . . . . . . . . . . . . . 322
13.2.2 Offset indexing for BMI calculation . . . . . . . . . . . . . . . . . . . . . . . . 323
13.2.3 Character occurrence counting . . . . . . . . . . . . . . . . . . . . . . . . . . 325
13.2.4 Negative offset indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330
13.3 Primality Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
13.4 Using Multiple Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
13.5 ArrayIndexOutOfBoundsException . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
14 Class Arrays, Resizing Arrays, and Arrays with Capacity 347
14.1 Class Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
14.2 Coordinated Array Modifications with Sustained Length . . . . . . . . . . . . . . . . 351
14.2.1 Reversing element order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354
14.2.2 Cyclic shifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356
14.3 Modifications That Require Resizing . . . . . . . . . . . . . . . . . . . . . . . . . . . 360
14.3.1 Insertion and deletion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360
14.3.2 Merging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
14.4 args - the Argument Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
14.5 Searching in an Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
14.5.1 Sequential search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
14.5.2 Sequential search in an array with elements in order . . . . . . . . . . . . . . 370
14.5.3 Binary search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
14.6 Arrays with Capacity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 372
15 Multidimensional Arrays 385
15.1 Two-dimensional Rectangular Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
15.1.1 Multi-dimensional arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
15.1.2 Summation of over subsequences . . . . . . . . . . . . . . . . . . . . . . . . . 386
15.2 Matrix multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
15.2.1 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
15.2.2 Two dimensional rotations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
15.3 Jagged Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
IV Object Classes 401
16 Class File 403
16.1 An Introduction to Object Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
16.2 File Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
16.3 File methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405
16.3.1 List of File methods we may use . . . . . . . . . . . . . . . . . . . . . . . . . 405
16.3.2 Error handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 407
16.3.3 Listing of File objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417
16.4 Scanner of a File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
16.5 Writing to Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427
17 Designing Object Classes 435
17.1 Using Object Classes for Packaging Data Elements . . . . . . . . . . . . . . . . . . . 435
17.1.1 The position of a game piece . . . . . . . . . . . . . . . . . . . . . . . . . . . 435
17.1.2 Private instance variables and the toString method . . . . . . . . . . . . . . 440
17.1.3 Using constants in an object class . . . . . . . . . . . . . . . . . . . . . . . . 442
17.1.4 Information hiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447
17.2 Bank Account . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453
17.3 Array with Capacity (as an Object Class) . . . . . . . . . . . . . . . . . . . . . . . . 461
18 Interfaces, Subclasses, Inheritance, and Polymorphism 471
18.1 Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
18.1.1 Interface as a template . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471
18.1.2 A simple pizza application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 472
18.1.3 The simple pizza collection class . . . . . . . . . . . . . . . . . . . . . . . . 473
18.1.4 The pizza collection main class . . . . . . . . . . . . . . . . . . . . . . . . . . 478
18.2 Subclasses and Superclasses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480
18.2.1 Extending existing classes and interfaces . . . . . . . . . . . . . . . . . . . . . 480
18.2.2 Writing extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482
18.3 Polymorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 490
18.4 Interface Comparable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493
V Advanced Concepts 499
19 Cumulative Algorithms 501
19.1 What is a Cumulative Algorithm? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501
19.2 Computing Recurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503
19.3 Computing the Factorial Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
20 Recursive Algorithms 513
20.1 The Factorial Again . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513
20.2 GCD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 516
20.3 The Tower of Hanoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 521
