Showing 0–0 of 0 results
# Exercise Title Features Description Platform Keywords
1 Programmed Instruction: Induction Proof For Factorial Programmed Instruction Programmed Instruction Frameset examples of induction proof proving a Factorial function implementation correct. OpenDSA Proof by Induction
2 Programmed Instruction: Induction Proof Examples Programmed Instruction Programmed Instruction Frameset examples of induction proofs. OpenDSA Proof by Induction
3 Programmed Instruction: Induction Proof For Two Coloring Programmed Instruction Programmed Instruction Frameset examples of induction proof for two-coloring the 2D plane. OpenDSA Proof by Induction
4 Programmed Instruction: Proof Techniques Introduction Programmed Instruction Programmed Instruction Frameset presentation of basic proofs review, including proof by contradiction review. OpenDSA Proof
5 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
6 Pumping Lemma Example: wwR Programmed Instruction, Proof Visualization Programmed Instruction slideshow showing the pumping lemma proof that the language consisting of a string w followed by the reverse... OpenDSA Non-Regular Language
7 Proof not all CFL are Deterministic Programmed Instruction Programmed Instruction Frameset with a proof that there exists a CFL that is not a deterministic CFL. OpenDSA Pushdown Automata
8 Heap Build Proof Slideshow Code Tracing Presentation, Algorithm Visualization Slideshow visualizing the cost of the efficient heap buiding algorithm, showing that it is a linear-time algorithm. OpenDSA Heap
9 Pumping Lemma Example: Harder Proof Programmed Instruction, Proof Visualization Programmed Instruction slideshow showing the harder pumping lemma proof where there are multiple cases to consider. OpenDSA Non-Regular Language
10 Geometric Summation Proof Presentation Slideshow showing how to calculate the closed form for the geometric series. OpenDSA Summation
11 Using Posets for a Lower Bounds Proof Presentation Slideshow showing the use of posets in a proof of the lower bound for search in an unsorted list. OpenDSA Poset, Search in Unsorted Lists
12 Programmed Instruction: Induction Proofs Programmed Instruction Programmed Instruction Frameset review of induction proofs. OpenDSA Induction Proof
13 Heapsort Analysis Slideshow Algorithm Visualization Slideshow showing a visual proof for the cost of Heapsort. OpenDSA Heapsort
14 Quicksort Average Case Analysis Slideshow Algorithm Visualization Slideshow showing a visual proof for the average-case cost of Quicksort. OpenDSA Quicksort
15 Quicksort Best Case Analysis Slideshow Algorithm Visualization Slideshow showing a visual proof for the best-case cost of Quicksort. OpenDSA Quicksort
16 Quicksort Partition Analysis Slideshow Algorithm Visualization Slideshow showing a visual proof for the cost of the partition step for Quicksort. OpenDSA Quicksort
17 Quicksort Worst Case Analysis Slideshow Algorithm Visualization Slideshow showing a visual proof for the worst-case cost of Quicksort. OpenDSA Quicksort
18 Sorting Lower Bound Analysis Slideshow Algorithm Visualization Slideshow showing a visual proof for the lower bound of the general sorting problem. OpenDSA Sorting Problem Lower Bound
19 Pumping Lemma Example: a^n b^n Programmed Instruction, Proof Visualization Programmed Instruction slideshow showing the pumping lemma proof that the language a^n b^n is not regular. OpenDSA Non-Regular Language
20 Pumping Lemma Slideshow Proof Visualization Simple demonstration of a Pumping Lemma proof to show that a language is not regular. OpenDSA Pumping Lemma, Non-Regular Language
21 Sorting Lower Bound Summary Questions Question, Battery Battery of self-assessment questions related to the lower bounds proof for the general sorting problem. OpenDSA Sorting Problem Lower Bound
22 Regular Expressions Equivalent to NFA: Part 1 Programmed Instruction Programmed Instruction Frameset presenting Part 1 of 4 parts of a proof of equivalence of Regular Expressions and NFAs. OpenDSA Regular Expression, Non-Deterministic Finite Automata
23 Regular Expressions Equivalent to NFA: Part 3: Concatenate Programmed Instruction Programmed Instruction Frameset presenting Part 3 of 4 parts of a proof of equivalence of Regular Expressions and NFAs. Concatenating... OpenDSA Regular Expression, Non-Deterministic Finite Automata
24 Regular Expressions Equivalent to NFA: Part 2: Or Programmed Instruction Programmed Instruction Frameset presenting Part 2 of 4 parts of a proof of equivalence of Regular Expressions and NFAs. Or'ing... OpenDSA Regular Expression, Non-Deterministic Finite Automata
25 Regular Expressions Equivalent to NFA: Part 4: Star Programmed Instruction Programmed Instruction Frameset presenting Part 4 of 4 parts of a proof of equivalence of Regular Expressions and NFAs. Kleene... OpenDSA Regular Expression, Non-Deterministic Finite Automata
26 Closure Properties for Regular Languages: Right Quotient Programmed Instruction Programmed Instruction Frameset presenting the concept of right quotient, and a proof that this operator is closed for regular languages. OpenDSA Regular Language, Closure Property
27 Closure Properties for Regular Languages: Homomorphism Programmed Instruction Programmed Instruction Frameset presenting the concept of homomorphism, and a proof that this operator is closed for regular languages. OpenDSA Regular Language, Closure Property
28 Turing Machine Extensions Frameset Presentation Slideshow presenting various potential extensions to Turing machines, such as two-dimensional tapes, multiple heads, and non-determinism. Includes proofs that these... OpenDSA Turing Machine