HWx5 and HWx6

DIFFERENCE IN FORWARD/REVERSE TOPSORT ALGORITHMS

think: outdegree 0 is either first or last

so... in the procedure: driver should find outdegree and based on this either starts procedure with leaf or ends with leaf

FINDING CENTER OF A DAG

think: the higher the outdegree, the better so.... start by comparing outdegrees, decrementing, and removing vertices (starting specifically with leaves)

DIFFERENCE IN BFS/DFS TOPSORT

think: when should we mark a vertex as started, and how do we track that so... BFS uses a list to differentiate between a started and untouched vertex, and after starting adds vertex to the list. DFS does not make usage of these lists, and can mark a vertex as started depending on procedure

DETERMINING RELATIONSHIP DYNAMICS IN DAG

think: how are they traversed differently so... ancestor's preid < descendant, but descendant postid < ancestor

TOPSORT ON CYCLIC GRAPHS

BFS: think: how would the list work for the vertices so.... a vertex is not added to the "done/ready" list until after finished processing which cannot be done in a cycle

DFS: think: how would markers prevent reprocessing so... using both a start and done marker will ensure that once a vertex is done, it is not reprocessed

DYNAMIC PROGRAMMING CONCEPT

think like a DAG: subproblems are like subtrees so... for each sub-answer, it builds upon the overall answer as we go back to the main point (no cycles as the solutions would operate like a branch of a DAG)

What is the importance of a Driver

think: DAGS cannot be traversed like trees because adj lists overlap.

how to fix this: driver will use variable (counter, start, etc) to mark all vertices in a graph and then call the actual procedure based on vertex status

How are unconnected vertices ensured to be traversed

think: before procedure is called, what does driver do: traverse all vertices

so..... driver procedure should be able to include the vertices without edges

start and end markers

start indicates a vertex has been reached, end indicates the vertex has been fully processed

outdegree and indegree

think: which way is the edge going in or out? AKA # of edges being sent/received by vertex v, used to determine a vertex's relation to others in DAG (ex: is it a "leaf")

traversing directed vs undirected graphs

think: difference is whether edges point in a direction so…. undirected graph traversals require identifying an edge from i to j as the same from j to i in adj[].

setting up tree vs DAG

think: how do relation lists differ so…. child[v] does not have overlapping answers like adj[v] does. to prevent reprocessing use a variable to track this