texts: Showing that $\lg(n!)$ is or is not $o(\lg(n^n))$ and $\omega(\lg(n^n))$

texts:
My instructor assigned a problem that asks us to determine which asymptotic bounds apply to a certain $f(n)$ for a certain $g(n)$, in my case $f(n) = \lg(n!)$ and $g(n) = \lg(n^n)$. For clarity, the convention we use in our class is that $\lg = \log_2$, the "binary logarithm".

I know that by Stirling's approximation, $\lg(n!)$ grows in $O(n\lg(n))$, and evaluating the limit $\lim_{n \to \infty} \frac{n\lg(n)}{n\lg(n)} = C$, some constant > 0, and so $\lg(n!)$ is in $\theta(\lg n^n)$.

$\theta$ also means that my $f(n)$ is is in $O(g(n))$ and $\Omega(g(n))$, but this does not mean that my $f(n)$ is in $o(g(n))$ or $\omega(g(n))$.

For that, I believe I would need to evaluate $\lim_{n \to \infty} \frac{\lg(n!)}{\lg(n^n)}$, but I am not certain.

What strategy would I use to show that $f(n)$ is in $o(g(n))$ or $\omega(g(n))$? Would I evaluate $\lim_{n \to \infty} \frac{\lg(n!)}{\lg(n^n)}$?


texts: Computationally 'hard' polynomial-time reduction to other NP-complete problems / Hierarchy of NP-complete problems

texts:
As we all know there exist plenty of polynomial-time reductions from one NP-complete problem to another. Are there any NP-complete problems that have a rather large polynomial bound for reductions to other NP-complete problems, like a poly-time sub-hierarchy of NP-complete problems...?

E.g. lets assume I have NP-complete problem A and B. They are reducible to each other in lets say at most $n^3$. Does there exist a NP-complete problem such that the best known reduction to both A and B (and all other) is, lets say, $n^{100}$.

Question: Are there (non-special-tailored) NP-complete problems with a large best known (deterministic?) polynomial-time reduction?
Question: Is there a upper (deterministic?) polynomial bound for polynomial-time reductions between NP-complete problems

(There is a question here asking for a hierarchy of NP-complete problems but with a different base-problem, so solution does not really answer my question:
Understanding reductions: Would a polynomial time algorithm for one NP-complete problem mean a polynomial time algorithm for all NP-complete problems?)


texts: What algorithm should I use for the following problem?

texts:
Suppose we have 2 lists:

List $G$: the goal, contains goal items each comes with a specific amount,
$$G = \{i_1 \times Item_1, i_2 \times Item_2,\dots, i_n \times Item_n\}$$

List $I$: a list that contains lists of items each also comes with a specific amount,
$$I = \{\{j_1 \times Item_1, j_3 \times Item_3\}, \{k_2 \times Item_2, k_3 \times Item_3,k_5 \times Item_5\}, \dots\}$$

Each of the lists in $I$ costs some amount to pick out and we know them.
It is guaranteed that each item in $G$ will appear in $I$ at least once.

Find a way to pick lists from $I$ so that their total items will be equal or exceed that of $G$ but also minimize the cost.
You can pick as many lists as you want and duplicates are allowed.

This problem came up to me while planning to make a tool for a game.


texts: Multiplication of Upper triangular matrix and Lower triangular matrix

texts:
If I have an Upper triangular matrix A and Lower triangular matrix B, what could be the most efficient algorithm to get AxB and BxA.
Also what would be the formula for total number of multiplication operations.


texts: How to best calculate the best possible path with weights

texts:
Given a set of nodes, with connections in certain directions (see image), what is the most coins you can collect between the first and last given node. Not all rooms have coins, and we want to output the path taken, as well as total coins taken. You may only travel in the direction of the arrows. We are allowed to take the same path twice. The solution for the situation in the figure below is the path 1 - 4 - 3 - 2 - 1 - 5 - 7 - 9 - 10 - 8 - 12, with a total of 7 coins. I think this should be possible in linear time. My idea so far is to start at the last node and go back, saving the "best attainable score" for each node. However, this implementation runs into issues when there are cycles in the graph. Is there a better way of doing this?

edit: Assuming n nodes, there will never be more than 10n connections total.


texts: Naviers Stokes equation and machine learning

texts:
I am looking for a reference explaining how to solve Navier-Stokes numerically using Machine learning algorithms .

Thank you in advance for your help .


texts: Community detection in weighted directed graphs for fixed number of communities

texts: I have a weighted directed graph $G=(V,E)$ with positive weights. Say these vertices represent cities and the weight $w : V_1 \rightarrow V_2$ represents number of students moving into other cities for college. Note here that a city $A$ may have a small population and it may be sending a major proportion of it's outgoing students to another city $B$. If the converse holds true for city $B$, in that, most of it's incoming students come from city $A$ as a proportion of the entire incoming population, we say the weight of the edge connecting city $A$ to city $B$ should be high. So one can think of formalizing the above as a function of $\% inflow$ and $\% outflow$ problem. Now an algorithm like Gervin-Newman algorithm will find communities in such a graph. Here the number of communities detected increases over the number of cities considered. Is there a community detection algorithm for weighted directed graphs where I can pre-specify the number of communities I will be looking to get as output.


texts: Best way to code a shopping cart consisting of items with different properties

texts:
This is an interview question. Interviewer wanted a scalable solution
Goal is to find value of shopping cart. Cart could have 3 different types of items(Physical,Digital,URL).
Only Physical Items have a shipping address.
Only Digital items have a redeemable code that is used in a merchant site.
Only URL items have a URL that gives access to some online resource.
I've suggested having an Item class with price property which is extended by classes PhysicalItem, DigitalItem, UrlItem. Objects of these classes added to list which is iterated over to find the total order amount. Interviewer wasn't impressed.
Is there any good design pattern/approach that is best applied here?


texts: I understand that Byte/ IL Codes are interpreted/executed by their corresponding run times.  Do those run time converts the Byte/IL codes directly to machine code which processor can execute or the intermediary codes are converted to C/C++ calls?  Similarly, for privileged actions like File IO, do the run time translates byte/IL code directly to "System Calls" or does it translate it to the Wrapper API calls provided on top of System Calls?


texts: How many recursively enumerable sets are there?

texts:
I'm trying to get some notion of how "many" recursively enumerable sets there are.

Here's one way of formalizing the question: consider $S =\{q: q\in Q\cap [0,1]\}$ and $R\subset S$ the set of recursively innumerable subsets of $S$.

What is the measure of $R$? My intuition is that it is 0 (i.e. a given set is almost surely not RE), but I am having difficulty proving it.


texts: what does “Configuration is valid for a viable prefix ” actually means?

texts:
I am learning LR(1) parsing from the Dragon Book. I am really confused with this sentence.

  Formally we say that a configuration $[A \to u•v, a]$ is valid for a viable prefix $α$ if  there is a rightmost derivation $S \Rightarrow^* βAw \Rightarrow^* βuvw$ where $α = βu$ and either $a$ is the first symbol of $w$ or $w$ is $∂$ and $a$ is $\$$.

I am not able to figure out how validation of a configuration for a viable prefix is useful . What does it speak intutively and why does it matters?


texts: How to find First in a left recursive grammar?

texts:
One of the basic requirements for a grammar to be LL(1) is : For every pai r of productions A -> X | Y, First(X) and First(Y) should be disjointed.
If a grammar is left-recursive, then the set of productions will contain at least one pair of the form A -> AX|B; and hence, First(AX) and First(Y) will not be disjoint sets, because everything in the First(Y) will also be in the First(AX).
Source : Compiler Design by Dr. O.G. Kakde

How can I calculate the First of (AX) because First(A) = First(AX) U First(Y) goes recursively forever ?


texts:
I read a post which talks about pretty much the same problem. But here I simplify the problem hoping that a concrete proof can be offered.

There is a set $A$ which contains some discrete points (one-dimensional), like $\{1, 3, 37, 59\}$. I want to pick one point from $A$ which minimizes the sum of distances between this point and others.

There may be lot of posts out there, and my problem is just the one-dimensional version of those. I know how to prove it if $A$ is not discrete, but I fail when $A$ is discrete like above.

Please answer with a concrete proof.


texts: Name for type of actions that only care for outcome

