# 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
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 ...
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 ...
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, ...
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. ...
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 ...
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 ...
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....