AL – SIGCSE 2022 Version

Algorithmic Foundations (AL)

CS’2013 CS’202X

(Draft)
Core
Tier 1		 Core 

Tier 2

 Required
AL/Fundamental Data Structures and Algorithms 9 3 12 + 2⍏
AL/Algorithmic Strategies 5 1 4 + 0
AL/Complexity Analysis  2 4* 5 + 5
AL/Automata Theory and Computability 3 1* 5 + 5
AL/Algorithms and Society 2 + 0

*As, CS’13 combined computability and complexity, two hours dealing with P, NP, and NP-C are listed under complexity instead of computability.
⍏The first number listed  in the required CS202X lecture hours redistributes the hours from CS’13, while the additional hours (+)  assume a dedicated AL course beyond CS1/CS2  of 2.5 lecture hours per week for sixteen weeks.

AL/Fundamental Data Structures and Algorithms 

This unit builds on the topics provided in the Software Development Fundamentals (SDF) area. It also complements the AL/Algorithmic Strategies unit since the listed algorithms represent examples of the various strategies.

Topics:

[Required]

  •       Abstract Data Types (ADTs): definition, representation, and properties including usage complexity

o   Arrays, Graphs, Hash Tables, Heaps, Linked Lists, Maps, Objects, Queues, Records, Stacks,
Stacks, Strings, and Trees

  •       Algorithms

o   Operations on ADTs: inserting, removing, finding elements and traversals, where appropriate

o   Search: sequential, binary, depth-first, best-first, bread-first

o   Sorting: quadratic, logarithmic, lexical, topological

o   Find shortest path of minimal spanning tree of a graph

o   Tree balancing

o   String matching

o   Map-Reduce

o   Differential Privacy

 

Learning Outcomes:

[Required]

  1.     Arrays and Linked Lists
  2.   Compare and contrast the definitions, properties, representations, and efficiencies of using fixed-length arrays versus linked lists.
  3. Insert elements into and remove elements from sorted and unsorted arrays and linked lists including single and doubly linked lists.
  4. Use sequential search to traverse or find an element in an array or linked list.
  5. Use binary search to find an element in a sorted array.
  6. Sort an unsorted array or linked list using a quadratic sort, such as selection sort.
  7.   Sort an unsorted array using a logarithmic time sort, such as Quicksort, Mergesort
  8.     Graphs
  9. Represent various graphs using adjacency lists and adjacency matrices.
  10. Compare and contrast the definitions, properoteis, representations, and efficiencies of using directed/undirected, connected/unconnected, acyclic/cyclic, and weighted/unweighted graphs.
  11. Use depth- and breadth-first search to find a vertex in a graph including calculating the path cost of reaching the vertex.
  12. Find the shortest path between vertices using an algorithm such as Dijkstra’s or Floyd’s
  13. Find a minimal spanning tree using an algorithm such as Prims or Kruskal’s
  14. Determine whether a graph is connected

g.Topologically short the vertices in a graph

  1.     Hash tables / Map
  2. Explain the properties, implementation, and efficiency of using a hash table/map
  3. Explain how to calculate a hash table key for a simple data type, such as a string.
  4. Explain how linear probing, chaining, and rehashing handle collision resolution.
  5.     Heaps
  6. Explain the properties, implementation, and efficiency of using a heap as a priority queue
  7. Use heapsort to sort an unordered list of elements.
  8.     Objects
  9. Define a class/object with local data and behaviors
  10. Explain how visibility is used to encapsulate local data and behaviors
  11.     Queues
  12. Explain how a queue implements first-in, first-out (FIFO) processing of data
  13. Use a queue to buffer and process simple job requests
  14.     Stacks
  15. Explain how a stack implements last-in, first-out (LIFO) processing of data

b.Use a stack to determine whether parenthesis are balanced in an arithmetic expression.

  1.     Strings
  2. Explain the properties of a string including representation as a fixed-size and null terminated arrays.
  3. Demonstrate brute-force and efficient string matching, such as Boyer-Moore or Knuth-Morris-Pratt.
  4.     Trees
  5. Explain the properties, implementation, and efficiency of using binary and balanced trees
  6. Traverse a tree using depth- or breadth first search using pre-, in-, or post-order node processing
  7. Insert and remove elements from a balanced a tree, such as an AVL, Red-Black,
  8.   Demonstrate the ability to evaluate algorithms, to select from a range of possible options, to provide justification for that selection, and to implement the algorithm in a particular context.
  9.   Discuss factors other than computational efficiency that influence the choice of algorithms, such as programming time, maintainability, and the use of application-specific patterns in the input data.

 

 

AL/Algorithmic Strategies 

As this unit complements the AL/Fundamental Data Structures and Algorithms unit, it’s expected these topics are typically covered during presentation of fundamental algorithm examples. Heuristic and branch-and-bound algorithms might also be presented in the IS/Search Strategies unit.

Topics:

[Required]

o        Backtracking

o        Branch-and-bound

o        Brute-force

