Questions tagged [proof-techniques]

Questions about general methods and techniques for proving multiple theorems. When asking about the proof of a single statement, use tags relating to what the proof is about instead.

66 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
0
votes
0answers
592 views

Expectation for the number of comparisons in a randomized Quicksort

I found this link: http://theory.stanford.edu/~tim/w11/l/qsort.pdf and it kind of theoretically describes how to approach finding expectation for the number of comparisons in a Quicksort. Using ...
0
votes
0answers
500 views

Proving a greedy algorithm

Hey so I'm studying for a midterm and I've run into this problem in the material. I'm not sure how to go about solving it. If I use regular induction in part a, I get something a bit tautological. Any ...
0
votes
0answers
69 views

Does a given Turing machine works in time limited by $5n$?

There doesn't exist an algorithm which decides on the following problem: Does a given Turing machine work in time limited by $5n$? $n$ is the length of $w$. $w$ is an input word. The answer is: No, ...
0
votes
0answers
77 views

How to prove that a stack is equivalent to a queue with reversed inputs

Say I push the values 1,2,3,4 onto a stack. Then popping them, they will come back in the order 4,3,2,1. If I push the values 1,2,3,4 onto a queue then removing from a queue results in 1,2,3,4. ...
0
votes
0answers
232 views

Writing a constructive proof for closure of a regular language under homomorphism

I've spend the last few days searching online for an example of a constructive proof of regular languages being closed under homomorphism, but I have not seen one. I am mostly unsure of how to show ...
0
votes
0answers
76 views

Boys And Girls Problem. How to prove that the algorithm is correct?

Given that, there are 10 children standing in a circle, 8 of them stand next to a boy, and 4 of them stand next to a girl. If 7 boys and 3 girls stand in the following order: GBGBGBBBBB, then 8 ...
0
votes
0answers
37 views

Proof of RAP-derivation sequence for a set of functional dependencies in relational databases

I'm reading David Maier's outstanding but out-of-print book on relational databases (the book,"The Theory of Relational Databases", is available online from the author's website http://web.cecs.pdx....
0
votes
0answers
41 views

How would one prove that the following scheme definition is an ordered stream of integers

How would one prove that the following scheme definition is an ordered stream of integers (define integers (cons-stream 1 (add-streams ones integers)))
0
votes
0answers
120 views

How not to prove that P ≠ NP implies NP ≠ PSPACE

Let's define the two variants of the Travelling salesman problem: $TSP_{opt}$ : Give me the shortest tour $TSP_{dec}$ : Is there a tour of $l$ or shorter (Yes/No) Now assume $P \neq NP$: Since $...
0
votes
0answers
76 views

Why if $G$ has two spanning trees $A$ and $A'$, then every edge of $A'\cup \{e_i\}\in A'$

Theorem: Let be $G$ a weighted graph in which every edge has a different weight. Suppose that $G$ has two spanning trees $A$ and $A'$. Let be $i$ the first index such that $e_i\ne e'_i$ ...
0
votes
0answers
317 views

Proving a dynamic programming recurrence for coin exchange correct

Suppose I have $n$ kinds of coins $c_1, c_2, \dots, c_n$. I'm given: $S$, an amount of money I should construct with minimum number of coins. I came into the following formula: $$ T(n,S) = \begin{...
0
votes
0answers
77 views

Is $AM = AM[2]$?

Any $k$ round AM can be reduced just two rounds whereby Arthus just does the $k$ coin tosses and passes on the information to Merlin. Merlin sees all the coin toss results and computes everything ...
0
votes
0answers
170 views

Union, Intersection, Difference, etc. of different types of languages

I am preparing for a competitive exam (GATE) in which questions are asked in Automata about operations among different types of languages. For example, If $L_1$ is recursive & $L_2$ is ...
0
votes
0answers
304 views

Proof by induction for a splay tree?

I'm preparing for an exam about Trees. One of the questions that appear in Mark Allen Weiss' "Data Structures and Algorithms Analysis in C++" is: Prove by induction that if all nodes in a splay ...
0
votes
0answers
188 views

Prove a bisimulation relation

I need to prove a bisimulation relation on $CA_{\tau}(N)$ (communication algebra with tau-steps) and names $N$. It need to prove that $p!d.x||p?d.y$ is bisimular with $p!d.(x||p?d.y)+p?d.(p!d.x||y)$ ...
-1
votes
2answers
293 views

proof using induction of automaton

How I can explain this. Consider the following automaton, $A$. Prove using the method of induction that every word/string $w\in L(A)$ contains an odd number(length) of $1$'s. Show that there are ...