Algorithms and Complexity (AL)

   AL1. Basic algorithmic analysis [core]
   AL2. Algorithmic strategies [core]
   AL3. Fundamental computing algorithms [core]
   AL4. Distributed algorithms [core]
   AL5. Basic computability [core]
   AL6. The complexity classes P and NP [elective]
   AL7. Automata theory [elective]
   AL8. Advanced algorithmic analysis [elective]
   AL9. Cryptographic algorithms [elective]
   AL10. Geometric algorithms [elective]
   AL11. Parallel algorithms [elective]

Algorithms are fundamental to computer science and software engineering. The real-world performance of any software system depends on only two things: (1) the algorithms chosen and (2) the suitability and efficiency of the various layers of implementation. Good algorithm design is therefore crucial for the performance of all software systems. Moreover, the study of algorithms provides insight into the intrinsic nature of the problem as well as possible solution techniques independent of programming language, programming paradigm, computer hardware, or any other implementation aspect.

An important part of computing is the ability to select algorithms appropriate to particular purposes and to apply them, recognizing the possibility that no suitable algorithm may exist. This facility relies on understanding the range of algorithms that address an important set of well-defined problems, recognizing their strengths and weaknesses, and their suitability in particular contexts. Efficiency is a pervasive theme throughout this area.

AL1. Basic algorithmic analysis [core]

Minimum core coverage time: 4 hours

Topics:

• Asymptotic analysis of upper and average complexity bounds
• Identifying differences among best, average, and worst case behaviors
• Big O, little o, omega, and theta notation
• Standard complexity classes
• Empirical measurements of performance
• Time and space tradeoffs in algorithms
• Using recurrence relations to analyze recursive algorithms

Learning objectives:

1. Explain the use of big O, omega, and theta notation to describe the amount of work done by an algorithm.
2. Use big O, omega, and theta notation to give asymptotic upper, lower, and tight bounds on time and space complexity of algorithms.
3. Determine the time and space complexity of simple algorithms.
4. Deduce recurrence relations that describe the time complexity of recursively defined algorithms.
5. Solve elementary recurrence relations.

Minimum core coverage time: 6 hours

Topics:

• Brute-force algorithms
• Greedy algorithms
• Divide-and-conquer
• Backtracking
• Branch-and-bound
• Heuristics
• Pattern matching and string/text algorithms
• Numerical approximation algorithms

Learning objectives:

1. Describe the shortcoming of brute-force algorithms.
2. For each of several kinds of algorithm (brute force, greedy, divide-and-conquer, backtracking, branch-and-bound, and heuristic), identify an example of everyday human behavior that exemplifies the basic concept.
3. Implement a greedy algorithm to solve an appropriate problem.
4. Implement a divide-and-conquer algorithm to solve an appropriate problem.
5. Use backtracking to solve a problem such as navigating a maze.
6. Describe various heuristic problem-solving methods.
7. Use pattern matching to analyze substrings.
8. Use numerical approximation to solve mathematical problems, such as finding the roots of a polynomial.

Minimum core coverage time: 12 hours

Topics:

• Simple numerical algorithms
• Sequential and binary search algorithms
• Quadratic sorting algorithms (selection, insertion)
• O(N log N) sorting algorithms (Quicksort, heapsort, mergesort)
• Hash tables, including collision-avoidance strategies
• Binary search trees
• Representations of graphs (adjacency list, adjacency matrix)
• Depth- and breadth-first traversals
• Shortest-path algorithms (Dijkstra's and Floyd's algorithms)
• Transitive closure (Floyd's algorithm)
• Minimum spanning tree (Prim's and Kruskal's algorithms)
• Topological sort

Learning objectives:

1. Implement the most common quadratic and O(NlogN) sorting algorithms.
2. Design and implement an appropriate hashing function for an application.
3. Design and implement a collision-resolution algorithm for a hash table.
4. Discuss the computational efficiency of the principal algorithms for sorting, searching, and hashing.
5. 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.
6. Solve problems using the 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.
7. Demonstrate the following capabilities: to evaluate algorithms, to select from a range of possible options, to provide justification for that selection, and to implement the algorithm in programming context.

Minimum core coverage time: 3 hours

Topics:

• Consensus and election
• Termination detection
• Fault tolerance
• Stabilization

Learning objectives:

1. Explain the distributed paradigm.
2. Explain one simple distributed algorithm.
3. Determine when to use consensus or election algorithms.
4. Distinguish between logical and physical clocks.
5. Describe the relative ordering of events in a distributed algorithm.

Minimum core coverage time: 6 hours

Topics:

• Finite-state machines
• Context-free grammars
• Tractable and intractable problems
• Uncomputable functions
• The halting problem
• Implications of uncomputability

Learning objectives:

1. Discuss the concept of finite state machines.
2. Explain context-free grammars.
3. Design a deterministic finite-state machine to accept a specified language.
4. Explain how some problems have no algorithmic solution.
5. Provide examples that illustrate the concept of uncomputability.

Topics:

• Definition of the classes P and NP
• NP-completeness (Cook's theorem)
• Standard NP-complete problems
• Reduction techniques

Learning objectives:

1. Define the classes P and NP.
2. Explain the significance of NP-completeness.
3. Prove that a problem is NP-complete by reducing a classic known NP-complete problem to it.

Topics:

• Deterministic finite automata (DFAs)
• Nondeterministic finite automata (NFAs)
• Equivalence of DFAs and NFAs
• Regular expressions
• The pumping lemma for regular expressions
• Push-down automata (PDAs)
• Relationship of PDAs and context-free grammars
• Properties of context-free grammars
• Turing machines
• Nondeterministic Turing machines
• Sets and languages
• Chomsky hierarchy
• The Church-Turing thesis

Learning objectives:

1. Determine a language's location in the Chomsky hierarchy (regular sets, context-free, context-sensitive, and recursively enumerable languages).
2. Prove that a language is in a specified class and that it is not in the next lower class.
3. Convert among equivalently powerful notations for a language, including among DFAs, NFAs, and regular expressions, and between PDAs and CFGs.
4. Explain at least one algorithm for both top-down and bottom-up parsing.
5. Explain the Church-Turing thesis and its significance.

Topics:

• Amortized analysis
• Online and offline algorithms
• Randomized algorithms
• Dynamic programming
• Combinatorial optimization

Learning objectives:

1. Use the potential method to provide an amortized analysis of previously unseen data structure, given the potential function.
2. Explain why competitive analysis is an appropriate measure for online algorithms.
3. Explain the use of randomization in the design of an algorithm for a problem where a deterministic algorithm is unknown or much more difficult.
4. Design and implement a dynamic programming solution to a problem.

Topics:

• Historical overview of cryptography
• Private-key cryptography and the key-exchange problem
• Public-key cryptography
• Digital signatures
• Security protocols
• Applications (zero-knowledge proofs, authentication, and so on)

Learning objectives:

1. Describe efficient basic number-theoretic algorithms, including greatest common divisor, multiplicative inverse mod n, and raising to powers mod n.
2. Describe at least one public-key cryptosystem, including a necessary complexity-theoretic assumption for its security.
3. Create simple extensions of cryptographic protocols, using known protocols and cryptographic primitives.

Topics:

• Line segments: properties, intersections
• Convex hull finding algorithms

Learning objectives:

1. Describe and give time analysis of at least two algorithms for finding a convex hull.
2. Justify the Omega(N log N) lower bound on finding the convex hull.
3. Describe at least one additional efficient computational geometry algorithm, such as finding the closest pair of points, convex layers, or maximal layers.

Topics:

• PRAM model
• Exclusive versus concurrent reads and writes
• Pointer jumping
• Brent's theorem and work efficiency

Learning objectives:

1. Describe implementation of linked lists on a PRAM.
2. Use parallel-prefix operation to perform simple computations efficiently in parallel.
3. Explain Brent's theorem and its relevance.

CC2001 Report December 15, 2001