texts:
There is a definition for kind of actions that only care for outcome.
Classic example for such an action is remove from collection:
When you try to remove an item that doesn't exist in collection, there are two possible outcomes: failure with item doesn't exist or success (because the outcome is that the item doesn't exist).
I'm interested in the second one.
How do you call remove that succeeds when the item it is trying to remove is not present?


texts: Differences between $\text{BPP}$ and $\overline{\text{BPP}}$ vs $\text{co-BPP}$

texts:
Is $\overline{\text{BPP}}$ different from $\text{co-BPP}$? I am having trouble understanding the "co" part of these complexities.

I think yes and here is what I think: It seems given that $\text{BPP}$ is the class of languages decided by PTMs with error probability 1/3, then this is equal to $\text{co-BPP}$. But $\overline{\text{BPP}}$ is the class of languages decided by PTMs with success probability 1/3. So $\overline{\text{BPP}}$ is different from $\text{co-BPP}$.

Am I correct on these definitions?
Thanks!


texts: Is model theory useful for computer scientists

texts:
It is often stated in the CS folklore that Turing was inspired by Gödel's incompleteness theorem, more specifically the diagonalization proof and the isomorphism between axiomatically generated statements (Gödel numberings).

Are there other such links between model theory and computer science? Should a computer scientist be interested in model theory?


texts: Trouble understanding Break-Even Point for upgrade

texts:
Null, Linda; Lobur, Julia: The Essentials of Computer Organization and Architecture, Jones&Bartlett Learning 2006, Ch. 7 Ex 2:

  Suppose the daytime processing load consists of 60% CPU activity and 40% disk activity.
  Your customers are complaining that the system is slow. After doing some research, you have learned that you can upgrade your disks for 8,000 dollars to make them 2.5 times as fast as they are currently. You have also learned that you can upgrade your CPU to make it 1.4 as fast for 5,000 dollars.

  a. Which would you choose to yield the best performance improvement for the least amount of money?
  b. Which option would you choose if you don't care about the money, but want a faster system?
  c. What is the break-even point for the upgrades? That is, what price would be charged for both upgrades to make their cost and performance improvement equal?

Ans.

Fraction of work: 60% CPU, 40% disk.

SCPU = 1/((1-f)+(f/k)) = 1/((1-0.60)+(0.60/1.4)) = 120.69%

SDISK= 1/((1-f)+(f/k)) = 1/((1-0.40)+(0.40/2.5)) = 131.58%

a. Choose the CPU upgrade:
5000/120.69% = $41.43

8000/131.58% = $38.00
b. The disk option gives a better performance improvement.

c. All things are equal when you pay 41.43 * 131.58 = $5451.16 for the disk upgrade.

I don't quite understand the break-even logic. How are things equal when you do 41.43 * 131.58? Maybe I'm approaching it wrong.


texts: creditcard validation - why does nit not fail for 7 digits?

texts:
using luhns credit card check algorithm why is digits with 7 length allowed ?  for example 1111111 is a verfied credit card number meaningly if it has only six digits its not. this does not look like a credit card number to me, am i missing something ?

go to any online credit card validation site and try 1111111 and see that it returns valid. why ?

I have tried going to the following websites: http://www.dcode.fr/luhn-algorithm and a few others.


texts: Can the plus operator in regex be replaced by the star operator?

texts:
Full disclosure, I'm interested in what this means about transformations on NFAs, but regex expressions seem like a easy way to ask the question.

If you have a regex that uses the plus operator (match one or more) can it, in the general case, be transformed into a regex that uses only the star operator (match zero or more).

Since all regular expressions can be converted into an NFA, and all NFAs can be converted into a regular expression (assuming the alphabet is the unicode character set lol), if it's true for one, it's true for both.

An hand-contrived example regex:

<[a-zA-Z]+>

A regex recognizing the same language, without the + operator:

<[a-zA-Z][a-zA-Z]*>

This may seem intuitively true for such a simple example, but I'd like to know for certain that it is generally true. Also, is there an algorithm that can convert an NFA containing a plus-like flow into a star-like flow NFA? Thanks!


texts: Quick testing tool for context sensitive grammars

texts:
Is there a ready-made tool / library that takes as input a context sensitive grammar $G$ over an alphabet $\Sigma$, and gives the ability to quickly check if a set of strings $\{w_1, w_2, ..., w_n \}$ belongs to $L(G)$ or not? (and if a string belongs to $L(G)$ outputs the derivation tree)?

...OR ...

  ... in the case there is no such tool, what approach do you suggest ?

What I have in mind is to use a contraint modelling language such as MiniZinc and build a simple "CS grammar to minizinc converter" on top of it; using the derivation length as a parameter to keep the running time feasible on hard cases (for some G the resulting membership problem could even be PSPACE complete) ...


texts: Do Karnaugh maps yield the simplest solution possible?

texts:
I'm learning to use a Karnaugh map, but I'm not sure if I obtained the simplest expression possible. Have a look at this example:

Truth table (inputs are A B C; output is F):

A   B   C   |   F
0   0   0   |   1
0   0   1   |   0
0   1   0   |   1
1   0   0   |   0
0   1   1   |   1
1   0   1   |   1
1   1   0   |   0
1   1   1   |   1

The Karnaugh map looks like this:

AB
--
C|

    00  01  11  10
    --------------
0|  (1  1)  0   (1)
1|  0   (1  1)  (1)

And this yields $\bar{C}\bar{A}+CB+A\bar{B}$. Is there any simpler way of choosing the 1s from the map and getting a simpler result? Are Karnaugh maps guaranteed to always yield the simplest result possible?


texts: Express a number with a combination of arithmetic operations and a single number

texts:
Today I ran into a this relatively simple (At least from my perspective ) problem. Basically the task is to be able to express any number using only a single number an any combination of arithmetic operations, square roots, exponentiation or factorials. To further elaborate I will make an example.

The input of the program would be a number 57 and a 8. The solution would be expressing the number 57 using only 8s and any of the defined operations.

In this case the number 57 could be expressed as
57 = (8+8+8+8+8+8+8)+8/8
Alternatively if we had the number
25 and 3 as an input, we could also do
25 = 3^3 - 3/3 - 3/3

The task is to define the input number with a similar method mentioned above, using the least amount of operations.

The person who created this problem defined it as difficult and no matter how hard I think about it, I just can not find a reason why. In most cases the problem will spin around simple integer factorization and in special cases, using factorials (With big numbers) or exponentiation will yield a less lengthy result.

What I am asking for is if there is any better, more efficient method to solve this problem and whether I am missing something obvious which would make this problem look as "Difficult" as it was defined.

Thanks for the answers in advance.


texts: How to write register machine code for Fibonacci

texts:
I am not sure whether this is the right place to ask this question, but since it involves register machine and computability, hopefully this is the right place.

I have tried to post on Programmers and Stack Overflow, but they redirected me to this site, they said it is more related to CS.

The question is about how can I write a register machine code/program that computes the Fibonacci number. The syntax of the code is actually really simple.

(Below are just for reference only, sorry for the long post)
(For more explanation see the book on Formal Logic: Its Scope And Limits by Richard Carl Jeffrey)

According to Wikipedia a register machine is a generic class of abstract machines used in a manner similar to a Turing machine. A (processor) register is a small amount of storage available as part of a CPU or other digital processor.

We can simplify the problem by modelling the registers as empty buckets, and we can let marbles or rocks to be put into the register ("bucket"). The rule is to add or remove marbles from the bucket to perform computations.

The rules are:
1. A register machine uses of a finite number of buckets, and an unending supply of marbles.
2. Each bucket can be individually identified. The marbles need not be distinguishable.
3. A register machine program is a finite set of instructions:
- To add marble to a bucket (and then to go on to the next instruction).
- Or to take a marble away from a bucket (and to go on to one next
instruction if you can, or another one, if you can’t).
4. The program can be written in a flowchart or in a list of instructions.

Here is an example of a register machine program that performs addition.
Let A, B, C be buckets.
1. (-B; 2,4) means take away one marble from bucket B, go to instruction 2 if can, or 4 if cannot
2. (+A; 3) means add one marble to bucket A, then go to instruction 3
3. (+C; 1) means add one marble to bucket C, then go to instruction 1
4. (-C; 5,-) means take away one marble from bucket C, go to instruction 2 if can, or exit if cannot
5. (+B; 4) means add one marble to bucket B, then go to instruction 4

It is easily shown that suppose we have 3 marbles in bucket A and 2 marbles in bucket B, and 4 marbles in bucket C. After performing this algorithm, there will be |A|+|B| = 3+2 = 5 marbles in bucket A and |B|+|C| = 2+4 = 6 marbles in bucket B.

(I hope the example above is clear enough for illustration purpose)

(Now here comes the question)

Now, I would like to write a register machine code which when given an input of n in bucket A, returns (also in bucket A) the nth Fibonacci number. The Fibonacci numbers are 0 (the 0th), 1 (the 1st), 1 = 0 + 1 (the 2nd), etc. We can use any number of buckets, the goal is to write the code as simple as possible (i.e. with fewest instructions). Fibonacci recurrence relation is F(n)=F(n-1)+F(n-2) given F(0)=0 and F(1)=1.

Here is my attempt and the code:
My idea is to use bucket A as input and finally as output F(n) (since the question requires the output in bucket A), bucket B as the "counter", bucket C as the F(n-1) and bucket D as F(n-2).
1. (+C; 2)
2. (-A; 3,4)
3. (+B; 2)
4. (-D; 5,7)
5. (+A; 4)
6. (-C; 5,7)
7. (-B; 6,-)

But my code only works for up to n=2 sadly, I am struggling to make the code works for any n>2.

I have been thinking for this days and nights, I would appreciate if anyone could help me on this. Please do not hesitate to ask me for clarification if anything is unclear.

Many many thanks in advance!


texts: Smallest segment after whose removal all elements are distinct

texts:
I am interested in the following problem:

  We are given an array of integers and we need to find the size of smallest subsegment such that after removing it all elements in the array are distinct.

How to solve this problem using binary search in $O(n\log n)$? I tried to read various submissions which use binary search, for example this one, but I couldn't understand them.

My attempt - I solved this problem in $O(n^2\log n)$ using brute force, but I want to know how to apply binary search to solve this problem in $O(n\log n)$.


texts: How to handle missing continuous attribute values in ID3 (Iterative Dichotomiser 3)?

texts:
I'm implementing the ID3 algorithm (Iterative Dichotomiser 3). I have an attribute which happens to be continuous like 12.21, 3.01, etc. AND have missing values which are marked as "NA".

How I'm discretizing the data: I'm finding the optimal split which results in the max information gain. How I'm dealing with missing values: I will use the most probable attribute value to replace the "?".

Of course I can do either process in both ways, and this is where my confusion arises. Is there a correct way in handling this?


texts: Minimal requirements for Kleene's recursion theorem

texts:
Kleene's recursion theorem guarantees that any Turing complete language must have quines. However, consider the following quine (in C, taken from the Quine page):

 char*f="char*f=%c%s%c;main()
 {printf(f,34,f,34,10);}%c";
 main(){printf(f,34,f,34,10);}

It makes no use of while or recursive functions, or any other of the features that make C Turing complete. It would work just fine in a subset of C that included only printf and basic string manipulations.

This makes me wonder whether Turing completeness is really necessary for the proof of Kleene's recursion theorem. Does the proof actually require it? If not, what is the most general class of languages to which the theorem applies?

Note that I'm not asking for the most general class of languages that have quines (which would be rather trivial), but the most general class of languages that have quines because of Kleene's recursion theorem. That is, I'm asking for the minimal set of language features needed to implement the recursion trick that's used in the most conservative proof of the theorem, thus guaranteeing that all languages within that class must have quines. Presumably the set of all languages that implement these features will be a subset of the set of all languages that exhibit quines, but it might be a superset of the Turing complete languages.

The Wikipedia page hints at this with the following text:

  However, a direct proof of Kleene's theorem (Kleene 1952: p. 352-353) does not make use of a universal program, which means that the theorem holds for certain subrecursive programming systems that do not have a universal program.

I don't currently have access to that reference, and I would like to know precisely which set of "subrecursive programming systems" this is referring to.


texts: Is there a standard name for this property of hash functions?

texts:
A hash function $H$ operating on strings can have the following property:
Let $x$ be a string and $c$ a character. Given $H(x \cdot c)$ and $c$,
$H(x)$ can be determined uniquely (where $\cdot$ stands for concatenation).
Note that it may not be possible to determine $x$, only $H(x)$.
An example of such hash function is the "polynomial hash function"
$H(c_1 c_2 ... c_k) = a^{k-1} c_1 + a^{k-2} c_2 + ... + a c_{k-1} + c_k \; (mod \; P)$
for a prime $P$ and an integer $0 < a < P$. Given $H(x \cdot c)$ and $c$, $H(x)$
is given by $a^{-1} (H(x \cdot c) - c) \; (mod \; P)$.
Another function having this property is Pearson hashing.
Is there a standard name for hash functions having this property?


texts:
As you can see from the title this is the impression that i have on this problem, but probably it isn't impossible.

The required DFA is :

"The set of the strings with equal number of 0 and 1 such that for each prefix the difference between the number of 0's and the number of 1's is minor(<) than 2".

Maybe I've misread the requirements I've thought of them as follows :

by prefix I thought of all the strings with length < than the original one, for example in my opinion the prefixes for "cat" are "c" and "ca" but not "cat";

"the difference between the number of 0's and the number of 1's is minor(<) than 2" by this i thought that we should have (number of 0 - number of 1) < 2, but now I'm realazing that even (number of 1 - number of 0) < 2 should be fine.

One user suggested to do this :

"Note that you can build a simple DFA which checks if the difference between the number of ones and the number of zeroes never exeeds 2 for any prefix of the input string: Add accepting states qk for −2≤k≤2 (where q0 is the initial state) and a rejecting sink state qs with transitions qk→qk+1 via 1 and qk→qk−1 via 0 for appropriate values of k and qk→qs for the other values."

but I don't understand quite well what it means, I've tried some solutions on my own and they don't work properly :

Any possible solutions? EDIT The DFA should be impossible as a matter of fact : here is the explanation


texts: Can this question be solved without knowing the Page Table Entry?

texts:
I'm preparing for the exams and this question came up -

  Consider a machine with $64MB$ physical memory and a $32$-bit virtual address space. If the page size is $4KB$, what is the approximate size of the page table?
  (A) 16MB
  (B) 8MB
  (C) 2MB
  (D) 24MB

The way I've solved it -
Physical Address Space = $64MB = 2^{26}B$
Virtual Address = $32$-bits, $\therefore$ Virtual Address Space = $2^{32}B$
Page Size = $4KB=2^{12}B$
Number of pages =$\,\Large\frac{2^{32}}{2^{12}}$$=2^{20}$ pages.
Number of frames =$\,\Large\frac{2^{26}}{2^{12}}$$=2^{14}$ frames.
$\therefore$ Page Table Size = $2^{20}\times 14\,bits \approx 2^{20}\times 16\,bits\approx 2^{20}\times 2B= 2MB.$

Some books claim the answer to be $8MB$ and I don't see why, but that confuses me.
Is this the correct way to solve it? Is the answer correct?


texts: What is the complexity class of arranging $1,\ldots, n$ so that all neighbors sum to a perfect square?

texts:
I recently saw a problem from Numberphile here, where the goal is to arrange the numbers $1,\ldots,n$ so that the sum of adjacent numbers is a perfect square. This question from Mathematics Stack Exchange has a good analysis of the generalization of the problem for arbitrary powers, but I have been unable to find an analysis of the complexity class of the decision version of the problem. It is $NP$ since you can check if an arrangement satisfies the square sum condition efficiently, but I have been unable to come up with a better algorithm than creating the associated graph and solving the Hamiltonian path problem.

So my question is if this problem is $NP$-complete or if there is a polynomial time algorithm that can decide if $1,\ldots,n$ can be arranged to satisfy the square-sum condition.

Arranging the integers means to find a permutation $a_1, \ldots, a_n$ of $1,\ldots, n$ with the property that for all $1 < i < n$, $a_i + a_{i+1}$ and $a_i + a_{i-1}$ are perfect squares.


texts: quicksort - Why is $\log_4 n$ used as an approximation instead of $\log_2 n$?

texts:
Below is an excerpt from Khan Academy's Quick Sort Analysis page.

In the average case of quicksort they assume that each time the partition function breaks the input array into the ratio 1:3 each time.

So why is it easier to assume $\log_4 n$ levels when the $n$ elements are being partitioned ? Why not assume it to be $\log_2 n$ levels ?

Wouldn't $\log_4 n$ and $\log_2 n$ mean the same thing here ?


texts:
I'm missing two details from Paxos made easy

P1. An acceptor must accept the first proposal that it receives.

What exactly is the reason for rule P1? What if the rule P2 was different, i.e. Upon receiving a proposal: acceptor memorizes the proposal as most recent proposal; if acceptor is not waiting with a running countdown, a countdown of Xmsec is set up; upon a countdown timeout acceptor accepts the most recent proposal

I'm not proposing the above rule as better or more interesting -- rather I'm posing a question of which exactly requirement is fulfilled by following P1.

Observe that P1a subsumes P1.

What does this mean? That P1a is more general? Fulfilling P1a fulfills P1? At least scenario mentioned in section 2.4 suggest P1a does not imply P1. What am I missing?


texts: Solving $T(n)=2T(n/2) + n \lg n$ , For ex: Counting inversions implemented with full mergesort

texts:
How to solve the recurrence equation $T(n)=2T(n/2) + n \lg n$

For ex: I implemented "Counting inversions" with a full mergesort instead of just using merge part, So the outer complexity will be $n \lg n$.

Also, What is the  $O$(complexity) of above ?

Introduction to Algorithms, 3rd edition (p.95) has an example of how to solve the a similar recurrence $T(n)= 3T\left(\frac{n}{4}\right) + n  \log(n)$  using master theorem by showing $f(n)$ is polynomially larger than $n^{\log_b a}$. But I am not sure about this one.


texts: Calculate coherence for non-gensim topic model

texts:
I've built a topic model, with:

Input: list of tokenized lists
Output: a m x t matrix (with each cell indicating the probability of word i appearing in topic k).
Output: a k x n matrix (with each cell indicating the probability of topic k in document j).

To find the optimal number of topics, I want to calculate the coherence for a model. However, I am only aware of sklearn's Coherencemodel, which seems to require a Gensim model as input.
Are there any other packages/implementations that I could use to calculate the coherence of a computed topic model? Or, if it is indeed possible to use the Coherencemodel without inputting a LDAmodel, could someone show me how to do that?


texts: Is multiple equation 0/1 linear integer programming with bounded integer weights NP-hard?

texts:
Suppose we forget about optimizing and just want to find a feasible solution to a set of equations:

$$\sum_i w_{ij} x_i = W_j.$$

Here we are given $w_{ij}$ and $W_j$, and want to solve for $x_i$.  Also $x_i$ are restricted to be 0/1 and we're promised that $w_{ij}$ and $W_j$ will be non-negative integer constants and we will have $w_{ij} \leq M$ for some universal constant $M$.  The number of variables and equations can be arbitrary.

Is this an NP-complete problem? If we have just one or a universal bounded number of equations then the problem can be solved in polynomial time. Certainly if we can find a solution then we can verify it in polynomial time, so the problem is in NP. I was trying to find a reduction from something like 3-SAT in the general case but to no avail.


texts:
Could you explain, please, the difference between the nested dissection and kd-tree. For me they look same representing a tree data structure for a distribution of points in a multi-dimensional Euclidean space, but with different labeling of nodes. Is there any more fundamental difference?

I will appreciate a reference discussing both terms. I have found that there is no literature covering both notions simultaneously.


texts:
At work I stumbled across this problem of allocating resources:

We are given a set of objects belonging to one of seven possible classes (multiple objects per class are allowed). We distinguish between classes A, B, ... G, because they have 3 possible attributes (weight, interest, size).
We also have four boxes X, Y, W, Z. The boxes have three characteristics on their own: importance, strength, size.
We want to put the objects into the boxes in order to maximize a metric based on the properties of the classes and the boxes.
We are also wondering if, given enough pairs "set of objects"-"allocation in boxes" tweak the characteristics of the classes in order to minimize a cost function representing the difference between the desired assignment and the one computed.

I tried checking standard methods of resource allocation or cost minimization (definitely not my expertise), but I couldn't manage to apply them to this specific problem. Any ideas on how to proceed, or on where could I find info related to this problem?

EDIT: This is the definition of the metric used that must be maximized. After that a simple example.

Let's just define $W_{obj}$, $I_{obj}$, $S_{obj}$ as the characteristics of an object and $I_box$, $St_box$, $Si_box$ as the characteristics of the box. The metric is the sum, over all the boxes, of this measure:

$I_{box} * \sum{I_{obj}} + 1/(St_{box} - \sum{W_{obj}}) + 1/(Si_{box} - \sum{S_{obj}})$

If you have multiple objects you just some over all of them.

As an example, suppose we have Box 1 and Box 2, with properties:

$St_{b1} = 10$, $I_{b1} = 3$, $Si_{b1} = 9$;
$St_{b2} = 20$, $I_{b2} = 1$, $Si_{b2} = 10$;

and three objects with properties:

$I_{o1} = 1$, $W_{o1} = 3$, $S_{o1} = 4$;
$I_{o2} = 1$, $W_{o2} = 3$, $S_{o2} = 4$;
$I_{o3} = 3$, $W_{o3} = 8$, $S_{o3} = 1$;

If we put all the objects in Box 2, our score will be:

$I_{b2} * (I_{o1} + I_{o2} + I_{o3}) + 1/(St_{b2} - (W_{o1} + W_{o2} + W_{o3})) + 1/(Si_{b2} - (S_{o1} + S_{o2} + S_{o3}))$
 $= (1 * 5) + 1/(20-14) + 1/(10-9)$
 $= 6.16$

Since no objects goes in Box 1, its score will be:

$1/St_{b1} + 1/Si_{b1} = 1/10 + 1/9 = 0.21$

Hence the score for this particular configuration is $6.16 + 0.21 = 6.37$

The aim is to find the configuration (i.e. the object distribution) maximising such score.

Hope it's a bit clearer now.


texts: Dijkstra algorithm vs breadth first search for shortest path in graph

texts:
I have asked this question in StackOverflow. I was asked to move in here. so here it is:

I need some clarifications and inputs regarding Dijkstra's algorithm vs breadth first search in directed graphs, if these are correct.

Dijkstra's algorithm finds the shortest path from Node A to Node F in a weighted graph regardless of if there is a cycle or not (as long as there are no negative weights)

but for that, All paths from A to all other Nodes in the graph are calculated and we grab the path from A to F by reversing the sequences of nodes in prev.

BFS: finds the shortest path from node A to node F in a non-weighted graph, but if fails if  a cycle detected.

however, BFS just calculates the path from Node A to Node F and not necessarily all path from Node A.
if Node F is reached early, it just returns the path.


texts:
I am supposed to create CFG for this languague:

$L= \{w : w \in \{a, b\}^*, |w_b| = 3k, k \geq 0 \}$

where $|w_b|$ is count of terminals $b$ in $w$.

For example:

aa - OK, no 'b'

abb - wrong, only 2 'b'

aaabbb - OK, 3 times 'b'

aababbb - wrong, 4 times 'b'

abbbbbaaa - wrong, 5 times 'b'

abababbbaaab - OK, 6 times 'b'

and so on...

I can't come up with any solution. Any advice?

My goal is to design context-free grammar, not automaton or regular expression (i don't know how to design automatons or RE yet).

What about CFG

G = {{S,A}, {a,b}, R, S}

where R rules are:

1] S -> S A b A b A b A S
2] S -> A
3] S -> ε
4] A -> a A
5] A -> ε

