Problem Detail: Consider this code: Precondition: Postcondition: rv == i <==> ∃i, 0 ≤ i ≤ a.length-1, a[i] == key function Find(Array<int> a, int key) returns (int i) { i = a.length -1; while i ≥ 0 { if a[i] == Read More …
Category: Uncategorized
[Solved]: Mergesort with $O(n^2 log n)$ runtime
Problem Detail: I have a task where i need to find a problem in which mergesort has to have a runtime of $O(n^2 log n)$. In our lecture we said that the runtime is $O(n log n)$ assuming that every comparison Read More …
[Solved]: What is the effect of operating systems on execution speed?
Problem Detail: I’m using a Raspberry Pi 2 which works with 900MHz. (Asked this question there and they think it belongs to cs) My question is: since it also runs an operating system in the background, I expect this would take Read More …
[Solved]: MU0 instruction set
Problem Detail: As i know the MU0 processor instruction format is as follows: so the opcode is 4 bit, can anyone explain why it has only 8 instructions, if it could have 16 instructions, 2^4 = 16 ?? Asked By : rainman Read More …
[Solved]: Prove that regular languages and context-free languages aren’t closed under $Perm(L)$
Problem Detail: Let the operation $$Perm(L) = { w | exists u in L text{ such that } u text{ is a permutation of } w }$$ Prove that both regular languages and CFLs aren’t closed under $Perm(L)$. I’ve tried to Read More …
[Solved]: Is the language ${ a^pb^q mid p, q text{ are prime} }$ regular?
Problem Detail: I am interested to know whether that language $$ L = { a^pb^q mid p, q text{ are prime} } $$ is regular. How do you prove that it is not regular? Asked By : Alex Answered By : godfatherofpolka This Read More …
[Solved]: Can Floyd-Warshall be used to solve an APSP problem without copying the matrix?
Problem Detail: According to CLRS, each iteration of the outermost loop (on $k$) makes a new copy of the adjacency matrix. Is it safe not to copy the matrix on every iteration? What I mean is, according to CLRS: $d_{ij}^K = Read More …
[Solved]: Algorithm to partially sort list into equal-sized buckets
Problem Detail: Suppose I have a large list of numbers that I want to divide into equal-sized buckets so that every bucket contains only larger numbers than buckets to its left. Numbers within each bucket don’t need to be sorted. For Read More …
[Solved]: Seeking popular science book on bioinformatics or computational genomics
Problem Detail: An intelligent 15-year-old I know is interested in both computer science and genetics. I told her that these fields make an excellent combination. I’d like to give her a book on bioinformatics or computational genomics. I’m looking for a Read More …
[Solved]: Homomorphism erasing information
Problem Detail: I would be grateful if anyone could help me with the tricky exerciese *7.52 from Sipser’s Introduction to the Theory of Computation 3rd ed. I got stuck in proving that, if P is closed under nonerasing homomorphism (replacing all Read More …
