Skip to main content

Introduction

Summary

keywords

TODO

HW

Exercise*

Next time

Topological Sort

Can be solved by post order DFS. if the input is DAG. directed acyclic graph? Start from the node without any dependency.

Kahn's Algorithm​

  1. First calculate in-order numbers for each nodes. This helps you to find the minimum dependency nodes.
  2. push the no dependency node to the queue.
  3. By queue, start a topological sort starting from the popped node.
  4. For neighbor nodes, decrease the in-order numbers.
  5. go to step 2 until the queue is empty.

Test prewrap

  • choice diagram.

  • table for recursions. tabulations

  • practice pseudocode

  • huffman coding, put the smaller nodes to the left. (follow the book)

  • practice dijstra algortihm with the table.

  • limitations of dijstra algorithm, and how you can solve it.

  • Terminologies important.

  • graph representations important