Date: Tue, 20 Aug 2002 06:56:40 -0400 From: Frank Van Bussel To: Tristan Miller Subject: Final marks Marking scheme: Baseline: to 100% - Did one of the more ambitious tasks (dynamic routing, Webster's formula) + good distribution (justified in report and efficiently implemented) to 95% - Did both of less ambitious tasks +... to 85% - Did one of the less ambitious tasks (static load-based routing, traffic light sensors) + changed distribution to 70% - Changed distribution to 55% - Got starter code to work Note: these marks represent (upper) baselines: to obtain the limits given here your implementation must work properly, be stylistically/mathematically elegant, and not adversely affect the existing parts of the simulation; and your report must be well-written and informative. Particular deficiencies/mistakes will result in deductions, and very problematic implementations/reports will result in dropping down a category or two. As well, extra marks may be given occasionally, for efforts above and beyond the call of duty. The baseline is multiplied by the mark calculated below to obtain the assignment mark: 1. Programming tasks (50%) a) In report (15%) Full marks: Distribution & task(s) done are explicitly stated, with description of implementation and explanation of any material not covered in the course. For people in the last category above this requires stating at some point that you did not implement anything. ~10%: Certain implementation details are missing or vague. ~5%: No implementation details are given. No marks: Dist/tasks not stated OR report missing OR implementation does not match description. Note: For this last case, implementation had to be very clearly coded, well commented, and in an obvious place to get anything close to full marks for part b (below). b) Implementation I. Distribution (15%) - Choice of dist'n (5%): Best: Empirically based distribution (e.g. bimodal or generic hump) Good: Normal or poisson with appropriate parameters, some empirical justification given. OK: Normal or poisson without justification. Note: Justification requires something more than what is already stated in the assignment handout. Note on exponential distribution: if used in the manner of the above distributions, not good; if pairs are used to create a peaked dist'n, barely acceptable but not as good as e.g. paired linear dist'ns; if used to calculate time until next departure, better, depending on the overall shape of departures (e.g. rate must change over time). - Calculation of departure times using above dist'n (10%): Best: Constant time numerical approximation (e.g. polynomial fit, polar method, Box-Muller). Good: Constant time table lookup: even unif. -> uneven invervse(CDF) OK: Linear time table scan: uneven unif -> even inverse(CDF) Not so good: division of total time into bins during which departure times are generated using uniform distributions with different rates. Notes: With table lookup you are expected to use interpolation to obtain exact departure times. Table size is a factor (for accuracy < 6 is bad, >= 12 is decent; but very large tables increase the running time noticeably). Deductions: were made for replacing or writing over the current random number generators (which would affect all other uses of random numbers in the program), as well as for mistakes in the implementation. I. Tasks (20%), mark averaged for multi-task assignments i) Load based routing - Load factor (6%) Best: The original length, the load, and the speed of the street should be the main contributors, with consideration of load vs. capacity if the ratio gets close enough to 1:1 for there to be a significant chance the street is full by the time the car gets there. Example: (length + load/speed) * (1 + (load/capacity > 0.9)) (this doubles the weight if the street is near capacity). Acceptable: Multiply by (1 + load/capacity) or variant. Not-so-good: length + load, length*(load/capacity); the former is too simplistic, while the latter can result in long streets being added to a path just because they have no load. Otherwise: Some justification required; if it looked like the load factor was just some random combination of available values it was not worth much. Deductions: were made for incorrectly keeping track of the load on the streets, as well as for mistakes in the implementation. - Algorithm (14%) Best: Implemented a single-pair shortest paths alg. (e.g. Dijkstra with termination when path found). Not-so-good: Adapted all-pairs-shortest-paths alg. (inefficient) Worse: Original APSP replaced by modified alg. Deductions: made if original lengths were not used to calculate expected arrival (this affects delay calculations), as well as for mistakes in the implementation. ii) Dynamic routing - Load Factor (6%): same considerations apply as above. - Algorithm (14%): Best: Again, any SPSP algorithm, run for each car whenever it is ready to leave intersection. Acceptable but...: Periodic "traffic report" system, with all cars being re-evaluated simultaneously (using APSP) regardless of their position. This only achieves a granular approximation to a dynamic routing system. Notes & Worse: same as above. iii) Sensors Best: Load balancing sensors with limits: Green extended until some parameter (cars at intersection, load/capacity) roughly equalized on incoming streets, or limit time reached. Good: Green extended while incoming red street has no load. OK: Automatic switching if incoming green load goes below a certain point, as long as a decent minimum cycle time is enforced. So-so: Load balancing without limit times: This allows arbitrarily long blocking on cross streets. Not-so-good: Automatic switching which allows arbitrarily small cycle times. Not worth anything: Unilaterally lowering the cycle times. Note: The point being that extension of cycle times etc. is physically unproblematic, while with reduction you will have to take into account physical limits. So anything you do here that significantly reduces cycle time will need strong justification e.g. you going out to the street corner with a stopwatch. Deductions: For inadvertently or on purpose squeezing, reducing, or discarding the given ALL_RED_TIME (this is already as low as it can plausibly go), as well as for mistakes in the implementation. iv) Nobody successfully attempted to use Webster's formula. 2. General (50%) a) Report Style (10%) Excellent: Clear, concise, well organized, relevant, informative. Decent: Readable, not too lacking in the above departments. Adequate: Could extract minimum necessary info without massive efforts, but problems with organization, vagueness etc. Poor: Too vague, disorganized, perfunctory; in general, hard to make out what was going on. b) Testing (10%) i) For program correctness: Good: Brief description of testing strategy: strategy included multiple runs on the same input (to check consistency of program) and use of different (valid) inputs to test robustness etc. ii) Statistical tests: Good: Brief description of testing strategy: strategy involved methodically varying parameters and city properties to extract general statistics about average delay time, gridlock, and whatever other information you gathered. - In either case: lots of printouts of raw program output were not required or helpful. c) Code Style (10%) Very good: Readable (like a book). Acceptable: Avoided common problems (too many, too few comments; magic numbers; etc.), implementation details could be found and kept track of without great difficulties. Poor: Besides common problems, convoluted code which made it hard to make out what is happening. d) Test Runs (20%) Full marks: Compiles and runs with no problems. 10%: Compiles/runs but output doesn't make sense/highly improbable. 5%: Crashes or probable infinite loop. Nil: Did not compile. Deductions: 5% if compiled/ran but compilation had problems with makefile/dependencies that I needed to fix myself to get it to work. -------------------------------------------------------------------------- SUBTOTAL = TASKS + GENERAL ASSIGNMENT MARK: SUBTOTAL * BASELINE