Explanation:

rule 2] is for cases when there are no 'b' symbols in w

rule 3] is for case of empty string

rule 4] is for adding 'a' symbols between 'b', e.g. baaaabab, babaab

rule 5] is for cases, when there are multiple 'b' next to each other, e.g. abbbaaa

Is this CFG ok?


texts:
Based on CLRS question 2.2:

Consider linear search again. How many elements of the input
sequence need to be checked on the average, assuming that the element being
searched for is equally likely to be any element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in $\theta$-notation? Justify your answers.

I have a question regarding the average case.

"assuming that the element being
searched for is equally likely to be any element in the array" - what does that exactly mean? Does it mean that the probability for each to happen is $\frac{1}{n}$?

Or could it also be that the element is not in the array at all - is that a case is this probability the same as the rest (and then they are all $\frac{1}{n+1}$)?

Does it matter for the average case how many duplicated are there? Are we assumming that there are no duplicates?

A good explanation about what exactly is the average case would be helpful.

Thanks a lot!!!


texts: Is there a useful algorithm with a decreasing asymptotic time?

texts:
Algorithmic complexity is usually increasing and almost always strictly increasing based on input size. This is logical since algorithms take time to execute steps, and for almost all problems, the larger the input the more steps are needed to handle that input.

I want to know if there is an algorithm that does not increase with input size but rather decreases.

