Transcript int[]

Guest Speaker - Cryptography
Wednesday (Apr. 22) – Prof. abhi shelat
Final Exam Review
Built-In Datatypes
CS101: Introduction to Computer Science • Slides adapted from Sedgewick and Wayne • Copyright © 2007 •
Variables


A variable has three parts:
1.
Name (e.g., “x”)
2.
Type (e.g., int, double, String)
3.
Value
How does a variable get a value?
– Can be initialized in the program
 E.g., int x = 10
– Can be computed when the program is running
 E.g., x = y + z;
Built-in Data Types
Data type. A set of values and operations defined on those values.
type
set of values
literal values
operations
char
characters
'A'
'@'
compare
String
sequences of
characters
"Hello World"
"CS is fun"
concatenate
int
integers
17
12345
add, subtract,
multiply, divide
double
floating point
numbers
3.1415
6.022e23
add, subtract,
multiply, divide
boolean
truth values
true
false
and, or, not
5
Math Library
6
Type Conversion
Type conversion. Convert from one type of data to another.
Automatic: no loss of precision; or with strings.
Explicit: cast; or method.


7
Conditionals and Loops
Control Flow Summary
Control flow.
Sequence of statements that are actually executed in a program.
Conditionals and loops: enables us to choreograph the control flow.


Control Flow
Description
Examples
Straight-line
programs
All statements are
executed in the order given.
Conditionals
Certain statements are
executed depending on the
values of certain variables.
if
if-else
Loops
Certain statements are
executed repeatedly until
certain conditions are met.
while
for
do-while
9
Nesting Conditionals and Loops

Nest conditionals within conditionals.

Nest loops within loops.

Nest conditionals within loops within
loops.
10
Monte Carlo Simulation

General 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;
}
11
Single-Dimensional Arrays
Arrays in Java
Java 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.



int N = 10;
double[] a;
a = new double[N];
for (int i = 0; i < N; i++)
a[i] = 0.0;
//
//
//
//
declare the array
create the array
initialize the array
all to 0.0
Compact alternative.
Declare, create, and initialize in one statement.
Default initialization: all numbers automatically set to zero.


int N = 10;
double[] a = new double[N];
// declare, create, init
13
Array Layout in Memory
Memory is split into equal sized units known as “addresses”. (Address Space)

Addresses

0
1
...
2
N-2 N-1
Arrays occupy consecutive addresses in this linear space:
int[] a = {5, 6, 10};
0
1
2
3
4
5
N-2 N-1
a[0] a[1] a[2]
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 TYPE
14
Array Length




The array length can be obtained
using the .length operator
for(i=0; i< myArray.length; i++)
The array length cannot be changed
after memory allocation
Can use arraylists to get around this
limitation
15
Auto-increment
Auto-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; x = y; y = y+1;
y = 0; z = ++y; Y=0; y = y+1; z = y;
16
Multidimensional Arrays
Two Dimensional Arrays in Java
Array 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 Array
18
Memory Layout 2-D Arrays
array[0]
array[1]
array[0][0]
Row
array[1][2]
array[2]
array[3]
19
Ragged Arrays

Row lengths can be non-uniform

Can use .length
Number of rows
int[][] 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("");
}
Number of columns for a
given row
20
Functions/Static Methods
Components of a Function
Flow Control – Call by Value
Call by reference – For reference types (arrays, objects)
23
Things to Remember About Functions





Functions can be overloaded
Different argument types
Different number of arguments
Different return value is NOT overloading
Scoping Rules for functions and conditional
and loop code-blocks
Recursion
Recursion
What is recursion? When one function calls itself directly or
indirectly.
Gcd. Find largest integer d that evenly divides into p and q.
 p
if q  0
gcd( p, q)  
gcd(q, p % q) otherwise
public static int gcd(int p, int q) {
if (q == 0) return p;
else return gcd(q, p % q);
}
base case
reduction step,
converges to base case
base case
reduction step
26
How-To’s on Writing Recursive Functions
Base 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 Hanoi
Are their return values chosen, combined?
27
Objects
Objects
Object. An entity that can take on a data type value.
Data Type
Set of Values
Operations
Color
24 bits
get red component, brighten
Picture
2D array of colors
get/set color of pixel (i, j)
String
sequence of characters
length, substring, compare
An object’s “value” can be returned to a client or be changed by one of
the data type’s operations.
29
Things to Remember About Objects




Class API
Constructor
Instance Methods
Difference between constructors and
methods
Objects are Reference Types






Assigning one object/array to another
object/array results in an alias
Cannot use == operator to check the equality of
objects
Use instance method equals(). Can define
this method for any class.
Mutable vs. Immutable Objects
Immutable – Can’t change the value of an
object after its created
Aliases to immutable objects are less
problematic
31
Principles of Object Oriented Programming
Encapsulation: Combine data and the functions that operate on that
data into a single unit (object)
Data Hiding: Clients should not be able to manipulate data in objects
directly


Declare instance variables to be “private”
– Use getter methods to read data within objects
Any object should be able to invoke the instance methods
– Declare instance methods to be “public”
Summary of Classes
(“Charge” Class Discussed in the Textbook)
33
Data Structures
Data Structures
Lists
A collection of a variable number of items

Typical Operations on Lists
Add an item to the list
Remove an item from the list
Read an item from the list
Check whether the list is empty
Get the current size of the list





All of these are provided via the Java ArrayList class
35
Generics
Generics. Parameterize the datatype used in the data
structure.
You need to import the library: import java.util.ArrayList;
ArrayList<Apple> list= new ArrayList<Apple>();
Apple a = new Apple();
Orange b = new Orange();
list.add(a);
list.add(b);
// compile-time error
a = list.get(0); // returns an Apple object
sample client
36
Autoboxing
Generic ArrayList implementation. Only permits reference types.
Wrapper type.
Each primitive type has a wrapper reference type.
Ex: Integer is wrapper type for int.


Autoboxing. Automatic cast from primitive type to wrapper type.
Autounboxing. Automatic cast from wrapper type to primitive type.
ArrayList<Integer> list= new ArrayList<Integer>();
list.add(17);
// autobox
(int -> Integer)
int a = list.get(i);
// autounbox (Integer -> int)
37
Lists Can Be Organized in Different Ways
Linked List
Linear sequence of elements

Queue
Remove the item least recently added.
First-In, First-Out (FIFO)


Stack
Remove the item most recently added.
Last-In, First-Out (LIFO)


Array Implementation vs. ArrayList Implementation
38
Guest Speaker - Cryptography
Wednesday (Apr. 22) – Prof. abhi shelat