The next 4 questions, refer to the following problem: in the College of Winterhold, young apprentices, gifted in the magic arts, must follow a rigorous program before completing their degree on Magika Arcana. The apprentices must complete the following courses: alteration (ALT), destruction (DEST), illusion (ILL), fire basics (FB), ice basics (IB), shock basics (SB), conjuration (CONJ), necromancy (NEC), alchemy (ALCM), summoning (SUMM), restoration (RESTO), wards (WARD), potions (POTS), introduction to the elements (ELEM) and dragon shouts (SHOUT). Apprentices can take one course per semester, and courses have the following pre-requisites: SHOUT requires ALT, DEST, ILL, CONJ, ALCM, and RESTO. DEST requires FB, IB, WARD, and SB. NEC requires CONJ. ALCM requires POTS and WARD. CONJ requires SUMM. Each of the following: FB, IB and SB require ELEM. POTS require ELEM and WARD. SUMM requires POTS and WARD.

2. (20 points) Show a graph G = (V, E) modeling these prerequisites in such a way you can solve Problem 5.1 (Hint: check out the CSE prerequisites graph: http://www.cse.lehigh.edu/images/academics/diagrams/cse%20diagram%20class%202019%20or%20later%202.pdf)

3. (20 points) Please show the resulting graph after calling DFS(G) on the graph G you obtained in Question 2. In particular, indicate v.d and v.f for each vertex v G.V , and indicate which edges are tree edges (e.g., by marking them in a different color). Please use similar conventions as shown in Figure 22.4 (p), Page 605.

4. (15 points) Based on your result of Question 3, list two of each of the following: tree edges, back edges, cross edges and forward edges.

5. (15 points) Help an apprentice obtain a sequence of courses that will not violate the prerequisites.2 For this you must use the topological sort procedure on the graphs obtained in Questions 2 and 3. Describe the process you used (you dont have to show step-by-step; just a description of how you generated a sequence of courses using topological sorting). Please show details of your work to allow for possible parti

22.3 Depth-first search 605 1/ 2/ 1/ 2/ (Ch) 91 9 C) T) 9/ 27 912 CM 1011 3611 Figure 22.4 The progress of the depth-first-search algorithm DFS on a directed graph. As edges are explored by the algorithm, they are shown as either shaded (if they are tree edges) or dashed (otherwise). Nontree edges are labeled B, C, or F according to whether they are back, cross, or forward edges. Timestamps within vertices indicate discovery time/finishing times. 22.3 Depth-first search 605 1/ 2/ 1/ 2/ (Ch) 91 9 C) T) 9/ 27 912 CM 1011 3611 Figure 22.4 The progress of the depth-first-search algorithm DFS on a directed graph. As edges are explored by the algorithm, they are shown as either shaded (if they are tree edges) or dashed (otherwise). Nontree edges are labeled B, C, or F according to whether they are back, cross, or forward edges. Timestamps within vertices indicate discovery time/finishing times