CIS 621 Winter 1995
Theory of Computation: Complexity
Assignments
Reading Assignment (Jan. 8):
Chapter 1 of AHU.
Reading Assignment (Jan. 22):
Chapters 2 and 3 of AHU.
Reading Assignment (Mar. 9):
Chapter 3 of GJ.
Homework#1 (due Jan. 17) (and a solution).
Homework#2 (due Jan. 26)
Homework#3 (due Feb. 14)
Homework#4 (due Feb. 28)
Homework#5 (due Mar. 13)
CIS 621 Winter 1995
Theory of Computation: Complexity
Notes
- I have posted some FAQs in the newsgroup "uo.cs.cis621". Also, there is a typo in the bubble-sort: the outer loop should be controled by "i:=i-1".
- Final Exam: will be a comprehensive take home test given out the last Friday of classes and due in my mail box by the scheduled Final's time (15:15 on Tuesday, March 19).
- Homework #4 scores: average 5.5±
2.2 (out of 10).
- Class evaluation Feb. 21 (avg.+stdv.):
- novelty: 5.2+2.2
- difficulty:
6.0+1.6
- speed: 5.1+1.6
- clarity: 5.1+1.8
- Student comments
(and my reaction):
- "Still very interesting but would
prefer to be able to relate to applications." (See, for instance,
exercise 2.34 from the text. For another example, consider the
shortest path tree routing problem.)
- "Difficulty using the material in real life." (This course intends
to give you a set of tools -- not claimed to be complete -- to help
you in your problem-solving activities. These tools are: algorithm
design strategies, correctness proofs, structuring of information,
complexity analysis.)
- "I'm concerned that we are 3 weeks behind the syllabus." (It is
only the syllabus that is ahead of the course (:-) I have the feeling
that we would have not covered well the material so far at a faster
pace -- and I'd rather have students learn something than rush through
more without learning.)
- Homework #3 scores: mostly 19 (out of 20).
- Grading criteria for Programming Assignment #1 (approximately
10% each):
- Coding:
- presentation (readability);
- comments;
- Algorithms:
- recursion;
- partitioning;
-
alternate method
- Analysis:
- Class evaluation Jan.29 (avg.+stdv.):
- novelty: 6.2+1.9
- difficulty: 6.3+1.6
- speed: 6.1+1.6
- clarity: 5.3+2.2
- Student comments (and my reaction):
none (none)
- Class evaluation Jan.19 (avg.+stdv.):
- novelty: 5.1+1.9
- difficulty: 5.7+1.9
- speed: 5.0+1.4
- clarity: 5.7+2.0
- Student comments (and my reaction):
- "Assumption of previous knowledge is high but the
intimidation/uncertainty it imposes on students should not be
underestimated." (read on)
- "I would have assumed that most grad students would already
have a solid grounding in algorithm design and complexity." (see
above)
- "Hand out some formal proofs of correctness and example of complexity arguments." (click here)
- "Interesting." (my sentiment exactly)
- Homework #1 scores: 5.25±
2.27 (out of the total of 8pts.)
- Midterm vs. HM#3: Since the (tentative) syllabus calls for
the take home midterm exam to be administered during the next weekend
(Feb. 9-11), it seems appropriate to defer the HW#3 due date to the
following week (as stated in the text of the assignment). If the
student preference is towards the opposite ordering of the tasks,
please let me know.
- People have spoken: HW#3 due next Monday, the Midterm --
the following Monday.
- Homework #2 scores: 6.30±
1.13 (out of the total of 8pts.)