Grading and Deliverables for Project Part 1a

The most important requirement of Project 1a, as indicated on the project 1a specification, is that

“Whatever your design, it should adhere roughly to the implementation of the generic search algorithm of Poole and McWorth Section 3.4 or Russell and Norvig as a depth-first search, and a backward or regression search implementation of a scheduler, as addressed in sections 3.8.2 and 6.3, or corresponding sections of Russell and Norvig.”

The structure is clear, and the main challenge of Project 1a is in translating a specification of a general problem into a formalization that is amenable to automated solutions. This is why I am not terribly concerned that you can find Python code on the Web for depth-first search and related algorithms like topological sort. You should always cite such code if you use it, but just as you would certainly lose points in an English class for turning in a paper that quoted and cited too much of another paper, the same applies here with respect to code.

There will be two deliverables, as listed here, with a summary of grading factors to follow.

1) Deliverable 1 — Code

You will be submitting your Python 3 code. While the spec says that this should be as one file, we are relaxing this and your code submission can be one file or a (zipped) folder of files, but there must be a MAIN file that is called and run.

  • Whether you are submitting one code file or a folder of code files, there should be a ReadMe file that provides instructions on how to run your code, including some example calls if command-line arguments are involved, and includes notes about any external libraries/packages that are needed (make sure these are free and publicly available for download).
  • The team number and names of members should be in comments at the top of each file, code and ReadMe
  • The scripts should contain proper documentation and comments such that anyone can understand what your code does without having to dive deeply into the code itself. You can use this format for comments at the head of functions/methods, but it doesn’t need to be exactly like this, as long as it’s informative:
    • Brief, one-to-two lines about the function does
    • @param param_name (dtype) – what is param represents
    • …
    • @return (dtype) – what this function returns
    • …

2) Deliverable 2 — Project report (in PDF)

A report, which will have up to 6 sections, will accompany the code. Throughout the paper, cite other sources that you used, including other student presentations and code/concepts that you find on the Web. The last section of the paper will be references.

Section 1: Architectural Overview

Give an architectural overview of your project code. Reference the Poole and Mackworth and/or Russell and Norvig algorithms to describe how your code deviates from, specializes, and otherwise implements those algorithms. This can be a paragraph or two, describing your system as a depth first regression planner, and whether (for example) you broke the schedule into multiple stages (e.g., course ordering based on prerequisites and course scheduling by semester). Be explicit if you modified the project specifications in any way, for the better or worse. Three positive modifications would be adding a heuristic and making it an iterative deepening depth first search in pursuit of minimal-semester schedules (see my response to the Piazza post on “Section K” regarding this).

Section 2: Alternative Small Scale Designs Considered

Also, describe any interesting issues, be they challenges or simply alternative implementation and small scale design choices, that you encountered. For example, did you consider a two stage approach alluded o above, or a more integrated approach? Did you consider a recursive algorithm versus using an explicit stack? Did you consider formatting alternatives or alternative internal data structures? This can be up to two paragraphs. Just write NA (Not Applicable) under Section 2 if you have nothing to add to this section.

Section 3: Evaluation

Comment on the functionality of your project. Did any test cases fail for which you thought a valid schedule existed? In this section, also list 5-10 test cases (goal specifications + initial states) that you used to test your code on and show the plans that resulted in Appendix A. Here are some ideas about formatting, but I give these only as ideas.

For each test case, state whether a valid plan was found or not. Also, for each test case. give an estimate of the “wait” time for your planner to solve the problem (or not). If you instrumented your code to find more precise execution times then great — report those — that can result in a bump to your score. But minimally we are just looking for a ballpark response time for purposes of grading. List this information with the test case solutions in Appendix A as well.

Section 4: Alternative Approaches

Describe any alternative approaches to achieving the basic functionality, but that deviates from the procedural requirements of a regression, DFS scheduler. These alternatives can be alternative basic AI methods, or even non-AI methods. These alternative approaches are not a substitute to the DFS, regression planner requirement. Rather, they can be a jumping off point for discussion on alternatives, what distinguishes AI and non-AI, etc. Remember that you can also do class presentations on these alternatives.

Basic Grade

