CS/ECE 374: Final Skillset

The final exam is cumulative and will test material covered in the entire course. However, a few topics will be omitted and they are highlighted below (basically we omit some advanced topics on regular languages, and context free languages/grammars).

Post Midterm 2 Skillset

• Turing Machines and Complexity Classes
  • Definition of a TM at a high-level and equivalence with programs. We will not ask you to design TMs for any concrete problem.
  • Definition of decidable/recursive and recursively enumerable.
  • Definition of P via TMs
  • Knowledge of Universal TM and what it enables you to do - simulate a given TM on a given input.
• Undecidability
  • Knowledge that the universal language and halting are undecidable.
  • Ability to prove that problems on program behaviour are undecidable via reductions from L_u and HALT.
• NP, NP-Completeness and Polynomial-time Reductions
  • Definitions of NP, NP-Complete, NP-Hard
  • Knowledge of standard NP-Complete problems: SAT, 3SAT, CircuitSAT, Independent Set, Clique, Vertex Cover, Hamiltonian Cycle/Path in directed/undirected graphs, 3Color, Color.
  • Ability to prove that a given problem is in NP
  • Ability to prove that a given problem is NP-Hard via a polynomial time reduction from an existing NP-Hard problem from the given list.
  • Understand the definition of a polynomial-time reduction and its implications.
  • Ability to prove correctness of reductions
  • Understand basic boolean logic and properties of SAT/CircuitSAT formulas to enable reductions

Midterm 2 Skillset

• Divide and Conquer Paradigm
  • Solving recurrences characterizing the running time of divide and conquer algorithms.
  • Familiarity with specific Divide and Conquer Algorithms and the running times: Binary Search, Merge Sort, Quick Sort, Karatsuba's Algorithm, Linear Selection.
  • Ability to design and analyze divide and conquer algorithms for new problems.
• Backtracking and Dynamic Programming Algorithms
  • Using the dynamic programming methodology to design algorithms for new problems.
  • Ability to analyze the running time of dynamic programming algorithms.
• Graphs
  • Basic definitions of undirected and directed graphs, DAGs, paths, cycles.
  • Definitions of reachable nodes, connected components, and strongly connected components.
  • Understand the structure of directed graphs in terms of the meta-graph of strongly connected components.
  • Understand the structure of DAGs: sources, sinks and topological sort.
• Graph Search
  • Understand properties of the basic search algorithm and its running time.
  • Understand properties of depth first search traversal on directed and undirected graph.
  • Understand properties of the depth first search tree.
  • Understand properties of depth first search traversal on directed and undirected graph.
  • Algorithms based on search for finding connected components in undirected graphs, checking whether a graph is a DAG, topological sort for DAGs, knowledge of a linear-time algorithm to create the meta-graph, finding a cycle in a graph etc.
• Shortest Paths in Graphs
  • Understand properties of the breadth first search tree.
  • Understand properties of breadth first search traversal on directed and undirected graph to find distances in unweighted graphs.
  • Dijkstra's algorithm for finding single-source shortest paths in undirected and directed graphs with non-negative edge lengths.
  • Negative length edges and Bellman-Ford algorithm to check for negative length cycles or find shortest paths if there is none.
  • Single-source shortest paths in DAGs—linear time algorithm for arbitrary edge lengths.
  • Shortest path trees and their basic properties.
  • Dynamic programming for shortest path problems in graphs.
• Graph reductions and tricks
  • Modeling problems via graphs and solving them using graph structure, reachability and shortest path algorithms.
  • Adding sources, sinks, splitting edges, nodes
  • Creating layered graphs

Midterm 1 Skillset

• Basic mathematics
  • Comfort with set notation, especially set operations like cross product and power set. Should know how to read and understand formally described sets, and should be able to describe new sets precisely.
  • Familiarity with alphabets, strings, and languages.
  • Ability to critically evaluate proofs and write proofs, especially induction proofs.
  • Ability to comprehend inductive definitions.
• Formal models of computation (regular expressions, DFAs, NFAs)
  • Understand formal definitions of machines, and expressions. Be able to execute machines on simple examples, and infer if strings belong to sets defined by expressions/grammars. Understand what it means for a language to be described/accepted by a computational model.
  • Ability to design machines/expressions to describe/accept languages. Ability to formally describe them.
• Transformations between computational models
  • Familiarity with proofs transforming NFAs to DFAs, and regular expressions to NFAs. Ability to carry out these constructions on examples.
  • Familiarity with the cross product construction to run multiple machines simultaneously.
  • Know asymptotic bounds of the resulting automata constructed by these transformations.
  • Ability to perform new transformations on automata to prove regularity or construct automata/expressions with special properties.
• Closure properties
  • Know standard closure properties (concatenation, union, intersection, complementation, set difference, Kleene star, reverse) for regular languages. Understand the proofs for these properties.
  • Know how to prove new closure properties either through automata tranformations or using previously established closure properties.
• Non-regularity
  • Ability to distinguish regular and non-regular languages
  • Ability to prove languages to be non regular using the fooling set argument. Know how to prove lower bounds on the number of DFA states using the fooling set argument as well.