Computer Science 225
Advanced Programming
Spring 2022, Siena College
Lecture 9: Spatial Data Structures
Date: Monday, February 28, 2022
Agenda
- Announcements
- Problem Set 3: see sample solutions video
- Exam tonight as you know
- Lab 5: Java Graphics and Mouse Events (in Canvas and GitHub) due the day
before your lab meeting during the week of March 7
- With the evening exam, we have no lab meetings this week
- I am at a conference for the second half of the week, so no
class on Friday
- Participate in the CS Club Hackathon next weekend
- those who participate in a meaningful way get an automatic
24-hour grace period on Problem Set 4
- Sign up to volunteer at the High School Programming Contest, April 8
- see the email from Dr. Cotler
- if we get over 90% participation from our class, we will
have an across-the-board 1-point final average bonus
- Problem Set 4 is out
- task: finish up Concentration
- groups/repositories by Thursday
- due in a week
- Art projects!
- See last Friday's snow day video on Bailey's graph structures
- Spatial data structures
Terminology
- graph
- vertex
- edge
- weighted graph
- adjacent vertices
- path of vertices
- simple path
- cycle
- directed graph/digraph
- undirected graph
- vertex degree, in-degree, out-degree
- connected vertices
- subgraph
- connected component
- acyclic graph
- complete graph
- adjacency matrix
- adjacency list
- spatial data structure
- quadtree
- quadrant
Examples