Algorithms and Complexity

Algorithms and Complexity (AL) (12%) For Computer Science Students


   AL1. Basic algorithmic analysis [core]
   AL2. Algorithmic strategies [core]
   AL3. Fundamental computing algorithms [core]
   AL4. Automata theory [elective]
   

Recommended Books:

1.    Design and Analysis of Algorithms By Jefry D. Smith

2.    Introduction to Automata and Language Theory by John E.
Hopcroft, Rajeev Motwani and Jeffrey D. Ullman

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 [3%] [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.

AL2. Algorithmic strategies [2%] [core]

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.

AL3. Fundamental computing algorithms [4%] [core]

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.

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. 

AL4. Automata theory [3%] [elective]

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.