Problem Detail: What I’m trying to do is to show a problem in NP can be reduced to the min weight vertex cover problem I’ve chosen the max independent weight problem = input: A graph G with weights on each vertex, Read More …
Author: ignougroup
[Solved]: From Whence the Randomization in Randomized Quicksort
Problem Detail: Cormen talks briefly about the advantages of picking a random pivot in quicksort. However as pointed out here(4th to the last paragraph): Using a random number generator to choose the positions is relatively expensive So how is picking a Read More …
[Solved]: Sorted-greedy for Load Balancing Problem
Problem Detail: In load balancing problem we have $m$ machines and $n$ jobs, each taking processing time $t_j$. Total processing time on the machine $i$ is $T_i =sum_{jin A(i)}{t_j}$, where $A(i)$ is the set of jobs assigned to machine $i$. Goal Read More …
[Solved]: Little’s law and average time on a system with a switch
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 …
[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]: 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]: 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 …
