CS/ECE 374 Sec A: 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
• Greedy algorithms
  • Ability to design simple greedy algorithms and to provide simple counter examples
  • Ability to prove correctness via exchange property and induction
• Minimum Spanning Trees
  • Cut and cycle properties, safe and unsafe edges and characterization of MST when edge lengths are distinct
  • Standard algorithms for MST: Kruskal, Prim, Borouvka. Run times and high-level implementation ideas

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
  • Ability to save space in iterative algorithms derived via dynamic programming
• 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.
  • 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 in particular for finding hop-constrained paths.
  • Negative length edges and Bellman-Ford algorithm to check for negative length cycles or find shortest paths if there is none.
• 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

• Strings, languages, and understanding basic operations on languages (union, intersection, complement, concatenation, Kleene star)
• Ability to do induction proofs
• Regular languages via recursive/inductive definition
  • base cases, closure under finite union and concatenation
• Regular expressions
  • ability to generate a regular expression for a given language decription
  • ability to understand regular expressions and explain the language in English or other formal ways
• Deterministic Finite Automata (DFAs)
  • formal definition via graphical notation and tuple notation
  • understand δ and δ*
  • meaning of the language accepted by a DFA
  • ability to design DFAs for a given language
  • ability to understand a given DFA and the language it accepts
  • product construction of two or more DFAs
  • prove following closure properties for languages accepted by DFA: complement, intersection, union, and set difference via product construction
• Non-deterministic Finite Automata
  • formal definition via graphical notation and tuple notation
  • understand δ, δ*, ε-closure
  • understand meaning of the language accepted by a NFA
  • understand how to check whether a given string is accepted by a given NFA
  • ability to design NFAs for a given language
  • ability to understand the language accepted by a NFA
  • closure properties captured by NFA: union, concatenation, Kleene star
  • Thompson construction to create an NFA from a regular expression
  • Subset construction to converτ an NFA into an equivalent DFA
    Incremental subset construction to generate only the useful states
• Closure properties of regular languages
  • via definition of regular languages (union, intersection, Kleene *) or NFAs
  • via DFAs (complement, intersection, union, set difference etc)
  • via more avanced constructions using reg exps, DFAs, NFAs and their combination
    (examples: PREFIX, SUFFIX, CYCLE insert1, delete1, etc that are in labs, home works)
• Non-regularity
  • Meaning of non-regularity and existence of simple non-regular languages
  • Distinguishable pair of strings with respect to a language
  • Definition of a fooling set
  • Understand why a fooling set provides a lower bound on the number of states in a DFA for a given language
  • Proving that a given language is non-regular via infinite fooling sets or other methods
  • Using basic closure properties to prove non-regularity
• Context free languages and grammars
  • formal definition of a context free grammar
  • formal definition of the derivation of a string in a grammar, and the language defined by a cfg
  • ability to design a context free grammar for a given language and explain it
  • ability to understand the language of a given simple context free grammar
  • basic closure properties of cfls (union, concatenation, Kleena star) and ability to prove these via grammars