Chapter 1 - Introduction

9/30/2018
Introduction
Data Structures & Algorithm in Java
Objectives
 Provide background in data structures (arrangements of data
in memory) and algorithms (methods for manipulating this
data)
 Why is this important? The answer is there is far more to
programming than finding a solution that will work:
 Execution time
 Memory consumption
 So by the end of the course, you should be more equipped to
not just develop an accurate solution to a problem, but the
best solution possible.
1
9/30/2018
Definition of a Data Structure

 A data structure is an arrangement of data in a computer’s
memory (or disk).
 Questions to ponder:
 What are some examples of data structures you already know
about from your Java course?
 How can the arrangement of data in memory affect

performance?
Definition of an Algorithm
 An algorithm provides a set of instructions for manipulating
data in structures.
 Questions to ponder:
 What’s an example of an algorithm?
 How can the design of an algorithm affect performance? How

can it affect memory?
2
9/30/2018
Data Structure or Algorithm?

 Linked List
 Sort
 Search
 Stack
 Vector
Real World Data Storage

 Real-world data: data that describes physical entities external
to the computer. Can we think of some examples?
 What’s an example of non-computer data storage?

 Addresses and phone #s:
 Book names, titles, ISBNs:
 What method do these use?
3
9/30/2018
Real World Modeling

 How about a ‘queue’ of data, where the first element in is the
first element out (termed ‘FIFO’):
 Example applications:
 Grocery store lines
 Traffic (Queues are actually used when determining timing of
traffic lights!! How? Let’s think about it)
Data Structure Trade-offs

 A structure we have dealt with before: arrays
 Requirement that is enforced:
 Arrays store data sequentially in memory.
 Let’s name the advantages (i.e., when is an array efficient?)
 Let’s name the disadvantages
4
9/30/2018
Idea of Objects
 A programming unit which has associated:
 Variables (data), and
 Methods (functions to manipulate this data).
 How does this address the two problems on the previous
slide?
 Real World Modeling
 Organization
Inheritance
 Creation of one class, called the base class
 Creation of another class, called the derived class
 Has all features of the base, plus some additional features.
 Example:
 A base class Animal may have associated methods eat() and
run() and variable name, and a derived class Dog can inherit
from Animal, gaining these methods plus a new method
bark().
 If name is private, does Dog have the attribute?
 How do we enforce Dog to also have attribute name?
10
5
9/30/2018
Polymorphism
 Idea: Treat objects of different classes in the same way.
 What’s the requirement?
 Let’s return to an example with Animal and Dog, and

throw in another derived class Cat.
11
Final Review of some Java Concepts

 Difference between a value and a reference:
int intVar;
BankAccount bc1;
 Which is a value and which is a reference?
 How did the interpreter know to allocate them differently?
 What does the address stored in bc1 contain right now?

 What must I do before I use bc1?
12
6
9/30/2018
Java Assignments
 What must be noted about the following code snippet:
int intVar1 = 45;

int intVar2 = 90;
BankAccount bc1(72.45);
BankAccount bc2 = bc1;
intVar1 = intVar2;
intVar1 = 33; // Does this modify intVar2?
bc2.withdraw(30.00); // Does this modify object bc1?
13
Java Garbage Collection

 When is the memory allocated to an object reclaimed in Java?
 Code like this would leak memory in C++, but does not in Java
because of the garbage collector:
while (true) {
Integer tmp = new Integer();
…
}
14
7
9/30/2018
Passing by Value vs. Reference

 Same idea:
void method1() {
BankAccount ba1 = new BankAccount(350.00);
float num = 4;
}
void method2(BankAccount acct) { … }
void method3(float f) { … }
 If I change f in method3, does that affect num?

 If I change acct in method2, does that affect object ba1?
15
== vs. equals()
carPart cp1 = new carPart(“fender”);
carPart cp2 = cp1;
// What’s the difference between this:
if (cp1 == cp2)
System.out.println(“Same”);
// And this:
if (cp1. equals(cp2)
System.out.println(“Same”);
 Does “Same” print twice, once, or not at all?
16
8
9/30/2018
Primitive Sizes and Value Ranges
17 Source: roseindia.net
Screen Output
 System.out is an output stream which corresponds to
standard output, which is the screen:
int var = 33;

// What’s do these three statements print?
System.out.print(var);
System.out.println(var);
System.out.println(``The answer is `` + var);
18
9
9/30/2018
Keyboard Input
 Package: java.io
 Read a string: InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
 Read a character: char c = s.charAt(0);
 Read an integer: int i = Integer.parseInt(s);
19  Read a float: double d = Double.valueOf(s).doubleValue();
10

Chapter 1 - Introduction

Uploaded by

Copyright:

Available Formats

Chapter 1 - Introduction

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Chapter 1 - Introduction

Uploaded by

Copyright:

Available Formats

9/30/2018

Data Structures & Algorithm in Java

Definition of a Data Structure

 How can the arrangement of data in memory affect

 How can the design of an algorithm affect performance? How

Data Structure or Algorithm?

Real World Data Storage

 What’s an example of non-computer data storage?

 What method do these use?

Real World Modeling

Data Structure Trade-offs

 Let’s name the disadvantages

 Let’s return to an example with Animal and Dog, and

Final Review of some Java Concepts

 Which is a value and which is a reference?

 How did the interpreter know to allocate them differently?

 What does the address stored in bc1 contain right now?

int intVar1 = 45;

Java Garbage Collection

Passing by Value vs. Reference

 If I change f in method3, does that affect num?

Primitive Sizes and Value Ranges

int var = 33;

 Read a character: char c = s.charAt(0);

 Read an integer: int i = Integer.parseInt(s);

19  Read a float: double d = Double.valueOf(s).doubleValue();

You might also like