Attachment | Size |
---|---|

CS2013-Strawman-AL-Algorithms and Complexity.pdf | 49.01 KB |

The CS2013 Strawman Report comment period is now closed. Please see the CS2013 Ironman report for the latest CS2013 draft to comment on. Forum to comment on "AL-Algorithms and Complexity" Knowledge Area in the CS2013 Strawman report. We ask that comments related to specific text in the report please specify the page number and line number(s) of the text being commented on. Line numbers are provided on the far left-hand side of the each page.

I like the thought that has gone into separating really vital material (order of growth, finite-state machines and regular expressions) from elective topics like regular languages, turing machines, etc.

However, in line 35 and 51, the term "complexity class" is used in ways that do not match my experience. Here is seems to refer to a class of cost functions that have similar growth (eg logarithmic) and perhaps to a class of algorithms having performance whichgrows that way. I have only ever seen the term used for a class of problems whose *intrinsic* cost (ie that of the best possible algorithm) is of a particular growth. In any case, it is a hard thing to master the extra level of abstraction, moving from particular examples that grow in a way to the set of all things that grow a certain way; I don't think it belongs in the Core at all, let alone in Core-Tier1. What does belong in Core-Tier1 is the concept of "functions that grow at different rates, especially the common ones of constant, logarithmic, linear, n log n, quadratic, and exponential; and examples of algorithms whose performance grows in each of these ways."

We appreciate your contribution and understand your point, but after much discussion, we have decided to keep the language as is for consistency with the previous two ACM/IEEE Curricula documents, assuming that the intent of the topics will be understood by the community.

Line 113 in AL/Fundamental Data Structures and Algorithms places graph representations in Core-Tier1. I think this is excessive; I would not even see this as Core-Tier2. I agree that the key graph algorithms need to be in the core, but these can all be presented abstractly, working on the graph as an ADT; building a representation of a graph using lists etc is just an artefact of working in languages (or with collection libvraries) that lack a good Graph abstraction. For knowledge required of all, or even almost all, graduates, we don't need to go to the level of coding the graph from primitive structures. I would move graph representations to AL.Advanced Data Structures, Algorithms and Analysis.

We believe we're in agreement here. As we hope we've conveyed in the Learning Outcomes for this knowledge unit, we didn't intend for the representation topic to be an implementation issue. Rather, we hope students will understand that different representation formalisms can allow for easier/more difficult graph manipulation -- for example, when finding shortest paths between 2 nodes in a graph.

AL/Basic Analysis, Page 36, line 33

The report mentions "average case" analysis here and in several other places (e.g., page 60, line 192). I would suggest "expected case" instead, since this meshes better with probability, hashing and (randomized) quicksort.

True average-case analysis is quite hard (e.g., not all inputs to quicksort are equally likely, since lots of data is already sorted or near-sorted).

Good point. We've made the change from "average case" to "expected case".

Were heaps intentionally omitted from AL/Fundamental Data Structures and Algorithms (p 38)? Given everything that was included by name, it seems a strange omission (except, curiously, in the form of heapsort, line 108). Priority queues are mentioned elsewhere (SDF/Fundamental Data Structures, p 141) as an application, but I think "heap", the implementation, belongs in the same unit as e.g. "binary search tree" and "hash tables".

Thanks for noticing this. We've added "Heaps" to the Core-Tier2 topics in AL/Fundamental Data Structures and Algorithms.

I have posted some comments that I believe apply to all KAs within the CS2013 Strawman Report-Chapters 1-5 thread. I would like to make reference to those comments here since they apply to all KAs.

The comments are posted under the following subjects:

First of All: Thank You.

Matching of Topics and Learning Outcomes for Core-Tier-1 and 2.

Unique Labeling or Numbering of all Topics and Learning Outcomes.

Improved Correspondence between Learning Outcomes and Topics.

Consistent Labeling for Levels of Understanding.

On the Importance of the Learning Outcomes in Core-Tier1 and 2.

Comments for this KA:

