Homework SourseBelow is a set of required courses for a degree The directed
Below is a set of required courses for a degree. The directed acyclic graph shows the prerequisite structure for the courses.
Your job is to devise an academic plan for a student. An academic plan is a set of courses for the student to take in each quarter. In each case, you need to devise an academic plan which respects the prerequisites and takes the fewest number of quarters. You can assume that every course is offered in every quarter.
1.Devise an academic plan for the student if he can only take one course per quarter.
2. Devise an academic plan for the student if he can take up to two courses per quarter.
CS 10 Math 2A Math 6A CS 11 Math 2B CS 101 CS 12 CS 160 CS 51 CS 181Solution
1. There are total of 10 courses and a student can take only one course per quater. There can be various academic plans and irrespective of these plans the minimun number of quaters needed is 10 as only one course is allowed per quater. so the plan can be as follows:
2. In this case a student can take upto 2 subjects per quarter. So here the minimum quarter can be 5. the academic plan can be as follows:
So this can be the academic plan for the second case.
| Quarter 1 | Quarter 2 | Quarter 3 | Quarter 4 | Quarter 5 | Quarter 6 | Quarter 7 | Quarter 8 | Quarter 9 | Quarter 10 |
| CS10 | |||||||||
| Math A | |||||||||
| Math 6A | |||||||||
| CS11 | |||||||||
| CS12 | |||||||||
| Math 2B | |||||||||
| CS51 | |||||||||
| CS 160 | |||||||||
| CS181 | |||||||||
| CS101 |