You could make an algorithm with decreasing asymptotic time by for example, making it loop -n + 10000 times, where n is the size of an array of integers.

This however doesn't do anything other than cycling, it shows that you could make such an algorithm, if the algorithm doesn't do anything useful. Is there an algorithm that decreases asymptotically as the size of the input increases, that solves an actual problem (theoretical or other)?

EDIT:

Some people seem to be getting confused by the question so i want to clarify.

Is there a non-trivial algorithm that executes less steps as the size of the input increases?


texts: FA for when length of $w$ is $4$ or $w$ contains the substring $01$

texts:
I have been trying to create an FA for the language.
$\{w \in \{0, 1\}^∗ , |w|= 4 \vee w \text{ contains the substring }01\}$
I created one that accepts words that contain the substring $01$, but I have a hard time finding a solution for the length part.
This is my attempt so far:

Any help is greatly appreciated.


texts: complexity of dividing set of number with constraints

texts:
I've been thinking about a division problem for groups that I haven't found a dynamic programming solution and I'm trying to analyze the complexity of the problem.
There is a set of $n$ positive numbers ($S$), a vector of group sizes (let's call it $Sizes$), and a parameter $Y$. Find a way for divide the $n$ numbers into groups that their size describes in $Sizes$ s.t. the $constraint$ in close as possible to $Y$.
For example, $ S = \{1,1,2,2,3,4,4,7,9,11\}$, $Sizes = [2,2,3,3]$, $Y=2$ and $constraint =$ the variance of the group. Of course that the $constraint$ could be changed in other cases. But this is representative example.
Has this problem any dynamic programming solution? or that the complexity is exponential (which means $NP$ problem)?
Which approximation approaches can help me in this case?
Thanks in advance!


texts: Why is dominating set in $W[2]$, but independent set in $W[1]$

texts:
In Parameterized Complexity the Independent Set Problem for a Parameter $k$ ist $W[1]$-complete, and Dominating set is $W[2]$-complete. Now the prototypical $W[1]$ problem is deciding by a single-tape non-deterministic Turing machines if it has an accepting run with at most $k$ stepts, and for $W[2]$ it is the same notion with a multitape machine.

Intuitively they are both set selection problems, so a non-deterministic machine can guess in at most $k$ steps what elements to take into an independent (or dominating) set. So with this intuition, that the first problem ist in $W[1]$ is clear, but not why dominating set is not? So what am I missing, what is the distinguishing feature, why do we need a multitape machine for the second, but not for the first? My gut feeling would put domination set into $W[1]$, but that is not true as I know.

EDIT: I took the Turing machine definition of $W[1]$ from the following seminal paper Fixed-Parameter Tractability and Completeness I: Basic Results, but it is also written on wikipedia, together with the characterisation of $W[2]$. If you do not have access to the paper you can get a pdf from here, but the diagrams are missing in there (see page 6 for the definition of the Turing machine problem).


texts: What is the difference between a R-tree and a BVH?

texts:
I've just read about R-Trees:

  The key idea of the data structure is to group nearby objects and represent them with their minimum bounding rectangle in the next higher level of the tree; the "R" in R-tree is for rectangle.

This seems to be a Bounding Volume Hierarchy (BVH) with axis-aligned bounding boxes (AABBs):

  A bounding volume hierarchy (BVH) is a tree structure on a set of geometric objects. All geometric objects are wrapped in bounding volumes that form the leaf nodes of the tree. These nodes are then grouped as small sets and enclosed within larger bounding volumes. These, in turn, are also grouped and enclosed within other larger bounding volumes in a recursive fashion, eventually resulting in a tree structure with a single bounding volume at the top of the tree.

  [...]

  One of the most commonly used bounding volumes is an axis-aligned minimum bounding box.

Both allow overlapping nodes.

I've learned about BVHs in a Computer Graphics lecture and about R-trees by a professor who is mainly working on databases. So it might be that different communities developed the same datastructure independently.

Is there any difference between R-Trees and BVHs?


texts: How is RANSAC used to estimate a homography given the descriptors of both images computed with SIFT?

texts:
Let image $x$ be an original (non-warped) image. Let $I_1$ be $I_1'$ having suffered some projective transformation and possibly some noise.
Suppose we have computed SIFT descriptors for both images.

Can you explain how RANSAC is concretely used to find the homography that aligns image $x$ and $y$?

More concretely, I understand we give to the RANSAC function the keypoints ($I_1$) and keypoints ($I_1'$).

My understanding (from various papers/tutorials I've read) is that it will take the positions of keypoints in $I_1$, which I denote as $(x,y)$, and the positions of keypoints $I_1'$, $(x', y')$, i.e. RANSAC($(x,y),(x',y')$), and then take randomly pairs of $(x',y')$ and $(x,y)$, and then compute the homography by trying to solve for each $x_i', y_i'$: $$[x'_i, y'_i]=H*[x_i, y_i]$$

But then how to estimate inliers? I guess by looking at the Euclidean distance between each pair of points found in the homography.

However, I don't really see the 'big picture'. I don't completely link this process of 'finding homography' and checking inliers etc.

It would be great if someone could summarize that in a clear way?

P.S.
In general, tutorials say that they "find the homography" and then check for inliers - in some way - but they don't explain in a more pragmatic way what really happends.... w.r.t sift descriptors


texts: Why does a first-child-next-sibling tree implementation have parent pointers?

texts:
Below is the code,

class SibTreeNode extends TreeNode {
  protected Object item;
  protected SibTreeNode parent;
  protected SibTreeNode firstChild;
  protected SibTreeNode nextSibling;

  .....
}

As per below diagram, I could not understand the purpose of parent member in every node.

Why do we require parent member in every node? Does it improve space/time complexity of insert/find/update operation?

Note: Beginner in Data-structure


texts: Error correction for windowed reads from cyclic tapes

texts:
I have an array of N symbols written on a cyclic tape. I read a sequence of M symbols starting from a random place on the tape. What error correcting scheme and even a coding scheme should I use for such "channel"?
Also will this problem  be simpler if tape is not cyclic?


texts: Meaning of $\mu t$ terms in dependent type theory

texts: What is the meaning of the term $\mu t$ in the type theory formalized in this paper (section 2.1, page 2)?


texts:
I have two numbers, which are each the product of a large number of smaller numbers that I know. I want to find the GCD (Greatest common divisor) of these two numbers. Is there any way I can make use of the partial factorization I have to speed up the process?

In particular, each larger number is the product of $2^{15}$ smaller numbers, each of which is on the order of $2^{4000}$. I don't know anything about the factorization of the smaller numbers.

Edit:
While the input numbers are about 120,000,000 bits, the GCD is about 500,000 bits. The factors of the numbers are in particular in sequence. They are all integers in a consecutive range.

All of the GCD algorithms I've seen make use of the numbers directly, not in a partially factored form or anything. Are there any algorithms which could incorporate this information to speed things up?


texts: What is happening in this part of the LC3?

texts:
This is a diagram of the LC3 Computer

I am trying to understand what is happening in the parts I highlighted. The part I had highlighted had the instruction bit sign extended to 16 bits and then passed on to the SR2 Mux. Does anyone know what instruction is being carried out here or what the role of the mux(SR2) is here?


texts: Triangulation algorithm for an arbitary amount of points?

texts:
I have multiple cameras that records the 2D pixel coordinates of the features each camera sees. After some searching, I came across this paper with a method to calculate the 3D coordinates of the features.

My problem is that the input of that algorithm requires a "feature tracks" for each feature. Meaning for each feature, there is a list of 2D coordinates corresponding to the camera that recorded them. In my case, I can have any number of features, how do I know which of the pixel coordinates belong to which feature? Is there a widely accepted algorithm for this? What would be the key word to search for the algorithm for this problem, would it be just a clustering algorithm I should look for?

Edit: In other words, I want to determine the 3D positions of a set of points by a set of 2D images taken by surrounding cameras. I do not know how many points I have.


texts:
Consider following grammar:

$$X\to Yc|ZY$$

$$Y\to ab|cX$$

$$Z\to d|\epsilon$$

Can this be converted to LL(1)?

Cleary, its not LL(1) because of First/First conflict at first production. Can anyone suggest something to make it LL1?


texts: What is the standard way to choose a new leader in Multi-Paxos?

texts:
If you are unfamiliar with multi-Paxos or paxos, the following link might be a good refresher on it:

http://amberonrails.com/paxosmulti-paxos-algorithm/

or the paper by Leslie Lamport:

http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf

I was thinking about multi-Paxos and what one should do to elect a new leader if one is to fail (or in general, just if we want to re-elect a leader). I know that Multi-Paxos normally operates under the assumption that there is a stable leader. However, it does not mean that the Leader never fails or that we might never want to change the leader. It might be uncommon, but we must do something so that the system can function properly in the case that we might want to change leader.

I was wondering, what was the standard way to handle leader failures in multi-Paxos?

I have thought of different ways to handle failures of leaders and also google them, but it's still not clear to me how it should be done.

Let me also clarify what I mean by multi-Paxos and clarify that its not the mechanism described in the following source:

http://www.ict.kth.se/courses/ID2203/material/Lecture_11._Sequence_Consensus.pdf

What I mean by multi-Paxos is the abstract idea of deciding a list of Paxos instances by a single leader. This leader sends a range of Paxos Instances it wants to prepare and thus, it can hear a single a single prepare acknowledgement for the whole range instead of one per Paxos instances. Therefore, we can avoid a round-trip and have a more efficient prepare phase. Furthermore, we can now send accept messages immediately for that range since we have already prepared the values.

However, I was a little unsure of how multi-Paxos normally handled choosing a new leader, if the current leader happened to die. Does it doing by running a Paxos instance? Also, how often does it change leader? Can we do a leasing mechanism that after some time t a leader is re-elected? If we do, can this only be achieved if one assumes clock synchronization? The article I initially posted talks about multi-Paxos but kind of skips the detail I am trying to address.

If anyone has better sources or an idea of how one should implement leader election, I would love to hear about it, because I am sure that implementing multi-Paxos is not a "new" problem and that is has been addressed before at some point (and I would rather avoid very very weird "ad-hoc" ideas...)


texts: Behavior of an algorithm with inner loop step by 2 and outer loop decrements inner loop times

texts:
I designed an algorithm like this but I do not know how to perform its analysis to determine how it runs $($$O(n)$, $O(n^2)$, $O(log(n)$, $etc$$)$

m = some constant
for i = 1 to n
{
    for j = 1 to m step 2
    {
        // do some stuff here
    }
    m = m - 2
}

Can you please provide a clue to solve my issue? This is a homework and I only have to deliver the algorithm, but I want to go farther and determine its behavior. I have analyzed other (maybe simpler) algorithms but this is kind of different of what I have seen.

Respectfully,

Jorge Maldonado


texts: Are there languages generated by linear grammar which aren't regular?

texts: Are there languages generated by linear grammer which aren't regular?


texts: When is the minimum spanning tree for a graph not unique

texts:
Given a weighted, undirected graph G: Which conditions must hold true so that there are multiple minimum spanning trees for G?

I know that the MST is unique when all of the weights are distinct, but you can't reverse this statement. If there are muliple edges with the same weight in the graph, there may be multiple MSTs but there might also be just one:

In this example, the graph on the left has a unique MST but the right one does not.

The closest I could get to finding conditions for non-uniqueness of the MST was this:

Consider all of the chordless cycles (cycles that don't contain other cycles) in the graph G. If in any of these cycles the maximum weighted edge exists multiple times, then the graph does not have a unique minimum spanning tree.

My idea was that for a cycle like this

with n vertices, you can leave out exactly one of the edges and still have all of the vertices be connected. Therefore, you have multiple choices to remove the edge with the highest weight to get a MST, so the MST is not unique.

However, I then came up with this example:

You can see that this graph does have a cycle that fits my condition: (E,F,G,H) but as far as I can see, the minimum spanning tree is unique:

So it seems like my condition isn't correct (or maybe just not completely correct). I'd greaty appreciate any help on finding the necessary and sufficient conditions for the non uniqueness of the minimum spanning tree.


texts: Create an order from several incomplete orders

texts:
Here is the motivation and how it should behave, but I need a help how to implement it.

I have several (typically) incomplete orders given as ordered values, for ex.:
1. A, C, D
2. D, E
3. X, B
4. B, C
5. C, F
6. C, A

and the resulting order should be:
A, X, B, C, D, E, F or A, X, B, C, F, D, E or A, X, B, C, D, F, E

The idea behind it is sort the result based on first seen order. I will try explain it on the example in steps:
order A, C, D
D, E - D seen, so add E after D, so order A, C, D, E
X, B - no value seen yet, so we can not determine the order now, so create 2nd temporary order X, B
B, C - C already seen, so order A, B, C, D, E
and 2nd order can be merged via B, so A, X, B, C, D, E
C, F - C see, so order A, X, B, C, D, E, F
C, A - ignore, both values are part of already defined order (by first incomplete order A, C, D)

But what if an additional incomplete order F, D or F, E will be part (added to the end) of the input? The step-by-step mental algorithm will fail - F was already placed.

How can the idea be implemented, any idea?


texts: Disconnecting a complete graph by removing edges randomly

texts:
Given a complete graph with $n$ nodes, I remove edges randomly with probability $p$ such that I want to disconnect the graph.

I want to find out the minimum number of edges that I must remove randomly to disconnect the graph. Also the value of $p$ where I can disconnect the graph by removing the least number of edges.


texts: On wikipedia it says that boruvka can be implemented in linear time for planar graphs, but I don't know how to prove that.


texts: Let's say an algorithm has an asymptotic time complexity of $\Theta(N)$. However in practice, $N$ is bound by a small upper limit (e.g. the size of a character set). Can we then say the complexity is $\Theta(1)$? Or is there a better way of describing the performance of an algorithm in a particular real-life situation?


texts: Where is the mistake in this apparently-O(n lg n) multiplication algorithm?

texts:
A recent puzzle blog post about finding three evenly spaced ones lead me to a stackoverflow question with a top answer that claims to do it in O(n lg n) time. The interesting part is that the solution involves squaring a polynomial, referencing a paper that describes how to do it in O(n lg n) time.

Now, multiplying polynomials is practically the same as multiplying numbers. The only real difference is the lack of carries. But... the carries can also be done in O(n lg n) time. For example:

    var value = 100; // = 0b1100100

    var inputBitCount = value.BitCount(); // 7 (because 2^7 > 100 >= 2^6)
    var n = inputBitCount * 2; // 14
    var lgn = n.BitCount(); // 4 (because 2^4 > 14 => 2^3)
    var c = lgn + 1; //5; enough space for 2n carries without overflowing

    // do apparently O(n log n) polynomial multiplication
    var p = ToPolynomialWhereBitsAreCoefficients(value); // x^6 + x^5 + x^2
    var p2 = SquarePolynomialInNLogNUsingFFT(p); // x^12 + 2x^11 + 2x^10 + x^8 + 2x^7 + x^4
    var s = CoefficientsOfPolynomial(p2); // [0,0,0,0,1,0,0,2,1,0,2,2,1]
    // note: s takes O(n lg n) space to store (each value requires at most c-1 bits)

    // propagate carries in O(n c) = O(n lg n) time
    for (var i = 0; i < n; i++)
        for (var j = 1; j < c; j++)
            if (s[i].Bit(j))
                s[i + j].IncrementInPlace();

    // extract bits of result (in little endian order)
    var r = new bool[n];
    for (var i = 0; i < n; i++)
        r[i] = s[i].Bit(0);

    // r encodes 0b10011100010000 = 10000

So my question is this: where's the mistake, here? Multiplying numbers in O(n lg n) is a gigantic open problem in computer science, and I really really doubt the answer would be this simple.

Is the carrying wrong, or not O(n lg n)? I've worked out that lg n + 1 bits per value is enough to track the carries, and the algorithm is so simple I'd be surprised if it was wrong. Note that, although an individual increment can take O(lg n) time, the aggregate cost for x increments is O(x).
Is the polynomial multiplication algorithm from the paper wrong, or have conditions that I'm violating? The paper uses a fast fourier transform instead of a number theoretic transform, which could be an issue.
Have a lot of smart people missed an obvious variant of the Schönhage–Strassen algorithm for 40 years? This seems by far the least likely.

I've actually written code to implement this, except for the efficient polynomial multiplication (I don't understand the number theoretic transform well enough yet). Random testing appears to confirm the algorithm being correct, so the issue is likely in the time complexity analysis.


texts: Can interval partition solve by sort by different approach

texts:
The interval partitioning problem is described as follows: Given a set
  {1, 2, …, n} of n requests, where ith request starts at time s(i) and
  finishes at time f(i), find the minimum number of resources needed to
  schedule all requests so that no two requests are assigned to the same
  resource at the same time.

I read from many sources, that the solution often is:

- sort again by earliest time of requests.
- For each requests in sorted request:
     if can choose one resource that can do this requests:
        assign that request to resource
     else
        create new resource
        count++
        assign that request to new resource

The result will be count after finishing algorithm.

However, I approach with different idea. The following is algorithm of my idea:

- Break all time range into 2 parts: (time=start_time, type=start) and (time=end_time, type=end)
- Sort all that events. If time equals, prefer type=end.
- Go from that sorted events, if type = start: count++. else count --

count will be the total machine we need.

My question is: is there any wrong with my approach.

Thanks


texts:
What are the complete specifications that must be documented in order to ensure the correct execution of a particular program written in Java? For instance, if one were archiving a program for long-term preservation, and no testing or porting would be done.

I need to be able to compile and execute the Java program. Thus preserving the byte code or capturing the whole thing as a VMware image are excluded. The JVM could be saved as a VMware image though, and compiled libraries that are linked to the compiled code are OK, too. However, if there are dependencies on the OS, the architecture of the machine executing the JVM, the networking environment, external libraries, specification of the Java version used, etc. etc. these must all be listed. Some tech leaders in Dig Pres claim that any program written in Java will be executable "forever". How to do it?


texts: Minimizing catastrophic risk in Gale-Shapley matching

texts:
In the hospital-resident assignment problem we have to match a large set of med students with a small set of hospitals. Hospitals may accept multiple students, but the number of students is much larger than the total number of residency slots available - several students are left unmatched.

If a particular student's primary concern is simply matching somewhere,  is there any strategy they can adopt that outperforms ranking hospitals according to their true preference?


texts: Transitions between lexicographical orders

texts:
I have six characters: (,),[,],{,}. They are stored lexicographically: '(' < ')' < '[' < ']' < '{' < '}'. So I can store all balanced parenthesis sequences of length $n$ lexicographically and each sequence will have unique number $1 \dots catalan(n)*3^n$. Than I want to get sequence by its number.
Problem: If I have another order, for example '}' < '[' < ')' < '(' < '{' < ']', then all balanced parenthesis sequences again are stored in lexicographical order, but the same sequences will have different numbers, according to these two orders. If I'm given a number of a sequence in second order, can I efficiently recalculate it to the number of the same sequence but in the first order? The main problem is that I don't know the sequence which corresponds to given number in second order. (I wish to find it)
Example: First order: '(' < ')' < '[' < ']' < '{' < '}'
Second order: '}' < '[' < ')' < '(' < '{' < ']'
I get number 1 for sequences with 1 pair of parthenses, the corresponding sequence is [] in the second order. I want to calculate number of [] in first order --- it is 2.
But I don't know how sequence for number 1 in seconds order looks like. I want just by number get the number of the same sequence in first "canonical" order.


texts: How to show that every quadratic, asymptotically nonnegative function $\in \Theta(n^2)$

texts:
In the book CLRS the authors say that every quadratic, asymptotically nonnegative function $f(n) = an^2 + bn + c$ is an element of $\Theta(n^2)$. Using the following definition

  \begin{align*}
\Theta(n^2) = \{h(n) \,|\, \exists c_1 > 0, c_2 > 0, n_0 > 0 \,\forall n \geq n_0: 0 \leq c_1n^2 \leq h(n) \leq c_2n^2\}
\end{align*}

the authors write that $n_0 = 2*\max(|b|/a, \sqrt{|c|/a})$.

I have difficulties proving that the value of $n_0$ is indeed that value.

We know that $a \ge 0$ because otherwise $f$ would not be asymptotically nonnegative. Calculating the roots of $f$ gives us:

\begin{align*}
n_{1/2} &= \frac{-b \, \pm \, \sqrt{b^2 - 4ac} }{2a} \\
        &\leq \frac{|b| + \sqrt{b^2 - 4ac} }{a}
\end{align*}

The case $c \ge 0$ gives us:

\begin{align*}
\frac{|b| + \sqrt{b^2 - 4ac} }{2a} \leq \frac{|b| + \sqrt{b^2}  }{a} = 2\frac{|b|}{a}
\end{align*}

which is two times the first argument of the $\max$ function.

But what about the case $c < 0$? How can we find an upper bound for that? Where does the value $\sqrt{|c|/a}$ actually come from?


texts:
The title puzzle has a setup of.   Www_bbb where there are always 3 w's And 3 b's and 1_ .

The rules of the puzzle are to get all w's on the right side of all b's where location of _ does not matter, to do the puzzle you have 6 possible moves. The move are

1, take the closest w or b to the left and move it to the right of the _(example www_bbb to ww_wbbb)cost of 1

2, take closest w or b to the right and move it to the left of the _(example www_bbb to wwwb_bb) cost of 1

3, take one w or b from the right and jump one letter to move to the left of _ (wbw_wbb to ww_bwbb) cost of 2

4, take one w or b from the left and jump one letter to move to the right of _ (wbw_wbb to wbwb_wb) cost of 2

5, take one w or b from the left and jump 2 letters to move to the right of _ (wbb_wbw to bb_wwbw) cost of 3

6, take one w or b from the right and jump 2 letters to move to the left of _ (wbw_bbw to wbww_bb) cost of 3

The optimal path is to do this with the lowest cost

I am having difficulties on tring to figure out where to start and how to use heuristics of the a* algorithm


texts:
Having a bit of an issue with this question and deciding which of these situations requires dynamic programming and which are NP-complete. In all of these situations the input is a "tip jar" consisting of some number of coins/bills of the various types in D (e.g., five nickels, a dime and three quarters) and the problem is to determine whether the money in the jar can be divided equally between two people:

All three (except the last one) ask how much goes to person A and B if they split the amount down the middle :

A. There are N coins of an arbitrary number of different denominations, but each denomination is a power of 2 (I.E. 2 cents, 4 cents, etc.)

B. There are N bills of arbitrary denominations. In other words, 3 cents or 44, etc.

C. Same as B but now person A and B want to split the tips in two unequal parts provided the difference between them is less than 10 (I.E. |A| - |B| < 10).

My main question is which of these A B and C situations lead to the problem being in P and what makes it NP-complete.


texts: Understanding implemetation of the Toffoli gate using other gates

texts:
I have a system with three qubits as input and I want to demonstrate this equality:

where the left part of the equal is the circuit representation of the Toffoli gate where the first two lines are the control qubits and the third one is the target. On the right side we have the CNOT gate whose matrix representation is

$$
CNOT=\left(\begin{array}{cccc}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 0 & 1\\
0 & 0 & 1 & 0
\end{array}\right)$$

T,S and H are the $\dfrac{\pi}{8}$ gate,phase gate and Hadamard gate, respectively, represented by the matrixes

$$H=\dfrac{1}{\sqrt{2}}\left(\begin{array}{cc}
1 & 1\\
1 & -1
\end{array}\right), S=\left(\begin{array}{cc}
1 & 0\\
0 & i
\end{array}\right), T=\left(\begin{array}{cc}
1 & 0\\
0 & exp(i\pi/4)
\end{array}\right)$$

The Toffoli gate is supposed to do this

My problem is that I don't know how, given some input, for example, the three qubits in the state |1>, the circuit acts on the input. For example, in the second control qubit there is a CNOT gate, so what I have to do is calculate the direct sum of |1> and the qubit which is below it once it has passed through the H gate? This is, before the target qubit reach $T^{\dagger}$, we have the state $|1>|1\oplus H|1>>=-\dfrac{1}{\sqrt{2}}|1>(|0>-|1>)$

Is this correct?


texts: Efficient algorithm for a modified stack to pop the smallest element

texts:
I was practicing the following problem :

  There are a total of $N$ operations.
  At each operation, you can either add an element to the top or remove several elements as described below.

  Inputs are integers. An input other than $-1$ indicates that we have to add the elements in last in first out fashion (LIFO). If the input is $-1$, then we have to remove (pop) all the elements that lie above the current minimum element of the stack, and then pop that minimum element.

  For each $-1$ in the inputs, print $(m,p)$ where $m$ is the minimum element on the stack and $p$ counts how many total elements we popped from the stack.

Example :

N=14 (Total 4 operations)
9
6
8
-1
2
0
6
-1
3
1
2
10
5
-1

In above example : First three operation is inserting operation ,
that is we need to insert them in LIFO Fashion.
So the stack after third operation is : [9  6   8*]
    PLEASE NOTE * represent the element at the top  of the stack.
Fourth Operation is -1 , that is we have to remove all elements
(including the minimum ) , that lie above the minimun elements.
The Minimum Element is 6 ,so we remove 8 and 6 and Hence the stack now is :
[9*]
So answer for fourth operation is (6,2)
6 - the minimum element in the stack and 2 ,as we removed
total 2 elements from the stack.

Operation 5 th ,6 th and 7th are Inserting operations.
After 4 th operation , the stack was [9*]
After 7th operation , the stack looks like [9 2 0 6*]
8th operation is -1 . Minimum element is 0 ,so we should remove 0,6
    from the stack
Hence Answer is (0,2)
As the minimum element is "0" and we removed total "2" elements from
    the stack.

The  stack at the end of eighth operation is:
[9 2]

Operation 9 ,10 ,11 12,13  are inserting operations
So Stack after 13th operation is:
[9 2 3 1 2 10 5* ]
operation 14 is -1.
The minimum element  in the stack is 2. However 2 lies at two
    different positions in the stack .
But we should remove that  2 , which is nearest to the top of the stack
(In order word ,if the minimum lies at more than two positions in the
    stack ,then the one which is closer to the top of the
stack is considered).
So remove 2 at Index 5 (as it is closer to the top of stack) and element
that lies above it in stack.
So after removing 2(the minimum element ) and 10,5 (the elements above
    the min element)
The stack looks like:
[9 2 3 1*]
    Answer is (2,3) //As 2 is the min element and we popped "3" elements

PLEASE NOTE * represent the element at the top  of the stack.

My approach

I am using a simple stack for the above problem. But the constraint is high: $1 \le N \le 10^6$. There are many $-1$'s in the input, so a simple stack will work very slowly. The time limit for the problem is just 1 second.


texts: Are depth-first/breadth-first considered special cases of best-first?

texts:
In literature in general, are DFS and BFS considered to be special cases of best-first search?

Suppose the cost function is:

$f(n) = g(n) + h(n)$

Is it correct to reason that if and $g(n) = depth(n)$, then

If $\forall_n h(n) = 0$, we have a breadth-first search

If $h(n) = i$, where i is the number of nodes visited before visiting, we have depth-first search.

?

Are depth-first and breadth-first search usually considered special cases of best-first search?


texts: A question regarding the Layered Architecture

texts:
Consider the following general form of a layered architecture :

I need to check my understanding about the second layer from top . More specifically I need to check my understanding the regarding the meaning of "User interface management " . According to my understanding , UI management is the code that underlies the UI , for example it is the code for each button and each UI elements . So for example , let us consider that the user needs to generate a report from a system that uses this layered pattern as its architecture. So what happens is the user press the generate report button then the underlying code of this button knows that it need to run the code of generate report system functionality ( which exists in the third layer). After that the generate report code ( lets assume that it is implemented as a class) will refer to the database to get the required info to generate this report and then the info will "propagates upward" until it reaches the UI again to be viewed by the user. So is this right ?  In other words , is this what is the meaning of the User interface management ? and do I understand the mechanism of this architecture ?


texts: Difficulty in understanding a portion in the proof of the $\text{"white path"}$ theorem as with in CLRS text

texts:
I was going through the $\text{DFS}$ section of the Introduction to Algorithms by Cormen et. al. and I faced difficulty in understanding the $\Leftarrow$ direction of the proof of the white path theorem. Now the theorem which is the subject of this question depends on two other theorems so I present the dependence before presenting the actual theorem and the difficulty which I face in the said.

Dependencies:

Theorem 22.7 (Parenthesis theorem)
In any depth-first search of a (directed or undirected) graph $G = (V, E)$, for any two vertices $u$ and $v$;, exactly one of the following three conditions holds:

the intervals $[d[u], f[u]]$ and $[d[v], f[v]]$ are entirely disjoint, and neither $u$ nor $v$ is a descendant of the other in the depth-first forest,

the interval $[d[u], f[u]]$ is contained entirely within the interval $[d[v], f[v]]$, and $u$ is a descendant of $v$; in a depth-first tree,

the interval $[d[v], f[v]]$ is contained entirely within the interval $[d[u], f[u]]$, and $v$ is a descendant of $u$ in a depth-first tree.

Corollary 22.8 (Nesting of descendants' intervals)
Vertex $v$ is a proper descendant of vertex $u$ in the depth-first forest for a (directed or undirected) graph $G$ if and only if $d[u] < d[v] < f[v] < f[u]$.

Theorem 22.9 (White-path theorem)
In a depth-first forest of a (directed or undirected) graph $G = (V, E)$, vertex $v$ is a descendant of vertex $u$ if and only if at the time $d[u]$ that the search discovers $u$, vertex $v$ can be reached from $u$ along a path consisting entirely of white vertices.
Proof
$\Rightarrow$ : Assume that $v$ is a descendant of $u$. Let $w$ be any vertex on the path between $u$ and $v$ in the depth-first tree, so that $w$ is a descendant of $u$. By Corollary 22.8, $d[u] < d[w]$, and so $w$ is white at time d[u].
$\Leftarrow$:

Suppose that vertex $v$ is reachable from $u$ along a path of white vertices at time $d[u]$, but $v$ does not become a descendant of $u$ in the depth-first tree.
Without loss of generality, assume that every other vertex along the path becomes a descendant of $u$. (Otherwise, let $v$ be the closest vertex to $u$ along the path that doesn't become a descendant of $u$.)
Let $w$ be the predecessor of $v$ in the path, so that $w$ is a descendant of $u$ ($w$ and $u$ may in fact be the same vertex) and, by Corollary 22.8, $f[w] \leq f[u]$.
Note that $v$ must be discovered after $u$ is discovered, but before $w$ is finished.$^\dagger$ Therefore, $d[u] < d[v] < f[w] \leq f[u]$.
Theorem 22.7 then implies that the interval $[d[v], f[v]]$ is contained entirely within the interval $[d[u], f[u]]$.$^{\dagger\dagger}$
By Corollary 22.8, $v$ must after all be a descendant of $u$. $^\ddagger$■

$\dagger$ : Now it is clear that since $u$ is the first vertex to be discovered so any other vertex (including $v$) is discovered after it. In point $1$  we assume that $v$ does not become the decendent of $u$, but by the statement that but before $w$ is finished I feel that this is as a result of exploring the edge $(w,v)$ (this exploration makes $v$ ultimately the descendant of $u$, so the proof should have ended here $^\star$)
$\dagger\dagger$ : Considering the exact statement of theorem 22.7 , I do not get which fact leads to the implication in $5$.
$\ddagger$ : The proof should have ended in the $\star$, but why the stretch to this line $6$.
Definitely I am unable to get the meaning the proof of the $\Leftarrow$. I hope the authors are using proof by contradiction.
(I thought of an alternate inductive prove. Let vertex $v$ is reachable from $u$ along a path of white vertices at time $d[u]$. We apply induction on the vertices in the white path. As a base case $u$ is an improper descendant of itself. Inductive hypothesis, let all vertices from $u$ to $w$ be descendants of $u$ , where $w$ is the predecessor of $v$ in the white path. We prove the inductive hypothesis by the exploration of the edge $(w,v)$. But I want to understand the proof the text.)


texts: Time Complexity for Creating a Graph from a File

texts:
Assume that I have a file that consists of pairs of numbers separated by a space. These numbers are the labels for vertices in my graph. For example:

0 5
0 7
2 3
4 5
1 5
.
.
.

I want to create a graph (adjacency list) by reading this file line-by-line. For each line, I will create an edge between the two vertices. Of course, if the vertex doesn't exist yet, then I will add it before creating the edge.

I read here of an algorithm that builds a graph with a time complexity of $O(|V| + |E|)$ where $V$ = set of vertices and $E$ = set of edges. That makes sense to me. However my algorithm doesn't insert the vertices in a loop first and then insert all of the edges in another loop second. My algorithm just adds the vertices as it's looping through the edges.

My question is if my algorithm is $O(|E|)$? It seems like that can't be right, but I read here that when calculating the time complexity you don't take into account if statements. That's exactly what my vertex creation would be -- an if statement that checks if the node exists in the middle of my looping through all the edges.


texts:
Initially the ambiguous grammar is as follows (with some cropped production rules):

<STMT>         -->  <IF-THEN> | <IF-THEN-ELSE>
<IF-THEN>      -->  if condition then <STMT>
<IF-THEN-ELSE> -->  if condition then <STMT> else <STMT>

To resolve the ambiguity, the previous grammar is transformed into the following one in the book I study:

<STMT>           -->  <IF-THEN> | <IF-THEN-ELSE>
<IF-THEN>        -->  if condition then <STMT>
<IF-THEN-ELSE>   -->  if condition then <E-STMT> else <STMT>
<E-STMT>         -->  <E-IF-THEN-ELSE>
<E-IF-THEN-ELSE> -->  if condition then <E-STMT> else <E-STMT>

What I cannot get is that why the following rule is necessary.

<E-IF-THEN-ELSE> -->  if condition then <E-STMT> else <E-STMT>

As far as I think about, the update on <IF-THEN-ELSE> and introduction of <E-STMT> is sufficient to resolve the ambiguity. Could you please give an example refuting my argument? Thanks..


texts: Restoring the minimum vertex cover on bipartite graph from the maximum matching

texts: I had to solve a problem on finding the minimum vertex cover on a bipartite graph, and I used the Kőnig's theorem and reduced it to maximum matching problem on bipartite graph, which is easily solvable, however I'm not sure how to find the actual minimum vertex cover from the edges I have. I easily get the size, however I'm not sure how to find the exact vertices in the minimum vertex cover.


texts: Monte-Carlo Algorithm for counting 'on' bits in a binary array

texts:
Given a Monte-Carlo algorithm (called A) that given a binary array with b 'on' bits (one-bits) returns a, where in a probability of 1/2:
$\frac b 3 \leq a \leq 3b$

How can I use A to build an algorithm that does the same, but with probability $poly(\frac 1 n)$ of success (success means $\frac b 3 \leq a \leq 3b$
 ), using A? if A runs in $O(T(n))$ time ($T(n)$ is much smaller than $n$), what's the runtime of the new algorithm?


texts: lower bound for Renyi–Ulam Game with lies

texts:
Player $A$ thinks of number between 1 and $n$ and ask $B$ to guess the number with minimum number of decision queries (yes or no type ).

Game :

$A$ chooses an element in {1,2....,n}
$B$ tries to guess this number by asking Yes/No
questions.

Binary search is a way to solve the problem, so with $\log n$ many queries will be sufficient to solve the problem when player $A$ does not lie. But if player $A$ lie exactly one time than we can problem with $2\log n$ many queries (by just asking the same query two times). There is an optimal way to solve this problem with $ \log n + \log \log n +c$ , where $c$ is a constant. We will first ask $\log n $ many queries to $B$ and going to get a $\log n $ bits long binary string and now apply binary search on this binary string. In general when A is allowed to lie say $l$ (constant) then also the number of queries need to solved the problem is $ \log n + \log\log n + c $

Questions : 1) How to prove that $ \log n + \log\log n + c$ is a lower bound ?

2) If only $\log n$ many queries are allowed in the general case Is there an approximation algorithm for this game ( original solution = $a$ * algorithm's solution, where $a$ is constant).

3) If $l$ is very large (say order of $n$) Is it possible in that case to correctly find out the guessed number ? I tried to use the  Hamming distance but not able to come up with a precise answer.

Reference :http://ac.els-cdn.com/S0304397503005814/1-s2.0-S0304397503005814-main.pdf?_tid=a880fa14-f82d-11e6-81df-00000aacb35e&acdnat=1487678746_7307f01621c154d9f6e006fc8b992ad0


texts: Running time of this recursive relation: T(n) = (n/2)T(n/2) + O(n^2)

texts:
I encountered these few recursive relations:

T(n) = (n/2)T(n/2) + O(n^2)

T(n) = T(n/2) + T(n/2-1) + ... + T(1) + O(n^2)

I do notice that these recursions can be solved faster by DP. I'm just curious as to:

What's the big-O of the running time of these relations, if we follow the resursive formula
How do you analysis recursive relations like these.
Does the trailing term (in this case O(n^2)) matter?

Any help is much appreciated.


texts:
Me and a friend were discussing how programming languages can perform asynchronous tasks, like waiting 15 seconds before performing another task, and we started a debate.

I know that computers have an internal clock that uses the CMOS battery that can keep track of time, but how does it know it has been 15 seconds since right now and since when I told it to wait 15 seconds without looping infinitely and performing conditional operations, or does it do that?


texts: How does the undecidability of Extensional Martin-Löf Type Theory apply to real type-checking compilers?

texts:
It is claimed in many sources (for example, here) that adding a rule like "if Id(X,Y) then X really equals Y" to a type theory is "problematic" because then its type-checking becomes undecidable. I have read Martin Hoffman's proof ("Extensional concepts in intensional type theory", Section 3.2.2), as well as this SE question, but I still don't see how this creates a problem for a "down-to-earth" programming language.
I understand that deciding whether x:A has type B can get difficult, because there might exist a proof of Id(A,B). But the purpose of any "normal" type-checker is to verify, not to decide, so how is it problematic?
As I see it, nothing prevents the compiler from functioning like this: whenever the user tries to use a value of type X where a Y belongs, if the user has previously provided a proof that Id(X,Y), then we allow it, as if X and Y were syntactically identical. But if such a proof hasn't been provided, we treat it as an error, because the user "hasn't made his case".
My question is: what difficulties, if any, can arise from treating identity types like that?


texts:
I try to figure out linear speed-up of Turing machine.

Prove that any problem that can be solved by a two-tape Turing machine that has time complexity t can be solved by another two-tape Turing machine having time complexity $t′$, where $t′(n) = O(n) + (t(n)/2)$.

The idea seems to show that what the first machine does within two steps the second machine is capable to do within one step. Time complexity $O(n)$  seems to be complexity of encoding input of first machine to input of second machine.

I have a problem with proving this statement and will appreciate any help.

In addition, why only two-tape Turing machine was mentioned, what about one-tape Turing machine.


texts: Data structure to insert, update and sort indexes by frequency and query an index for a particular cumulative frequency

texts:
Here is the description of the data structure I am looking for:

Initial Original Data

Index | Frequency |
  1         3
  2         1
  3         7
  4         2
  5         6

Now it should be kept Sort-ed by their frequency inside the data structure like this,

Index | Frequency | Cumulative Frequency |
  2         1               1
  4         2               3
  1         3               6
  5         6               12
  3         7               19

Now, if I Insert a new entry item (index 6) with frequency of 2, the data structure should maintain it like this:

Index | Frequency | Cumulative Frequency |
  2         1               1
  4         2               3
->6         2               5
  1         3               8
  5         6               14
  3         7               21

Now, a frequency increase of 3 at Index 2 should Update the structure as following:

  Index | Frequency | Cumulative Frequency |
|   2           1               1
|   4           2               2
|   6           2               4
|   1           3               7
|-> 2        1+3 = 4            11
    5           6               17
    3           7               24

You can see above that the frequencies can repeat in many indices. (see index 4 and  6 above).

Now my Query to find the index that contains a cumulative frequency should be resulted in the following way

Query(cumulative frequency) | Result (Index at the data structure)
            3                       6
            1                       4
            20                      3
            7                       1

I have already explored Fenwick Tree (Binary Indexed Tree). It has a very efficient, O(log(n)), way to insert and update frequency at an index and to find the index for a specfic cumulative frequency. But I did not find a way to keep the Indexes sorted by their frequency.

Other structures like Treap, Red-Black tree can store the frequency in a sorted way but I could not find a way to search the index with the specific cumulative frequency using those data structures.


texts: Compression of sequence with Direct Access

texts:
I have a sequence of $n$ integers in a small range $[0, k)$ and all the integers have the same frequency $f$ (so the size of the sequence is $n = f * k$). What I'm trying to do now is to compress this sequence while providing random access (what is the $i$-th integer). I'm more interested in achieving high compression at the expense of higher random access times.

I haven't tried with Huffman coding since it assigns codes based on frequencies (and all my frequencies are the same). Perhaps I'm missing some simple encoding for this particular case.

Any help or pointers would be appreciated.

Thanks in advance.


texts: Are neural network latent representations fitting a Gaussian distribution?

texts:
Neural network latent (or pre-activation) representations are the weighted sums of inputs to neurons in hidden layers before applying an activation function. The vector of representations of neurons in a layer $l$ can be represented as $\mathbf{z_l}$ where $l$ can be, for example, a fully-connected or convolutional layer. At a given time step $n$, the layer representations $\mathbf{z_{l,n}}$ are often fitting a Gaussian-like bell distribution, for example:

 (image source)

This is, I presume, especially likely if the outputs of layer $l-1$ are batch normalized.

It would be interesting to see if moments of the distribution of $\mathbf{z_{l,n}}$ (mean, variance, etc.) can be useful signals for training dynamics.

My question is about finding an explanation or mention of the distribution of representations in the literature. Is there any reference in the literature supporting the observation that the representations of layers during training are normally distributed, or explaining what non-normally distributed layer representations indicates in terms of training dynamics?


texts: On classes $\mathsf{\oplus PSPACE}$ and $\mathsf{\oplus L}$?

texts:
Savitch's theorem provides $\mathsf{PSPACE}=\mathsf{NPSPACE}$.

Is there a class $\mathsf{\oplus PSPACE}$ analogous to $\mathsf{\oplus L}$ and is it known to be equal to $\mathsf{PSPACE}$?

If $\mathsf{L}=\mathsf{NL}$ would it imply $\mathsf{L}=\mathsf{\oplus L}$?


texts:
I am interested in solving the following problem:

  Given an undirected graph whose vertices are weighted, find a subset of vertices of minimal weight whose removal disconnects the graph.

Is there any known algorithm solving this problem?

Here is an attempt at a solution (in python), using network flow:

deg_G = nx.degree(G)
max_weight = max([deg for i,deg in deg_G])+1

st_Weighted_Complement_G = nx.DiGraph()
r = np.arange(len(Complement_G.nodes))

nodes = ['s','t']
edges = []
for i in r:
    nIn = (str(i)+'in')
    nOut = (str(i)+'out')
    nodes.extend([nIn,nOut])
    edges.extend([(nIn,nOut,{'capacity':deg_G[i],'weight':deg_G[i]}),('s',nIn,{'capacity':math.inf,'weight':0}),
                  (nOut,'t',{'capacity':math.inf,'weight':0})])

for edge in Complement_G.edges:
    print(edge[0],edge[1])
    edges.extend([((str(edge[0]))+'out',(str(edge[1]))+'in',{'capacity':max_weight,'weight':0}),
                  ((str(edge[1]))+'out',(str(edge[0]))+'in',{'capacity':max_weight,'weight':0})])

print(edges)
st_Weighted_Complement_G.add_nodes_from(nodes)
st_Weighted_Complement_G.add_weighted_edges_from(edges)

mincostFlow = nx.max_flow_min_cost(st_Weighted_Complement_G, 's', 't',capacity='capacity',weight='weight')
print(mincostFlow)


texts: Find the max partition of unique elements where each element corresponds to the set pool containing that element

texts:
Given a list of sets:

a b c -> _
c d   -> d
b d   -> b
a c   -> a
a c   -> c

The objective is to find the max partition of unique elements with each element corresponding to the set containing that element.

I was thinking about ordering the elements in n * log(n) based on occurrence in other groups and then iteratively start with the lowest, and reorder the list each time based on subtracting the occurrences of other elements within the lists containing the removed element. We are able to do so, as each unique element contains a set of pointers to the lists where the element is contained in.

I can store the unique elements with its occurrences in a Min-Heap, where each unique element has handler to the node within the Min-Heap, thus we can remove the min and also decrease the key one for others within the same list as the contained element in log(n) giving that we have it's handler.

Is the approach feasible at all, if not, what approach I can make use of?


texts: Finding Feature Representation Such That Two Samples Are Similar in Feature Space

texts:
Consider one specific useful function of our human brain: abstraction of object. Take the example of two pictures: if we are told the pictures are similar, we actually make conclusion about the aspects in which they are close to each other.

I'm considering whether machine can have the ability described. More accurately, is it possible to find and select a set of feature representations of two samples (e.g. image, sound) such that under those representations, the samples are similar with respect to a metric, say weighted euclidean norm?


texts:
I am preparing for my exam in formal languages and I need some help with one question from one old exam.

I know that the number of equivalence classes of some regular language L, is the number of states of the minimal DFA for that language.

But how do I give a DFA for one of the equivalence classes ?

Thanks in advance


texts: Evolutionary optimisation algorithm and graph based search

texts:
Simulated annealing and genetic algorithm are examples of evolutionary optimisation algorithms. Both of these methods entail doing a search on a graph of candidate solutions.
Do all other evolutionary algorithms too entail - performing search on a graph?


texts: Does local optimization in a genetic algorithm decrease diversity?

texts:
I want to create a hybrid genetic algorithm for a project to solve really high dimensional problems (1000+) One of my ideas is to incorporate a local optimization method within GA so each individual will be optimized to its local optima before fitness evaluation.
I've read some papers on hybrid GAs with hill climbing. So I understand that doing this will allow a somewhat fairer representation of each individual's search area by preventing the GA from obtaining bad sample from good search regions. It would obviously increase the search completeness.
But I was wondering if adding such a local optimization method would significantly decrease genetic variation? If so, should this be a big problem? And how can one prevent it?


texts: Hardness of a special GAP-CLIQUE problem

texts: In the GAP-CLIQUE$(k,\ell)$ problem, we are given a graph $G$ over $n$ vertices and have to decide whether $G$ contains a clique of size $k$ or no clique of size $\ell$. Using a PCP system, it can be shown that GAP-CLIQUE$(k,\varepsilon k)$ is NP-hard for any positive constant $\varepsilon$ less or equal to $1$. In fact, even GAP-CLIQUE$(k,n^{\varepsilon - 1}k)$ is NP-hard. However, I am interested in GAP-CLIQUE instances, where $k$ and $\ell$ depend on the size of $G$. In particular, I am wondering if GAP-CLIQUE$(3/4n,1/4n)$ is NP-hard.


texts: What is an approximation factor for the Greedy Motif Search algorithm?

texts:
What is approximation factor for the Greedy Motif Search algorithm?
I couldn't find an answer to my question except for the fact that the algorithm has a unknown aproximation factor. I'm not a native speaker and there is almost nothing about it available in my first language which makes it really hard to even understand the definition of the "approximation factor" which may lead to this question that could be rather obvious to answer.

A possible algorithm is shown on page 4:
http://veda.cs.uiuc.edu/courses/fa08/cs466/lectures/Lecture5.pdf

I know that there isn't a known approximation factor because sources like the book "An Introduction to Bioinformatics Algorithms" are stating it.
I haven't really formed thoughts on it, because I'm not certainly sure what the definition of approximation factor is in a case like this. What I mean is: "The approximation ratio, or performance guarantee of algorithm A is defined as its maximum approximation ratio over all inputs of size n".
I would've thought that it may be unknown due to the fact that we could have a input of infinite, which is probably not the right thought in this regard. Another thought I had was that the algorithm has no lower bound for the optimal solution.


texts: Number of $n \times n$ binary matrices whose rows and columns sum to at most $m$

texts:
How many matrices satisfy the following constraints?

$n$ rows
$n$ columns
Cell values are either $0$ or $1$
Sum of any row is at most $m$
sum of any column is at most $m$

Is there a formula or an efficient algorithm to solve this problem?


texts: Input that causes an operation on a binomial heap to run in $\Omega(\log n)$ time?

texts: I was studying binomial heaps and its time analysis. Are there any inputs that cause DELETE-MIN, DECREASE-KEY, and DELETE to run in $\Omega(\log n)$ time for a binomial heap rather than $O(\log n)$?


texts:
minimax complexity has an upper bound complexity of o(b^m), where b are the legal moves in the game and m the depth of the search tree.

For an unbounded tic-tac-toe search, the max depth would be 9, and the number of legal moves goes decreasing as the search deepens e.g.  at depth 0 it's 9, at depth 1 8 and so on. Thus the complexity should be o(m!).

However my current implementation gives 434746 iterations to the minimax function (for the first movement), which leads me to think that my previous analysis is wrong.   Any hints/ideas?

9^9 > 434746 > 9!

Update: as it turns out the complexity relation can be expressed as

T n = n + n* T(n-1)
T 1 = 1

At the start we have n branches but each of these branches has n-1 branches.  For example when we have only 3 moves left the upper bound is 15 (my implementation yields 11).  At the start we have 9 moves the upperbound is 986409 significantly smaller than 9^9.

Is there any way to express this better?


texts:
I have to show if the following statement is true or false. Suppose we have two problems $A$ and $B$. We want to know whether the following is true:

  If $A \le_p B$ and there is an algorithm which solves $B$ in linear time, then there is an algorithm which solves $A$ in linear time as well.

So we recently started with polynomial time reductions and I am not sure what to do for this problem.


texts: Minhash Jaccard to find similarity between documents

texts: I wrote a program to check the similarity of 40 documents. Firstly i use exact Jaccard method and secondly Minhash Jaccard method. I consider that the 2 methods differ if their values are differ more than 0,1. I also run the program for permutations 10,40,100,200,450. Which Jaccard limit must i choose to consider 2 documents as similar?


texts: Given a low resolution video, is it possible to create a higher resolution image

texts:
This question is purely theoretical as I've not been able to find anyone who's done such a thing, so my question is - is it possible, and if not why?

Say you have a short video (CCTV) of a face, or number (car licence) plate, and that video is of too poor quality to discern who that person is or what the number plate says, would it be possible to combine details from several frames of video to interpolate and thus make a clearer image than can be gained from a single frame?

Surely some frames would contain detail that others lack (due to pixel boundaries, shadows etc)?  Are there any examples of machine learning or CV that  do this?


texts:
Given two $n$-bits numbers $a$ and $b$, I am not sure on how to find the runtime of the euclidean algorithm for finding the $\gcd$ of $a,b$. The problem (for me) in here is that apart from the size of $a$ and $b$, I don't feel like I have any other information that will help me  to know what is the runtime of the algorithm. I saw somewhere that the number of rounds is $\log_2 a = n$, but, assuming this is correct, I have no intuition as for why it is such?

My question is for an explanation to how much time it takes to calculate the $gcd$ (as a function of $n$)?
Is it linear in $n$?


texts: On the complexity analysis of quick-union in Algorithms by Sedgewick and Wayne

texts:
I am currently studying Algorithms, Fourth Edition by Sedgewick et al. On page 226, there is an analysis of the quick-union algorithm's find() method's worst case.

This is the algorithm:

  private int find(int p)
  { // Find component name.
      while (p != id[p]) p = id[p];
      return p;
  }

Suppose we have originally an array from 0 to N-1. Now I count N comparisons in total (inside the while) plus N-1 accesses (last comparison is false) to rewrite the value of p. This would give me 2N - 1 accesses to the array. The textbook however says there are 2N+1 accesses.
What am I doing wrong?
Thanks for your time.

Computational complexity is being measured by the number of accesses to the array that we use to model which site belongs to which component. Suppose we want to connect the site labeled 3 with the site labeled 1. In order to do that we just make sure id[3]=1.  The find() method exists to give us the  component to which an element belongs. If we now connect 1 to 4, then we just make id[1] = 4. Now find(3) will be 4, because 3 points to 1 which in turn points to 4.


texts: Big O Notation for Return List is it O(N)?

texts:
what is the Big O for Returning List? aka return list (e.g. list=[1,2,...])

is it o(1) or o(n) and is there  a good website for average big o for different operations including sorting for simple types like list or arrays, etc.


texts:
Let $X\leq Y$.

If $X$ is $NP$-hard, is $Y$ $NP$-hard? I think yes, as if an $NP$ problem is reducible to $X$ in polynomial time, then surely it is also reducible to $Y$ given that $X\leq Y$.
If $Y$ is $NP$-hard, is $X$ $NP$-hard? Not sure how to tackle this. Are some $P$ problems reducible to an $NP$-hard problem? If yes, then I think the answer is no but that's just intuition.

I'm trying to find a problem that is reducible to an $NP$-hard problem but itself is not $NP$-hard. However, I don't know how to identify that a problem is not $NP$-hard.


texts: Is it correct to say that the Clique Problem is in $P$ iff there exists a family of Boolean circuits $C$ to decide Clique whose sizes are bounded by a polynomial? And based on this question, does that imply that there exists an equivalent set of Boolean formulas $F$ to decide Clique whose sizes are bounded by a polynomial? And if there is such an $F$, would there be correct derivations based on propositional logic axioms from any member of $F$ to the corresponding large naive formula for Clique?


texts:
i have a dataset with movies review. I wish cluster my element but inside i have a
categorical / ordinal values.

i seen that exist:

MCA (Multiple Correspondence Analysis)
https://www.utdallas.edu/~herve/Abdi-MCA2007-pretty.pdf
K-Models

I seen both the implentation in Python but seems not very used. (i seen poor example online).
Maybe i don't consider anyway some(maybe simple) way to do this stuff?

Anyone can clarify me on this type of classification?


texts: How to convert an NFA with overlapping cycles into a regular expression?

texts:
If I understand correctly, NFA have the same expressive power as regular expressions. Often, reading off equivalent regular expressions from NFA is easy: you translate cycles to stars, junctions as alternatives and so on. But what to do in this case:

[source]

The overlapping cycles make it hard to see what this automaton accepts (in terms of regular expressions). Is there a trick?


texts: How to deal with $n\sqrt n$ in master theorem?

texts:
In classifying the following formula's asymptotic complexity using master theorem, I have $a = 8$, $b = 4$, and $d = ?$

$T(n) = 8T(n/4) + n\sqrt n$

How do I handle $n\sqrt n$ in this case to get $d$ ?