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 crossed out below (basically we omit some advanced topics on regular languages, as well as context free grammars and greedy algorithms).

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, 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 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
  • Proof that MST is unique when edge lengths are distinct.
  • Cut property: smallest edge with one endpoint in S must be in the MST.
  • 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, 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.
  • Dynamic programming for problems in DAGs, such as longest / shortest path.
• 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 using dynamic programming.
  • Shortest path trees and their basic properties.
  • Dynamic programming for shortest path problems in graphs in particular for finding paths with a limit on the total number of edges.
  • Bellman-Ford algorithm to check for negative length cycles, and find shortest paths if there are 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