CSC2025 Quiz 7

Fall 2013
Herbert J. Bernstein ( )

CSC2025 Quiz 7
Fall 2013

 		 

This web page is http://www.bernstein-plus-sons.com/.dowling/CSC2025F13/CSC2025_Quiz_7.html
Copyright © 2004, 2011, 2013 Herbert J. Bernstein and other parties. All rights reserved.

This is the seventh daily quiz to be taken or before Wednesday, 6 November 2013 You should need several hours to do this quiz properly, so it is being made available early. It involves some serious programming. You may work with whoever else you wish on this quiz, but you are responsible for understanding whatever you submit. You should submit your best effort on time, but you may return to this important quiz as often as you wish to try to improve your work for full credit. This is a very hard quiz. Don't get discouraged if you have trouble with it. We will work through the problems people have together and get everybdy to understand how to handle this, but if you don't try it yourself, you won't fully appreciate the discussion.

  <==== Do this AFTER you've answered all the questions

You probably DON'T want to do this ===>  

Please fill in the following information:

Name:


Email:

Skype ID:

Please answer the following questions on this form (or on a paper copy of this form).

  1. Using words, not code, give the design of a program that will accept a description of a project in terms of the names of tasks to be done and the dependencies between tasks. A dependency is simply a pair of name of tasks saying that starting on the first member of the pair depends on completion of the second member of the pair. One of the tasks will be called "START" and will not depend on any other task. One of the tasks will be called "END" and no other task will depend on END. For all other tasks, any task may be specified as depending on any other task, and any task may be specified as depending on multiple tasks. If a task other than START does not depend on any other tasks at all, it should be marked as depending on START. If a task other than END has no other tasks depending on it, then END should be marked as depending on that terminal task. You program is to accept an arbitrary number of tasks and an arbitrary number of pairs of dependencies, is to analyze the data provided, and fix it up according the the rules above, and then for each and every task, find a path from that task to END. Your design must include a careful consideration of how to implement the necessary data structures, trying for a good balance of timing, space and coding complexity, and explaining your reasoning. Give particular thought to how to format the output so that it will be comprehensible and useful. In particular, using the work you did for the prior quiz, you are to provide an alphabetized index of the tasks with their direct dependencies and with what depends directly on them. For extra credit specify how to improve that index to also list indirect dependencies for each task.

  2. Now estimate the timing and space requirements of your code in terms of the number of tasks.

  3. Now implement both the program you have designed and a test suite for that program. Post all of this on your course web site with detailed notes in your blog, and give the URLs here.

  4. Now test your program both for accuracy of the results and for timing. If your test suite does not do a good job of testing both, improve your test suite until it does. Be sure to explain the relationship between your timing test results and your timing estimate in your blog. Give the URL of the blog entries relating to this question.

  5. Explain the three most important things you learned from Dr. Garg's lecture 25

  6. Explain the three most important things you learned from Dr. Garg's lecture 26

  7. Explain the three most important things you learned from Dr. Garg's lecture 27

  <==== Do this AFTER you've answered all the questions

You probably DON'T want to do this ===>  

Revised 27 October 2013