Homework 6 and Interfaces in Section 5
undefined
SLIDES ADAPTED FROM ALEX MARIAKAKIS,
WITH MATERIAL FROM KRYSTA YOUSOUFIAN, MIKE ERNST, KELLEN DONOHUE
Section 5:
HW6 and Interfaces
How is Homework
6
going?
Agenda
•
Reminders
•
HW 6 due next Wednesday night (5/9)
•
Breadth-first search (BFS)
•
Interfaces
•
Parsing Marvel Data
Reminders:
Expensive CheckReps
are
BAD
(at least when assignments are turned in, but can be
useful for finding hard-to-discover problems – so need to
be able to control expensive checks)
Debug flags
are
GOOD
(or enums to indicate depth of debug)
Don’t forget your
CheckReps!
Graphs
A
B
C
D
E
Can I reach B
from A?
Breadth-First Search (BFS)
◦
Often used for discovering connectivity
◦
Calculates the shortest path
if and only if
all edges have same
positive or no weight
◦
Depth-first search (DFS) is commonly mentioned with BFS
◦
BFS looks “wide”, DFS looks “deep”
◦
DFS c
an also be used for discovery, but not the shortest path
Breadth-First Search (BFS)
A
B
D
C
E
G
F
S
t
a
r
t
i
n
g
a
t
A
,
w
h
i
c
h
n
o
d
e
s
w
i
l
l
b
e
v
i
s
i
t
e
d
f
i
r
s
t
i
n
a
B
F
S
?
Breadth-First Search (BFS)
A
B
D
C
E
G
F
S
t
a
r
t
i
n
g
a
t
A
,
w
h
i
c
h
n
o
d
e
s
w
i
l
l
b
e
v
i
s
i
t
e
d
f
i
r
s
t
i
n
a
B
F
S
?
B
,
C
,
D
Breadth-First Search (BFS)
A
B
D
C
E
G
F
S
t
a
r
t
i
n
g
a
t
A
,
w
h
i
c
h
n
o
d
e
s
w
i
l
l
b
e
v
i
s
i
t
e
d
s
e
c
o
n
d
i
n
a
B
F
S
?
Breadth-First Search (BFS)
S
t
a
r
t
i
n
g
a
t
A
,
w
h
i
c
h
n
o
d
e
s
w
i
l
l
b
e
v
i
s
i
t
e
d
s
e
c
o
n
d
i
n
a
B
F
S
?
E
,
F
,
G
BFS Pseudocode
put start node in a queue
while (queue is not empty)
:
pop node N off queue
mark node N as visited
if (N is goal):
return true
else:
for each node O that is child of N:
if O is not marked visit
push O onto queue
return false
Breadth-First Search
START:
Starting at A
Q: <A>
Goal: Fully explore
Pop: A, Q: <>
Q: <B, C>
Pop: B, Q: <C>
Q: <C>
Pop: C, Q: <C>
Q: <>
DONE
A
B
C
Breadth-First Search with Cycle
START:
Starting at A
Q: <A>
Goal: Fully Explore
Pop: A, Q: <>
Q: <B>
Pop: B, Q: <>
Q: <C>
Pop: C, Q: <>
Q: <A>
NEVER DONE
A
B
C
BFS Pseudocode
put start node in a queue
while (queue is not empty)
:
pop node N off queue
mark node N as visited
if (N is goal):
return true
else:
for each node O that is child of N:
if O is not marked visited:
push O onto queue
return false
Mark the node
as visited!
Breadth-First Search
Q: <>
A
B
C
D
E
Problem: Find everything reachable from A
Breadth-First Search
Q: <>
Q: <A>
A
C
D
E
B
Breadth-First Search
Q: <>
Q: <A>
Q: <>
A
E
D
C
B
Breadth-First Search
Q: <>
Q: <A>
Q: <>
Q: <C>
A
C
E
D
B
Breadth-First Search
Q: <>
Q: <A>
Q: <>
Q: <C>
Q: <C ,D>
A
C
D
E
B
Breadth-First Search
Q: <>
Q: <A>
Q: <>
Q: <C>
Q: <C ,D>
Q: <D>
A
C
D
E
B
Breadth-First Search
Q: <>
Q: <A>
Q: <>
Q: <C>
Q: <C ,D>
Q: <D>
Q: <D, E>
A
C
D
E
B
Breadth-First Search
Q: <>
Q: <A>
Q: <>
Q: <C>
Q: <C ,D>
Q: <D>
Q: <D, E>
Q: <E>
A
C
D
E
B
Breadth-First Search
Q: <>
Q: <A>
Q: <>
Q: <C>
Q: <C ,D>
Q: <D>
Q: <D, E>
Q: <E>
DONE
A
C
D
E
B
Shortest Paths with BFS
From Node B
A
C
D
E
1
1
1
1
1
1
Shortest path to D? to E?
What are the costs?
B
1
Shortest Paths with BFS
From Node B
A
C
D
E
1
1
1
1
1
1
Shortest path to D? to E?
What are the costs?
B
1
Shortest Paths with Weights
A
C
D
E
From Node B
100
2
6
2
3
100
Weights are not the same!
Are the paths?
B
2
A
C
D
E
From Node B
2
100
2
6
2
3
100
B
Shortest Paths with Weights
Interfaces
Classes, Interfaces, and Types
●
The fundamental unit of programming in
Java is a class
●
Classes can extend other classes and
implement interfaces
●
Interfaces can extend other interfaces
Classes, Objects, and Java
Everything is an instance of a class
◦
Defines data and methods
Every class extends exactly one other class
◦
Object if no explicit superclass
◦
Inherits superclass fields
Every class also defines a type
◦
Foo defines type Foo
◦
Foo inherits all inherited types
Interfaces
Pure type declaration
public interface Comparable {int compareTo(Object other);
}
Can contain:
◦
Method specifications (implicitly
public abstract
)
◦
Named constants (implicitly
public final static
)
Does not contain implementation!
Cannot create instances of interfaces
Implementing Interfaces
●
A class can implement one or more interfaces
class Kitten implements Pettable, Huggable
●
The implementing class and its instances have the interface type(s)
as well as the class type(s)
●
The class must provide or inherit an implementation of all methods
defined by the interface(s)
◦
Not true for abstract classes
Using Interface Types
●
An interface defines a type, so we can declare variables
and parameters of that type
●
A variable with an interface type can refer to an object of
any class implementing that type
List<String> x = new ArrayList<String>();
void sort(List aList) {…}Guidelines for Interfaces
●
Provide interfaces for significant types and abstractions
●
Write code using interface types like Map instead of
HashMap and TreeMap wherever possible
◦
Allows code to work with different implementations later on
●
Both interfaces and classes are appropriate in various
circumstances
Parsing Marvel Data
●
Data is in marvel.tsv
●
Will be pushed with hw6
●
Each line is in the form:
●
"character" "book”
●
Ex:
“CAPTAIN AMERICA"
"N 57”
●
Parsing is already implemented for you!
Parsing Marvel Data
●
MarvelParser.parseData(String filename,
Set<String> characters,
Map<String, List<String>> books)
●
Call parseData() with an empty Set, Map
●
parseData() will fill the Set with all comic book characters,
Map with Characters
List of books they’re in
HW 6 Demo
In this section, we delve into Homework 6 progress, reminders for effective programming practices, and essential concepts like Breadth-First Search (BFS) and Interfaces. Key points include the importance of controlling expensive checks, utilizing debug flags, and distinguishing between BFS and Depth-First Search (DFS) for connectivity and path calculations. Various images illustrate BFS processes and node visitation sequences starting from a given node.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Section 5: HW6 and Interfaces SLIDES ADAPTED FROM ALEX MARIAKAKIS, WITH MATERIAL FROM KRYSTA YOUSOUFIAN, MIKE ERNST, KELLEN DONOHUE
Agenda Reminders HW 6 due next Wednesday night (5/9) Breadth-first search (BFS) Interfaces Parsing Marvel Data
Reminders: Expensive CheckReps are BAD (at least when assignments are turned in, but can be useful for finding hard-to-discover problems so need to be able to control expensive checks) Debug flags are GOOD (or enums to indicate depth of debug)
Graphs B A Can I reach B from A? C D E
Breadth-First Search (BFS) Often used for discovering connectivity Calculates the shortest path if and only if all edges have same positive or no weight Depth-first search (DFS) is commonly mentioned with BFS BFS looks wide , DFS looks deep DFS can also be used for discovery, but not the shortest path
Breadth-First Search (BFS) Starting at A, which nodes will be visited first in a BFS? C E B A F D G
Breadth-First Search (BFS) Starting at A, which nodes will be visited first in a BFS? B, C, D C E B A F D G
Breadth-First Search (BFS) Starting at A, which nodes will be visited second in a BFS? C E B A F D G
Breadth-First Search (BFS) Starting at A, which nodes will be visited second in a BFS? E, F, G C E B A F D G
BFS Pseudocode put start node in a queue while (queue is not empty): pop node N off queue mark node N as visited if (N is goal): return true else: for each node O that is child of N: if O is not marked visit push O onto queue return false
Breadth-First Search START: Q: <A> Pop: A, Q: <> Q: <B, C> Pop: B, Q: <C> Q: <C> Pop: C, Q: <C> Q: <> DONE Starting at A Goal: Fully explore A B C
Breadth-First Search with Cycle START: Q: <A> Pop: A, Q: <> Q: <B> Pop: B, Q: <> Q: <C> Pop: C, Q: <> Q: <A> NEVER DONE Starting at A Goal: Fully Explore A B C
Mark the node as visited! BFS Pseudocode put start node in a queue while (queue is not empty): pop node N off queue mark node N as visited if (N is goal): return true else: for each node O that is child of N: if O is not marked visited: push O onto queue return false
Breadth-First Search Problem: Find everything reachable from A Q: <> B A C D E
Breadth-First Search Q: <> Q: <A> B A C D E
Breadth-First Search Q: <> Q: <A> Q: <> B A C D E
Breadth-First Search Q: <> Q: <A> Q: <> Q: <C> B A C D E
Breadth-First Search Q: <> Q: <A> Q: <> Q: <C> Q: <C ,D> B A C D E
Breadth-First Search Q: <> Q: <A> Q: <> Q: <C> Q: <C ,D> Q: <D> B A C D E
Breadth-First Search Q: <> Q: <A> Q: <> Q: <C> Q: <C ,D> Q: <D> Q: <D, E> B A C D E
Breadth-First Search Q: <> Q: <A> Q: <> Q: <C> Q: <C ,D> Q: <D> Q: <D, E> Q: <E> B A C D E
Breadth-First Search Q: <> Q: <A> Q: <> Q: <C> Q: <C ,D> Q: <D> Q: <D, E> Q: <E> DONE B A C D E
Shortest Paths with BFS 1 From Node B B Destination Path Cost A 1 A <B,A> 1 1 1 B <B> 0 C <B,A,C> 2 1 D C D E 1 1 Shortest path to D? to E? What are the costs? E
Shortest Paths with BFS 1 From Node B B Destination Path Cost A 1 A <B,A> 1 1 1 B <B> 0 C <B,A,C> 2 1 D <B,D> 1 C D E <B,D,E> 2 1 1 Shortest path to D? to E? What are the costs? E
Shortest Paths with Weights 2 From Node B B Destination Path Cost A 100 A <B,A> 2 100 3 B <B> 0 C <B,A,C> 5 2 D C D E 6 2 Weights are not the same! Are the paths? E
Shortest Paths with Weights 2 From Node B B Destination Path Cost A 100 A <B,A> 2 100 3 B <B> 0 C <B,A,C> 5 2 D <B,A,C,D> 7 C D E <B,A,C,E> 7 6 2 E
Classes, Interfaces, and Types The fundamental unit of programming in Java is a class Classes can extend other classes and implement interfaces Interfaces can extend other interfaces
Classes, Objects, and Java Everything is an instance of a class Defines data and methods Every class extends exactly one other class Object if no explicit superclass Inherits superclass fields Every class also defines a type Foo defines type Foo Foo inherits all inherited types
Interfaces Pure type declaration public interface Comparable { int compareTo(Object other); } Can contain: Method specifications (implicitly public abstract) Named constants (implicitly public final static) Does not contain implementation! Cannot create instances of interfaces
Implementing Interfaces A class can implement one or more interfaces class Kitten implements Pettable, Huggable The implementing class and its instances have the interface type(s) as well as the class type(s) The class must provide or inherit an implementation of all methods defined by the interface(s) Not true for abstract classes
Using Interface Types An interface defines a type, so we can declare variables and parameters of that type A variable with an interface type can refer to an object of any class implementing that type List<String> x = new ArrayList<String>(); void sort(List aList) { }
Guidelines for Interfaces Provide interfaces for significant types and abstractions Write code using interface types like Map instead of HashMap and TreeMap wherever possible Allows code to work with different implementations later on Both interfaces and classes are appropriate in various circumstances
Parsing Marvel Data Data is in marvel.tsv Will be pushed with hw6 Each line is in the form: "character" "book Ex: CAPTAIN AMERICA" "N 57 Parsing is already implemented for you!
Parsing Marvel Data MarvelParser.parseData(String filename, Set<String> characters, Map<String, List<String>> books) Call parseData() with an empty Set, Map parseData() will fill the Set with all comic book characters, Map with Characters List of books they re in
