0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Ryan1729 Mar 26 at 7:02
  • $\begingroup$ I you familiar with the concept of longest paths in DAGs? $\endgroup$ – Yuval Filmus Mar 26 at 12:30
  • $\begingroup$ @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 $\endgroup$ – pilolo Mar 26 at 16:38
  • $\begingroup$ @YuvalFilmus no, but i know of shortest paths and i was thinking to just reverse the condition on the weights $\endgroup$ – pilolo Mar 26 at 16:39
  • $\begingroup$ You might be looking for the longest path in the dependency DAG. $\endgroup$ – Yuval Filmus Mar 26 at 17:14
2
$\begingroup$

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.

This assumes there is no limit on the number of courses you can take in each semester. Under that condition, it will let you complete your degree in the minimum number of semesters, in an order that respects the prerequisites.

If there is a limit on the number of courses you can take in a semester, the problem is more challenging. This algorithm will find an order you can take your courses to get your degree, in an order that respects the prerequisites, but it is not necessarily the minimal number of semesters. If you're in that situation, the best solution may depend on the number of courses you have and whether this is a practical problem you want to solve in real life or a theoretical problem where you care about worst-case asymptotic running time.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So after i get the first 4 courses with 0 indegree, i could perform the longest dependency path among them then chooses the longest as the one with most priority? $\endgroup$ – pilolo Mar 29 at 18:58
  • 1
    $\begingroup$ @pilolo, no need to compute the longest dependency path explicitly. Kahn's algorithm is a lot simpler than that -- read the link I shared. See edited answer. $\endgroup$ – D.W. Mar 29 at 19:38
  • $\begingroup$ I took a look at the algorithm and it seems appropriate, thanks. do i need to handle these cases separately? 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) possible choices to take as prerequisites to a course 202. $\endgroup$ – pilolo Mar 30 at 5:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.