Responses to questions of April 17, 2020. ************************************************************************ On the relationship between the greedy approach and the dynamic programming approach to algorithm development 1. Both are techniques rather than specific algorithms. For example, Dijkstra's Shortest Paths Algorithm uses the greedy strategy as the key step in the algorithm---a shortest path has been found to the vertex whose current "distance from the start vertex" value is a minimum. 2. They are used in problems involving choices where there is some type of scoring mechanism for evaluating the quality of the choices. 3. When both are applicable to solving the same problem (i.e. proper usage of the approach will produce an optimal solution), the greedy approach will run more efficiently as by its nature, it doesn't consider subproblems in the process of making the optimal choice. 4. Since they are techniques, there is not a "one size fits all" approach for applying them to problems. We have to use our understanding of the fundamental principles and our experience to try to apply them to a new situation. That is one reason why questions related to these approaches are popular interview questions---it allows the interviewer to get a better feel for your ability to engage in general problem solving rather than "fact regurgitation". ************************************************************************ On aspects of topological sort 1. It must be DAG---if there's a cycle, then there's no legal ordering of the nodes. 2. For a given DAG, there may be multiple legal orderings---the ordering produced will depend on what the algorithm chooses as the start vertex for the DFS. ************************************************************************ On graph representation QUESTION: How do we represent a weight of 0 on an edge using an adjacency matrix? ANSWER: We would have to change the representation for what it means for there to be no edge between two vertices. -1 is a possibility that comes to mind. ************************************************************************ On graph searches and edge classification QUESTION: For the Breadth-First webex video, in reference to when you're running the algorithm at the 11 minute mark, if the vertices are prioritized alphabetically, why is W explored before R. ANSWER: If you go back and listen to the discussion again, you will hear me mention this inconsistency in the book's example. In other words, their approach when the vertex being visited is adjacent to several vertices is to arbitrarily order them in adding to the queue. We will stick to the convention of adding them alphabetically (or increasing numerically). QUESTION: I am confused by cross versus forward edges. To clarify, (u,v) is a forward edge if v was already complete and thus "black", but if (u,v) is an edge where u is in a different tree than v and v is complete/"black" then it is a cross- edge? Because v is not a descendant of u in this scenario? ANSWER: You will need to use time stamp information (reference exercise 22.3-5 on page 611) to computationally (i.e. unambiguously) distinguish between cross edges and forward edges. Given an edge (u,v), u.d < v.d < v.f < u.f when it's a forward edge, but v.d < v.f < u.d < u.f when it's a cross edge. ************************************************************************ Two wonderful questions that are related QUESTION: Considering depth first search only requires queuing 1 item per level in the search. Wouldn't it be better to always use depth first over breadth since it is more efficient on memory while operating? QUESTION: Is it possible to combines BFS and DFS to exploit the strengths and offset the weaknesses of both algorithms? ANSWER: I normally teach about this issue in a subject near and dear to my heart---Artificial Intelligence. One of the first fundamental modeling situations we look at with AI is a problem-solving graph where the nodes represent a problem state, and an edge represents an action that transforms the current state into a new state. The intent is to find a sequence of actions that change the start state into a desired outcome (otherwise known as a goal state). As a simple example, the start state in a game of tic-tac-toe is an empty 3x3 grid. The goal state would be a grid filled in (legally) with X's and O's such that we win. In studying the fundamentals of generic search techniques for exploring such a state graph to try to find a sequence of actions that gets us from the start state to a goal state, we start by comparing BFS and DFS. The memory tradeoff is exactly the issue mentioned in the first question. However, DFS is not guaranteed to produce a solution that minimizes the number of actions taken to achieve the solution. The second question gets at the solution. A popular technique is called depth-first search with iterative deepening. A reasonable introduction to that approach is found in the following Wikipedia entry https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search Of course, none of these generic approaches takes into account specific properties of a state. So the next avenue of investigation is to use heuristics to make choices about which state or state(s) seem to be more promising places from which to achieve the goal state. This idea has led to other search algorithms and computer software that can beat humans in many types of games. ************************************************************************ On problem scaling QUESTION: In the activity selection problem, would a human be able to come up with a maximal subset on their own, without the aid of a computer running an algorithm? (Provided they have a list of all the activities and their durations, of course). If so, could this be potentially faster and easier to do than inputting each activity and duration and running an algorithm? ANSWER: Remember that our science relates to principles that apply when the problems get big. Certainly many humans could handle our 11 activity sample problem just fine, but it won't go so well when you start scheduling 1100 activities using 25 resources, ... When you start thinking about the logistical challenges the medical community is facing across our country juggling resources for handling COVID-19 patients with other health concerns, I think it's easier to appreciate how computational approaches can assist people with important resource allocation decisions.