Computer Science

Define context-free grammars (CFGs) and construct derivations for strings in a language.

Design a CFG for a given context-free language.

Construct a parse tree for a given string and define grammatical ambiguity.

Define pushdown automata (PDA) and trace the computation of an input string.

Demonstrate the equivalence of CFGs and PDAs by constructing a PDA from a given CFG.

Apply the pumping lemma for context-free languages to prove a language is not context-free.

Explain the role of CFGs in defining the syntax of programming languages and in parsing.

Describe the Chomsky Hierarchy and situate regular and context-free languages within it.

Define a Turing machine formally and trace its computation on a given input.

Design a Turing machine to decide a given language (e.g., {0^n 1^n 2^n}).

Distinguish between a Turing machine that decides a language and one that recognizes it.

Describe variants of Turing machines (e.g., multi-tape, nondeterministic) and explain their equivalence to the standard model.

State the Church-Turing thesis and explain its philosophical significance for the definition of 'computation'.

Explain how the Turing machine model provides the theoretical foundation for modern general-purpose computers.

Define decidable and recognizable languages and provide examples of each.

Prove that the halting problem (A_TM) is undecidable using a proof by diagonalization.

Define mapping reducibility as a tool for proving undecidability.

Use mapping reductions from the halting problem to prove other problems are undecidable (e.g., HALT_ε).

Apply Rice's theorem to prove the undecidability of non-trivial properties of recognizable languages.

Explain the real-world implications of undecidability, such as the impossibility of a perfect virus detector or universal bug finder.

Define graphs, vertices, and edges, and describe their representation using adjacency lists and matrices.

Express the running time of an algorithm using Big-O, Big-Omega, and Big-Theta notation.

Analyze the time and space complexity of iterative algorithms by counting primitive operations.

Formulate recurrence relations to describe the complexity of recursive algorithms.

Apply the Master Theorem to solve common divide-and-conquer recurrence relations.

Distinguish between best-case, worst-case, and average-case complexity analysis.

Prove the correctness of an algorithm using loop invariants.

Design and analyze a divide-and-conquer algorithm for a canonical problem (e.g., merge sort).

Design a greedy algorithm and prove its correctness using a greedy-choice property and optimal substructure argument (e.g., activity selection).

Identify problems that exhibit optimal substructure and overlapping subproblems, indicating suitability for dynamic programming.

Formulate a recurrence relation to solve a dynamic programming problem (e.g., longest common subsequence).

Implement a dynamic programming solution using memoization (top-down).

Implement a dynamic programming solution using tabulation (bottom-up).

Compare and contrast the applicability of divide-and-conquer, greedy, and dynamic programming strategies.

Describe where these strategies appear in real-world software (e.g., route planning, sequence alignment).

Describe and analyze the Breadth-First Search (BFS) algorithm and its application in finding shortest paths in unweighted graphs.

Describe and analyze the Depth-First Search (DFS) algorithm and its applications, such as cycle detection and topological sorting.

Analyze the time and space complexity of BFS and DFS for both adjacency list and matrix representations.

Apply Dijkstra's algorithm to find the shortest paths from a single source in a weighted graph with non-negative edge weights.

Analyze the runtime of Dijkstra's algorithm using different priority queue implementations (array, binary heap).

Apply a minimum spanning tree algorithm (e.g., Kruskal's or Prim's) to find a minimum-weight set of connecting edges.

Prove the correctness of an MST algorithm using the cut property.

Define the complexity classes P and NP using deterministic and non-deterministic Turing machines.

Explain the P versus NP problem and its significance as a major open problem in computer science and mathematics.

Define polynomial-time reduction and the concepts of NP-hardness and NP-completeness.

State the Cook-Levin theorem and explain its importance in establishing the existence of NP-complete problems.

Explain the logic of using polynomial-time reductions to prove that a problem is NP-complete.

Construct a polynomial-time reduction from a known NP-complete problem (e.g., 3-SAT) to another problem (e.g., Vertex Cover).

Prove the correctness of the reduction from 3-SAT to Vertex Cover.

Describe the practical consequences of a problem being NP-hard for fields like logistics, cryptography, and bioinformatics.

Define the self-information of an event and the Shannon entropy of a discrete random variable.

Explain the intuitive meaning of entropy in terms of uncertainty, surprise, and average information content.

State Shannon's source coding theorem and explain how entropy defines the fundamental limit of lossless data compression.

Construct a prefix-free code using Huffman's algorithm for a given probability distribution.

Prove the optimality of the Huffman coding algorithm for constructing minimum-redundancy codes.

Calculate the average length of a code and compare it to the source's entropy.

Explain the difference between lossless and lossy compression, with examples like PNG vs. JPEG.

Describe the high-level strategy of dictionary-based compression, such as Lempel-Ziv (used in ZIP, GIF).

Define a discrete memoryless channel (e.g., Binary Symmetric Channel) and the concept of channel capacity.

State Shannon's noisy-channel coding theorem and explain its profound implication: that reliable communication is possible over noisy channels.

Define code rate and redundancy, and analyze these for a simple repetition code.

Explain the concepts of Hamming distance and its relation to error detection and correction capabilities.

Construct a Hamming code (e.g., Hamming(7,4)) and demonstrate its mechanism for detecting and correcting single-bit errors.

Explain the trade-off between the rate of a code and its error-correction capability.

Describe how error-correcting codes enable reliable communication in modern systems like Wi-Fi, cellular networks, and deep-space probes.

Describe the concept of randomized computation and define the complexity class BPP (Bounded-error Probabilistic Polynomial time).

Define the complexity class PSPACE and describe its relationship to P and NP.

Explain the basic idea behind interactive proof systems and the class IP.

Discuss the known relationships between major complexity classes, such as P ⊆ NP ⊆ PSPACE = IP.

Identify major open problems in complexity theory beyond P vs NP (e.g., NP vs co-NP, P vs BPP) and explain their significance.