December 10, 2010
Not everyone follows the suggested course grid provided by the Computer Science department. Transfer students, students who have changed majors, and free-willed spirits will often need to come up with their own plan to graduate in the fewest semesters possible. Based on a current transcript, this program will plot an efficient path to graduation.
- A* search is used to find course schedules for each semester to allow the student to graduate as quickly as possible.
- Using Berkeley's framework as a generic problem-solver.
- Applying AI techniques to a specific, real-world problem. Both an undergraduate advisor and the Registrar's office expressed interest in this project.
Technology Used Block Diagram
Evaluation of Results
The program does compute an efficient path to graduation (if possible, more below). Based on my undergraduate transcript, I ran through scenarios of having no classes on my transcript to only a few left. Based on the number of credits left to graduate, I was able to verify that the program found the quickest path to graduation.
I could add in more optimizations if time permitted, but currently the program can get bogged down fairly quickly. I was forced to play with a branching factor parameter to speed things up. Theoretically, I could find thousands of course combinations for a given semester. In 4 semesters at 1,000 combinations each, there are 1 trillion states. To have the program complete in a reasonable amount of time, I limited this to 15 branches at each step. For a student halfway through the program, the algorithm will find a path in 4 semesters about 80-90% of the time. We will have bad luck ~5% of the time and no path can be found, but the rest of the time a path can be found in 5 semesters.