C455 - Learning Goals
- Below is a list of Units and Topics from the "IEEE/ACM Computing
Curricula 2001"
- Each Topic is prefixed with a Marker designating to what extent each topic
will be covered in CSCI C455.
- The Markers are:
- (M) - Mastery
means the student will be able to exhibit knowledge of the material
and/or skill with the procedure, in a new but appropriate context, even
when not instructed to do so.
- (F) - Familiarity
means the student will be able to answer questions about the material
and/or to use the procedure, in a new but appropriate context, when
instructed to do so.
- (E) - Exposure
means the student will have heard the term and/or seen the procedure,
but may not be able to discuss or use it effectively without further
instruction.
- Each
of these Topics along with its Marker specifies the learning goals for CSCI
C455.
- AL1. Basic algorithmic analysis [core]
- (F) Asymptotic analysis of upper and average complexity bounds
- (E) Big "O," little "o," omega, and theta notation
- (F) Standard complexity classes
- (E) Empirical measurements of performance
- (F) Time and space tradeoffs in algorithms
- (F) Using recurrence relations to analyze recursive algorithms
- AL2. Algorithmic strategies [core]
- (F) Brute-force algorithms
- (F) Greedy algorithms
- (F) Divide-and-conquer
- (F) Backtracking
- AL3. Fundamental computing algorithms [core]
- (F) Sequential and binary search algorithms
- (M) Quadratic sorting algorithms (selection, insertion)
- (M) O(N log N) sorting algorithms (Quicksort, heapsort, mergesort)
- (M) Hash tables, including collision-avoidance strategies
- (F) Binary search trees
- (F) Representations of graphs (adjacency list, adjacency matrix)
- (F) Depth- and breadth-first traversals
- (F) Shortest-path algorithms (Dijkstra’s and Floyd’s algorithms)
- (F) Minimum spanning tree (Prim’s and Kruskal’s algorithms)
- AL6. The complexity classes P and NP [elective]
- (F) Definition of the classes P and NP
- (E) NP-completeness (Cook’s theorem)
- (F) Standard NP-complete problems
- (E) Reduction techniques
- DS5. Graphs and trees [core]
- (F) Trees
- (F) Undirected graphs
- (F) Directed graphs
- (F) Spanning trees
- (F) Traversal strategies
- PF2. Algorithms and problem-solving [core]
- (E) Problem-solving strategies
- (E) The role of algorithms in the problem-solving process
- (E) Implementation strategies for algorithms
- (E) The concept and properties of algorithms
- SE10. Formal methods [elective]
- (E) Formal specification languages
- (F) Pre and post assertions
- (E) Formal verification
Last Updated: 01/06/2002