Showing 0–0 of 0 results
# Exercise Title Features Description Platform Keywords
1 Symmetric Matrix Multiplication Reduction Presentation Slideshow showing a reduction of Matrix Multiply to Symmetric Matrix Multiply. This demonstrates that the lower bound for Symmetric Matrix... OpenDSA Reduction
2 Reduction of Pairing to Sorting Presentation Slideshow showing a reduction of Pairing to Sorting. This demonstrates that the upper bound for Pairing is the same as... OpenDSA Reduction
3 Reduction of Sorting to Pairing Presentation Slideshow showing a reduction of Sorting to Pairing. This demonstrates that the lower bound for Pairing is the same as... OpenDSA Reduction
4 Reduction of Circuit SAT to SAT Slideshow Presentation Slideshow demonstrating a reduction from an instance of the Circuit Satisfiability problem to an instance of the CNF Satisfiability problem. OpenDSA Reduction, Satisfiability Problem
5 Reduction of Clique to Independent Set Slideshow Presentation Slideshow demonstrating a reduction from an instance of the Clique problem to an instance of the Independent Set problem. OpenDSA Reduction, Clique Problem, Independent Set Problem
6 Reduction of Hamiltonian Cycle to Traveling Salesman Slideshow Presentation Slideshow demonstrating a reduction from an instance of the Hamiltonian Cycle problem to an instance of the Traveling Salesman problem. OpenDSA Reduction, Clique Problem, Independent Set Problem
7 Reduction of Independent Set to Vertex Cover Slideshow Presentation Slideshow demonstrating a reduction from an instance of the Independent Set problem to an instance of the Vertex Cover problem. OpenDSA Reduction, Independent Set Problem, Vertex Cover Problem
8 Reduction of 3-SAT to Clique Slideshow Presentation Slideshow demonstrating a reduction from an instance of the 3-Satisfiability problem to an instance of the Clique problem. OpenDSA Reduction, Satisfiability Problem, Clique Problem
9 Reduction of 3-SAT to Hamiltonian Cycle Slideshow Presentation Slideshow demonstrating a reduction from an instance of the 3-Satisfiability problem to an instance of the Hamiltonian Cycle problem. OpenDSA Reduction, Satisfiability Problem, Hamiltonian Cycle Problem
10 Reduction of True and False using Church Bools Algorithm Visualization Slideshow visualizing reduction of true and false using Church bools. OpenDSA Lambda Calculus
11 Applicative-order reduction Proficiency Exercise Tracing Exercise Algorithm Proficiency Exercise for determining applicative-order reduction in Lambda Calculus expressions. OpenDSA Lambda Calculus
12 Practicing Lambda Calculus Reduction Tracing Exercise Algorithm Proficiency Exercise for determining reduction orders in Lambda Calculus expressions. OpenDSA Lambda Calculus
13 Normal-order reduction Proficiency Exercise Tracing Exercise Algorithm Proficiency Exercise for determining normal-order reduction in Lambda Calculus expressions. OpenDSA Lambda Calculus
14 Lambda Calculus: Performing Beta Reductions Question, Battery A collection of self-practice questions related to performing Beta-reduction in the Lambda Calculus. OpenDSA Lambda Calculus
15 Lambda Calculus: Beta Reduction Order 1 Question, Battery A collection of self-practice questions related to Beta reduction order in the Lambda Calculus. OpenDSA Lambda Calculus
16 Lambda Calculus: Beta Reduction Order 2 Question, Battery A second collection of self-practice questions related to Beta reduction order in the Lambda Calculus. OpenDSA Lambda Calculus
17 Problem Notation Slideshow Presentation Slideshow showing the basic notation for defining a problem, with the example being sorting. OpenDSA Reduction
18 Church Numerals 2 Algorithm Visualization Slideshow illustrating reduction for Church numerals: Multiplication. OpenDSA Lambda Calculus
19 Church Numerals Algorithm Visualization Slideshow illustrating reduction for Church numerals. OpenDSA Lambda Calculus
20 Proof that 3-SAT is NP-Complete Slideshow Proof Visualization Slideshow demonstrating that 3-Satisfiability is NP-Complete by a reduction from Satisfiability. OpenDSA Clique Problem
21 Faster Computer or Faster Algorithm Exercise Question, Battery Battery of self-assessment questions on the distinction between speeding a computer processor vs. reducing computational complexity of an algorithm OpenDSA Problem, Algorithm, Program