If you have fully functioning code that is consistent with the functional and procedural specifications, and a well described Section 1 (required), Section 2 (can be NA), Section 3 (required), Section 4 (can be NA), and Appendix A (required), then your grade will be about a 85/100 (solid B), depending on our views of your test cases, the nature of any deviations from the spec, etc.

Section 5: Extending the Scheduler

You can achieve more than a score of 85 by means that we have already mentioned

  • implementing a depth-first heuristic search (or other depth-first preferential search),
  • implementing an iterative deepening depth-first search (IDDFS),
    • implementing a depth-bounded search (required for IDDFS),
  • precisely instrumenting your code,

each of which requires modest modifications to the basic algorithm. Another option is to implement an anytime algorithm, which continues to search for solutions even after the first one is found, and remembers the best plan found so far. This too requires a modest change to the basic search algorithm, but it also requires that you formalize what you mean by plan quality to identify the “best” one.

  • anytime scheduler with measure of plan quality

The changes above can be done in conjunction, and if you were to do all of them, and describe them well, you would probably be looking at a 95 – 100 (solid A).

There are other ideas for extending the scheduler, but these I do not expect you to implement. Rather, you describe the prospective extension in each case, with some detail. You can do as many of these as you wish, including none at all, but I prefer fewer that are well done rather than many that are poorly done (i.e., thrown together at the last minute). As a group, you should discuss the final answer to each that you submit. Each of these discussions will probably be a couple of pages. You can get more than 100%.

  • Bayesian Belief Networks: Based on your knowledge about the CS program and Vanderbilt curriculum, construct a partial Bayesian network (of at least 8 nodes) that predicts the probability of a student’s grade (A, B, C, D, or F) in a course conditioned on their grades in other courses. You don’t have data, so construct (make up) the BN’s structure and probability tables from your team experience in this domain. Explain how a complete BN for the Vanderbilt curriculum could be learned from data (e.g., from the Registrar’s Office). Explain how the BN and grade prediction could be used to give students and advisors feedback as a student moved through the curriculum (designed by your scheduler or not). Describe what you think are any necessary ethical considerations if Vanderbilt (or any University) or a non-school corporate entity were to implement and release such a system capability. (about 4% points)
  • Hidden Markov Models: Another possible extension that also uses belief networks, hidden Markov models in particular, is motivated by the observation that often students can’t get into courses when they want to, even when they have satisfied prerequisites. Again, in a real setting, actual data from many students over time would allow the system to compute objective probabilities of getting into a course or not, given various factors (e.g., primarily the year of student, but also classroom (capacity), days and times offered). Rather, you would hand craft an HMM with your subjective assessment of probabilities. Give an example HMM over two to three semesters that is able to estimate the probability that a course can(not) be taken in a particular semester of a particular year. If any course in a schedule cannot be taken when scheduled, then the schedule fails. Explain how estimates of schedule failure probability can be used to guide the search for schedules by your scheduler. (about 4% points)
  • Variabilization: The scheduler as currently construed is a propositional scheduler — all arguments are constants (e.g., a particular course). Abstract courses as they are currently represented can be thought of as (kind of) variables that can be satisfied in different ways. Point (P) of the project description suggests possibilities, but add explicit variables, such as ?X and ?Y, which you saw in planning lectures. Give two schedules that would use variables in the semester and/or course fields (it should be a variant of you chosen representation of schedules). Describe how variables could be used to represent that two courses in a schedule cannot be the same. Describe how your scheduling algorithm would be modified enable the introduction of variables. Describe how schedule execution would be affected by schedules with variables? (about 2 %)
  • Macros: Give  two examples of macros in course scheduling, with or without variablization, using the macro format covered in class as a basis for your macros. One example should be determined from the prerequisite relationships between courses. One example can be a course combination based on popularity of a course combination (which of course would respect prerequisite relationships too). Describe how macros might be learned in the course scheduling domain. (about 2%)
  • Inductive Decision Tree Induction: This project would craft a decision tree that recommended courses (and abstract conditions corresponding to minors and majors, for example) based on characteristics of the user, such as year, and students’ interests in courses (e.g., if you are a senior, and you liked course X, then people like you also liked course Y). This is known as collaborative filtering, which we discussed supervised machine learning. In the real world, collaborative filtering would find correlations between the likes and dislikes of courses from the data preferences of many students. Because, you won’t have the data to support machine learning of such correlations, you will craft at least two decision trees. Describe how a decision tree recommender system would be folded into your scheduling algorithm. Also, sketch an interface that could be used to actually collect and store data for machine learning of a better recommender system. (about 2%)
  • Domain Engineering: You could add higher-level requirements for other majors and minors beyond Computer Science, and present results on specifications involving these requirements. This would probably add a few extra percentage points (about 1%). You could go beyond this and define super-higher level requirements that specify desirable (soft) prerequisites for entry level career positions or graduate school after graduation. Utilities and rewards could be attached to these super-higher level requirements, which could be used in scheduling. We haven’t studied reinforcement learning, but some of you probably saw it in Intro to AI reinforcement learning, and demonstrate how rewards “percolate” down to courses over a reasonable number of scheduling trials.

