(chapter 1) A Concise and Practical Introduction to Programming Algorithms in Java

1A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Frank NIELSEN nielsen@lix.polytechnique.fr A Concise and Practical Introduction to Programming Algorithms in Java Chapter 1: Expressions, Variables, and Assignments

2A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Contents ● Learn to program with/in Java ● Computing as a science (some basic principles) ● Popular (computer) science HCI BMI MANET

3A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Jobs &Jobs & Computer ScienceComputer Science ● Industry ● CS Industry ● Others (information systems) ● Administration ● Research & Development Not feeling fluent with CS today, is like not being able to drive a car !

A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Digital worldDigital world Benefits of the analog-to-digital paradigm shift? • DissociateDissociate contentscontents fromfrom supportsupport : digitize/“binarize” Contents become mere binary 0/1 strings

A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Digital worldDigital world • Generic algorithms: copying, compressing, transmitting, archiving, etc. Raise the question: What is the (digital) information? •Text •Music •Image •Video •Data

A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Digital world: Why 0/1 bits?Digital world: Why 0/1 bits? Binary numeral systems: Information, first needs of counting... 8 Unary numeral systems: Logarithmic number of bits for countingLinear number of bits for counting vs 4 bits for counting 0 to 15

A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Nature of computing?Nature of computing? •Generic algorithms: copying, transmitting... ...genetics... DNA (double-helix structure of DNA) 1953, James Watson and Francis Crick (Nobel prize) Genetics

A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Nature of computing?Nature of computing? First envisioned by Erwin Schroedinger (What is life?, 1944) Transmit crystals? Nobel, Physics 1933 LIFE???

A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Digital world/computingDigital world/computing Ubiquitous computing= computing everywhere New features Digital = Binary + Calculations Example: Computational photography

11A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Computer science is not programming PCs Computers = computing machineries Difference engine of Charles Babbage (conceived in 1822 on paper, built much later on) Computing is a principle of reality (and science) Watson and Crick 1951 (DNA double helix heredity) Computing is 21st Century's Science of integration

12A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen INFORMATIQUE=INFORmation + autoMATIQUE Information= Data sets, input (discrete binary sequences of 0/1) Automatic= General recipe that works on any input = ALGORITHM Al-Khwarizmi (790 - 840) Al-Khwarizmi: Scholar of scientifically flourishing Bagdad: ● Algorithmi (latinization) -> Algorithm ● Al jabr -> Algebra Provide readers a generic pipelinepipeline solution to solve a quadratic equation: http://www.akiti.ca/Quad2Deg.html

13A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen 2121stst century computer sciencecentury computer science ● Computers (and computing) are omnipresent -> Ubiquitous computing (Mark Weiser) Computers are abundant and versatile: 1952-1999 Xerox parc chief scientist ● Computing impacted all Sciences: Computational sciences Eg., Biology -> Systems biology (simulation-prediction-experience in wet lab) ● The Science of computing is Computer Science (CS): Deep theoretical questions and important technologies (eg., medical imaging such as DT-MRI, economy) DW-MRI (Many more devices than PCs) Science of Integration (complex systems)

14A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Flavor of my research in computer science Visual computing: ● Computational geometry, ● Computer vision, ● Computer graphics, ● Machine learning For example, tackling computational photography Reinventing the photography: taking, sharing and experiencing photos...Reinventing the photography: taking, sharing and experiencing photos... Smile shutterDigital camera Analog camera Everything has yetEverything has yet to beto be invented!!!invented!!! Beyond 2D pixels Beyond single flash etc...

15A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Computer science is (also) for creative minds Not only the hardcore mathematical problems to solve, but also innovation by unleashing the power of digital calculus for soft problems: Human Computer Interactions (HCI), design Example: computational photography project (2004) Non-photorealistic camera (NPR) NPR Camera

16A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Algorithms and their performances (resource/complexities) There is usually not a single recipe for solving the task: Eg., compute 5422x2319 (human decimal, machine binary, indian base 60, many tricks, etc.) How to evaluate and compare different algorithms? Clean framework for assessing the use of ressources: ● time, ● memory, ● #communications, ● etc. Judge the generic algorithms not for a given instance. Therefore, analyze: ● Worst-case complexity ● Average-time complexity ● Modern challenges (inplace, i/o bottlenecks & streaming, etc.) ● Etc. Donald Knuth

