Problem Detail: We have a switch with $2$ lines of input and $2$ output. Each line is $10 Mbps$. The size of packets is fixed and is $1KB$. The $1^{st}$ line of input is active (transferring packets) $40%$ of the time, Read More …
Category: Uncategorized
[Solved]: Difference between symbolic execution and reachability analysis
Problem Detail: Now I am confused about symbolic execution (SE) and reachability analysis (RA). As I know, SE uses symbols to execute some code to reach each branch with branch conditions. And RA can be used to find the reachability of Read More …
[Solved]: Number of finite strings over a countably infinite alphabet
Problem Detail: If the alphabet is countably infinite, then is the number of finite-length strings over this alphabet countably or uncountably infinite? Asked By : Vivek Barsopia Answered By : David Richerby It’s countable. The set $S_ell$ of strings of length $ell$ is $SigmatimesdotstimesSigma$, which Read More …
[Solved]: How can I show a linear languages are closed against concatenating with regular ones?
Problem Detail: This was given as a homework problem but I have already submitted the assignment. I’d like to resolve it at this point for my own satisfaction. Given that $L_1$ is a linear language and $L_2$ is a regular language, Read More …
[Solved]: Difficult Question to Understand (Computer Artitechture)
Problem Detail: You are designing an elevator controller for a building with 25 floors. The controller has two inputs: UP and DOWN. It produces an output indicating the floor that the elevator is on. There is no floor 13. What is Read More …
[Solved]: If an NP-complete problem is shown to have a non-polynomial lower bound, would that prove that P != NP?
Problem Detail: I understand that the Cook-Levin theorem proved that any NP problem is reducible to an NP-complete problem, which signifies that if a polynomial-time algorithm for an NP-complete problem is found, it will mean that all problems in NP can Read More …
[Solved]: How to prove $(n+1)! = O(2^{(2^n)})$
Problem Detail: I am trying to prove $(n+1)! = O(2^{(2^n)})$. I am trying to use L’Hospital rule but I am stuck with infinite derivatives. Can anyone tell me how i can prove this? Asked By : Sid Answered By : Yuval Filmus You Read More …
[Solved]: Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem
Problem Detail: The Master theorem is a beautiful tool for solving certain kinds of recurrences. However, we often gloss over an integral part when applying it. For example, during the analysis of Mergesort we happily go from $qquad T(n) = Tleft(leftlfloor Read More …
[Solved]: Get the nth lexicographic string of “all” possible combinations of an alphabet
Problem Detail: Is there a way to find the nth string of characters from an alphabet, without having to store “all” of the combinations? Example: Alphabet $A = {a,b,c}, n=12$. All possible combinations in lexicographic order are $C = {a, ab, Read More …
[Solved]: Big O Notation of $n^{0.999999}log(n)$
Problem Detail: I’m taking the MIT Open Courseware for Introduction to Algorithms and I’m having trouble understanding the first homework problem/solution. We are supposed to compare the asymptotic complexity (big-O) for different functions: $f_1(n) = n^{0.999999}log(n)$ $f_2(n) = 10000000n$ $f_2(n)$ is Read More …
