Computer Science 501
Data Structures and Algorithm Analysis
Fall 2014, The College of Saint Rose
Lecture 11: Heapsort; Graphs
Date: Tuesday, November 18, 2014
Agenda
- Announcements
- Practice final exam questions out
- Lab 10: Trees [HTML] [PDF] lecture assignment portion recap
- Lab 9: BestOf [HTML] [PDF] programming recap
- Heapsort
- Graphs
- definition and terminology
- graph structures: directed/undirected, adjacency matrix/adjacency list
- Graph algorithms
- reachability
- single-source shortest paths
- Lab 11: Dijkstra's Road Trip [HTML] [PDF] out
Readings and References
Terminology
- heapsort
- skew heap
- graph
- node/vertex
- edge
- edge weight
- adjacent
- path
- simple path
- cycle
- directed graph/digraph
- degree (of a graph vertex)
- in-degree/out-degree
- connected (vertices)
- subgraph
- connected component
- acyclic (graph)
- complete (graph)
- adjacency matrix
- adjacency list
- reachability
- Dijkstra's algorithm
Examples