17A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Programming algorithms in Java ● Conceived by Bill Joy (SUN co-founder) and James Gosling ● Started in 1990, for the ''next wave in computing'' ● On-time for the Internet and WEB (applets are Java applications, Javascript, etc.) Cross-platform= runs on various operating systems (Windows, UNIX, Leopard, etc.) ● Typed language (a=b, with a and b from different types will generate a compiler error) ● Object oriented (OO, ease the conception and modularity of applications) ● Rich set of Applications Programming Interface (API) ● Free Software Development Kit on many platforms (SDK) ● Verbose for catching bugs and debugging applications.

18A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Why programming languages? Machines are “stupid”: they obey you 100% -> Need to fully and precisely specify your intentions (no room for ambiguity, the bug is yours!!!) ... Machines only “understand” 0/1 binary sequences (eg., instruction codes of microprocessors) Machine = Processing + Peripherals (I/O) ... controlled by an Operating System (OS) But Human masters “natural language” ... and we need to unleash ease of programming ASSEMBLER, FORTRAN, ALGOL, BASIC, .......JAVA Key principle of CS: Bootstrapping! use existing languages to create more powerful languages: Python, Ruby, etc.

19A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen My first (java) program Programmers and CScientists cherrish... ... their “Hello World” programs class FirstProgram{ public static void main (String[ ] args){ System.out.println("Hello INF311 !"); } } First programs often looks magic! Special function main: entry of the program

20A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen My first (java) program ● Type this program into a text editor (nedit, notepad) Save this “text” as FirstProgram.java ● Compile the program FirstProgram.java prompt% javac FirstProgram.java ● Execute the compiled program prompt% java FirstProgram prompt% Hello INF311 !

21A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen My first (java) program FirstProgram.java FirstProgram.class 1) EDIT and SAVE 3) EXECUTE 2) COMPILE (Java Byte code in .class) java FirstProgram (Java Virtual machine: JVM) ... low-level language instructions for processors High-level language concepts/abstraction

22A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen My first algorithm in Java: A solver for quadratic equations In Java http://www.java.com/fr/ Input: a, b, c of the quadratic equations Solution: the at most two real roots Install the SDK (you do not have to do this in room machines)

23A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Programming: Solver for quadratic equations class QuadraticEquationSolver { public static void main(String[] arg) { double a,b,c; a=Math.sqrt(3.0); b=2.0; c=-3.0; double delta=b*b-4.0*a*c; double root1, root2; root1= (-b-Math.sqrt(delta))/(2.0*a); root2= (-b+Math.sqrt(delta))/(2.0*a); System.out.println(root1); System.out.println(root2); System.out.println("Let us check the roots:"); System.out.println(a*root1*root1+b*root1+c); System.out.println(a*root2*root2+b*root2+c); } } QuadraticEquationSolver.java

24A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen class QuadraticEquationSolver { public static void main(String[] arg) { double a,b,c; a=Math.sqrt(3.0); b=2.0; c=-3.0; double delta=b*b-4.0*a*c; double root1, root2; root1= (-b-Math.sqrt(delta))/(2.0*a); root2= (-b+Math.sqrt(delta))/(2.0*a); System.out.println(root1); System.out.println(root2); System.out.println("Let us check the roots:"); System.out.println(a*root1*root1+b*root1+c); System.out.println(a*root2*root2+b*root2+c); } } Programming simple formula Variable (declare) Assignments Declare+Assign

25A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen class QuadraticEquationSolver { public static void main(String[] arg) { double a,b,c; a=Math.sqrt(3.0); b=2.0; c=-3.0; double delta=b*b-4.0*a*c; double root1, root2; root1= (-b-Math.sqrt(delta))/(2.0*a); root2= (-b+Math.sqrt(delta))/(2.0*a); System.out.println(root1); System.out.println(root2); System.out.println("Let us check the roots:"); System.out.println(a*root1*root1+b*root1+c); System.out.println(a*root2*root2+b*root2+c); } } Programming simple formula Arithmetic expressions Display

26A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Programming: Solver for quadratic equations Use any text editor to program (nedit in UNIX, notepad under windows) Magic code for printing onto the console Indentation is up to you -> helps read programs

27A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen CompilingCompiling andand executingexecuting a Java programa Java program prompt>javac filename.java prompt>java filename If no compile error happens, it produces a file filename.class Then excute the compiled code. To store output to a file: prompt>java filename > result.txt Redirect console to filename result.txt

28A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Fundamentals of Java: Variables ● A variable is uniquely named (not a reserved keyword) ● A variable stores a value in a memory slot ● The value of a variable is accessed by its name ● The value of a variable can be modified A=32 B=16 C=A Left hand side (reference) and right hand side (value) of = means different things Memory bank A B C 32 16 32 valuereference

