Evaluate & ACM-IEEE CS Computer Science Curricula 2013 Strawman Draft
The version of the browser you are using is no longer supported. Please upgrade to a supported browser.Dismiss

ABCDEFG
1
AreaUnitTopicCore Tier-1Core Tier-2Related to Evaluate
2
Algorithms and Complexity (AL) 199
3
AL/Basic Analysis22
4
Differences among best, average, and worst case behaviors of an algorithmx
5
Asymptotic analysis of upper and average complexity bounds x
6
Big O notation: formal definitionx
7
Complexity classes, such as constant, logarithmic, linear, quadratic, and exponentialx
8
Empirical measurements of performancexx
9
Time and space trade-offs in algorithmsx
10
Big O notation: usex
11
Little o, big omega and big theta notationx
12
Recurrence relations and analysis of recursive algorithmsx
13
Some version of a Master Theoremx
14
AL/Algorithmic Strategies51
15
Brute-force algorithmsx
16
Greedy algorithmsx
17
Divide-and-conquer (cross-reference SDF/Algorithms and Design/Problem-solving strategies)x
18
Recursive backtrackingx
19
Dynamic Programmingx
20
Branch-and-boundx
21
Heuristicsx
22
Reduction: transform-and-conquerx
23
AL/Fundamental Data Structures and Algorithms93
24
Simple numerical algorithms, such as computing the average of a list of numbers, finding the min, max, and mode in a list, approximating the square root of a number, or finding the greatest common divisor
x
25
Sequential and binary search algorithmsx
26
Worst case quadratic sorting algorithms (selection, insertion)x
27
Worst or average case O(N log N) sorting algorithms (quicksort, heapsort, mergesort)x
28
Hash tables, including strategies for avoiding and resolving collisionsx
29
Binary search treesx
30
Common operations on binary search trees such as select min, max, insert, delete, iterate over treex
31
Graphs and graph algorithmsx
32
33
34
Graphs and graph algorithmsx
35
Shortest-path algorithms (Dijkstra’s and Floyd’s algorithms) x
36
Minimum spanning tree (Prim’s and Kruskal’s algorithms)x
37
Pattern matching and string/text algorithms (e.g., substring matching, regular expression matching, longest common subsequence algorithms)x
38
AL/Basic Automata Computability and Complexity33
39
Finite-state machinesx
40
Regular expressionsx
41
The halting problemx
42
Context-free grammars (cross-reference PL/Syntax Analysis)x
43
P vs NP (tractable and intractable problems)x
44
Definition of P, NP, and NP-completex
45
Exemplary NP-complete problems (e.g., SAT, Knapsack)x
46
47
Review definitions of the classes P and NP; introduce EXP
48
NP-completeness (Cook’s theorem)
49
Classic NP-complete problems
50
Reduction Techniques
51
52
Sets and languages
53
Regular languages
54
Review of deterministic finite automata (DFAs)
55
Nondeterministic finite automata (NFAs)
56
Equivalence of DFAs and NFAs
57
Review of regular expressions; their equivalence to finite automata
58
Closure properties
59
Proving languages non-regular, via the pumping lemma or alternative means
60
Context-free languages
61
Push-down automata (PDAs)
62
Relationship of PDAs and context-free grammars
63
Properties of context-free languages
64
Turing machines, or an equivalent formal model of universal computation
65
Nondeterministic Turing machines
66
Chomsky hierarchy
67
The Church-Turing thesis
68
Computability
69
Rice’s Theorem
70
Examples of uncomputable functions
71
Implications of uncomputability
72
AL/Advanced Data Structures Algorithms and Analysis00
73
Balanced trees (e.g., AVL trees, red-black trees, splay trees, treaps)
74
Graphs (e.g., topological sort, Tarjan’s algorithm, matching)
75
Advanced data structures (e.g., B-trees, tries, Fibonacci heaps)
76
Network flows (e.g., max flow [Ford-Fulkerson algorithm], max flow – min cut, maximum bipartite matching)
77
Linear Programming (e.g., duality, simplex method, interior point algorithms)
78
Number-theoretic algorithms (e.g., modular arithmetic, primality testing, integer factorization)
79
Geometric algorithms (e.g., points, line segments, polygons [properties, intersections], finding convex hull, spatial decomposition, collision detection, geometric search/proximity)
80
Randomized algorithms
81
Approximation algorithms
82
Amortized analysis
83
Probabilistic analysis
84
Online algorithms and competitive analysis
85
Architecture and Organization (AR)016
86
AR/Digital logic and digital systems03
87
Overview and history of computer architecturex
88
Combinational vs. sequential logic/Field programmable gate arrays as a fundamental combinational + sequential logic building blockx
89
Multiple representations/layers of interpretation (hardware is just another layer)x
90
Computer-aided design tools that process hardware and architectural representationsx
91
Register transfer notation/Hardware Description Language (Verilog/VHDL)x
92
Physical constraints (gate delays, fan-in, fan-out, energy/power)xx
93
AR/Machine-level representation of data03
94
Bits, bytes, and wordsx
95
Numeric data representation and number basesx
96
Fixed- and floating-point systemsx
97
Signed and twos-complement representationsx
98
Representation of non-numeric data (character codes, graphical data)x
99
Representation of records and arraysx
100
AR/Assembly level machine organization06