A | B | C | D | E | F | G | |
---|---|---|---|---|---|---|---|

1 | Area | Unit | Topic | Core Tier-1 | Core Tier-2 | Related to Evaluate | |

2 | Algorithms and Complexity (AL) | 19 | 9 | ||||

3 | AL/Basic Analysis | 2 | 2 | ||||

4 | Differences among best, average, and worst case behaviors of an algorithm | x | |||||

5 | Asymptotic analysis of upper and average complexity bounds | x | |||||

6 | Big O notation: formal definition | x | |||||

7 | Complexity classes, such as constant, logarithmic, linear, quadratic, and exponential | x | |||||

8 | Empirical measurements of performance | x | x | ||||

9 | Time and space trade-offs in algorithms | x | |||||

10 | Big O notation: use | x | |||||

11 | Little o, big omega and big theta notation | x | |||||

12 | Recurrence relations and analysis of recursive algorithms | x | |||||

13 | Some version of a Master Theorem | x | |||||

14 | AL/Algorithmic Strategies | 5 | 1 | ||||

15 | Brute-force algorithms | x | |||||

16 | Greedy algorithms | x | |||||

17 | Divide-and-conquer (cross-reference SDF/Algorithms and Design/Problem-solving strategies) | x | |||||

18 | Recursive backtracking | x | |||||

19 | Dynamic Programming | x | |||||

20 | Branch-and-bound | x | |||||

21 | Heuristics | x | |||||

22 | Reduction: transform-and-conquer | x | |||||

23 | AL/Fundamental Data Structures and Algorithms | 9 | 3 | ||||

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 algorithms | x | |||||

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 collisions | x | |||||

29 | Binary search trees | x | |||||

30 | Common operations on binary search trees such as select min, max, insert, delete, iterate over tree | x | |||||

31 | Graphs and graph algorithms | x | |||||

32 | Representations of graphs (e.g., adjacency list, adjacency matrix) | x | |||||

33 | Depth- and breadth-first traversals | x | |||||

34 | Graphs and graph algorithms | x | |||||

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 Complexity | 3 | 3 | ||||

39 | Finite-state machines | x | |||||

40 | Regular expressions | x | |||||

41 | The halting problem | x | |||||

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-complete | x | |||||

45 | Exemplary NP-complete problems (e.g., SAT, Knapsack) | x | |||||

46 | AL/Advanced Computational Complexity | 0 | 0 | ||||

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 | AL/Advanced Automata Theory and Computability | 0 | 0 | ||||

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 Analysis | 0 | 0 | ||||

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) | 0 | 16 | ||||

86 | AR/Digital logic and digital systems | 0 | 3 | ||||

87 | Overview and history of computer architecture | x | |||||

88 | Combinational vs. sequential logic/Field programmable gate arrays as a fundamental combinational + sequential logic building block | x | |||||

89 | Multiple representations/layers of interpretation (hardware is just another layer) | x | |||||

90 | Computer-aided design tools that process hardware and architectural representations | x | |||||

91 | Register transfer notation/Hardware Description Language (Verilog/VHDL) | x | |||||

92 | Physical constraints (gate delays, fan-in, fan-out, energy/power) | x | x | ||||

93 | AR/Machine-level representation of data | 0 | 3 | ||||

94 | Bits, bytes, and words | x | |||||

95 | Numeric data representation and number bases | x | |||||

96 | Fixed- and floating-point systems | x | |||||

97 | Signed and twos-complement representations | x | |||||

98 | Representation of non-numeric data (character codes, graphical data) | x | |||||

99 | Representation of records and arrays | x | |||||

100 | AR/Assembly level machine organization | 0 | 6 |

Loading...