ECE 374

Changes depending on instructor.

CS/ECE 374 covers fundamental tools and techniques from theoretical computer science, including design and analysis of algorithms, formal languages and automata, computability, and complexity.

Specific topics include regular and context-free languages, finite-state automata, recursive algorithms (including divide and conquer, backtracking, dynamic programming, and greedy algorithms), fundamental graph algorithms (including depth- and breadth-first search, topological sorting, minimum spanning trees, and shortest paths), undecidability, and NP-completeness. The course also has a strong focus on clear technical communication.

A detailed outline can be found here: https://ecealgo.com/lectures.html

N/A

N/A

N/A

N/A

N/A

CS 173 (discrete mathematics, especially induction) and CS 225 (basic algorithms and data structures)

No required textbooks.

Required

This course aims to leave students with a understanding of the three major computer science topics covered in this course:

1. computational complexity - we want students to understand the four main complexity categories of languages (regular/context-free/context-sensitive/recursively-enumerable) and understand the automata theory associated with each of the language complexity classes.
2. basic algorithmic techniques - we want students to understand basics of recursive/dynamic-programming and graphing algorithms.
3. reductions - students should be able to use simple reductions to prove if a problem is (un)decidable and/or in P/NP/NP-hard.

Different from courses which either cover algorithms or computational complexity separately, this course focuses on building the theoretical underpinnings of computation by discussing automata theory, then discussing how to make computation more efficient by discussing basic algorithms and finally ending on how to use reductions to argue the difficulty of problems in relation to known historical problems.

After completing the course, students should:

• Understand how to formalize computation problems as languages (1,3)
• Be able to describe regular langauges. Specifically they need to understand what makes a language regular (Kleene's theorem) and construct a corresponding regular expression that describes that language and explain why this regular expression is correct (1,3,6,7)
• Formulate simple automata and describe regular languages as deterministic finite automata. This is especially try in language transformations where students will need to describe a process that changes any arbitrary regular language to a newly defined regular language. (1,6,7)
• Need to have a conceptual understanding of non-determinism and how it relates to computational complexity and automata theory. Students need to understand that in some cases, non-determinism makes a machine better able to understand a larger variety of problems while in other cases it does not.(1,6,7)
• Need to be able to formulate and describe standard recursive algorithms. This course emphasizes binary search types problems but the principles are applicable to a number of well-known recursive problems (e.g Towers of Hanoi) in homework. (1,2,3,6)
• Need to be able to formulate and describe divide and conquer type problems. This course places a unique emphasis on the deterministic time selection problem. (2,3,6)
• Formulate and describe dynamic programming problems. In particular we emphasize constructing the recurrence, describing the computation direction before finally do a running time analysis. The emphasis on describing dynamic programming according to recurrences is unique to this course. (1,2,3,6,7)
• Use graphing algorithms to solve problems. In particular, we discuss how to construct problems as graphs that can be solved using known graphing algorithms. (2,3,6)
• Understand how to combine algorithmic principles through our discussion of Bellman-Ford and Floyd-Warshall algorithms (which combine dynamic programming and graphing problems) (2,3,6,7)
• Understanding the difference between depth-first and breadth-first search, when one is more preferable than the other, how to formulate and switch between the two, and how to apply each to various problems. (2,6)
• How to use reductions to describe the algorithmic complexity of various problems. In particular, we emphasize gadget-type reductions and reductions to/from SAT. (1,2,7)
• How to use reductions to determine if a problem is decidable. This section to more to familiarize students with reduction proofs. (1,2,7)