A Concise Introduction to Programming Algorithms in Java PDF

Undergraduate Topics in Computer Science Undergraduate Topics in Computer Science’ (UTiCS) delivers high-quality instructional content for un- dergraduates studying in all areas of computing and information science. From core foundational and theoretical material to ﬁnal-year topics and applications, UTiCS books take a fresh, concise, and modern approach and are ideal for self-study or for a one- or two-semester course. The texts are all authored by established experts in their ﬁelds, reviewed by an international advisory board, and contain numerous examples and problems. Many include fully worked solutions. Also in this series Iain D. Craig Object-Oriented Programming Languages: Interpretation 978-1-84628-773-2 Max Bramer Principles of Data Mining 978-1-84628-765-7 Hanne Riis Nielson and Flemming Nielson Semantics with Applications: An Appetizer 978-1-84628-691-9 Michael Kifer and Scott A. Smolka Introduction to Operating System Design and Implementation: The OSP 2 Approcah 978-1-84628-842-5 Phil Brooke and Richard Paige Practical Distributed Processing 978-1-84628-840-1 Frank Klawonn Computer Graphics with Java 978-1-84628-847-0 David Salomon A Concise Introduction to Data Compression 978-1-84800-071-1 David Makinson Sets, Logic and Maths for Computing 978-1-84628-844-9 Orit Hazzan Agile Software Engineering 978-1-84800-198-5 Pankaj Jalote A Concise Introduction to Software Engineering 978-1-84800-301-9 Alan P. Parkes A Concise Introduction to Languages and Machines 978-1-84800-120-6 Gilles Dowek Principles of Programming Languages 978-1-84882-031-9 Frank Nielsen A Concise and Practical Introduction to Programming Algorithms in Java 123 Frank Nielsen École Polytechnique Paris France Sony Computer Science Laboratories, Inc. Tokyo Japan Series editor Ian Mackie, École Polytechnique, France Advisory board Samson Abramsky, University of Oxford, UK Chris Hankin, Imperial College London, UK Dexter Kozen, Cornell University, USA Andrew Pitts, University of Cambridge, UK Hanne Riis Nielson, Technical University of Denmark, Denmark Steven Skiena, Stony Brook University, USA Iain Stewart, University of Durham, UK David Zhang, The Hong Kong Polytechnic University, Hong Kong Undergraduate Topics in Computer Science ISSN 1863-7310 ISBN 978-1-84882-338-9 e-ISBN 978-1-84882-339-6 DOI 10.1007/978-1-84882-339-6 British Library Cataloguing in Publication Data A catalogue record for this book is available from the British Library Library of Congress Control Number: 2009921195 c Springer-Verlag London Limited 2009 Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms of licences issued by the Copyright Licensing Agency. Enquiries concerning reproduction outside those terms should be sent to the publishers. The use of registered names, trademarks, etc., in this publication does not imply, even in the absence of a speciﬁc statement, that such names are exempt from the relevant laws and regulations and therefore free for general use. The publisher makes no representation, express or implied, with regard to the accuracy of the information contained in this book and cannot accept any legal responsibility or liability for any errors or omissions that may be made. Printed on acid-free paper Springer Science+Business Media springer.com To my family, To Audrey and Julien. “Dinosaur,” Julien, October 4th, 2008 (painting, 5 years old). Preface This concise textbook has been primarily designed for undergraduate students as a very ﬁrst course in programming. The book requires no prior knowledge of programming nor algorithms. It provides a gentle introduction to these topics. The contents of this book have been organized into ten chapters split over two parts, as follows: – The ﬁrst part is concerned with getting ready to program basic tasks using the modern language JavaTM. The fundamental notions of variables, expres- sions, assignments with type checking are ﬁrst explained. We present the conditional and loop statements that allow programmers to control the in- struction work ﬂows. The concepts of functions with pass-by-value arguments and recursion are explained. We proceed by presenting arrays and data en- capsulation using objects, and insist on the notion of references for the latter. – The second part of the book focuses on data-structures and algorithms. We ﬁrst describe the fundamental sequential and bisection search techniques, and analyze their respective eﬃciency using complexity analysis. Since the eﬀec- tive bisection search requires sorted data, we then explain basic iterative and recursive sorting algorithms. We follow by explaining linked lists and describe common insertion/deletion/merge operations on them. We then introduce the concept of abstract data-structures (illustrating them with queues and stacks) and explain how to program them in Java using the object-oriented style methods. Finally, the last chapter is an introduction to more evolved algorithmic tasks that tackle combinatorial optimization problems. The goal of this book is two-fold: Namely, during the ﬁrst part, novice pro- grammers progressively learn the basic concepts underlying most imperative programming languages using Java. The second part then introduces fresh pro- viii Preface grammers with the very basic principles of thinking the algorithmic way, and explain how to turn these algorithms into programs using the programming concepts of Java. The book progressively conveys to the reader that “program- ming” is in fact a complex task that consists of modeling a given problem, designing algorithms and purposely structuring its data for solving the prob- lem, coding the algorithm into a program, and ﬁnally, testing the program. Each chapter of the book concludes with a set of exercises that lets students practice notions covered by the chapter. The third part of the book consists of an overall exam that allows readers to evaluate their assimilation level. A solu- tion is provided. Exercises and sections that are recommended to be skimmed through in a ﬁrst reading are indicated using the mark **. Additional materials, including all Java source codes for each chapter, are avail- able at the following book web page: http: //www.lix.polytechnique.fr/Labo/Frank.Nielsen/JavaProgramming/ Preface for Instructors The Java programming curriculum (called INF311) from which this book has been prepared has been taught at École Polytechnique (Palaiseau, France) for many years. Every year about 250 students enroll into the curriculum. For most of them, it is their ﬁrst experience with the Java programming language. Some of them have a prior programming experience using mathematical pack- ages such as MapleTM which are interpreters. This yields an important source of confusion not only from the standpoint of the language syntax but also from the conceptual sides of using an imperative programming language. The INF311 curriculum does not assume any prior programming experience and concentrates on teaching the fundamental notions of programming an imper- ative object-oriented language. This book is intended as a ﬁrst programming course with two objectives in mind: – Get a ﬁrsthand experience on programming basic algorithms using basic features of Java, and – Introduce the very ﬁrst fundamental concepts underlying computer science (that is, complexity analysis, decidability, abstract data-structures, etc.). The curriculum consists of ten lectures (each of them lasts 90 minutes) that deal with the following topics: Preface ix Lecture 1 Variables, expressions and assignments (with an introduction to the science of computing) Lecture 2 Conditional and loop statements Lecture 3 Static functions and recursions Lecture 4 Arrays Lecture 5 Objects (data encapsulation without object methods) Lecture 6 Rehearsal for mid-term programming exam Lecture 7 Searching and sorting Lecture 8 Linked lists Lecture 9 Data-structures and object methods Lecture 10 Combinatorial optimization algorithms A ﬁrst course in programming without hands-on experience on writing pro- grams by oneself is simply not conceivable. That is why each lecture is followed by a two-hour programming training class to let students become familiar with the notions covered during the lectures, and experience for themselves tracking and correcting bugs. To control the level of assimilation by students, we organize at mid-term of the curriculum a two-hour programming exam that is semi-automatically checked using scripts and Java input/output redirections. The ﬁnal exam is a two-hour paper exam that focuses more on checking whether students understand the basic data-structures and algorithms. A review exam with a detailed solution is provided in Chapter 11 (page 227). The pedagogic resources, which include slides of each lecture and recorded videos of the lectures taught in the auditorium, are available at the following web page: http://www.enseignement.polytechnique.fr/informatique/INF311/ Frank Nielsen December 2008. École Polytechnique (Palaiseau, France) Sony Computer Science Laboratories, Inc. (Tokyo, Japan) Acknowledgments It is my great pleasure to acknowledge my colleagues, Professors François Morain and Robert Cori at École Polytechnique (France), who taught this introductory course. I have greatly beneﬁted from their course materials but more importantly from their feedback and advice. I express my deepest thanks to Philippe Chassignet and the full team of teaching assistants for their shared x Preface passion of letting students get their ﬁrst programs to compile and work; Many thanks to Bogdan Cautis, Guillaume Chapuy, Philippe Chassignet, Etienne Duris, Luca de Féo, Yann Hendel, Andrey Ivanov, Vincent Jost, Marc Ka- plan, Gaëtan Laurent, David Monniaux, Giacomo Nannicini, Sylvain Pradalier, Stéphane Redon Maria Naya Plasencia, Andrea Roeck, David Savourey, and Olivier Serre. This book became possible thanks to the warm encouragement and support from Sony Computer Science Laboratories, Inc. I express my gratitude to Dr. Mario Tokoro and Dr. Hiroaki Kitano, as well as all other members of Sony Computer Science Laboratories, Inc. I thank Ian Mackie for asking me to write this undergraduate textbook for the Undergraduate Topics in Computer Science series on behalf of Springer-Verlag. I apologize for any (involuntary) name omissions and remaining errors. Finally my deepest thanks and love go to my family for their everlasting sup- port. Contents List of Figures.................................................. xvii List of Tables................................................... xxi Listings.........................................................xxiii Part I. Getting Started 1. Expressions, Variables and Assignments.................... 3 1.1 Introduction............................................. 3 1.2 My ﬁrst Java programs.................................... 3 1.2.1 A minimalist program.............................. 3 1.2.2 Hello World....................................... 4 1.3 Expressions and programs as calculators..................... 5 1.3.1 Arithmetic operations and priority order.............. 6 1.3.2 Mathematical functions............................. 8 1.3.3 Declaring constants................................. 10 1.4 Commenting Java programs............................... 10 1.5 Indenting programs....................................... 11 1.6 Variables, assignments and type checking.................... 11 1.6.1 Variables for storing intermediate values............... 12 1.6.2 Type checking for assignments and casting............. 15 1.6.3 The inner mechanisms of assignments................. 17 xii Contents 1.7 Incrementing/decrementing variables........................ 17 1.7.1 General mechanism for incrementation................ 17 1.7.2 Pre-incrementation and post-incrementation........... 18 1.7.3 A calculator for solving quadratic equations........... 19 1.8 Basics of Java input/output (I/O).......................... 20 1.8.1 Computing does not mean displaying................. 20 1.8.2 Keyboard input.................................... 21 1.8.3 File redirections.................................... 23 1.9 Bugs and the art of debugging............................. 24 1.10 Integrated development environments (IDEs)................ 26 1.11 Exercises................................................ 27 1.11.1 Note to instructors................................. 27 1.11.2 First set of exercises................................ 28 2. Conditional Structures and Loops.......................... 31 2.1 Instruction workﬂow...................................... 31 2.2 Conditional structures: Simple and multiple choices........... 32 2.2.1 Branching conditions: if... else................. 32 2.2.2 Ternary operator for branching instructions: Predicate ? A : B........................................... 34 2.2.3 Nested conditionals................................. 35 2.2.4 Relational and logical operators for comparisons........ 36 2.2.5 Multiple choices: switch case....................... 39 2.3 Blocks and scopes of variables.............................. 40 2.3.1 Blocks of instructions............................... 40 2.3.2 Nested blocks and variable scopes.................... 41 2.4 Looping structures........................................ 41 2.4.1 Loop statement: while............................. 42 2.4.2 Loop statement: do-while........................... 43 2.4.3 Loop statement: for................................ 45 2.4.4 Boolean arithmetic expressions....................... 46 2.5 Unfolding loops and program termination................... 47 2.5.1 Unfolding loops.................................... 47 2.5.2 Never ending programs.............................. 47 2.5.3 Loop equivalence to universal while structures......... 48 2.5.4 Breaking loops at any time with break................ 48 2.5.5 Loops and program termination...................... 48 2.6 Certifying programs: Syntax, compilation and numerical bugs.. 49 2.7 Parsing program arguments from the command line........... 51 2.8 Exercises................................................ 53 Contents xiii 3. Functions and Recursive Functions......................... 57 3.1 Advantages of programming functions....................... 57 3.2 Declaring and calling functions............................. 58 3.2.1 Prototyping functions............................... 58 3.2.2 Examples of basic functions.......................... 59 3.2.3 A more elaborate example: The iterative factorial function 60 3.2.4 Functions with conditional statements................ 61 3.3 Static (class) variables.................................... 62 3.4 Pass-by-value of function arguments........................ 64 3.4.1 Basic argument passing mechanism................... 64 3.4.2 Local memory and function call stack................. 64 3.4.3 Side-eﬀects of functions: Changing the calling environment 67 3.4.4 Function signatures and function overloading.......... 68 3.5 Recursion............................................... 70 3.5.1 Revisiting the factorial function: A recursive function... 71 3.5.2 Fibonacci sequences................................ 72 3.5.3 Logarithmic mean.................................. 73 3.6 Terminal recursion for program eﬃciency **................. 74 3.7 Recursion and graphics **................................. 76 3.8 Halting problem: An undecidable task....................... 77 3.9 Exercises................................................ 79 4. Arrays...................................................... 83 4.1 Why do programmers need arrays?......................... 83 4.2 Declaring and initializing arrays............................ 83 4.2.1 Declaring arrays.................................... 83 4.2.2 Creating and initializing arrays....................... 84 4.2.3 Retrieving the size of arrays: length.................. 85 4.2.4 Index range of arrays and out-of-range exceptions...... 86 4.2.5 Releasing memory and garbage collector............... 87 4.3 The fundamental concept of array references................. 87 4.4 Arrays as function arguments.............................. 90 4.5 Multi-dimensional arrays: Arrays of arrays................... 93 4.5.1 Multi-dimensional regular arrays..................... 93 4.5.2 Multi-dimensional ragged arrays **................... 95 4.6 Arrays of strings and main function......................... 97 4.7 A basic application of arrays: Searching **................... 99 4.8 Exercises................................................ 101 xiv Contents Part II. Data-Structures & Algorithms 5. Objects and Strings........................................ 107 5.1 Why do programmers need objects?........................ 107 5.2 Declaring classes and creating objects....................... 108 5.2.1 Constructor and object creation...................... 109 5.2.2 The common null object............................ 110 5.2.3 Static (class) functions with objects as arguments...... 111 5.3 Objects and references.................................... 113 5.3.1 Copying objects: Cloning............................ 114 5.3.2 Testing for object equality........................... 114 5.4 Array of objects.......................................... 115 5.5 Objects with array members............................... 117 5.6 The standardized String objects........................... 117 5.6.1 Declaring and assigning String variables.............. 117 5.6.2 Length of a string: length()......................... 118 5.6.3 Equality test for strings: equals(String str)......... 118 5.6.4 Comparing strings: Lexicographic order............... 119 5.7 Revisiting a basic program skeleton......................... 122 5.8 Exercises................................................ 123 6. Searching and Sorting...................................... 127 6.1 Overview................................................ 127 6.2 Searching information..................................... 128 6.3 Sequential search......................................... 129 6.3.1 Complexity of sequential search...................... 131 6.3.2 Dynamically adding objects.......................... 131 6.3.3 Dichotomy/bisection search.......................... 133 6.4 Sorting arrays............................................ 134 6.4.1 Sorting by selection: SelectionSort.................. 135 6.4.2 Extending selection sort to objects................... 136 6.4.3 Complexity of selection sorting....................... 138 6.5 QuickSort: Recursive sorting............................... 139 6.5.1 Complexity analysis of QuickSort..................... 140 6.6 Searching by hashing..................................... 140 6.7 Exercises................................................ 142 7. Linked Lists................................................ 145 7.1 Introduction............................................. 145 7.2 Cells and lists............................................ 145 7.2.1 Illustrating the concepts of cells and lists.............. 145 Contents xv 7.2.2 List as an abstract data-structure.................... 146 7.2.3 Programming linked lists in Java..................... 146 7.2.4 Traversing linked lists............................... 147 7.2.5 Linked lists storing String elements................... 148 7.2.6 Length of a linked list............................... 149 7.2.7 Dynamic insertion: Adding an element to the list....... 150 7.2.8 Pretty printer for linked lists......................... 151 7.2.9 Removing an element from a linked list............... 151 7.2.10 Common mistakes when programming lists............ 153 7.3 Recursion on linked lists................................... 153 7.4 Copying linked lists....................................... 155 7.5 Creating linked lists from arrays............................ 156 7.6 Sorting linked lists........................................ 156 7.6.1 Merging ordered lists............................... 157 7.6.2 Recursive sorting of lists............................ 158 7.7 Summary on linked lists................................... 160 7.8 Application of linked lists: Hashing......................... 160 7.8.1 Open address hashing............................... 162 7.8.2 Solving collisions with linked lists.................... 164 7.9 Comparisons of core data-structures........................ 165 7.10 Exercises................................................ 165 8. Object-Oriented Data-Structures........................... 169 8.1 Introduction............................................. 169 8.2 Queues: First in ﬁrst out (FIFO)........................... 169 8.2.1 Queues as abstract data-structures: Interfaces.......... 169 8.2.2 Basic queue implementation: Static functions.......... 170 8.2.3 An application of queues: Set enumeration............. 172 8.3 Priority queues and heaps................................. 173 8.3.1 Retrieving the maximal element...................... 175 8.3.2 Adding an element................................. 175 8.3.3 Removing the topmost element....................... 177 8.4 Object-oriented data-structures: Methods.................... 178 8.5 Revisiting object-oriented style data-structures.............. 182 8.5.1 Object oriented priority queues...................... 182 8.5.2 Object-oriented lists................................ 183 8.6 Stacks: Last in ﬁrst out (LIFO) abstract data-structures....... 185 8.6.1 Stack interface and an array implementation........... 186 8.6.2 Implementing generic stacks with linked lists........... 187 8.7 Exercises................................................ 189 xvi Contents 9. Paradigms for Optimization Problems...................... 191 9.1 Introduction............................................. 191 9.2 Exhaustive search........................................ 192 9.2.1 Filling a knapsack.................................. 192 9.2.2 Backtracking illustrated: The eight queens puzzle....... 198 9.3 Greedy algorithms: Heuristics for guaranteed approximations.. 201 9.3.1 An approximate solution to the 0-1 knapsack problem... 201 9.3.2 A greedy algorithm for solving set cover problems...... 205 9.4 Dynamic programming: Optimal solution for the 0-1 knapsack problem................................................. 211 9.5 Optimization paradigms: Overview of complexity analysis..... 214 9.6 Exercices................................................ 216 10. The Science of Computing.................................. 219 10.1 The digital world......................................... 219 10.2 Nature of computing?..................................... 221 10.3 The digital equation...................................... 222 10.4 Birth of algorithms and computers.......................... 222 10.5 Computer science in the 21st century....................... 223 Part III. Exam Review 11. Exam & Solution.......................................... 227 Bibliography.................................................... 247 Index........................................................... 249 List of Figures 1.1 Implicit casting rules of primitive types......................... 16 1.2 Snapshot of the JCreator integrated development environment..... 26 2.1 Visualizing unary, binary and ternary operators................. 34 2.2 A geometric interpretation of Euclid’s algorithm. Here, illustrated for a = 65 and b = 25 (GCD(a, b) = 5).......................... 43 2.3 Newton’s method for ﬁnding the root of a function............... 44 3.1 Illustrating the function call stack: The function variables are allo- cated into the local memory stack and are thus not visible to other functions. The pass-by-value mechanism binds the function argu- ments with the respective expression values at calling time......... 65 3.2 Visualizing the local function call stack and the global memory for program FunctionSideEffect.java............................ 69 3.3 Visualizing the function call stack for the recursive factorial function. 72 3.4 Koch’s mathematical recursive snowﬂakes....................... 76 3.5 Sierpinski’s triangle fractal obtained by the program Sierpinski.java 78 4.1 A way to visualize arrays in Java, explained for the array declaration and assignment: int [] v ={2,3,1,2,7,1};........................... 89 4.2 Visualizing the structure of a ragged array in the global memory... 96 5.1 Visualizing the class ﬁelds and the object records when creating object instances of a class..................................... 111 5.2 Objects are non-primitive typed structures that are stored in the program global memory and manipulated by references (and not by values)...................................................... 113 xviii List of Figures 5.3 Testing for object equality using a tailored predicate that compares ﬁeld by ﬁeld the objects....................................... 115 7.1 Creating a linked list by iteratively calling the static function Insert. The arrows anchored at variable myList mean references to objects of type ListString................................. 150 7.2 Removing an element to the list by deconnecting its cell from the other chained cells............................................ 152 8.1 A queue implemented using an array requires two indices to indicate the last processed element and the ﬁrst free location.............. 170 8.2 A heap is a binary tree specialized so that the keys of all children are less than the keys of their parents........................... 174 8.3 Adding element 25 to the heap: First, add a new node at the ﬁrst immediate empty position; then eventually swap this node with its parent until the heap property is recovered...................... 176 8.4 Removing the maximal element of the heap: First, replace the root by the last leaf node, and then potentially swap this node with its current children until the heap property is recovered.............. 177 9.1 Illustrating one of the 92 distinct solutions to the eight queen puzzle 198 9.2 The 0-1 knapsack problem consists of ﬁnding the set of items that maximizes the overall utility while ﬁtting the knapsack capacity... 202 9.3 Example of an instance of a set cover problem: (a) input range space: set X = {X1 ,..., X12 } of 12 elements and a collection S = {{X1 , X2 }, {X5 , X6 }, {X9 , X10 }, {X2 , X8 }, {X6 , X7 , X10 , X11 }, {X1 , X2 , X3 , X5 , X9 , X10 , X11 }, {X3 , X4 , X7 , X8 , X11 , X12 }} of 7 sub- sets, and (b) optimal covering of size 3 since elements X1 , X4 and X6 are covered once by a diﬀerent subset........................ 206 9.4 Set cover problem for urban radio network planning of mobile phones: (a) Covering of 99 base transceiver stations, and (b) cover- ing using only 19 base stations. Here, some redundant areas covered more than four times......................................... 207 9.5 A bad instance for which the greedy set cover heuristic poorly be- haves. This generic construction yields an approximation factor of O(log n)..................................................... 211 10.1 In the digital world, all kinds of content is represented using univer- sal binary strings. Furthermore, all this content can be appropriately rendered using a universal computer. Nevertheless, for the consumer, industry proposes many tailored devices......................... 220 List of Figures xix 10.2 Once the content is available as a binary string we can apply generic algorithms such as copying, compressing, transmitting or archiving it without having to know, say, that it is a music or book string.... 221 List of Tables 1.1 Primitive data types of Java.................................... 13 7.1 Performance of various data-structures......................... 165 9.1 Table of u(i, j) evaluations..................................... 213 9.2 Extracting the solution from the dynamic programming table. Oi and ¬Oi meaning that we selected/did not select object Oi , respec- tively....................................................... 215 Listings 1.1 My ﬁrst Java program — A minimalist approach.............. 3 1.2 The Hello World Java program.............................. 5 1.3 Expression: Evaluating the volume of a 3D box................ 6 caption=Verbose program for calculating expressions............... 6 1.4 Boolean expressions and boolean variable assignments.......... 8 1.5 Program demonstrating the use of mathematical functions...... 9 1.6 Declaring constants........................................ 10 caption=Calculating the volume of a 3D box...................... 10 1.7 Sketch of the balance sheet program......................... 11 1.8 Balance sheet using integer variables......................... 12 1.9 Volume of a 3D box using double type variables.............. 14 1.10 Java distinguishes upper/lower cases......................... 14 1.11 Variable names should not belong to the list of reserved keywords 16 1.12 A quadratic equation solver................................. 19 1.13 Reading an integer value................................... 22 2.1 Quadratic equation solver with user input.................... 33 2.2 Lazy evaluation of boolean predicates........................ 38 2.3 Demonstration of the switch case statement................. 40 2.4 Euclid’s Greatest Common Divisor (GCD).................... 43 2.5 Newton’s approximation algorithm.......................... 45 2.6 Cumulative sum........................................... 45 2.7 Approaching π by Monte-Carlo simulation.................... 46 2.8 Boolean arithmetic expression............................... 47 2.9 Syracuse’s conjecture...................................... 48 2.10 Syntactically correct program............................... 49 2.11 Quadratic equation solver.................................. 50 2.12 A simple numerical bug.................................... 51 xxiv Listings 3.1 Basic program skeleton for deﬁning static functions............ 58 3.2 A basic demonstration class for deﬁning and calling static functions 59 3.3 Implementing the factorial function n!....................... 60 3.4 Function with branching structures.......................... 62 3.5 An example using a static (class) variable.................... 63 3.6 Illustrating the function call stack........................... 65 3.7 Pass-by-value does not change local variable of calling functions. 66 3.8 Toy example for illustrating how functions can change the envi- ronment.................................................. 67 3.9 Function signatures and overloading......................... 69 3.10 Function signatures do not take into account the return type.... 70 3.11 Recursive implementation of the factorial function............. 71 3.12 Displaying Fibonacci sequences using recursion................ 73 3.13 Logarithmic mean......................................... 74 3.14 Writing the factorial function using terminal recursion......... 75 3.15 Fibonacci calculation using terminal recursion................ 75 3.16 Sierpinski’s fractal triangles................................. 76 3.17 Recursive Syracuse: Testing for termination................... 78 3.18 Euclid’s greatest common divisor using recursion.............. 80 4.1 Static array declarations and creations....................... 85 4.2 Arrays and index out of bounds exception.................... 86 4.3 Arrays and references...................................... 88 4.4 Assign an array reference to another array: Sharing common elements................................................. 88 4.5 Printing the references of various typed arrays................ 89 4.6 Array argument in functions: Minimum element of an array..... 90 4.7 Creating and reporting array information using functions....... 91 4.8 Calculating the inner product of two vectors given as arrays.... 91 4.9 Function returning an array: Addition of vectors.............. 92 4.10 Swapping array elements by calling a function................ 93 4.11 Matrix-vector product function.............................. 94 4.12 Creating multidimensional arrays and retrieving their dimensions 95 4.13 Writing to the output the arguments of the invoked main function 97 4.14 Array of strings in main.................................... 98 4.15 Sequential search: Exhaustive search on arrays................ 99 4.16 Binary search: Fast dichotomic search on sorted arrays......... 100 4.17 Permuting strings and Java’s pass-by-reference................ 101 4.18 Bug in array declaration................................... 102 5.1 A class for storing dates with a constructor method............ 109 5.2 A small demonstration program using the Date class........... 109 5.3 Objects as function parameters and returned results........... 111 Listings xxv 5.4 Testing the Date class..................................... 112 5.5 Cloning objects: Two scenarii............................... 114 5.6 Predicate for checking whether two dates of type Date are iden- tical or not............................................... 114 5.7 The class XEvent and arrays of objects....................... 116 5.8 Lower/upper cases and ASCII codes of characters............. 119 5.9 Lower-case to upper-case string conversion.................... 120 5.10 Implementation of the lexicographic order on strings........... 121 5.11 Reporting the lexicographically minimum string of the command line arguments............................................ 121 5.12 A more evolved basic skeleton program that also deﬁnes classes. 122 5.13 A class for polynomials..................................... 124 6.1 Structuring data of a dictionary into basic object elements...... 128 6.2 Linear search on objects.................................... 130 6.3 A demonstration program using the Person object array....... 130 6.4 Adding new Person to the array............................ 132 6.5 Bisection search on sorted arrays............................ 133 6.6 Sorting by selecting iteratively the minimum elements.......... 135 6.7 Redeﬁning the predicate/swap primitives for sorting other types of elements............................................... 137 6.8 Selection sort on a set of EventObject elements............... 137 6.9 Experimentally calculating the worst-case complexity of selec- tion sorting............................................... 138 6.10 The partition procedure in QuickSort........................ 139 6.11 Recursive sorting.......................................... 140 6.12 A demonstration code for hashing strings..................... 141 7.1 Declaration of a linked list.................................. 147 7.2 Linked list class with constructor and basic functions.......... 147 7.3 Checking whether an element belongs to the list by traversing it. 148 7.4 Linked list storing String elements........................... 148 7.5 Static (class) function computing the length of a list........... 149 7.6 Inserting a new element to the list........................... 150 7.7 Pretty printer for lists..................................... 151 7.8 Static function writing the structure of a linked list into a String object.................................................... 151 7.9 Removing an element from a list............................ 152 7.10 Recursive function for computing the length of a list........... 153 7.11 Recursive membership function............................. 154 7.12 Recursive display of a list.................................. 154 7.13 Reversed recursive display of a list........................... 154 7.14 Copying iteratively a source list but reversing its order......... 155 xxvi Listings 7.15 Copying a source list by maintaining the original head-tail order 155 7.16 Merging two ordered linked lists............................. 158 7.17 Recursively sorting an arbitrary linked list.................... 159 7.18 Hashing a set of strings into a hash table..................... 161 7.19 A class for manipulating sparse polynomials.................. 166 7.20 An example of signature function for the Karp-Rabin pattern matching algorithm........................................ 167 8.1 A double queue with interface primitives implemented using static functions........................................... 170 8.2 Enumerating set elements using queues....................... 172 8.3 Retrieving the maximal priority............................. 175 8.4 Adding an element to the heap.............................. 176 8.5 Removing the topmost element from the heap................. 177 8.6 Linked list with static functions............................. 178 8.7 Linked list with static functions attached to a Toolbox class.... 179 8.8 Static functions attached to a library class.................... 180 8.9 Object methods for the list................................. 181 8.10 Object-oriented method for computing the volume of a 3D box.. 182 8.11 Heap: Prototyping object methods........................... 183 8.12 Linked list with object methods............................. 183 8.13 Linked list the object-oriented style: Methods................. 183 8.14 Demonstrating various calls of object methods................ 185 8.15 Stack implementation using an array......................... 186 8.16 Stack in action: A simple demonstration program.............. 187 8.17 Minimal list implementation................................ 188 8.18 Implementing the stack interface using a linked list as its back- bone data-structure........................................ 188 8.19 Demonstration program: Stacks using linked lists.............. 189 9.1 Plain enumeration using nested loops........................ 193 9.2 Enumerating all 2n binary number representations with n bits.. 194 9.3 Exhaustive search for the perfect ﬁlling of a knapsack.......... 196 9.4 Adding a cut to the recursive exhaustive search............... 197 9.5 Eight queen puzzle: Search with backtracking................. 199 9.6 Check whether two queens are in mutually safe position or not.. 199 9.7 Check whether the i-th queen is safe wrt. the k-th queens, for k < i.................................................... 200 9.8 Solving the 8-queen puzzle.................................. 200 9.9 Greedy approximation algorithm for solving the 0-1 knapsack... 203 9.10 Initializing a set cover problem.............................. 207 9.11 Basic operations for supporting the greedy algorithm.......... 208 9.12 Creating an instance of a set cover problem................... 209 Listings xxvii 9.13 Greedy algorithm for solving SCPs.......................... 209 9.14 Dynamic programming for solving the 0-1 knapsack............ 212 9.15 Extracting backward the optimal solution from the 2D table.... 213 exam/MysteriousProgram.java................................... 227 11.1 The class Point3D......................................... 230 11.2 Class Atom with the bump predicate.......................... 231 11.3 Class Molecule........................................... 231 11.4 Test program for Molecule................................. 232 11.5 The centroid of an Atom object.............................. 233 11.6 The Molecule class equipped with the bump predicate.......... 233 11.7 The various functions acting on Signal objects............... 238 11.8 Nim game solution........................................ 244 Part I Getting Started 1 Expressions, Variables and Assignments 1.1 Introduction In this chapter, we cover the very basics lying at the heart of every Java program. That is, we introduce the minimalist program that forms the skeleton common to all programs, and explain the programming cycle of writing, compiling, editing and executing code. We provide an overview of the key concepts of typed language and describe the primitive types of Java. Finally, we present the syntax of arithmetic operators and give details on basic input/output operations for writing our ﬁrst programs. 1.2 My ﬁrst Java programs 1.2.1 A minimalist program When learning any new programming language, it is traditional to start by ﬁrst looking at what programmers call the basic skeleton of any program. This skeleton lets them gain some understanding of the language syntax and presents the necessary wrapping code. First programs look often mystic, if not weird, since they reveal at once some of the key syntax components of the programming language. In its simplest form, consider the following “shortest” Java program: F. Nielsen, A Concise and Practical Introduction to Programming Algorithms in Java, Undergraduate Topics in Computer Science, DOI 10.1007/978-1-84882-339-6 1, c Springer-Verlag London Limited, 2009 4 1. Expressions, Variables and Assignments Program 1.1 My ﬁrst Java program — A minimalist approach c l a s s MyFirstProgram { public s t a t i c void main ( S t r i n g [ ] a r g s ) {} } At ﬁrst, everything in the above code seems strange to novice programmers. In fact, we will have to wait until Chapter 5 to get a full understanding of what the ﬁrst two lines actually mean. For now let us ignore these lines. To execute this program, we need to perform the following three steps: – Type this program into any text editor1 and store this ﬁle under ﬁlename MyFirstProgram.java. Extensions.java means that the ﬁle is a Java source code. The name of the ﬁle should bear the name appearing after the class keyword. – Compile the program by typing at the console: javac MyFirstProgram.java. This will generate a compiled ﬁle, called the bytecode, bearing the name MyFirstProgram.class. Check in the directory2 that this ﬁle was created. – Execute the program by typing the command java MyFirstProgram at the console prompt. This will execute the bytecode of MyFirstProgram.class. That is, it will run the program on the java virtual machine3 (JVM). Well, the program ran correctly but produced no apparent result, so that it is not very convincing to us that something really took place on the processor. In fact, the main function of the program was called upon execution, and the set of instructions contained inside the function was executed stepwise. Here, there was nothing to execute since the body of the main function is empty; the body of the main function is encapsulated into the program class MyFirstProgram and is delimited by the opening/closing of braces {}, also called curly brackets. So let us spice up this program by writing a message on the console output. 1.2.2 Hello World The “Hello Word” program is the emblematic program for comparing at a glance the syntax of diﬀerent programming languages. What we need to do is to add a single instruction line inside the former program to display the message 1 Like Notepad under WindowsTM or Nedit in Linux-based KDE environments. 2 In Windows, type dir at the console prompt. In Unix, use the equivalent ls command. 3 Java bytecode is cross-platform, which means that provided that there exists a JVM implementation for the target machine, you will be able to run your bytecode on that environment. This is one of the key strengths of Java in today’s market. 1.3 Expressions and programs as calculators 5 “Hello World.” Let us choose the program name to be HelloWorld.java. Then we need to label the program class with that name too. To display a message, we use the instruction System.out.println(message);. Instructions are followed by a semi-colon “;” mark. Thus we get our slightly revised program: Program 1.2 The Hello World Java program c l a s s HelloWorld { public s t a t i c void main ( S t r i n g [ ] a r g s ) { System. out. p r i n t l n ( " Hello World " ) ; } } Again, let us go through the workﬂow of editing/compiling and running the program as follows: – Type this program and store it under ﬁlename HelloWorld.java. – Compile this program by typing in the console: javac HelloWorld (im- plicitly meaning javac HelloWorld.java). A bytecode HelloWorld.class is produced in the same directory. The bytecode is not human readable, only machine readable! Try to open the ﬁle and look at the strange sequence of symbols that encode this compiled program. At this stage, it should be clear that ﬁles ending with the extension.java are source codes, and ﬁles ending with extensions.class are bytecodes. – Execute the program by typing the command java HelloWorld (implicitly meaning java HelloWorld.class) at the console prompt. You will now get the result visible in the output console as follows: Hello World Congratulations, you successfully wrote your ﬁrst program. Let us now see how to perform arithmetic calculations. 1.3 Expressions and programs as calculators The ﬁrst program you may think of is to compute formulas4 for various input. Assume, for example, we are given a 3D box with the following dimensions: 4 Historically, this objective was one of the very ﬁrst motivations for programming languages. FORTRAN, which stands for FORmula TRANslation, is such an example that was widely used by physicists for simulation purposes. Although FORTRAN is nowadays a bit outdated, there is still a lot of legacy code running daily (for example, weather forecasting). 6 1. Expressions, Variables and Assignments 50cm in width, 100cm in height and 20cm in depth. We simply do compute the volume in cubic meters m3 by converting the dimension units into meter equivalents and performing the product of these dimensions to get the volume. Thus the volume of that 3D box is 0.5m × 1m × 0.2m = 0.1m3. How do we program this? We simply need to evaluate the arithmetic expression 0.5 × 1 × 0.2 Program 1.3 Expression: Evaluating the volume of a 3D box c l a s s VolumeBox{ public s t a t i c void main ( S t r i n g [ ] a r g s ) { System. out. p r i n t l n ( 0. 5 ∗ 1 ∗ 0. 2 ) ; } } Storing the above program into ﬁlename VolumeBox.java, compiling and executing it, we get the expected output: 0.1 Thus we can calculate the value of any arithmetic expression, say the generic myExpression expression, and display its value by executing the instruction System.out.println(myExpression); Of course, this straight number alone is not very informative, so it is better to display a message on the console telling what the number really means. We do this by printing the message without the return carriage (line return) using the instruction System.out.print. c l a s s VerboseVolumeBox { public s t a t i c void main ( S t r i n g [ ] a r g s ) { System. out. p r i n t ( " Volume of the box ( in cubic meters ):" ) ; System. out. p r i n t l n ( 0. 5 ∗ 1 ∗ 0. 2 ) ; } } Compiling and running this program yields the better verbose output: Volume of the box (in cubic meters):0.1 1.3.1 Arithmetic operations and priority order The arithmetic operations used in expressions are: – The addition (+) 1.3 Expressions and programs as calculators 7 – The subtraction (-) – The multiplication (*) – The division (/) – The modulo (remainder, %) These operations depend on the type of operands, and yield the usual bugs. For example, consider the variable q deﬁned as: int q=2/3; This initializes the integer variable q to 0 since the division / is the Euclidean division.5 Programmers have to take care with variable initializations, especially when implicit casting occurs. To illustrate these points, consider the following code snippet: double qq=2/3; double qqq=2/3.0; Although variable qq is declared of type double the division operands 2 and 3 have been identiﬁed as integers so that the compiler will compute the Euclidean division and get the integer 0, which will then be implicitly cast into a double (see Figure 1.1): 0.0. However, when declaring and initializing double variable qqq, since the second operand is of type double, the ﬁrst operand will be cast into a double, and the double division will be performed yielding the expected result: 0.6666666666666666. The operators unambiguously satisfy priority rules so that parentheses may be omitted when forming expressions for ease of reading. For example, consider the expression 7+9*6. This expression admits two kinds of parentheses: (7+9)*6 and 7+(9*6). But since the multiplication has higher priority over the addition, it is understood that the expression 7+9*6 is meant to be 7+(9*6), and evaluates to 61. As we will see in the next chapter, an important class of expressions are boolean expressions, which are used in program control structures. Boolean expressions admit only two outcomes: true or false. The most common logical operators are && for AND and for OR. Thus for boolean variables a and b, the boolean expression a&&b; is evaluated to true if and only if both a and b are true. The following program presents the use of boolean expressions and boolean variable assignments: 5 In Euclidean division, x/y computes the Euclidean ratio of x by y, and x%y computes the remainder. 8 1. Expressions, Variables and Assignments Program 1.4 Boolean expressions and boolean variable assignments class BooleanExpression { public s t a t i c void main ( S t r i n g [ ] a r g s ) { boolean a=true ; boolean b=f a l s e ; boolean expr1=a | | b ; boolean expr2=a&&b ; System. out. p r i n t ( "a || b=" ) ; System. out. p r i n t l n ( expr1 ) ; System. out. p r i n t ( "a && b=" ) ; System. out. p r i n t l n ( expr2 ) ; } } Compiling and running this program, we get the following console output: a||b=true a&&b=false Boolean expressions and their role in program workﬂows will be presented in the next chapter. 1.3.2 Mathematical functions In Java, mathematical functions including trigonometric sine and cosine functions and constants are all encapsulated into the Math class. The most usual functions6 are summarized in the table below: 6 Refer to the on-line documentation at http://java.sun.com/j2se/1.4.2/docs/ api/java/lang/Math.html for complete description of the available set of functions. 1.3 Expressions and programs as calculators 9 Math.PI π (3.141592...) Math.E e (2.71828...) Math.abs(x) x (absolute value) Math.ceil(x) x (ceil function) Math.round(x) round to nearest integer √ Math.sqrt(x) x (square root function) Math.log(x) ln x (loge x) Math.log10(x) log10 x Math.pow(x,y) xy (power function) Math.cos(x) cos x (cosine function) Math.sin(x) sin x (sine function) Math.tan(x) tan x (tangent function) The program below demonstrates a more elaborate program for computing a formula: Program 1.5 Program demonstrating the use of mathematical functions c l a s s MathFunction { public s t a t i c void main ( S t r i n g [ ] a r g s ) { double x=Math. E ; double f x=Math. l o g ( x ) ; System. out. p r i n t ( " Is this precisely 1 or are there numerical errors ? " ) ; System. out. p r i n t l n ( f x ) ; x=Math. PI / 1 5. 0 ; f x=Math. s i n ( x ) ∗Math. s i n ( x )+Math. c o s ( x ) ∗Math. c o s ( x ) ; System. out. p r i n t ( " What about this trigonometric equality ( should be 1) ?" ) ; System. out. p r i n t l n ( f x ) ; } } The output of the program is: Is this precisely 1 or are there numerical errors? 1.0 What about this trigonometric equality (should be 1) ?1.0000000000000002 Note that the constant Math.E is deﬁned as the double value that is closer than any other to e. Observe that in the second case, we should mathematically have the identity sin2 θ + cos2 θ = 1, but due to numerical imprecisions, we end up only with a very close number: 1.0000000000000002. 10 1. Expressions, Variables and Assignments 1.3.3 Declaring constants Constants are declared by prepending to the type of variables the keyword static. That is, constants are immutable variables. Constants are also typed too. For instance, we may wish to deﬁne our own approximation of the mathematical constant π as follows: final double PI = 3.14; The declaration of constants should be made inside the body of the class (and not inside functions). Program 1.6 Declaring constants class ConstantDeclaration { f i n a l s t a t i c i n t One=1; f i n a l s t a t i c i n t Two=2; public s t a t i c void main ( S t r i n g [ ] a r g s ) { i n t Three=One+Two ; System. out. p r i n t l n ( Three ) ; } } 1.4 Commenting Java programs It is useful to comment programs to describe parts of the code and the various input/output formats of programs. Not only does it become crucial for us when revisiting a program months later, it also becomes absolutely necessary when sharing a program with others. Java has two types of comments: single lines and multiple lines illustrated as below: // This is a single line comment Let us illustrate the comment syntax by commenting the former VerboseVolumeBox.java program: c l a s s VerboseVolumeBox { 1.5 Indenting programs 11 public s t a t i c void main ( S t r i n g [ ] a r g s ) { System. out. p r i n t ( " Volume of the box ( in cubic meter ):" ) ; // Result is in cubic meter unit System. out. p r i n t l n ( 0. 5 ∗ 1 ∗ 0. 2 ) ; } } 1.5 Indenting programs Java source codes are parsed by the compiler javac, which checks the syntax of the program and generates an overly optimized bytecode that is a low-level machine-interpretable bytecode. Indenting a program consists of making the source code prettier by adding a few extra spaces or return lines. Indenting consists of applying several conventions like aligning columns of opening/closing braces, etc. Code indentation does not change the bytecode. For example, the following badly indented source code will produce the same bytecode although it obfuscates its readibility. c l a s s NotIndentedVolumeBox { public s t a t i c void main ( S t r i n g [ ] a r g s ) { System. out. p r i n t ( " Volume of the box ( in cubic meter ):" ) ; System. out. p r i n t l n ( 0. 5 ∗ 1 ∗ 0. 2 ) ; } } As a rule of thumb, it is important for programmers to comment and indent source codes well to improve their readibility. Indenting also helps browsing lengthy source codes. 1.6 Variables, assignments and type checking Suppose now that we would like to compute the balance of a set of credits with a set of debits. We ﬁrst need to compute the total credit ﬁgure, then the total debit ﬁgure and subtract these two ﬁgures to get the balance. Computing the total credit and debit can be done and displayed using the former syntax System.out.println(myExpression);. But what about the balance? For example, consider we have two credit lines (say, 100 and 150 dollars), and three debit lines (50, 25 and 100 dollars). Then, we would have the following code: Program 1.7 Sketch of the balance sheet program class BalanceSheet { public s t a t i c void main ( S t r i n g [ ] a r g s ) 12 1. Expressions, Variables and Assignments { System. out. p r i n t ( " Total credit ( in US dollars ) :\ t" ) ; System. out. p r i n t l n (100+150) ; System. out. p r i n t ( " Total debit ( in US dollars ) :\ t" ) ; System. out. p r i n t l n (50+25+100) ; System. out. p r i n t ( " Balance :" ) ; } } Running this program, we get: Total credit (in US dollars): 250 Total debit (in US dollars): 175 Note that the \t inside the string "Total credit (in US dollars):\t" denotes the tabulation character that allows one to nicely align the latter numbers. The problem is to get the balance we need to subtract 175 from 250. Of course, this could be computed and displayed with the instruction: System.out.println((100+150)-(50+25+100));...but this will not yield an eﬃcient approach since we would again compute the two cumulative credit/debit sums. A much better strategy consists of storing intermediate calculations in containers by using variables, as explained next. 1.6.1 Variables for storing intermediate values In Java, variables are all typed. Java belongs to the large category of typed programming languages. This means that we need to specify the type of variables when declaring variables. To declare a variable named credit for storing the overall credit modeled as an integer number, we use the syntax: int credit; Variables always need to be declared before use. By convention, we choose in this textbook to declare all variables at the beginning of the main block (delimited by the braces {}). In this application, we consider that credit/debit numbers are natural numbers (integers), so that we declare the variable to be of type int. Program 1.8 Balance sheet using integer variables class BalanceSheet2 { public s t a t i c void main ( S t r i n g [ ] a r g s ) { int c r e d i t ; int d e b i t ; 1.6 Variables, assignments and type checking 13 c r e d i t =100+150; System. out. p r i n t ( " Total credit ( in US dollars ) :\ t" ) ; System. out. p r i n t l n ( c r e d i t ) ; d e b i t =50+25+100; System. out. p r i n t ( " Total debit ( in US dollars ) :\ t" ) ; System. out. p r i n t l n ( d e b i t ) ; System. out. p r i n t ( " Balance :" ) ; System. out. p r i n t l n ( c r e d i t −d e b i t ) ; } } Running the above program, we get the console output: Total credit (in US dollars): 250 Total debit (in US dollars): 175 Balance:75 In Java, we can choose to declare variables using one of the following primitive types7 : int (integer simple precision stored onto a machine word of 32 bits), long (integer double precision stored onto two machine words, 64 bits), float (simple precision real stored onto a machine word), double (double precision real ), char (character encoding worldwide language characters using 16 bits8 ) and boolean (two states: true or false). Table 1.1 lists the primitive types of Java with their respective encoding representations and range of values. All primitive types of Java are manipulated by value. Boolean boolean 1 bit true or false Character char 2 bytes UNICODE Integer byte 1 byte [−128, 128] Integer short 2 bytes [−32768, 32767] Integer int 4 bytes [−231 = −2147483648, 231 − 1 = 21477483647] Integer long 8 bytes [−263 = −9223372036854775808, 263 − 1 = 9223372036854775807] Real float 4 bytes [1.40129846432481707e − 45f, 3.40282346638528860e + 38f ] Real double 8 bytes [2.2250738585072014e − 308d, 1.79769313486231570e + 308d] Table 1.1 Primitive data types of Java. We can also compactly declare and initialize variables at once as follows: 7 There is also the less used byte and short primitive types that we voluntarily omit in this book. 8 Java uses the UNICODE standard for coding characters using 16 bits (2 bytes). This allows programmers to encode a wide range of characters including Chinese/Korean and Japanese kanji. The traditional 8-bit ASCII encoding is limited to the Roman alphabet. 14 1. Expressions, Variables and Assignments int credit1=100, credit2=150; int credit=credit1+credit2; int debit1=50, debit2=25, debit3=100; int debit=debit1+debit2+debit3; int balance=credit-debit; System.out.print("Balance:"); System.out.println(balance); This example illustrates two constructions: – Variable declaration and assignment to a constant (a basic expression — see for example, variable credit1) – Variable declaration and assignment to an arithmetic expression (see for example, variable debit1). As we have formerly seen, variables are useful for storing initial values. Thus these variables play an important role in the initialization of programs. For example, the former program for computing the volume of a 3D box can be rewritten as: Program 1.9 Volume of a 3D box using double type variables c l a s s VerboseVolumeBox2 { public s t a t i c void main ( S t r i n g [ ] a r g s ) { double width =0.5 , h e i g h t =1.0 , depth = 0. 2 ; System. out. p r i n t ( " Volume of the box ( in cubic meter ):" ) ; System. out. p r i n t l n ( width ∗ h e i g h t ∗ depth ) ; } } Java distinguishes upper from lower case in variable names, as exempliﬁed below: Program 1.10 Java distinguishes upper/lower cases c l a s s UpperLowerCase { public s t a t i c void main ( S t r i n g arguments [ ] ) { i n t MyVar ; // myvar variable is different from MyVar i n t myvar ; // Generate a syntax error at compile time : // cannot find symbol variable myVar System. out. p r i n t l n ( myVar ) ; } } That is, Java is case-sensitive. 1.6 Variables, assignments and type checking 15 1.6.2 Type checking for assignments and casting 1.6.2.1 Type checking. Whenever assigning a variable, the compiler javac checks that the type of the expression coincides with the type of the variable. If not, the compiler reports an error message and aborts (without generating proper bytecode). For example, consider the code below: class TypeError{ public static void main (String[ ] args) { double myFavoriteReal=3.141592; int myFavoriteNat=2.71; } } Compiling this code will generate an error as follow: prompt%javac TypeError.java TypeError.java:5: possible loss of precision found : double required: int int myFavoriteNat=2.71; ^ 1 error prompt% That is, the compiler performed the type checking and found that the type of the expression (here, the real constant 2.71 of type double) does not agree with the type of the int variable myFavoriteNat. Typing provides an essential safeguard mechanism for writing more coherent programs, that is programs without obvious bugs. 1.6.2.2 Casting types. We can eventually transform that real 2.71 by truncating it into the integer 2 by a casting operation: int myFavoriteNat=(int)2.71; This results in a loss of precision, as noticed by the compiler. In general, we can explicitly cast a type TypeExpr into a TypeVar using the following syntax: TypeVar myVar=(TypeExpr)(Expression); Typed languages such as Java are useful to abstract notions and types of variables characterizing semantic parameters. In college, we are familiar with similar notions to assign quantity of the same units. For example, it does not make sense to assign to a velocity (type m×s−1 ) an acceleration (type m×s−2 ). In fact, some earlier casting operations were already carried out when declaring and initializing constants: 16 1. Expressions, Variables and Assignments double x=2; // implicit casting int -> double double x=(double ) 2 ; // explicit casting long x = 2. 0 ; // implicit casting double -> long double x =2.0d ; // The constant 2.0 is declared of type double // add a ’d ’ after the number The implicit casting rules of primitive types are summarized in Figure 1.1. double float long int char short byte Figure 1.1 Implicit casting rules of primitive types For example, consider the following code snippet that implicitly casts a character (of type char) into its corresponding ASCII integer code: char c=’X’; int code=c; System.out.println(code); We get the ASCII code 88 for the capital letter ’X’. There are slight restrictions on the names of variables that should not begin with a digit, nor bear the name of a reserved keyword of the language. Trying to use a reserved keyword for the name of a variable will result in a compiler error as illustrated in the following code: Program 1.11 Variable names should not belong to the list of reserved keywords c l a s s ReservedKeyword { public s t a t i c void main ( S t r i n g a r g [ ] ) { double x , y ; // Generate a syntax error : // " not a statement " i n t import ; } } 1.7 Incrementing/decrementing variables 17 The list of reserved keywords for Java is: abstract, assert, boolean, break, byte, case, catch, char, class, const, continue, default, do, double, else, extends, false, final, finally, float, for, goto, if, implements, import, instanceof, int, interface, long, native, new, null, package, private, protected, public, return, short, static, strictfp, super, switch, synchronized, this, throw, throws, transient, true, try, void, volatile, while. 1.6.3 The inner mechanisms of assignments The prototype instruction for assigning a variable var of type TypeVar is the following atomic instruction: var=Expression; The compiler proceeds the following three steps: – Evaluate the expression Expression into a value, – Check that the type of the value coincides with the type of the variable (type checking). If not, check whether some implicit casting rules apply (see Figure 1.1). If types cannot coincide, then the compiler generates an error message and aborts. – Store the value of the expression at the memory location referenced by the variable. We further explain these two sides value/memory location of variables in the next section dealing with special assignment instructions: variable increments. 1.7 Incrementing/decrementing variables 1.7.1 General mechanism for incrementation Incrementing a variable x by an amount increment (that is, incrementing the variable x by a step of width increment) consists of adding to the value of the variable the value of the increment, and in storing the result at the memory location referenced by variable x. Incrementing a variable without specifying its amount means to add one to its value. Incrementation is thus nothing other than a particular form of assignment where a variable appears on both sides of the equality sign =: x=x+increment; 18 1. Expressions, Variables and Assignments The variable on the left hand side means “store at the memory location referenced by that variable,” while the variable on the right hand side means “get the value stored at the memory location referenced by that variable.” For programmer novices, the instruction x=x+increment; is quite confusing at ﬁrst since it makes no mathematical sense. Let us deconstruct the action taken by the compiler when encountering such an instruction: – Evaluate arithmetic expression x+increment: – Perform type checking of increment with x (cast increment type if necessary), – Get the value xVal stored at memory location referenced by x, – Get the value incrementVal stored at memory location referenced by increment, – Return the value xVal+incrementVal. – Finally, store the expression value at memory location referenced by x. Instead of writing x=x+increment, we can equivalently write this instruction compactly using the following shortcut: x+=increment Similarly, we can decrement a variable by a given step as follows: x-=increment These basic shortcuts extend9 also to the / and ∗ operators: int y=1; y*=3; // y=3, multiplication assignment int z=12; z/=2; // z=6, division assignment int p=23; p%=2; // p=1, modulo assignment 1.7.2 Pre-incrementation and post-incrementation Often we need to add or subtract one to (the value of) a variable, say x. This can be done as follows: x=x+1; x+=1; // compact form x=x-1; x-=1; // compact form 9 These shortcut instructions are, however, rarely used in practice. 1.7 Incrementing/decrementing variables 19 These incrementation instructions are so frequent that they can be ei- ther written compactly as ++x or x++ (for pre-incrementation and post- incrementation). Let us explain the diﬀerence between pre-incrementation and post-incrementation: Consider the following code: i=2; j=i++; This gives the value 3 to i and 2 to j as we do a post-incrementation. That is, we increment after having evaluated the expression i++. The above code is equivalent to: i=2; j=i; i=i+1; // or equivalently i+=1; Alternatively, consider the pre-incrementation code: i=2; j=++i; This code is equivalent to... i=2; i=i+1; j=i;... and thus both the values of i and j are equal to 3 in this case. The same explanations hold for pre-decremention −−i and post-decrementation i−−. Note that technically speaking the ++ syntax can be seen as a unary operator. 1.7.3 A calculator for solving quadratic equations Let us put altogether the use of mathematical functions with variable initializa- √ 2 −4ac tions and assignments in a simple program that computes the roots b ± b 2a of a quadratic equation ax2 + bx + c = 0: Program 1.12 A quadratic equation solver class QuadraticEquationSolver { public s t a t i c void main ( S t r i n g [ ] a r g ) { double a , b , c ; a=Math. s q r t ( 3. 0 ) ; b=2.0; c = −3.0; double d e l t a=b∗b −4.0∗ a ∗ c ; double r o o t 1 , r o o t 2 ; 20 1. Expressions, Variables and Assignments r o o t 1= (−b−Math. s q r t ( d e l t a ) ) / ( 2. 0 ∗ a ) ; r o o t 2= (−b+Math. s q r t ( d e l t a ) ) / ( 2. 0 ∗ a ) ; System. out. p r i n t l n ( r o o t 1 ) ; System. out. p r i n t l n ( r o o t 2 ) ; System. out. p r i n t l n ( " Let us check the roots :" ) ; System. out. p r i n t l n ( a ∗ r o o t 1 ∗ r o o t 1+b∗ r o o t 1+c ) ; System. out. p r i n t l n ( a ∗ r o o t 2 ∗ r o o t 2+b∗ r o o t 2+c ) ; } } Note that for this particular initialization, we have delta>0. Otherwise, there are imaginary roots, and the program will crash in the Math.sqrt function. 1.8 Basics of Java input/output (I/O) In this section, we quickly review the elementary instructions for reading or writing on the console. We will then see how to redirect input/output from/to ﬁles. 1.8.1 Computing does not mean displaying In Java, one needs to explicitly display results on the console to read them back. Printing the results on the console is one way to retrieve or export the results of programs. This is very diﬀerent from most mathematical symbolic systems such as Maple,R 10 which computes and displays results at once. For example, in Maple computing 2 + 2 will not only compute the sum but also display the result 4: >2+2; 4 This is one frequent source of confusion for beginners who have had prior “programming” experience with such mathematical packages. Remember that in Java, we need to explicitly display results. 1.8.1.1 Displaying results on the console. To display messages on the console in Java, one invokes either System.out.println for writing a string message with a return line, or System.out.print for writing a message without the return line. One can also display integers, reals or strings. Since it is quite cumbersome to write several System.out.print[ln] at a row like: 10 http://www.maplesoft.com/ 1.8 Basics of Java input/output (I/O) 21 System.out.println("The value of x is "); System.out.print(x); To bypass these two instructions, one often uses string concatenations when formatting messages compactly. 1.8.1.2 Displaying & String concatenations. The former code is equivalent to the following: System.out.println("The value of x is "+x); For novice programmers, this code looks like a magic expression for outputting messages on the console. However, this can also at ﬁrst yield unexpected results for beginners like: int x=3; System.out.println("value="+x+1); Since the printed message on the console is 31, and not 4 as one would expect. The correct result would have been obtained by setting parentheses around x+1 as follows: System.out.println("value="+(x+1)); The trick is that the + between "value=" and (x+1) has a diﬀerent semantic than the + in x+1. What happens is that in the former case, the argument "value="+x+1 of System.out.println is evaluated following the priority order rules. That is, the compiler cast the integer value x into a string “3” and appends it to string “value=” giving the string “value=3.” Then the integer 1 is converted into the string “1” and appended to “value=3” giving the ﬁnal string “value=31.” Setting parenthesis around x + 1 let us change the priority order, so that x + 1 is ﬁrst evaluated to give integer 4, and then string concatenation are performed after casting the 4 into the corresponding string “4.” The following program summarizes and exempliﬁes our discussion: i n t a =1 , b=−2; System. out. p r i n t ( "a=" ) ; System. out. p r i n t ( a ) ; System. out. p r i n t ( " b=" ) ; System. out. p r i n t l n ( b ) ; System. out. p r i n t l n ( "a="+a+" b="+b ) ; S t r i n g s 1=" Lecture in " , s 2=" Java " ; S t r i n g s=s 1+s 2 ; // Perform explicit string concatenation System. out. p r i n t l n ( s ) ; 1.8.2 Keyboard input Programs often require users to give interactive parameters that play an important role in initialization of programs. At each run, the program asks for 22 1. Expressions, Variables and Assignments some user keyboard input to deliver the solution. Java I/O is quite elaborate compared to other similar imperative languages like C++ because it has been designed to ﬁt the object-oriented style that will be explained later on. For now, consider reading input from the console using the following syntax: Program 1.13 Reading an integer value import j a v a. u t i l. ∗ ; c l a s s KeyboardIntInput { public s t a t i c void main ( S t r i n g [ ] a r g s ) { Scanner keyboard=new Scanner ( System. i n ) ; int val ; System. out. p r i n t ( " Enter an integer please :" ) ; v a l=keyboard. n e x t I n t ( ) ; System. out. p r i n t ( "I read the following value :" ) ; System. out. p r i n t l n ( v a l ) ; } } The output of a running session gives: Enter an integer please:5 I read the following value:5 In the former code, we again used two magic lines, import java.util.∗; and Scanner keyboard=new Scanner(System.in);, which will be fully explained later, in the second part of this book. We can similarly read float and double values using keyboard.nextFloat(); and keyboard.nextDouble() instructions: System. out. p r i n t ( " Enter a single - precision real please :" ) ; v a l f=keyboard. n e x t F l o a t ( ) ; System. out. p r i n t ( "I read the following value :" ) ; System. out. p r i n t l n ( v a l f ) ; System. out. p r i n t ( " Enter a double precision please :" ) ; v a l d=keyboard. nextDouble ( ) ; System. out. p r i n t ( "I read the following value :" ) ; System. out. p r i n t l n ( v a l d ) ; In case the above code snippet yields an error at run time, which is due to the number formatting conventions 11 , add the instruction keyboard.useLocale( Locale.US); 11 In the US, real numbers are written using the a decimal dot “.” while in European countries it is a decimal comma “,.” By default, Java is installed with the country local settings. 1.8 Basics of Java input/output (I/O) 23 1.8.3 File redirections Instead of writing messages to the console, one can redirect them to a text ﬁle without changing the source code, using the > symbol in the command line. For example consider the following toy program, which asks for an integer and squares it: import j a v a. u t i l. ∗ ; c l a s s SmallProg { public s t a t i c void main ( S t r i n g [ ] a r g s ) { Scanner keyboard=new Scanner ( System. i n ) ; int val ; System. out. p r i n t ( " Enter an integer please :" ) ; v a l=keyboard. n e x t I n t ( ) ; v a l ∗=v a l ; // squared the input value System. out. p r i n t l n ( " Squared value ="+v a l ) ; } } Running the program from the console, we get: prompt%java SmallProg Enter an integer please:5 Squared value=25 Let us now store the output message into a text ﬁlename output.txt. We have prompt%java SmallProg >output.txt 4 The above number 4 is the number input by the user when running the program. Let us inspect the ﬁle named output.txt by opening it: Enter an integer please:Squared value=16 Thus all messages printed out using the instruction System.out.print[ln ] have been redirected to ﬁlename output.txt. Similarly, we can set the input of a program from a ﬁlename by redirecting the input from the command line using the symbol =0 in the block of instructions executed when expression delta>=0 is true. Running this program twice with respective user keyboard input 1 2 3 and -1 2 3 yields the following session: Enter a,b,c of equation ax^2+bx+c=0:1 2 3 No real roots Enter a,b,c of equation ax^2+bx+c=0:-1 2 3 Two real roots:3.0 -1.0 In the if else conditionals, the boolean expressions used to select the appropriate branchings are also called boolean predicates. 34 2. Conditional Structures and Loops 2.2.2 Ternary operator for branching instructions: Predicate ? A : B In Java, there is also a special compact form of the if else conditional used for variable assignments called a ternary operator. This ternary operator Predicate ? A : B provided for branching assignments is illustrated in the sample code below: double x1=Math. PI ; // constants defined in the Math class double x2=Math. E ; double min=(x1>x2 ) ? x2 : x1 ; // min value double d i f f = ( x1>x2 ) ? x1−x2 : x2−x1 ; // absolute value System. out. p r i n t l n ( min+" difference with max ="+ d i f f ) ; Executing this code, we get: 2.718281828459045 difference with max=0.423310825130748 The compact instruction double min=(x1>x2)? x2 : x1;...is therefore equivalent to: double min; if (x1>x2) min=x2; else min=x1; Figure 2.1 depicts the schema for unary, binary and ternary operators. Unary operator Binary operator Ternary operator ++ * ?: a a b Predicate a b a++ a*b (Predicate? a : b) post-incrementation multiplication compact branching Figure 2.1 Visualizing unary, binary and ternary operators 2.2 Conditional structures: Simple and multiple choices 35 2.2.3 Nested conditionals Conditional structures may also be nested yielding various complex program workﬂows. For example, we may further enhance the output message of our former date comparison as follows: int h1 =... , m1 =... , s 1 =... ; int h2 =... , m2 =... , s 2 =... ; int hs1 = 3600∗ h1 + 60∗m1 + s 1 ; int hs2 = 3600∗ h2 + 60∗m2 + s 2 ; int d=hs2−hs1 ; i f ( d>0) { System. out. p r i n t l n ( " larger " ) ; } else { i f ( d0) System.out.println("larger"); else if (d= greater than or equal to == equal to != not equal to One of the most frequent programming errors is to use the equality symbol = instead of the relational operator == to test for equalities: int x=0; if (x=1) System.out.println("x equals 1"); else System.out.println("x is different from 1"); Fortunately, the compiler generates an error message since in that case types boolean/int are incompatible when performing type checking in the expression x=1. But beware that this will not be detected by the compiler in the case of boolean variables: boolean x=false; if (x=true) System.out.println("x is true"); else System.out.println("x is false"); In that case the predicate x=true contains an assignment x=true and the evaluated value of the “expression” yields true, so that the program branches on the instruction System.out.println("x is true");. A boolean predicate may consist of several relation operators connected using logical operators from the table: && and || or ! not The logic truth tables of these connectors are given as: && true false || true false true true false true true true false false false false true false Whenever logical operators are used in predicates, the boolean expressions are evaluated in a lazy fashion as follows: – For the && connector, in Expr1 && Expr2 do not evaluate Expr2 if Expr1 is evaluated to false since we alreaady know that in that case that Expr1 && Expr2 = false whatever the true/false outcome value of expression Expr2. 38 2. Conditional Structures and Loops – Similarly, for the || connector, in Expr1 || Expr2 do not evaluate Expr2 if Expr1 is evaluated to true since we already know that in that case Expr1 || Expr2 = true whatever the true/false value of expression Expr2. The lazy evaluation of boolean predicates will become helpful when manipu- lating arrays later on. For now, let us illustrate these notions with a simple example: Program 2.2 Lazy evaluation of boolean predicates class LazyEvaluation { public s t a t i c void main ( S t r i n g [ ] a r g s ) { double x =3.14 , y = 0. 0 ; boolean t e s t 1 , t e s t 2 ; // Here division by zero yields a problem // But this is prevented in the && by first checking whether the denominator is // zero or not i f ( ( y ! = 0. 0 ) && ( x/y >2.0) ) { // Do nothing ; } else { // Block t e s t 1 =(y ! = 0. 0 ) ; t e s t 2 =(x/y >2.0) ; System. out. p r i n t l n ( " Test1 :"+t e s t 1+" Test2 :"+t e s t 2 ) ; System. out. p r i n t l n ( " We did not evaluate x/y that is equal to "+(x/y ) ) ; } // Here , again we do not compute x/y since the first term is true i f ( ( y==0.0) | | ( x/y >2.0) ) { // Block System. out. p r i n t l n ( " Actually , again , we did not evaluate x/y that is equal to "+(x/y ) ) ; } } } Running this program, we get the following console output: Test1:false Test2:true We did not evaluate x/y that is equal to Infinity Actually, again, we did not evaluate x/y that is equal to Infinity 2.2 Conditional structures: Simple and multiple choices 39 2.2.5 Multiple choices: switch case The nested if else conditional instructions presented in § 2.2.3 are somehow diﬃcult to use in case one would like to check that a given variable is equal to such or such a value. Indeed, nested blocks of instructions are diﬃcult to properly visualize on the screen. In the case of multiple choices, it is better to use the switch case structure that branches on the appropriate set of instructions depending on the value of a given expression. For example, consider the code: c l a s s ProgSwitch { public s t a t i c void main ( S t r i n g a r g [ ] ) { System. out. p r i n t ( " Input a digit in [0..9]: " ) ; Scanner keyboard=new Scanner ( System. i n ) ; i n t n=keyboard. n e x t I n t ( ) ; switch ( n ) { case 0 : System. out. p r i n t l n ( " zero " ) ; break ; case 1 : System. out. p r i n t l n ( " one " ) ; break ; case 2 : System. out. p r i n t l n ( " two " ) ; break ; case 3 : System. out. p r i n t l n ( " three " ) ; break ; default : System. out. p r i n t l n ( " Above three !" ) ; break ; }}} The conditional statement switch consider the elementary expression n of type int and compare it successively with the ﬁrst case: case 0. This means that if (n==0)Block1 else \{... \}. The set of instructions in a case should end with the keyword break. Note that there is also the default case that contains the set of instructions to execute when none of the former cases were met. The formal syntax of the multiple choice switch case is thus: switch ( TypedExpression ) { case C1 : SetOfInstructions1 ; break ; case C2 : SetOfInstructions2 ; break ;... case Cn : SetOfInstructionsn ; break ; default : SetOfDefaultInstructions ; } } 40 2. Conditional Structures and Loops Multiple choice switch conditionals are often used by programmers for displaying messages2 : Program 2.3 Demonstration of the switch case statement i n t dd=3; // 0 for Monday , 6 for Sunday switch ( dd ) { case 0 : System. out. p r i n t l n ( " Monday " ) ; break ; case 1 : System. out. p r i n t l n ( " Tuesday " ) ; break ; case 2 : System. out. p r i n t l n ( " Wednesday " ) ; break ; case 3 : System. out. p r i n t l n ( " Thursday " ) ; break ; case 4 : System. out. p r i n t l n ( " Friday " ) ; break ; case 5 : System. out. p r i n t l n ( " Saturday " ) ; break ; case 6 : System. out. p r i n t l n ( " Sunday " ) ; break ; default : System. out. p r i n t l n ( " Out of scope !" ) ; } 2.3 Blocks and scopes of variables 2.3.1 Blocks of instructions A block of instructions is a set of instructions that is executed sequentially. Blocks of instructions are delimited by braces, as shown below: { // This is a block // (There are no control structures inside it) Instruction1; Instruction2;... } A block is semantically interpreted as an atomic instruction at a macroscopic level when parsing. 2 Or used for translating one type to another when used in functions 2.4 Looping structures 41 2.3.2 Nested blocks and variable scopes Blocks can be nested. This naturally occurs in the case of if-else structures that may internally contain other conditional structures. But this may also be possible without conditional structures for controlling the scope of variables. Indeed, variables deﬁned in a block are deﬁned for all its sub-blocks. Thus a variable cannot be redeﬁned in a sub-block. Moreover variables deﬁned in sub-blocks cannot be accessed by parent blocks as illustrated by the following example: c l a s s NestedBlock { public s t a t i c void main ( S t r i n g [ ] a r g ) { i n t i =3; i n t j =4; System. out. p r i n t l n ( "i="+i+" j="+j ) ; { // Cannot redefine a variable i here i n t i i =5; j ++; i −−; } System. out. p r i n t l n ( "i="+i+" j="+j ) ; // Cannot access variable ii here } } i=3 j=4 i=2 j=5 Finally note that single instructions in control structures such as if-else are interpreted as implicit blocks where braces are omitted for code readibility. 2.4 Looping structures Loop statements are fundamental structures for iterating a given sequence of instructions, repeating a block of instructions. Java provides three kinds of constructions for ease of programming, namely: while, for and do-while. Theoretically speaking, these three diﬀerent constructions can all be emulated with a while statement. We describe the semantic of each structure by illustrating it with concrete examples. 42 2. Conditional Structures and Loops 2.4.1 Loop statement: while The syntax of a while loop statement is as follows: while (boolean_expression) {block_instruction;} This means that while the boolean expression is evaluated to true, the sequence of instructions contained in the block instruction is executed. Consider calculating the greatest common divisor (gcd for short) of two integers a and b. That is, the largest common divisor c such that both a and b can be divided by c. For example, the GCD of a = 30 and b = 105 is 15 since a = 2×3× 5 and b = 5×3×7. Euclid came up with a simple algorithm published for solving this task. The algorithm was reported in his books Elements around3 300 BC. Computing the GCD is an essential number operation that requires quite a large amount of computation for large numbers. The GCD problem is related to many hot topics of cryptographic systems nowadays. Euclid’s algorithm is quite simple: If a = b then clearly the GCD of a and b is c = a = b. Otherwise, consider the largest integer, say a without loss of generality, and observe the important property that GCD(a, b) = GCD(a − b, b). Therefore, applying this equality reduces the total sum a + b, and at some point, after k iterations, we will necessarily have ak = bk. Let us prove a stronger result: GCD(a, b) = GCD(b, a mod b). Proof To see this, let us write a = qb + r where q is the quotient of the Euclidean division and r its reminder. Any common divisor c of a and b is also a common divisor of r: Indeed, suppose we have a = ca and b = cb , then r = a − qb = (a − qb )c. Since all these numbers are integers, this implies that r is divisible by c. It follows that the greatest common divisor g or a and b is also the greatest common divisor of b and r. Let us implement this routine using the while loop statement. The terminating state is when a = b. Therefore, while a = b (written in Java as a!=b), we retrieve that smaller number to the larger number using a if conditional structure. This gives the following source code: 3 It is alleged that the algorithm was likely already known in 500 BC. 2.4 Looping structures 43 Program 2.4 Euclid’s Greatest Common Divisor (GCD) c l a s s GCD { public s t a t i c void main ( S t r i n g [ ] a r g ) { int a ; int b ; while ( a !=b ) { i f ( a>b ) a=a−b ; e l s e b=b−a ; } System. out. p r i n t l n ( a ) ; // or b since a=b } } Running this program for a = 30 and b = 105 yields GCD(a, b) = 15. Euclid’s algorithm has a nice geometric interpretation: Consider an initial rectangle of width a and height b. Bisect this rectangle as follows: Choose the smallest side, and remove a square of that side from the current rectangle. Repeat this process until we get a square: The side length of that square is the GCD of the initial numbers. Figure 2.2 depicts this “squaring” process. Figure 2.2 A ge- ometric interpretation of Euclid’s algorithm. Here, illustrated for a = 65 and b = 25 (GCD(a, b) = 5) 2.4.2 Loop statement: do-while Java provides another slightly diﬀerent syntax for making iterations: the do loop statement. The diﬀerence with a while statement is that we execute at least once the sequence of instructions in a do statement, whereas this might not be the case of a while statement, depending on the evaluation of the boolean predicate. The syntax of a

A Concise Introduction to Programming Algorithms in Java PDF

Document Details

Tags

Related

Summary

Full Transcript