UT Austin campus
unvisited
identified
visiting
visited
speed
←→ space
from
to
click map sets
Predict the trace
Click the vertex that gets visited next. Levels 1–6 use the lecture graphs.
0
x1
speed
→
vs
List vs matrix
| operation | list | matrix |
|---|---|---|
| space | O(V+E) | O(V²) |
| add vertex | O(1) | O(V²) |
| add edge | O(1) | O(1) |
| remove vertex | O(V+E) | O(V²) |
| remove edge | O(E) | O(1) |
| edge (u,v)? | O(V) | O(1) |
- matrix: dense graphs, fast edge checks. Use ∞ for "no edge" in weighted graphs.
- list: sparse graphs, fast neighbor loops (what BFS/DFS do).
BFS vs DFS
| BFS | DFS | |
|---|---|---|
| uses | queue (FIFO) | stack / recursion |
| order | level by level | deepest first |
| shortest? | yes (fewest edges) | no |
| time | O(V+E) | O(V+E) |
- "Lowest value first" DFS: go recursively into the smallest unvisited neighbor.
- A stack with ascending pushes pops the largest first: DFS(0,2) gives 0,3,7,6,4,5,2.
- Recursive DFS has a discovery order and a finish order.
Adjacency list
Adjacency matrix
Code
Call stack
Console
Exception classes
Catch it!
An exception is thrown. Which catch block runs? The first match wins.
ready
DNSTCPHTTPdata
URL
Packet
Java client
Simple Bank Access Protocol · Lecture 17
Client
PrintWriter buffer
TCP · port 8888
Server
Accounts
Protocol
| client sends | server replies | meaning |
|---|---|---|
BALANCE n | n and the balance | get the balance of account n |
DEPOSIT n a | n and the new balance | deposit amount a into account n |
WITHDRAW n a | n and the new balance | withdraw amount a from account n |
QUIT | none | quit the connection |
Thread t:
Call a method or trigger an event
History
Making a thread
t1
t2
CPU: who printed, in order
t1 Hellot2 Goodbye
Press run, then run again and compare.
Console
GreetingThreadDriver
Scheduler rules
- Each thread runs for a short time slice, then another ready thread gets the CPU.
- The highest-priority ready thread runs first. MIN 1, NORM 5, MAX 10.
- With equal priorities there is no guarantee about order.
main calls
What does it print?
Lecture 18