Appendix A:

Give examples of results of actual I/O in test runs. You might use formatting like this ( *** like annotations are helpful), but it should be easily comprehensible in any case.

  • Goal Condition: {(‘CS’, ‘mathematics’) (‘CS’, ‘core’) (‘MATH’, ’3641’) (‘CS’, ’1151’) (‘MATH’, ‘2410’)}
  • Initial State: {(‘CS’, ‘1101’)} .  *** will not be in resulting schedule
  • Schedule:
    • MATH 1200 3 Fall Frosh
    • CS 1151 3 Fall Frosh **** in the goal
    • CS 2212 3 Fall Frosh
    • EECE 2116 3 Fall Frosh
    • EECE 2116L 1 Fall Frosh
    • MATH 1201 3 Spring Frosh
    • CS 2201 3 Spring Frosh
    • CHIN 1011 3 Spring Frosh (note, this is not implied by goal)
    • CSET 3840 3 Spring Frosh (note, this is not implied by goal)
    • CS 2231 3 Fall Soph
    • MATH 1301 4 Fall Soph
    • CS 3250 3 Fall Soph    *** CS2201 and CS2212 preqs
    • CS 3251 3 Fall Soph
    • MATH 2300 3 Spring Soph
    • CS 3270 3 Spring Soph
    • CS 3281 3 Spring Soph
    • … fill Spring Soph up to at least 12 hours
    • MATH 2410 3 Fall Junior **** in the goal
    • … fillFall Junior up to at least 12 hours
    • MATH 2810 3 Spring Junior
    • … fill Spring Junior up to at least 12 hours
    • MATH 3640 3 Fall Senior
    • CS 3259 3 Fall Senior (note, this is not implied by goal)
    • … fill Fall Senior up to at least 12 hours
    • MATH 3641 3 Spring Senior **** in the goal
    • … fill Spring Senior up to at least 12 hours (though we allowed for final semester of less than 12, but I’m not sure that will be any easier than filling it up too)
    • CS mathematics 0 Spring Senior (these can be placed separately, as soon as they are satisfied too) **** in the goal
    • CS core 0 Spring Senior **** in the goal
    • CS calculus 0 Spring Senior
    • CS statsprob 0 Spring Senior
    • CS mathelective 0 Spring Senior

Grading Factors:

There will be variability in project implementations, so what follows is not so much a rubric as factors that we will consider in grading. Each factor is associated with an upper bound on its weight. These upper bounds do not sum to 100%

  • Basic Grade 85%
    • Quality of Code
      • Correctness of scheduler
        • Thoroughness of test cases
        • You should not have schedules that repeat courses
        • Courses should follow their pre requisites
        • Courses should be offered in allowable semesters only (ignore Summers)
        • each semester between 12 and 18 hours, inclusive
      • Clarity of I/O (See Appendix A above)
      • Adheres to regression, depth-first structure (see Doug or Nhung if you have questions, or post to Brightspace)
      • Clarity of code
        • Structuring of Code
        • Commenting of Code
    • Quality of Report
      • Adherence to prescribed report format
      • Clarity of writing
      • Thoroughness
      • Citations
      • Effort (again, if you reuse code wholesale you may lose points, but again, the emphasis of this project is in translating from a domain description to a runnable program).
  • Extensions 0% to 30%
    • See Section 5 discussion above