# taking school courses efficiently

I want design algorithm that allows a student to take important courses quickly up until graduation. no time, room number, professors needed here. just my selected courses I know will allow me to graduate but how best to take them based on prerequisites. the student can decide how many courses to take a semester. And, you cant take a course's prerequisite and itself eg cs101 cs102 201 but cs201 cant be taken in the first semester because i have to take its prerequisites first. Additionally prequisites can be such that 101 and 102 or 101 and 104 are possible choices to take as prerequisites to a course 201. We could also have 101 or 106 and 102 or 105 ossible choices to take as prerequisites to a course 202.

any suggestions and how to go about it. Trees, graph adjacency list

I was thinking topological sort will give a valid ordering but i think i would ran into trouble when placing them in across semesters because topological sort order them linearly eg cs101 cs102 201 but cs201 cant be taken in the first semester because i have to take its prerequisites first. And what about if we have cs 103 cs104 cs202. cs103 and 104 have nothing to do with cs101 102

• I’m not sure whether you are interested in an algorithm you can apply to many problems or whether you want a particular instance of the problem solved. Assuming the latter, the first thing I would try is roughly enumerating how many possible orderings there are for your particular problem. You may have fewer meaningfully different choices than you think. – Ryan1729 Mar 26 at 7:02
• I you familiar with the concept of longest paths in DAGs? – Yuval Filmus Mar 26 at 12:30
• @Ryan1729 the latter. How do i roughly enumerate. I was thinking topological sort will give a valid ordering but i think i would ran into trouble when placing them in across semesters because topological sort order them linearly – pilolo Mar 26 at 16:38
• @YuvalFilmus no, but i know of shortest paths and i was thinking to just reverse the condition on the weights – pilolo Mar 26 at 16:39
• You might be looking for the longest path in the dependency DAG. – Yuval Filmus Mar 26 at 17:14

Form a directed graph of dependencies, with an edge $$x\to y$$ if course $$x$$ is a prerequisite for course $$y$$. Use Kahn's algorithm to topologically sort the graph. In particular, in each semester, you take all courses with indegree 0 (i.e., all courses where you've satisfied all prerequisites), then delete those courses from the graph.