29A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Fundamentals of Java: Expressions ● Formed by variables, operators (+,-,/, x, etc.) and constants (1, Math.PI, etc.) ● Expressions are evaluated and return a result (eventually stored in a variable) ● Operators follow priority rules: 5x3+2 ? ...avoid overuse of parenthesis 5x3+2 = (5x3)+2 Few examples of expressions in Java: // Expressions 5+3*x/y “Hello “+”INF311!” // Assignment (expressions) terminate with a ; x=cx + r*Math.cos(theta); y=cy+ r*Math.sin(theta);

30A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Fundamentals of Java: Affectation (sign =) Var = Expression ; ● Var is the name of a variable ● Expression is a well-formed expression Assignment left hand side=right hand side is decomposed as : ● The Expression is evaluated yielding value v ● The reference (memory slot) of Var is determined ● Value v is stored in the memory slot of Var lhs = rhs Reference Value lhs rhs Memory bank Atomic instruction

31A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Basic typesBasic types Type = Domain of values of variables All variables must be typed in JavaAll variables must be typed in Java Basic types (=basic data structures): Integers: byte 8 bits short 16 bits int 32 bits [-2**31,2**31-1] long 64 bits [-2**63,2**63-1] Reals: float (single precision, 32 bits) double (double precision, 64 bits) char 16 bits (Unicode, world languages) boolean true or false

32A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Why do we type variables?Why do we type variables? To ensure homogeneous operations 2 +3 =5 3 +4 =7 5 +2 =??? 3 +4 =7

33A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Basic types:Basic types: castingcasting expressionsexpressions Euclidean (integer) division versus usual (real) division int p=2; int q=3; int quotient=p/q; int reminder=p%q; // modulo double div=p/q; double realdiv=(double)p/(double)q; System.out.print(quotient); System.out.print(“ “); System.out.println(reminder); System.out.println(div); System.out.println(realdiv); Cast (coercion)

34A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Typing: Safeguards for basic bugs in programs Allows one to perform static analysis of programs CastingCasting expressionsexpressions Implicit casting for assignment x=Expression; Should be of the same type. Casting: Var=(TypeOfVar)Expression; double x=2; // implicit casting double x=(double)2;// explicit double x=2.0; // same type

35A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Implicit castingImplicit casting Implicit casting rules char c='X'; int code=c; System.out.println(code); Answers 88 (ASCII code of X)

36A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Fundamentals of Java: Types ● Everything is typed (variables, constants, etc.) ● Require to declare types of variables ● The result of an expression has a type ● Variable and expression should have the same type for assignment (d=5.0f) (different types) ERROR ERROR Compiler warns you of implicit casting (possible loss of precision!)

37A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Recap of simple (formula) programs Declare variables of basic types: Type var; double x; int n,m; //separate with a comma variables char c; Assignment: var=Expression; x=2.71; n=2008; c='X'; Arithmetic expression: Expression1 Operator Expression2 m=300%23; delta=b*b-4*a*c; Declare+Assign at once (shortcut): int year2secs=365*24*60*60;

38A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Incrementing/Decrementing x=x+1; x=x+step; // Instructions equivalent to x+=1; x+=step; // Decrement now x-=3; i=2; i++; // equivalent to i=i+1; ++i; // similar, equivalent to i=i+1; Incrementing is useful for loops

39A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Pre- and post-incremention i=5; j=i++; // post-incrementation ii=5; jj=++ii; // pre-incrementation compare... Var++ returns the value of var and then increment it ++Var first increment var and then return its value Thus j=5 but jj=6

40A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Chopping Programs (Language) Syntax of programs Word Sentence Paragraph Chapter Book Library Reserved keywords Variables Instruction I; Block (of instructions) {I;} Function Program Library (API)