o        Decrease-and-conquer

o        Divide-and-conquer

o        Dynamic Programming

o        Greedy algorithms

o        Heuristic

o        Iterative

o        Recursive

o        Reduction: transform-and-conquer

 

Learning Outcomes:

[Required]

  1.     For each of the algorithmic strategies in this unit:
  2.   Explain the characteristic properties of the strategy that can be used to judge whether a specific algorithm is a member of the category]
  3. Identify a practical example to which it would apply and explain why this example lends itself to being solved by the associated strategy.
  4.   Apply an algorithmic instance of the strategy to solve an appropriate problem.
  5.     Give an example of where a greedy algorithm leads to a globally optimal problem solution and an example where a greedy algorithm does not lead to a globally optimal problem solution. [Assessment]
  6.     Describe the role heuristics and branch-and-bound search strategies play in time and space complexity.
  7.     Compare and contrast an iterative and recursive approach to solving a problem, such as binary search.

 

AL/Complexity Analysis 

Topics:

[Required]

o        Best, expected, and worst-case algorithm behavior

o        Asymptotic analysis of upper and expected complexity bounds

o        Big and little O, Omega, and Theta notation

o        Constant, logarithmic, linear, quadratic, cubic, and exponential complexity classes

o        Empirical measurements of performance

o        Time and space trade-offs in algorithms

o        Analysis of iterative and recursive algorithms

o        Strategies to solve recurrence relations (e.g. substitution, Master Theorem)

o        P, NP, and NPC complexity classes including P-NP problem NPC problems (e.g., SAT, Knapsack)

 

Learning Outcomes:

[Required]

  1.     Explain the use of Big-O, Omega, and Theta notation to describe the amount of work done by an algorithm.
  2.     List and contrast standard complexity classes.
  3.     Explain what is meant by “best”, “expected”, and “worst” case behavior of an algorithm
  4.     Determine the time and space complexity of simple algorithms, including those associated with the ADTs in the AL/Fundamental Data Structures and Algorithms knowledge unit
  5.     Explain the difference in complexity between sequential and binary search
  6.     Explain the difference in complexity between quadratic and logarithmic sorting (e.g. Selection vs. Quicksort)
  7.     Perform empirical studies to validate hypotheses about runtime stemming from mathematical analysis.  Run algorithms on input of various sizes and compare performance.
  8.     Give examples that illustrate time-space trade-offs of algorithms.
  9.     Use recurrence relations to determine the time complexity of recursively defined algorithms.
  10.   Solve elementary recurrence relations, e.g., substitution, Master Theorem.
  11.   Define the classes P and NP. (Also appears in AL/Basic Automata, Computability, and Complexity).
  12.   Explain the significance of P, NP, and NP-Completeness.

 

 

 

AL/ Automata and Computability

This knowledge area complements PL Programming Languages

Topics:

[Required]

  •       Formal Languages, Grammars, and Chomsky Hierarchy:

o   Regular, Context-Free, Context-Sensitive, and Recursively Enumerable

o   Regular expressions

  •       Formal Automaton: Finite State, Pushdown, Linear-Bounded, and Turing Machines

o   Deterministic versus Nondeterministic and equivalencies

o   Relation to formal languages and grammars

o   Decidability and limitations

  •       Uncomputability and the halting problem
  •       The Church-Turing Thesis
  •       The P, NP, and NPC complexity (cross-reference AL/Complexity Analysis)

o   Exemplary NP-complete problems (e.g., SAT, Knapsack)

 

Learning Outcomes:

[Required]

  1.     Explain the concept of a formal automaton
  2.     Compare and contrast the definitions, capabilities, and limitations of finite state, pushdown, linear bounded, and Turing Machines
  3.     Design finite state machines, pushdown automata, and Turing Machines that accept a specified language.
  4.     Generate a regular expression to represent a specified language.
  5.     Compare and contrast regular, context-free, context sensitive, and Recursively Enumerable languages and their uses
  6.     Compare and contrast regular, context-free, context sensitive, and Recursively Enumerable languages (e.g. Type-X in the Chomsky Hierarchy) and their uses
  7.     Design regular and context-free grammars to represent a specified language.
  8.     Convert among equivalently powerful notations for a language, including among DFAs, NFAs, and regular expressions, and between PDAs and CFGs.
  9.     Explain why the halting problem has no algorithmic solution.
  10.   Explain the Church-Turing thesis and its significance.
  11.   Define the classes P and NP.
  12.   Explain the significance of NP-completeness.

 

AL/ Algorithms and Society

As the impact of computing on society, both beneficial and harmful, traces to the design of algorithms, this unit reinforces the notion that the use of any algorithm should be considered within the social context in which it is used. This unit complements the topics in the Social Issues, Ethics, and Professional Practice (SEP) knowledge area

Topics:

[Required]

  •       Context-aware computing
  •       Ethical Algorithms

 

Learning Outcomes:

[Required]

  1.     Consider and explain the impact that an algorithm’s design will have on society when used to solve any real-world problems.