Guest Speaker - CryptographyFinal Exam ReviewBuilt-In DatatypesVariablesBuilt-in Data TypesMath LibraryType ConversionConditionals and LoopsControl Flow SummaryNesting Conditionals and LoopsMonte Carlo SimulationSingle-Dimensional ArraysArrays in JavaArray Layout in MemoryArray LengthAuto-incrementMultidimensional ArraysTwo Dimensional Arrays in JavaMemory Layout 2-D ArraysRagged ArraysFunctions/Static MethodsComponents of a FunctionFlow Control – Call by ValueThings to Remember About FunctionsRecursionSlide 26How-To’s on Writing Recursive FunctionsObjectsSlide 29Things to Remember About ObjectsObjects are Reference TypesPrinciples of Object Oriented ProgrammingSummary of Classes (“Charge” Class Discussed in the Textbook)Data StructuresSlide 35GenericsAutoboxingLists Can Be Organized in Different WaysSlide 39Guest Speaker - CryptographyWednesday (Apr. 22) – Prof. abhi shelatFinal Exam ReviewCS101: Introduction to Computer Science • Slides adapted from Sedgewick and Wayne • Copyright © 2007 • http://www.cs.Princeton.EDU/IntroCSBuilt-In DatatypesVariablesA variable has three parts:1. Name (e.g., “x”)2. Type (e.g., int, double, String)3. ValueHow does a variable get a value?–Can be initialized in the programE.g., int x = 10–Can be computed when the program is runningE.g., x = y + z;5Built-in Data TypesData type. A set of values and operations defined on those values.add, subtract, multiply, divide3.14156.022e23floating point numbersdoubleadd, subtract, multiply, divide1712345integersintand, or, nottruefalsetruth valuesbooleansequences of characterscharactersset of values operationsliteral valuestypecompare'A''@'charStringconcatenate"Hello World""CS is fun"6Math Library7Type ConversionType conversion. Convert from one type of data to another.Automatic: no loss of precision; or with strings.Explicit: cast; or method.Conditionals and Loops9Control Flow SummaryControl flow.Sequence of statements that are actually executed in a program.Conditionals and loops: enables us to choreograph the control flow.Straight-lineprogramsAll statements areexecuted in the order given.ConditionalsCertain statements areexecuted depending on thevalues of certain variables.ifif-elseLoopsCertain statements areexecuted repeatedly untilcertain conditions are met.whilefordo-whileControl Flow Description ExamplesNesting Conditionals and LoopsNest conditionals within conditionals.Nest loops within loops.Nest conditionals within loops within loops.10Monte Carlo SimulationGeneral Code Structure:class MonteCarloSimulation {for(i=0; i<num_trials; i++) {Perform one independent trial {Generate random input;Deterministic computation on that input;}}Compute results aggregated over all trials;}11Single-Dimensional Arrays13Arrays in JavaJava has special language support for arrays.To make an array: declare, create, and initialize it.To access element i of array named a, use a[i]. Array indices start at 0.Compact alternative. Declare, create, and initialize in one statement.Default initialization: all numbers automatically set to zero.int N = 10; double[] a; // declare the arraya = new double[N]; // create the arrayfor (int i = 0; i < N; i++) // initialize the array a[i] = 0.0; // all to 0.0int N = 10;double[] a = new double[N]; // declare, create, initArray Layout in MemoryMemory is split into equal sized units known as “addresses”. (Address Space)Arrays occupy consecutive addresses in this linear space: int[] a = {5, 6, 10};Key Point: Name of the array indirectly references its starting address.int[] b = new int[3]; b=a;//b is an alias to a. REFERENCE TYPE140 1 2 . . . N-2 N-1 0 1 2 3 4 5 N-2 N-1 a[0] a[1] a[2] 5 6 10 AddressesArray LengthThe array length can be obtained using the .length operatorfor(i=0; i< myArray.length; i++)The array length cannot be changed after memory allocationCan use arraylists to get around this limitation15Auto-incrementAuto-increment and auto-decrement operators used with arrays.++i means “add one to i’s value and use the updated value”i++ means “use i’s value now and then add one to the old value”Can use on line by itself as a single statement–In which case they do exactly the same thing!Differences between the auto-increment operators are important when used in expressions: y = 0; x = y++; y = 0; z = ++y; 16Y=0; x = y; y = y+1;Y=0; y = y+1; z = y;Multidimensional Arrays18Two Dimensional Arrays in JavaArray access. Use a[i][j] to access element in row i and column j. Zero-based indexing. Row and column indices start at 0.double[][] a = new double[10][3];for (int i = 0; i < 10; i++) { for (int j = 0; j < 3; j++) { a[i][j] = 0.0; }}Declaring and Initializing a 10-by-3 ArrayMemory Layout 2-D Arrays19Rowarray[0]array[1]array[2]array[3]array[0][0]array[1][2]Ragged ArraysRow lengths can be non-uniformCan use .lengthint[][] a = ...;for (int rows=0; rows < a.length; rows++) {for (int cols=0; cols < a[rows].length; cols++) System.out.print(" " + a[rows][cols]);System.out.println("");}20Number of rowsNumber of columns for a given rowFunctions/Static MethodsComponents of a Function23Flow Control – Call by ValueCall by reference – For reference types (arrays, objects)Things to Remember About FunctionsFunctions can be overloadedDifferent argument typesDifferent number of argumentsDifferent return value is NOT overloadingScoping Rules for functions and conditional and loop code-blocksRecursion26RecursionWhat is recursion? When one function calls itself directly or indirectly.Gcd. Find largest integer d that evenly divides into p and q.base casereduction steppublic static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q);}base casereduction step,converges to base case27How-To’s on Writing Recursive FunctionsBase Case: You must check if we’ve reached the base case before doing another level of recursion! Make Progress Towards Base Case:Your recursive calls must be on a smaller or simpler input. Eventually this must reach the base case (and not miss it).Multiple recursive calls:Sometimes more than one recursive call.–H-Tree, Towers of HanoiAre their return values chosen, combined?Objects29ObjectsObject. An entity that can take
View Full Document
Unlocking...