41A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Commenting programs ● Adopt conventions Eg., class ClassName .... stored in file ClassName.java ● Name variables explicitly (so that you can remember them easily) ● Comment programs (single line // or multiple lines /* */) // Written for INF311 class CommentProgram { /* This is a simple Java program that illustrates how to comment source code */ // Entry of the program public static void main(String[ ] args) {// it does nothing } }

42A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen A basic skeleton program in Java Name of your program: Prog.java Magic formula 2 Magic formula 1 > javac Prog.java (builds a Prog.class file) > java Prog (execute the program) 2008 // Basic skeleton program for INF311 class Prog { public static void main(String[] arg) { int x=2008; System.out.println(x); } }

43A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Integrated Development Environment (IDE) An IDE allows one to create, edit, compile and debug seamlessly applications at the tip of mouse clicks. (Eg., Jcreator, www.jcreator.com/ ) Eclipse

45A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Euclid's Greatest Common Divisor (GCD) Input: Two numbers a,b Output: Find the greatest common divisors c of a and b Euclid's original algorithm History, proof, etc http://en.wikipedia.org/wiki/Euclidean_algorithm For example, GCD of (30,105): Mathematical proof: GCD(30,105) =GCD(30,75) =GCD(30,45) =GCD(30,15) =GCD(15,15) =GCD(15,0) => GCD(30,105)=15 30=2*5*3 105=7*5*3

46A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Euclid's Greatest Common Divisor (GCD) Input: Two numbers a,b Output: Find the greatest common divisors c of a and b Euclid's original algorithm History, proof, etc http://en.wikipedia.org/wiki/Euclidean_algorithm class GCD { public static void main(String[] arg) { // Parse arguments into integer parameters int a= Integer.parseInt(arg[0]); int b= Integer.parseInt(arg[1]); while (a!=b) { if (a>b) a=a-b; else b=b-a; } // Display to console System.out.println(a); } }

47A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Euclid's greatest common divisor (GCD) > javac gcd.java (compile in a gcd.class) > java gcd 234652 3456222 > gcd.txt (execute and store result in gcd.txt) arg[0] arg[1]

48A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Geometric interpretation of Euclid's GCD Visualize a (65) and b (25) on two axes a=b=5, Stopping criterion + GCD

49A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Programming is helpful for simulation Simulation by Monte Carlo methods: Eg., approaching PI=3.41592... using simulation Draw a random point uniformly in a square: Probability of falling inside a centered unit disk? Monte-Carlo sampling extremely used in graphics and financial economy !!! How do we get (pseudo-)random numbers in Java? Call function random() of class Math Math.random();

50A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Monte-Carlo estimation of PI in Java Monte-Carlo simulation techniques proved useful in computational sciences import java.util.*; class MonteCarloPI { public static void main(String [] args) { int iter = 10000000; // # iterations int hits = 0; for (int i = 0; i < iter; i++) { double rX = 2*Math.random() - 1.0; double rY = 2*Math.random() - 1.0; double dist = rX*rX + rY*rY; if (dist <= 1.0) // falls inside the disk hits++; } double ratio = (double)hits/iter; // Ratio of areas double area = ratio * 4.0; System.out.println("Estimation of PI: " + area+ " versus machine PI "+Math.PI); } }

51A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Human versus Machine #transistors x2 every 18 months http://www.kurzweilai.net/articles/art0134.html?printable=1 The Law of Accelerating Returns of Ray Kurzweil ● Machines are dull but extremely fast ● Designing software is difficult (as difficult as building an Airbus) ● Artifical intelligence (AI) is a key topic in Computer Science Bug: ● Abnormality of the system ● Not by the faulty machine but by the programmer! ● Small bugs, big consequences!!! (Ariane 501, Intel's Pentium division bug, etc.) ● Cost 100 billion$/ years (Dept. of Commerce)

52A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Small bugs, big consequences: Numerical errors If (a<b) then Block 1 else Block 2 Predicate Expressions lhs=expression(rhs) Branching instruction Finite precision, roundings of arithmetic operations may cause devastating effects Wrong evaluation of a predicate yields a different path of instructions: Bug! Small numerical errors may not be so capital here.

53A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen CAPTCHA versus SPAM (Human vs Machine) Completely Automated Public Turing test to tell Computers and Humans Apart Image-recognition CAPTCHAs: Difficult task (OCR, segmentation, etc.) To fight undesirable bulk spam, we need to differentiate whether it is the action of a human or an automated jam program. (visual) CAPTCHA

54A Concise and Practical Introduction to Programming Algorithms in Java © 2009 Frank Nielsen Turing test... Alan Turing, 1912-1954 (41 years old) Pioneer of modern computer science Proposed the “universal” Turing machine: A ribbon, a head, a state and an action table (automaton) Turing test: proposal for a test of machine's capability to demonstrate intelligence. Originally, for natural language conversation (and processing). Initially, by text-only channel such a teletype machine DNA, ribosome Association for computing machinery (ACM)'s Turing Award (250000$) [Nobel prize in computer science]

(chapter 1) A Concise and Practical Introduction to Programming Algorithms in Java

More Related Content

Viewers also liked

Similar to (chapter 1) A Concise and Practical Introduction to Programming Algorithms in Java

Recently uploaded

(chapter 1) A Concise and Practical Introduction to Programming Algorithms in Java