Skip to content

test3.md

Latest commit

 

History

History
40 lines (31 loc) · 1.02 KB

test3.md

File metadata and controls

40 lines (31 loc) · 1.02 KB
Raw

Test 3

27 questions: 7 questions (3 pts each) - fill in Adjacency Matrix, directed vs undirected 4 questions (4 pts each) - traversals (pre, post, inOrder) 4 questions (4 pts each) - graph from Adjacency Matrix 3 questions (3 pts each) - Incident and Adjacent nodes in Adjacency Matrix 2 questions (4 pts each) - hash table, load factor 2 questions (4 pts each) - Prims 2 questions (4 pts each) - Kruskal 2 questions (4 pts each) - Shortest Path (Dijkstra, Travelling Salesman Problem), definition questions

5 questions (1 pt each) - Bonus (definitions)

Adjecency Matrix

Symmetry about axis = undirected graph

  • Directed Graphs

  • Undirected Graphs

Two Algorithms

Prim (build the tree incrementally) Kruskal

What are minimum spanning trees used for?

  • Traveling salesman problem
  • Minimum spanning forest?

Definitions:

  • Hamiltonian circuit

    • a route returning to the beginning is known as a Hamiltonian circuit

  • Hamiltonian path

  • Walk

  • Tour

  • Traveling Salesman Problem

    • classical problem
    • practical problem