Page 37, Lines 34 and 40: I believe that informally introducing and using the Big-O notation can be done in Core-Tier-1. Introducing the formal definition of big O and its formal application should be done in Core-Tier-2 since students need more mathematical background in order to effectively understand and apply these formal definitions.

Page 37, Line 42: I believe we should separate 'Recurrence relations' from 'Analysis of recursive algorithms'. The former is a prerequisite of the latter that maybe introduced within a different course. In addition, both of these would need at a minimum 1 hour each.

Page 37, Line 44: We may want to add 'Analysis of iterative algorithms' (in Core-Tier2) and maybe add one Core-Tier2 hour. 'Analysis of recursive algorithms' appear in line 42 but iterative does not.

Page 37, Line 72: I would move 'Recursive backtracking' to Core-Tier2 or as Elective.

Page 38, Line 120: This line includes several sub-topics that may need 1 or 2 extra hours or more depending on how many algorithms are covered; maybe this topic should be left as Elective.

Page 39, Line 152: I believe that to meaningfully cover Context-free grammars much more than 1 hour is needed. I would move this topic (line 152) to be an Elective topic.

Page 39, Lines 153 – 155: The topics in lines 153 and 154 could be, if needed briefly introduced in 1 hour, so I would rewrite these 3 topics (lines 153 - 155) as the following two:

Introduction to the P and NP classes and the P vs NP problem.

Introduction to the NP-complete class and exemplary NP-complete problems (e.g., SAT and Knapsack).

Many thanks for your comments and suggestions. We have discussed all of them and are making modifications as follows:

Your suggestion:

Page 37, Lines 34 and 40: I believe that informally introducing and using the Big-O notation can be done in Core-Tier-1. Introducing the formal definition of big O and its formal application should be done in Core-Tier-2 since students need more mathematical background in order to effectively understand and apply these formal definitions.

Our response:

Here we felt strongly that it would be embarrassing if a computer scientist did not know the formal definition. To signal that importance, we have left it as is. Applying it formally remains in Core-Tier2.

Your suggestion:

Page 37, Line 42: I believe we should separate 'Recurrence relations' from 'Analysis of recursive algorithms'. The former is a prerequisite of the latter that maybe introduced within a different course. In addition, both of these would need at a minimum 1 hour each.

Our response:

We've split them, as you suggested. (Good idea. Thank you.) We still feel that the hours, as originally given, are fine, and have left them as they were.

Your suggestion:

Page 37, Line 44: We may want to add 'Analysis of iterative algorithms' (in Core-Tier2) and maybe add one Core-Tier2 hour. 'Analysis of recursive algorithms' appear in line 42 but iterative does not.

Our response:

Thanks for catching the fact that "analysis of iterative algorithms" was not explicit. We've now added that. Here, as above, we've left the number of hours as they were.

Your suggestion:

Page 37, Line 72: I would move 'Recursive backtracking' to Core-Tier2 or as Elective.

Our response:

After much discussion, we believe it should remain in Core-Tier1.

Your suggestion:

Page 38, Line 120: This line includes several sub-topics that may need 1 or 2 extra hours or more depending on how many algorithms are covered; maybe this topic should be left as Elective.

Our response:

As the learning outcomes indicate, we intended that the instructor simply select 1 or maybe 2 of these, and so we have left the hours as they were. We will attempt to clarify our intentions in the document.

Your suggestion:

Page 39, Line 152: I believe that to meaningfully cover Context-free grammars much more than 1 hour is needed. I would move this topic (line 152) to be an Elective topic.

Our response:

Here we really don't mean much more than the ability to design a CFG, and so we have left the hours as they were.

Your suggestion:

Page 39, Lines 153 – 155: The topics in lines 153 and 154 could be, if needed briefly introduced in 1 hour, so I would rewrite these 3 topics (lines 153 - 155) as the following two:

Introduction to the P and NP classes and the P vs NP problem.

Introduction to the NP-complete class and exemplary NP-complete problems (e.g., SAT and Knapsack).

Our response:

We've made your suggestion changes. Thanks!