ACM/IEEE

ALG0. History and overview of algorithms and complexity [core]

Minimum core coverage time: 1 hour
Topics: / Coverage in the current curricula / Coverage in the new proposed curricula
  1. Indicate some reasons for studying analysis, complexity, and algorithmic strategies.

  1. Highlight some people that contributed or influenced the area of algorithms and complexity.

  1. Mention some basic algorithms and some reasons for their differences.

  1. Highlight how the use of theory influences algorithms and complexity.

  1. Indicate how algorithms are part of many different computer applications.

  1. Provide some knowledge themes such as relating complexity with algorithms.

  1. Contrast complexities of different algorithmic strategies.

  1. Explore some additional resources associated with algorithms and complexity.

  1. Explain the purpose and role of algorithms and complexity in computer engineering.

Learning objectives:
  1. Identify some contributors to algorithms and complexity and relate their achievements to the knowledge area.

  1. Associate some of the themes involved with algorithms and complexity.

  1. Name some applications where algorithms are important.

  1. Relate contributors with their achievements to the subject.

  1. Describe how computer engineering uses or benefits from algorithms and complexity.

ALG1. Basic algorithmic analysis [core]
Minimum core coverage time: 4 hours
Topics: / Coverage in current curricula / Coverage in the new proposed curricula
  1. Asymptotic analysis of upper and average complexity bounds
/ ICS 353
  1. Identifying differences among best, average, and worst case behaviors
/ ICS 353
  1. Big “O,” little “o,” omega, and theta notation
/ ICS 353
  1. Empirical measurements of performance
/ ICS 353
  1. Time and space tradeoffs in algorithms
/ ICS 353
  1. Using recurrence relations to analyze recursive algorithms
/ ICS 353
Learning objectives:
  1. Use big O, omega, and theta notation to give asymptotic upper, lower, and tight bounds on time and space complexity of algorithms.

  1. Determine the time complexity of simple algorithms.

  1. Deduce the recurrence relations that describe the time complexity of recursively defined algorithms, and solve simple recurrence relations.

ALG2. Algorithmic strategies [core]

Minimum core coverage time: 10 hours
Topics: / Coverage in current curricula / Coverage in the new proposed curricula
  1. Brute-force/Exhaustive Search algorithms
/ ICS 353
  1. Greedy algorithms
/ ICS 353
  1. Divide-and-conquer
/ ICS 353
  1. At least one of: Backtracking, Branch-and-bound, Heuristics
/ ICS 353
Learning objectives:
  1. Design algorithms using the brute-force, greedy, and divide-and-conquer strategies.

  1. Design algorithms using at least one other algorithmic strategy from the list of topicsfor this unit.

ALG3. Fundamental computing algorithms [core]

Minimum core coverage time: 12 hours
Topics: / Coverage in current curricula / Coverage in the new proposed curricula
  1. Simple numerical algorithms
/ ICS 353
  1. Sequential and binary search algorithms
/ ICS 353
  1. Sorting algorithms
/ ICS 353
  1. Hash tables, including collision-avoidance strategies
/ ICS 353
  1. Binary search trees
/ ICS 353
  1. Representations of graphs (adjacency list, adjacency matrix)
/ ICS 353
  1. Depth- and breadth-first traversals
/ ICS 353
  1. Shortest-path algorithms (Dijkstra’s and Floyd’s algorithms)
/ ICS 353
  1. Transitive closure (Floyd’s algorithm)
/ ICS 353
  1. Minimum spanning tree (Prim’s and Kruskal’s algorithms)
/ ICS 353
  1. Topological sort
/ ICS 353
Learning objectives:
  1. Use and implement the fundamental abstract data types—specifically including hash tables, binary search trees, and graphs—necessary to solve algorithmic problems efficiently.

  1. Solve problems using an efficient sorting algorithms, and fundamental graph algorithms, including depth-first and breadth-first search, single-source and all-pairs shortest paths, transitive closure, topological sort, and at least one minimum spanning tree algorithm.

  1. Demonstrate the following abilities: to evaluate algorithms, to select from a range ofpossible options, to provide justification for that selection, and to implement thealgorithm in simple programming contexts.

ALG4. Distributed algorithms [core]
Minimum core coverage time: 3 hours
Topics: / Coverage in current curricula / Coverage in the new proposed curricula
  1. Concurrency
/ ICS 353
  1. Scheduling

  1. Fault tolerance
/ ICS 353
Learning objectives:
  1. Explain the distributed paradigm.

  1. Distinguish between logical and physical clocks.

  1. Describe the relative ordering of events.

  1. Explain one simple distributed algorithm.

ALG5. Basic computability theory [elective]

Minimum elective coverage time: 6 hours
Topics: / Coverage in current curricula / Coverage in the new proposed curricula
  1. Deterministic finite Automata (DFA)
/ ICS 353
  1. Non-deterministic finite Automata (NFA)
/ ICS 353
  1. Simple recursive procedures

  1. Equivalence of DFA’s and NFA’s

  1. Context-free grammars
/ ICS 353
  1. Pushdown automata (PDA)

Learning objectives:
  1. Explain the idea that some problems may have no algorithmic solution.

  1. Provide examples that illustrate the implications of uncomputability.

ALG6. Basic Decidability and complexity [core]

Minimum core coverage time: 9 hours
Topics: / Coverage in current curricula / Coverage in the new proposed curricula
  1. Tractable and intractable problems
/ ICS 353
  1. Definition of the classes P and NP
/ ICS 353
  1. NP-completeness (Cook’s theorem)
/ ICS 353
  1. Standard NP-complete problems
/ ICS 353
  1. Uncomputable functions
/ ICS 353
  1. The halting problem
/ ICS 353
  1. Implications of uncomputability
/ ICS 353
Learning objectives:
  1. Define the classes P and NP.

  1. Explain the significance of NP-completeness.

  1. Prove that a problem is NP-complete by reducing a classic known NP-complete problem to it.