texts: Group adjacent sections to create groups with biggest value, value is changing in groups

texts:
I have sections 1,2,3...44. We can group only adjacent ones and create groups of maximum size S = 4.
There are two possible variations of this problem:

can not overlap at all (preferred)
can overlap only in outer sections (numbers) /i.e. 1+2+3, 3+4+5+6, 6+7+8 ...

Each section (or group) has it's own value, which is calculated in database query. To simplify, let's assume that it is something like:
SELECT COUNT(*) FROM table WHERE section IN (:sectionNumbers)

Where sectionNumbers parameter is array of sections in group (1,2,3 i.e.)
The value is always greater or equal to value of group with less elements. For example group 1+2+3+4 has value of 100 but the same group without element 4 has value of 70(but it could be 100 as well).
Is there an algorithm which can group those sections (numbers) to maximize sum of group values and in same time try to make those groups as small as possible? If there's not such an algorithm, which is the most similar problem to this one? Maybe I can figure out how to solve this with some similar problem solution.
Not every section has to be in group, but if it is possible, merge them.
Correct result for example could be:
Group: [1], [2+3+4+5], [5+6+7+8], [9+10+11+12], [13+14+15+16], [16+17+18], [19+20+21] ...
Value: (11)   (965)      (146)       (242)         (600)         (611)       (94)

In this example is section 1 alone, because value of group 2+3+4+5 (965) is higher then if we group 1+2+3+4 (i.e. 300)


texts: Two way finite state Automaton NP Compleness definition clarification?

texts:
INSTANCE: A two-way nondeterministic finite state automaton A over single Alphabet I.
QUESTION: Is there an string x (over I) such that A accepts x ?

Since a 2-way NFA with N states, there’s an equivalent nfa with n^(n+1) states. So that’s we get the exponential time from.

I am clear about that, but if I understand correctly the size of the string accepted by the 2Way NFA would still be (in the worst case) polynomial to number of states in the 2Way NFA. Cause if the smallest string accepted was exponential in size, the verification will also take exponential time and thus the problem by definition would not be NP Complete ? Or is there a mistake in this reasoning?


texts: Complexity of active set method for Quadratic Programming

texts:
The Quadratic Programming problem is as follows:

$$\min_x \{\frac12x^THx+x^Tg\}$$

$$Ax\le b$$
where $H$ is symmetric and positive semi-definite.

What is the complexity of the active set method for quadratic programming?

The complexity might be dependant on size of $x$ or both size of $x$ and size of constraints.


texts:
I am trying to construct NFA for all languages ending in 00.

I got this

and this

First one I could convert to DFA by subset construction and I got the correct DFA. For the second one I got the DFA by subset construction, but it is not the correct one since it couldn't accept strings like 100.

Is this beacuse, there is no non determinism in the second NFA? Or what is the general rule in drawing an NFA? We could always provide some form of non determinism?


texts: Is an infinite tape alphabet for TM valid?

texts:
Can I use an infinite alphabet for the tape in a turing machine?

e.g. with input string as (1, 0)*
can I define the symbol 1j as the symbol 1 with j marks on top of it where j in a natural number, to be used on the tape?


texts: How a 10GB network can copy 1TB data in 2 hours?

texts:
In the slides of a university lecture, the following phrase got my attention.

Assuming 10GB network, it takes 2 hours to copy 1TB.

My calculation was as follows.

10GB network = 10 gigabits per second network = 10 x 10^9 bits per
second ------> (1)
1TB = 10^3 x 10^9 x 8 bits --------------> (2)
Then the time to copy 1TB data = (2) / (1) = 8 x (10^12) / (10^10) =
800s = 13.33 minutes

I'm not getting 2 hours as the result of the above calculation, seems like I have got something wrong.
Can someone please educate me on this? Thanks in advance.


texts: How to draw (intuitively) the first and second principal component in PCA methods?

texts:
Assume I have some data in 2D. How to draw the first and second principal component in PCA method?

By referring to the image: the plot on the right is confusing, how I can detect the position of first PCA?


texts:
This is a practice problem from my algorithms class. (And no, it was not assigned as homework. I can't prove this, but you don't have to answer if you don't believe me.) To me this seems like a very difficult problem to show NP-completeness for since due to its abundance of features, it's tricky to mold a known NP-complete problem into it.

  You’ve been asked to organize a freshman-level seminar. The plan is to have the first portion of the semester consist of a sequence of $l$ guest lectures by outside speakers, and have the second portion of the semester devoted to a sequence of $p$ hands-on projects that the students will do. There are $n$ options for speakers overall, and in week number $i$ (for $i = 1, 2, \ldots, l$) a subset $L_i$ of these speakers is available to give a lecture. On the other hand, each project requires that the students have seen certain background material in order for them to be able to complete the project successfully. In particular, for each project $j$ (for $j = 1, 2, \ldots , p$), there is a subset $P_j$ of relevant speakers so that the students need to have seen a lecture by at least one of the speakers in the set $P_j$ in order to be able to complete the project. So this is the problem: Given these sets, can you select exactly one speaker for each of the first $l$ weeks of the seminar, so that you only choose speakers who are available in their designated week, and so that for each project $j$, the students will have seen at least one of the speakers in the relevant set $P_j$. We’ll call this the Lecture Planning Problem.
  Prove that Lecture Planning is NP-complete.

I should note that it isn't explicitly stated in the problem, but I'm assuming that a speaker can only give at most one talk. (But if this seems to prevent the problem from being NP-complete, let me know.)

At first I tried solving some graph-based problems (e.g., Independent Set) using Lecture Planning, but wasn't able to proceed because I'm not sure how you would partition vertices into subsets $L_i$ or $P_j$.

Thus I decided to go to 3-SAT. Even then, it is not obvious how you would solve 3-SAT using this setup. E.g., what would the clauses be? My first thought was they could be the $l$ subsets $L_i$, and you would need a variable to be true in each; this would correspond to picking a speaker for that week. But then how do you incorporate the $P_j$ so as to ensure the formula is satisfied (if satisfiable)?

Also thought about making the clauses the $P_j$, but again, this didn't really seem to work.

I would greatly appreciate a hint. Thanks!


texts:
I am learning about preceptrons and my professor noted that z-scores are a commmon pre-processing step to normalizing input variables. Following this, I am having trouble understanding why z-scores are useful when training a preceptron?

My current understanding is that z-scores allows us to calculate the probability of a score landing inside the normal distribution and compare with scores from other normal distributions. However, how does this translate to perceptrons?


texts:
I have found a dataset which involves surnames dispersion around the world that sorted by population which I use it for a name recommender system.

Its readme page caught my attention because it has mentioned that suitable for cybersecurity and ML fields. Unfortunately on I'm a newbie person in these fields, and I can not understand how it is proper in other topics such as the mentioned topics.

On the other word, I would like to know how sort of names is usable on other topics?


texts: How are kernels (and operating systems in general) written in C?

texts:
I'm trying to understand how you set about writing an OS in something like C.
I've always used C to write applications - using commands like malloc and fork and so on to request things from the OS. If these methods don't exist when you're programming the OS itself (or perhaps the Kernel in particular), how do you write them?
If I can summarise what I'm stuck on:

Am I right in thinking that fork, malloc, etc. are wrapper methods that call the Kernel?

Do the OS components' code call the Kernel the same way you would call a library? Is it more like it's a microservice you make calls to? When we say that Windows provides a 'hosted' implementation of C, is this what the methods are doing under the hood?

When you have a 'freestanding' implementation of C, are the standard libraries written in Assembler, but have C headers?

Are the freestanding components of a hosted C implementation implemented the same way they would be if they were freestanding?

How do you implement memory and process management in C, what is exposed to allows you to do this in the language? (what do you call to interact with memory / devices / interrupts?)

I can imagine this isn't a small question, so I'm more than happy for an answer that includes some further reading but if you'd be able to summarise the main points related to each question that would be super handy for me!
Thanks in advance!


texts: Knowledge driven software development - is it possible?

texts: Model driven software development is driven by UML models and OCL expressions, ontology driven software development is driven by ontologies but is it possible (are there research trends) to introduce knowledge based software development? E.g. there are quite expressive and extensive logic based knowledge representation frameworks like Cyc/OpenCyc (or closed source CogPrime). Maybe it is possible to extend those frameworks with more formal knowledge in accounting and law domains and use these frameworks for code generation? Are there endeavours and what could be the possible paths forward?


texts: How CompCert "proves" different things in its codebase

texts:
In order to understand examples of formal proofs, I am interested in how CompCert applies "proof" techniques. Specifically, I am wondering what a particular example is of something CompCert "proves" in their GitHub repo, so I can get a grasp of how proofs are applied in practice (to something that is somewhat familiar, compiler technology). I have had some minimal experience with Coq so I should be able to follow along. I also have some experience with x86, so perhaps something in the x86 folder would be a good example. Or perhaps something directly to do with the C language (such as Clight), or with memory.

In x86/Asm.v, they have several Inductive definitions, which I think is a proof in itself. For example:

Inductive ireg: Type :=
  | RAX | RBX | RCX | RDX | RSI | RDI | RBP | RSP
  | R8  | R9  | R10 | R11 | R12 | R13 | R14 | R15.

Inductive instruction: Type :=
  ...

Then they have some Definition definitions:

Definition code := list instruction.

Definition is_label (lbl: label) (instr: instruction) : bool :=
  match instr with
  | Plabel lbl' => if peq lbl lbl' then true else false
  | _ => false
  end.

Wondering if this is also a "proof" of some sort since (I think) it is some sort of type.

They also have Lemma definitions, where the explicit proofs are:

Lemma is_label_correct:
  forall lbl instr,
  if is_label lbl instr then instr = Plabel lbl else instr  Plabel lbl.
Proof.
  intros.  destruct instr; simpl; try discriminate.
  case (peq lbl l); intro; congruence.
Qed.

I understand about Coq tactics, but haven't actually written any proofs myself so don't have applied knowledge.

So here we have Inductive is used in a Definition which is used in a Lemma. And then it looks like that lemma is used by other lemmas:

Lemma transl_code_label:
  forall lbl f c ep tc,
  transl_code f c ep = OK tc ->
  match Mach.find_label lbl c with
  | None => find_label lbl tc = None
  | Some c' => exists tc', find_label lbl tc = Some tc' /\ transl_code f c' false = OK tc'
  end.
Proof.
  induction c; simpl; intros.
  inv H. auto.
  monadInv H. rewrite (transl_instr_label' lbl _ _ _ _ _ EQ0).
  generalize (Mach.is_label_correct lbl a).
  destruct (Mach.is_label lbl a); intros.
  subst a. simpl in EQ. exists x; auto.
  eapply IHc; eauto.
Qed.

In this question I am wondering what a proof consists of in CompCert, given some example like the above. I would like to be able to know what I need to write a proof for my own software, by first knowing what CompCert is actually "proving", and how they are "proving it". It seems that there are types (Inductive and Definition), and then proofs (Lemma and Proof). Not sure if the Inductive/Definition things are proofs in and of themselves. Proofs traditionally are essentially just derivation trees of applying rules, but I'm not exactly sure if that is what is happening here. It seems the Coq tactics are just creating a derivation tree, correct me if I'm wrong. Then the lemma/proof is just a derivation tree (a bunch of rules applied) down to the "axioms" (definitions and inductive types). The fact that there could be an electronics error isn't accounted for (I don't think), so the proof is really of a "pure" system in some sense. So practical proofs are applied to pure systems that make some assumptions about the environment.

In the end, I'm wondering, the kind of "proof system" CompCert is. What is making it a good system of formal proofs. Knowing that, I would be able to apply "proofs" to stuff outside of CompCert but in other programming contexts. Also wondering if there is some sort of "specification" that CompCert is formally verified against, or if it is just the "model" (as in the model in model checking vs. specification).


texts:
This is the problem that I have to solve:

  given a node in a binary search tree, find the node
  with the smallest key that is greater than the key of the given
  node..

The algorithm that is often given is this one:

bst_successor(x)
{
        if(x == NULL)
                return NULL;
        if(x.right != NULL)
                return abr_min(x.right)
        y = x.p;
        while(y != NULL && x = y.right)
        {
                x = y;
                y = y.p;
        }
        return y;
}

(you can find further explanations of the problem here.)

Now, I was wondering if this can be another solution:

bst_successor(x)
    {
            if(x == NULL)
                    return NULL;
            if(x.right != NULL)
                    return abr_min(x.right)
            y = x.p;
            while(y != NULL && y.key < x.key)
            {
                    y = y.p;
            }
            return y;
    }


texts: Can you obtain more than two vertex covers from a bipartite graph using a max-flow algorithm?

texts: Applying a max-flow algorithm to the graph it's trivially possible to find one or two vertex covers, inverting source and sink and the directions of the flows. Is it possible to find more?


texts: Is matrix multiplication cheaper than inverse?

texts: In wiki, it is shown that the time complexity of matrix multiplication and matrix inverse is similar. But people always to argue it is easier to do matrix multiplication rather than inverse. Is this claim true? Maybe we need to consider various computation platform, CPU or GPU.


texts:
I have a complete (every vertex is  connected by an edge to every other vertex) undirected positively weighted graph. I want to find vertex-disjoint paths in the graph whose total weight is as large as possible.

To me this sound like a mix of the longest path problem (NP-complete) and minimum spanning tree. Finding the best solution is not required, so maybe some greedy algorithm or something would be a good fit.

Any ideas and algorithms on how to approach this problem?


texts: Regular expression for containing 010 as a subword

texts:
I am studying for a test in computer science, and am encountering difficulties with regular expression. Here is example of a question I don't understand.

I managed to solve the following question:

  Give a regular expression for the language of all words over $\{a,b\}$ which contains one of $aa,bb$ as a subword.

My solution:
$$(a ∪ b)^*(aa ∪ bb)^*(a ∪ b)^*.$$

I am having trouble with the following question:

  Give a regular expression for the language of all words over $\{0,1\}$ which contains $010$ as a subword.


texts: Dynamic array updated by adding arithmetic progressions

texts:
I have an array $a_1, a_2, \dots, a_n$. After $O(n)$ preprocessing, I want to be able to compute each of the following in amortized $O(\log n)$:

Given $l,r,b,d$, for each $i \in \{l,\ldots,r\}$, increase $a_i$ by $b + (i-l)d$.
Given $l,r$, compute $\sum_{i=l}^r a_i$.


texts: How to find the Expected height of a randomly built binary tree

texts:
I would like to find out the Expected height of a binary tree where the insertions are based on a random function. I.e. for each node I visit, there is a $\frac{1}{2}$ probability of choosing right or left. I know that the following property holds for height $h$, but it's difficult to add the probability:$$h_{tree}= 1+max(h_{left}, h_{right})$$I think that this version/random tree differs from the random (search) tree mentioned in CLRS chapter 12.4, where you pick a random element from a sorted list $\{1,\dots, n\}$ and insert based on whether the visited node is greater or less than the inserted element. Because, here we choose each path on each visited node to be random.
Note: the binary tree has all its elements at the leafs and internal nodes are only used for routing (see Figure 1.)
//pseudocode
insert(i, tree):
    if at leaf v:
        split(); //Create a parent u and set its children to be the leaf v and element i.
    else:
        int left = random()
        int right = random()
        if (left > right):
            insert(i, left-subtree):
        else:
            insert(i, right-subtree)

Figure 1:


texts: Training and testing image sizes for classification in computer vision

texts:
When training a classifier for object detection using features extracted from images (eg HoG features), how important is it that the images used for training fed into the classifier in their natural aspect ratio?

For example, regardless of their aspect ratio, would a classifier work if all images were edited re-sized into squares of equal dimensions? (I know that OpenCV does this in its cascaded classifiers).

And if this is possible, then in the end, when we want to test the classifier, do we provide test images in their natural aspect ratio, or would the test images, too, have to be resized into squares?


texts: Problem with implementing Brzozowski's algorithm

texts:
I've been trying to implement Brzozowski's algorithm but I've just discovered that it creates suboptimal automata for a certain class of inputs, having one more state than what is really needed in the result. I can show it on a trivial automaton:

   a b           a   b           a b            a     b            a b
>0 0 1  rev  *0 0,2  -   det  >0 - 1  rev  *0   -     -    det  >0 1 2
 1 1 2  -->   1  1   0   -->   1 2 5  -->   1   -    0,4   -->   1 1 2
*2 0 2       >2  -  1,2        2 2 3        2  1,2    -          2 2 3
                              *3 4 -        3   -     2         *3 1 3
                              *4 4 1        4  3,4    -
                              *5 5 5        5   5    1,5
                                           >6 3,4,5 1,2,5

Here rev is the edge reversal part, where I'd already removed the transitions on epsilon, and det is determinization through powerset construction, creating new states as soon as it discovers them, recursively.

The problem here is this: once I add the extra state to make up for the three different start states after the first edge reversal and powerset construction, nothing ever returns to that state and thus I can't get rid of it later for being equivalent to the original start state.

Is there something wrong with the way I'm doing it? Am I missing something?


texts: Why is the blank symbol not considered part of the input alphabet of a Turing machine?

texts:
Definitions of Turing machines are always explicit about the blank symbol not being part of the input alphabet.

I wonder what goes wrong when you would make it part of the input alphabet, because effectively the blank symbol already seems to be part of the input.

To explain that 'seems' in the last sentence, consider the following.

In the default setup, an infinite number of blank symbols appear on the right of the input. When the tape head moves over the first blank symbol, computation can just continue, as it doesn't need to be an accept or reject state.

Now suppose the computation would subsequently write symbols from the input alphabet to the right of that first blank symbol, then return to the leftmost position while also returning to the start state. It would then 'start over' with a different tape. Effectively, it now starts with a different input, where there are input symbols to the right of the blank that weren't there before. The input seems to effectively include the blank symbol. The further behavior of the machine could now also be different: after encountering the blank again, it will now encounter different symbols to the right.

Supposing this scenario is indeed possible, why wouldn't you consider the blank symbol part of the input alphabet and why wouldn't you allow including it as part of the 'initial' input?

Perhaps it is just a way to define the input such that it isn't always infinite?


texts: Clarification on an Hopcroft book DFA minimization example

texts:
At page 156 there is an example on how to find the distinguishable states for the following automaton:

The following table shows the distinguishable states:

By applying the given definition for distinguishable states, it is not clear why E and G are considered distinguishable. For my understanding there is at least one string, "110" for example, that make them distinguishable, but one cannot test all the possible strings.
I'm sorry if my question sounds dumb but I'm a beginner for this topic.


texts:
Given the following function,
$$f(n)=\prod_2^n \log i. $$
How can I find $f(n)=\Omega (?)$ and $f(n)=O(?)$ ?

I tried to do it, but I have no idea how to do it ..


texts: Algorithm for generating random incrementing numbers up to a limit

texts:
I'm trying to write a code to generate incremental sequences of numbers such as:

0 + 1 + 3 + 5 + 1 = 9
0 + 5 + 1 + 1 + 1 = 8
0 + 1 + 1 + 2 + 1 = 5

I have 3 constraints:

1) I need to have limited number of addends (here it is =5)

2) final sum must be smaller than certain limit ( here limit is <9)

3) addends must be random

As for now, I generate sequences randomly and select only suitable ones. For 2-digit numbers and for long sequences (>8) my algorithm takes significant time.

Is there a better algorithm for such problem?

As least could you tell me, what branch of CS is studying such problems?

UPDATE (algorithm):

0) array = [0,]; // initial array
1) if sum(array) > 99, go to 6)
2) generate random number in [1..99], let's say rand = 24
3) rand = array[-1] + rand // add random number to last value of array
4) array.push(rand) // add the random number to array
5) goto 1)
6) if length(array) < 5, goto 0) // 5 is desired sequence length


texts: Impact of Polynomial Time Algorithm for an NP Complete problem on Complexity Theory

texts:
Assuming (hypothetically) someone proves $P=NP$ by providing a polynomial time algorithm for a $NP-Complete$ problem the Polynomial Hierarchy collapses.

What are the other (important) questions that are still left in complexity theory in respect to the remaining complexity classes?

If possible can someone help with a link where it might have been answered already (which I am guessing it might be) is perfectly fine too.


texts: Let there be a set of cardinality $n\in \mathbb{N}$. Let there also be $n$ subsets of that set. What is the smallest k such that union of some $n-k$ of those subsets is of cardinality at most $k$? The problem is very similar to minimal $k$ union problem, but is more specific, how can I prove it is NP-complete?


texts: Best way for two players to visit a set of graph vertices in a given order

texts:
I am struggling with the following dynamic programming problem:

  Given a complete $N$ vertex digraph  and a list of vertices $List$, find a way for two players who start at vertices 1 and 2 respectively to visit each vertex from $List$ (order matters, i.e. $List_{i + 1}$ should be the vertex visited after $List_i$). Some vertices may appear in $List$ more than once (multiset). It is sufficient for a vertex to be visited by only one of players (i.e. one of them can visit all vertices while the other would remain at his starting position) If one player makes a move, the other stands still (can't make moves in parallel). If the current vertex to be visited is $List_i$, players must move to it directly, i.e. take either $(List_{i - 1}, List_i)$ edge (since the previous move guarantees one of player is in $List_{i - 1}$) or $(List_j, List_i)$, for some $j < i$ ($List_j$ is the position other player stopped at during some previous move). This means the path with $L$ vertices in it consists of exactly $L$ edges. The weight/cost of the path should be minimal. Weight of edge $(i, i)$ is always $0$, all weights are non-negative integers, no multi-edges or loops are allowed.
  Output the cost of such a path.

This is actually a problem from a Russian online judge. The original problem has three players (starting at $1, 2, 3$) in it and also asks to output what player did visit $List_i$, but I reduced the problem for the case of two players which should just make things easier for perception. I think according to the rules I should provide the link for the source problem even if this is a Russian language only website, so here it is http://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=3379 . If someone really needs it, the stated constraints (that shouldn't matter since we are talking about a simplified version of a problem) for the original problem are $(3 \leq N \leq 200)$ and the number of vertices to be visited is at most $1000$ (I swapped denoting letters), no memory/time limits are given.

The problem has a 2D dynamic programming tag.

My thoughts would be to denote $dp_{i, j}$ as a shortest path that visits vertices from $List_i$ to $List_j$, i.e. $(List_i, List_{i + 1}, ...,List_{j - 1}, List_j)$. The answer is would be stored in $dp_{1, L}$, provided that indexing goes from $1$ and $L$ stands for the length of the $List$. The problem is that I don't have a clear idea how to compute this dp-table. I thought of doing someting like $dp_{i, j} = \min_{k \in i..j}\{ dp_{i,k - 1} + cost(k - 1, List_k) + cost(List_k, k + 1)  + dp_{k+1,j}\}$.
Naturally, I'd at first compute all paths of length 2, then 3 and so on. The thing is, I don't understand how to deal with the main 'problem' of this problem, determining when the move is made by player 1 or 2. I thought there would probably have to be different costs of paths for different players, but they actually use the same graph, so all that matters is the position player $x$ ended up at. Filling the DP-table would actually have to consider two cases, the one described above which is guaranteed to exist as in path $dp_{i,k - 1}$ we know that one of players ended up in vertex $k - 1$.  The case where the other player goes from 'some previous' vertex should be taken into consideration as well,
$\min\{ dp_{i,k - 1} + cost(j, List_k) + cost(List_k, k + 1)  + dp_{k+1,j}\}$
 , where $j$ stands for 'some previous' vertex.  While writing this, I also realized that I'd probably need a little hint how to remember the player that visited vertex $List_i$ which is needed for the original problem.

Could you provide me some help please?


texts: Karp reduction from PARTITION to SUBSET SUM

texts:
PARTITION: Given a set of positive integers $A=\{a_1,...,a_n\}$ does there exist a subset of $A$ with sum equal to the sum of it's complement?

SUBSET SUM: Given a set of positive integers $A=\{a_1,...,a_n\}$ and another positive integer $B$, does there exist a subset of $A$ such that it's sum is equal to $B$?

I was trying to prove that if PARTITION is NP-complete then SUBSET SUM is also NP-complete, by reducing PART to SSUM.

My solution was: let $A=\{a_1,...,a_n\}$ be a set of positive integers. Then if A when fed into PART gives the solution $I=\{k_1,...,k_m\}$ (where $k_i$ are the indices of the members of the solution subset), then we construct $A'=\{a_1,...a_n,S\}$ where $S$ is the sum of $\{a_{k_1},a_{k_2},...,a_{k_m}\}$. $A'$ is a solution to SSUM.

My problem with this is that this goes only one way, meaning that we can't show that given A' then A is a solution to PART. Is this a problem? and how could i modify the proof to cover it?


texts: Efficient formulation for binary integer linear programming

texts:
Problem:

There are two types of balls, big (B) and small (S), which need to packed into boxes. One box can contain either:

nothing, or
1 S, or
1 B, or
2 S, or
2 B, or
1 B and 2 S

We are given the weight (float not integer) of each ball (in array $w$). There are some constraints on the weights of the boxes and balls:

The total weight of a box $ \leq T$
In configurations 4 and 6 above, the difference of S should be $ \leq D$
In configuration 6 above, the weight of 2 S should be $\geq$ weight of 1 B

Now I want to minimise the number of boxes used.

My approach

I have modelled this as a linear programming problem with binary variables.

Let there be $M$ boxes, $N_S$ small balls and $N_B$ big balls.

Decision variables:

$b1_j$ is a binary variable which is $1$ if box $j$ is in configuration $1$, else $0$. Similarly for $b2_j, b3_j, b4_j, b5_j, b6_j$ for each box $j$.
$x_{ij}$ is a binary variable which is $1$ if ith big ball is in box $j$, else $0$.
$y_{ij}$ is a binary variable which is $1$ if ith small ball is in box $j$, else $0$.

Constraints:

Total weight of any box $\leq T$
$$\sum_{i}x_{ij}w_i + \sum_{i}y_{ij}w_i \leq T \qquad \forall \, j$$
Weight difference constraint:
$$y_{ij}w_i-y_{kj} w_k \leq D \qquad \forall \, i,j,k$$
Each ball used exactly once:
$$\sum_{j}x_{ij}=1 \qquad \forall \, i$$
$$\sum_{j}y_{ij}=1\qquad \forall \, i$$
Each box is exactly one configuration:
$$b1_j+b2_j+b3_j+b4_j+b5_j+b6_j=1$$
Similarly for other constraints. I hope you get the way I am trying to solve this.

Now the problem is this approach is taking a lot of time to solve using PuLP. For just 15 balls and 10 boxes it took minutes and time is increasing exponentially as the balls increase. I want to solve this for at least 100 balls.

Any help would be appreciated.


texts:
If we have two $NP$ complete problems $\Pi_1$ and $\Pi_2$ such that yes instances of $\Pi_1$ are no instances of $\Pi_2$ and vice versa then we know $NP=coNP$.

  Is the converse true as well?

  That is if $NP=coNP$ then can we find two $NP$ complete problems $\Pi_1$ and $\Pi_2$ such that yes instances of $\Pi_1$ are no instances of $\Pi_2$ and vice versa?

Note for $NP=coNP$ it suffices that all instances of $NP$ complete and $coNP$ complete problems have short certificates and it is not apriori clear if we can find $\Pi_1$ and $\Pi_2$.

  Does any $\Pi_1$ that is $NP$ complete work? If $\Pi_1$ is $NP$ complete then $\Pi_1^c$ (complement) is also $NP$ complete (since $NP=coNP$) and so does taking $\Pi_2=\Pi_1^c$ work?

  Can we get other non-trivial pairs of $NP$ complete problems which are complementarily paired?


texts:
Given a Directed Tripartite graph with 3 Groups of vertices {A, B, C} such that:

Edges from A are directed in B.
Edges from B are directed in C.

Objective: Minimize the number of vertices in B (by keeping few and deleting the rest) such that every vertex in C is reachable from every vertex in A.

I think this can be converted into a flow problem but i am not sure how to go about it. Anyone ?


texts: Turing recognizable -decidable languages-

texts:
I was wondering how to prove that $C$ (which is a language) is Turing-recognizable iff a decidable language $D$ exists such that $C = \{x \mid \exists y \;(\langle x, y\rangle \in D)\}$.
I do not know how to prove this kind of questions, is there any help to help me solve this problem or any problem as this kind.


texts: Can the height of a binary search tree be less than that of a red-black tree?

texts:
This is a question from the book Algorithms by Robert Sedgewick and Kevin Wayne.

"Find a sequence of keys to insert into a BST and into a red-black BST such that the height of the BST is less than the height of the red-black BST, or prove that no such sequence is possible."

I think that in most cases, if not all, the height of a RBT is less than the height of a BST because the RBT ensures balance. However, is it possible for the height of a BST to be less than the height of a RBT? If so, how? Else, how to prove it?


texts: Possible unique paths to reach cell (0,n-1) from cell (0,0) given vector of must visited rows and allowed movement directions

texts:
I've been given a matrix path problem to solve and I need some hints / advises. You're given a $m \times n$ matrix where $m$ is number of rows and $n$ number of columns. When you're in a cell $(i,j)$ you can only move to cells $(i,j+1)$, $(i-1,j+1)$ and $(i+1,j+1)$. Three subproblems have to be solved. I solved first two and I'm stuck solving the third one now.
First one is to find all possible paths from $(0,0)$ to $(0,n-1)$, second one is to find all paths with given obstacles. The third one is kind of tricky. You're given a vector of must visited rows while traversing (they don't have to be sorted). For example: if you're given a vector $[
r_2,r_1]$, you have to find all possible ways to reach row 2, then all possible ways to visit row 1 after visiting row 2 and finally all paths to come to cell $(0,n-1)$ with given restrictions.
Any advises or hints for this one?


texts:
I finished my exam a moment ago and one of the question was to calculate Huffman coding for given probabilities:

A: 0.15
B: 0.2
C: 0.55
D: 0.1

I encoded them as follows:

A: 110
B: 10
C: 0
D: 111

But my lecturer told me that this results seems odd and gave me just a fraction of points for my solution. I argued that all my encodings have unique prefixes. I also said that all my encodings has same length as his (he compared my solution with his reference solution), thus they have same entropy.

Do I really don't understand Huffman codding? I found the theory behind this algorithm amazing so I would like to know.


texts: Space-efficient representation of potentially very large arbitrary-precision rationals?

texts:
I'd like to know if there are good techniques for faithfully and (reasonably) representing rational numbers with forms similar to:

2/3
1/10
4 * 10 ^ 1,000,000,000,000

I know arbitrary precision rationals can be represented by pairs of arbitrary precision integers, and they can be normalized using gcd, so operations like equality testing are efficient. But trying to represent (3) this way would quickly exhaust memory.

(3) can be dealt with efficiently and faithfully with a scientific-notation-like representation, but this can't faithfully represent all rationals.

Is there a way to get the best of both worlds, i.e. be able to both faithfully represent all rational numbers, and deal with very large numbers efficiently?


texts: Algorithm to split bipartite graph into subgraphs

texts:
I'm looking for an algorithm to split a bipartite graph into subgraphs with a specific constraint.  I'm not sure if any existing algorithms solve my problem or not.

I have an undirected bipartite graph where the nodes are customers ($C$) and services ($S$).  I want to split this into several smaller subgraphs, limiting the amount of services in each subgraph to some maximum number $N$.  Unfortunately, looking for disconnected subgraphs is not sufficient because the graph connectivity is too high, so I think I will need to duplicate services.

Formally, I want a set of subgraphs such that:

Each customer $c \in C$ appears in exactly one subgraph
All edges appear in exactly one subgraph (the one in which their customer appears)
Each service $s \in S$ can appear in any number of subgraphs (it's okay to duplicate services to help the split)
Each subgraph should have at most $N$ services (where $N$ is a given constant that is guaranteed to be larger than the highest number of services connected to any single customer)
The subgraphs should have as many customers as possible (without this restriction, it's trivially solvable by putting each customer in their own subgraph with a copy of their services).  That can be a heuristic rather than formally proven.

Can anyone suggest an algorithm for doing this?  The number of nodes is not huge (roughly 1000 customers, 100 services, with each customer connecting to 5 or less services) so brute force approaches or those with bad big-O scaling may be suitable.


texts: What were the research outcomes of the Univalent Foundations Program year (Homotopy Type Theory)

texts:
The Institute for Advanced Study has had a year-long special program devoted to the Univalent Foundations Program.

At the end of this they have produced a book and a code repository.

At the end of this we see a blog entry in Scientific American claiming:

...it could provide a new, self-contained foundation for all of mathematics.

Now this is a bold claim. By contrast I can see humbler claims such as a simple proof in Agda that the sum of two odds is always an even.

My question is: What novel research did these guys actually produce at the end of the year? All the article indicates is that they wrote some code in Agda. Is it just that we have a new view of Martin-Löf type theory with some applications?

Assumptions

I understand the broader ideas of Martin-Löf type theory as it relates to the isomorphism between Types and Proofs.


texts: Item lookaheads versus dot lookaheads for $LR(k)$ with $k \gt 1$?

texts:
I was reading "Parsing Techniques: A Practical Guide, Second Edition" by Grune and Jacobs, which details a bunch of different parsing algorithms. In the section on $LR(2)$ parsing, they mention that unlike $LR(1)$ items, which just have an item lookahead (the token that should appear after the completed $LR(1)$ item), the items in an $LR(2)$ parser also need a dot lookahead (the tokens that should appear after the dot in the $LR(2)$ item).

I'm having trouble understanding what this means, how this lookahead is computed, and why this isn't needed in $LR(0)$ or $LR(1)$ items. Can anyone explain what this means?


texts:
I am given a system with a segmented paging architecture. Both physical and virtual address spaces contain $2^{16}$ bytes each.  The virtual address space is divided in $8$ equal size segments. The page table consist of $2$ byte page table entries.

Question 1:

What is the minimum page size in bytes so that page table for a segment requires at most 1 page to store it?

My interpretation:

There are $2^{16}$ virtual addresses. These are evenly divided between $8$ segments so each segment is $\frac{2^{16}}{2^3}=2^{13}$ bytes.

Now each segments will be divided into pages. Each page will be $2^n$ bytes. So there are $2^{13-n}$ pages (and page table entries) per segment. A page table entry is $2$ bytes long and page size is $2^n$. So $2^{n+1}$.

$2^{13-n} = 2^{n+1}$ gives $n = 6$.  But the answer should be $n = 7$.

I know I made a mistake in page table entry as I didn't get the page table entry concept properly. Is that a f (f+d = memory address)? I am not getting page table entry. Please explain to me this concept.

Question 2:

Assume that page size is $512$ bytes. Each page table entry contains (besides other information) $1$ valid bit, $3$ bits for page protection and $1$ dirty bit. How many bits are available in a page table entry for storing the aging information for the page?

My way of thinking about the answer here:

$16$ bits for physical memory. Page size is $512$ bytes means $9$ bits required. That's $16-9= 7$ bits for a frame.

Now I'm stuck.


texts: What can distributed computing do besides parallel computing?

texts:
I have some experiences of working on clusters and grids for parallel computing. But I wonder what distributed computing can do besides parallel computing?
If I understand correctly, parallel computing is to solve a common task by multiple processors (computers).

Are the Internet and a intranet considered distributed systems? They don't necessarily involve parallel computing, or solving a common task by multiple computers.


texts:
I have a set of related data/objects for which, when undergoing some algorithm, there should be only one valid match. Is there a unique term for this type of set?

A common practical use case would be a list displayed for user selection, or a list of keys that should have a single corresponding entry in a database table.

To illustrate this, here are a few examples:

[True, False]  (boolean)
[Forward, Neutral, Reverse] (state machine status)
[Rare, Medium, Well] (user preference)
[Credit, Debit] (reference type)

In each of these cases, only one element in the set will be contextually valid, where the context may be a database record, an instance of an object in memory, or a question on a survey.

Examples of sets that wouldn't meet this criteria:

[Garage, Kitchen, Bedroom, Bathroom] (rooms in a home)
[Email, Phone, Text] (method of communication)
[All Countries in Europe] (places I visited)

In these cases, the set is used as a bucket from which a selection may be made - but the selection is not necessarily expected to be a single item in the set.


texts: Does Type:Type lead to inconsistency without general inductive types?

texts:
In e.g. Agda , it is possible to derive an element of the empty type by enabling the "type in type" option.

Every proof I have seen (and come up with) involves making a special inductive type definition.
Can a contradiction be derived using type in type but with e.g. only using standard library types?


texts:
I simply need a standard way to find the upper and lower bound of a running time equation (please no shortcuts that only work for this specific problem)....

Example: $T(n)=\frac{c}{5}(4^{\left \lfloor \log_{4} (2n^{2}) \right \rfloor +1}-1)$

I think I understand how to put it in $\Theta$, $\Omega$, and $O$ after I get the bounds....  But I can't figure out a standard way to find the bounds for the running time of an algorithm (it's all unrelated or obscure shortcuts) for any given formula.  Any help out there?

EDIT: Apparently it might be thought I am asking for a specific number for each bound.  I am not, I'm looking for how to find the equation that the bound gives....  For instance, on a problem (not this one), a bound might be $3^\frac{\ln a}{\ln n}+1$ for a certain bound....  The actual problem says to show your work putting the equation into $\Theta$ by bounding it on the upper and lower bounds.  I need to know how to show work for that on this and similar problems.  Make more sense?


texts: P class definition in Garey and Johnson's Computers and Intractability

texts:
I'm reading right now Computers and Intractability by Garey and Johnson. I've found the definition of PTIME complexity class a little strange. This is how it looks:

Let $\Sigma = \{ 0,1\}$. By $\Sigma^{*}$ we denote the set of all finite strings created from symbols from $\Sigma$. If a computation on a Deterministic Turing Machine with input $x \in \Sigma^{*}$ ends in $q_{y}$ (yes-state), it means that TM accepts this input. Language $L_{M}$ recognised by the machine $M$ is given by:

$L_{M} = \{ x \in \Sigma^{*} :$ $M$ accepts $x \}$.

Time complexity function is given by:

$T_{M} = max\{ m : $ there is an $x \in \Sigma^{*}$, with $|x| = n$, such that the computation of $M$ on input $x$ takes time $m$$\}$.

We call program $M$ a polynomial time DTM program if there exists a polynomial $p$ such that, for all $n \in \mathbb{Z}^{+}$, $T_{M}(n) \leq p(n)$.

Then they give such $P$ class definition:

$P = \{ L :$ there is a polynomial time DTM program $M$ for which $L=L_{M} \}$

Does this mean that their P complexity class contains only languages that are composed of yes-instances, i.e. languages recognised by $M$, consisted of $x$ strings such that $M$ always halts in accepting state for every of them as an input? What about input that also causes halting, but in rejecting state $q_{n}$? Shouldn't these be also in PTIME?

Do I understand this correctly? If yes, why they decided to define P class in such way?

P.S. Maybe that matters, I have the first edition of the book (1979).


texts: Parsing based on logical connectives and quantifiers?

texts:
What techniques exist for parsing sentences based on logical connectives and quantifiers? That is, for parsing sentences that are structured "around" logical connectives and quantifiers.

E.g.

  [A] fish is [any] [member of] a paraphyletic [group of] organism[s] that [consist of] [all] gill- bearing aquatic craniate animal[s] that lack limb[s] [with] digit[s].

Here brackets [ ] are used to denote the semantics (quantifiers and connectives) that I'm interested in being able to parse.

Can e.g. the context-free grammar express all sorts of connectives and quantifiers?


texts: proof why worst case for bubble sort is array sorted in reverse order

texts:
Question 1: Let's say we have bubble sort algorithm which sorts numbers in ascending order.
Intuitively one might agree that the worst case input for this algorithm is array already sorted in descending order.
Like I said intuitively one might agree, but I am looking for a proof or formal argument why in such case, array already sorder in descending order is the worst case (and why not other arrangement of elements is worse than that worse case).

Also, aside, if you can comment on my below proof which computes worst case complexity of bubble sort WITHOUT the question 1, I would also appreciate.

In other words i would appreciate: (a) answer on question1, and (b) if my proof below (which doesn't rely on question 1) is correct.

PROOF(might not be written down in best way but hope you get the idea):

Let A[i] be element in array, such that it is x[j]-th biggest where x=[0,1,2...,arraySize]
(e.g. , in array [10,1,22,3,4] 10 is 4th biggest, where x = [0,1,2,3,4]).

By definition in bubble sort, if I compare ALL elements with A[i],
it will lose at most x[j]-1 times (e.g. 10 will lose with with 1,3,4 because it was 4th biggest) with other elements - or in other words I will need x[j]-1 swaps.

It follows that for each A[i] it can be swapped at most x[j] times.

Which gives 0+1+2+..+j = j*(j+1)/2.


texts: How important is to formulate a convex optimization for a proposed algorithm?

texts:
I proposed a new sparse coding algorithm which has good results compared to the baselines, however, it has a non-convex optimization framework.
I solved the problem using a general solver (e.g. Matlab), and although the solution is local optimum, it is still better than other relevant approaches.
So how important is to formulate the problem in a convex setting? especially for publishing the work.


texts: What is the generating function for the sequence $\{kH_k\}_{k \geq 1}$

texts:
I am trying to answer exercise 3.1 from Sedgewick and Flajolet's "Introduction to the Analysis of Algorithms".  That is, I am trying to find the Ordinary Generating Function for the sequence:

$$\{kH_k\}_{k \geq 1}$$

I think that the generating function for this sequence is:

$$H_1 + 2H_2z + 3H_3z^2 + 4H_4z^3 + ...$$

which abbreviates to

$$\sum_{n \geq 0} (n+1)H_{n+1}z^n $$

By inspection, I see that this has the form of the Index Multiply operation on OGFs.  This means that our generating function can be obtained by differentiating the OGF for the sequence

$$\sum_{n \geq 0}H_n z^n$$

I know that this

$$\sum_{n \geq 1}H_n z^n$$

has a well known OGF. But that is for the range $n \geq 1$, and our sequence has range $n \geq 0$.  If I split off the first term $n = 0$, we get the sum:

$$H_0 + \sum_{n \geq 1}H_n z^n$$

And it's now that I've lost my confidence.  Is the method I've outlined above the right way to go in finding the desired OGF?  If it is OK, it seems to rest on the existence of a zeroth Harmonic number.  Is there actually a zeroth Harmonic number $H_0$?

Thanks.


texts: Examples of interesting semantics to study during a small project for a graduate Semantics course

texts:
I have been following the course Concrete Semantics with Isabelle/HOL. At some point we are given the task to verify a program/extend some semantic construction/prove some mathematical fact. I personally prefer to dive a little bit more into operational semantics, so adding new features to the IMP language is the way to go.

The classical extensions are non-determinism/parallel execution. These are described in a variety of books (Winskel, Hennessy or Nielson to cite only classical authors). However, I feel the treatment is rather limited and I'm not sure that can be turned into project, it looks more like a bunch of exercises.

So my question is  are you aware of any simple but interesting extensions of the operational semantics approach to the study of a simple WHILE-program (such as IMP)? I would be looking specially for significant properties that can be proved in that semantics and illustrative examples that may be relevant.


texts: time complexity of erasing repeated entries

texts:
This problem involves the time complexity of erasing entries that occur more than once in a list. I think it might be  $n \log n$.
Problem
The input is a   finite set $S$   and a  finite list $T$ whose entries are in $S$.   The size of the input is  $n= |S|+ |T|$, where $|T|$ is the length of the list.  The output is a list of the elements of $S$ that occur in the list $T$, an output  list having  no repeated elements of $S$.  Does there exist a linear-time, $n p(\log n)$, where $p$ is a polynomial, or subquadratic-time algorithm for this problem?
I would be grateful for any ideas, direction, pseudo-code.


texts: How to find a minimum set of axioms within a set of propositions?

texts: I have a set of propositions, for example $\{a_1,a_2,\dots,a_n\}$. Some propositions depend on others (for example, $a_1,a_2\Rightarrow a_3$, means if $a_1,a_2$ are true, then $a_3$ is true). I want to find a subset of the propositions to be defined as axioms, in the sense that, these propositions being true imply that all the others are true. The number of axioms should be as small as possible. I want to know whether there are some methods?


texts: Is a BST considered a data structure or abstract data type

texts:
and why?

It seem abstract in that it is and idea created and implemented with nodes  arranged a certain way.

But it did not show up in the text here:

https://en.wikipedia.org/wiki/Abstract_data_type

Here:

https://en.wikipedia.org/wiki/Binary_search_tree

they are referred to as data structure b.c. other ADTs can be created from them.

In this train of thought, can I assume that SLLs and DLLs are data structures as well.

Is is not so black and white, perhaps more of a spectrum of classification?


texts: Valid method to prove NP completeness of a problem?

texts:
Suppose we are given that checking if there is a Hamiltonian path in a graph is NP Complete (HP problem). I want to prove that given a graph, node x, and node y, checking if there is a Hamiltonian path between x and y is NP Hard (HPN problem). Here is my proof:

Define a conversion from HP to HPN as follows:

result = False
for x in Nodes(G):
  for y in Nodes(G):
    result = result or hpn(G,x,y)
return result

This clearly solves the HP problem since it considers all possible starting and ending points. Also, HPN is called a polynomial (O(|Nodes(G)|^2) number of times. Hence, HPN must be NP-Hard since if it wasn't HP wouldn't be NP Complete and we know that this isn't true.

I understand I haven't used a reduction in the formal sense in my proof. However, I wanted to know if these sorts of "conversions" are valid in proving NP Hardness/Completeness.

Edit :  The goal was actually to prove NP hardness, not completeness, sorry!


texts: Are there any known implementations of a functional Heap's Algorithm?

texts:
TL;DR: Is an implementation of the Heap's Algorithm adhering to the principals of functional programming possible, and are any implementations of it known? And by "adhering to the principals of functional programming", I mean mainly not relying on the mutation of an object to carry out the algorithm.

I decided to write a function that generates permutations of a list

(permutations [1 2 3])
=> [[1 2 3] [2 1 3] [3 1 2] [1 3 2] [2 3 1] [3 2 1]]

And after some quick searching, somewhat arbitrarily picked Heap's Algorithm.

The problem is, I'm writing in Clojure, trying to adhere to proper FP principals as close as possible, and the entire algorithm seems to hinge on mutating a "global" array while recursing. I worked on this for a couple of hours, and could not find a way of sanely getting the results passed "back up the stack", since the recursive calls just kind of float between mutations:

(defn- swap-v [v i1 i2]
  (let [x (get v i1)]
    (-> v
        (assoc i1 (get v i2))
        (assoc i2 x))))

(defn permutate [coll]
  (let [coll-atom (atom coll)
        result-atom (atom [coll])]
    ((fn rec [n]
       (when (> n 1)
         (let [n-even? (zero? (rem n 2))
               swap-pos #(if n-even? % 0)]

           (doseq [i (range (dec n))]
             ; Recursive call
             (rec (dec n))

             ; Mutate the "array" by swapping two elements
             (swap! coll-atom swap-v (swap-pos i) (dec n))

             ; Then mutate the results array so they can be returned later
             (swap! result-atom conj @coll-atom)) ; Mutate the

           ; ... And another recursive call down here
           (rec (dec n))))

      (count @coll-atom)))

    @result-atom)) ; Dereference the atom and return the results

I tried changing the doseq to a reduction, then I had the results returned nicely, but seemingly nothing to do with them.

I ended up giving up on a FP approach, wrote the above code, and tried to find an example of an FP approach to the algorithm to see where I had gone wrong. To my surprise, I wasn't able to find any. The closest I could find was a Haskell implementation, but honestly, I have no clue what most of the code is doing; it's pretty obscure. I see unsafe in a few places though, so I think they snuck some mutation in there.

Is this possible?

Note, I'm not looking for a review of the code here, since I'm aware this is very imperative-styled, and I already has a review request open.


texts: Tighter analysis of modified Borůvka's algorithm

texts:
Borůvka's algorithm is one of the standard algorithms for calculating the minimum spanning tree for a graph $G = (V,E)$, with $|V| = n, |E| = m$.

The pseudo-code is:

MST T = empty tree
Begin with each vertex as a component
While number of components > 1
    For each component c
       let e = minimum edge out of component c
       if e is not in T
           add e to T  //merging the two components connected by e

We call each iteration of the outer loop a round. In each round, the inner loop cuts the number of components at least in half. Therefore there are at most $O(\log n)$ rounds. In each round, the inner loop looks at each edge at most twice (once from each component). Therefore the running time is at most $O(m \log n)$.

Now suppose after each round, we remove all the edges which only connect vertices within the same component and also remove duplicate edges between components, so that the inner loop only looks at some number of edges m' < m which are the minimum weight edges which connect two previously disconnected components.

How does this optimization affect the running time?

If we somehow knew that in each round, it would cut the number of edges in half, then the running time would be significantly improved:
$T(m) = T(m /2) + O(m) = O(m)$.

However, while the optimization will dramatically reduce the number of edges examined, (only 1 edge by the final round, and at most # of components choose 2 in general), it's not clear how/if we can use this fact to tighten the analysis of the run-time.


texts: What order of growth does a ratio of Bigh-Ohs have?

texts:
Say that $f(n) = \cal O(n^2)$ and $g(n) = \cal O(n)$.

If $h(n)=f(n)/g(n)$,  is it true that $h(n) =\cal O(n)$?

Is it mathematically correct to say that $h(n) = \cal O(n^2)/ O(n) = O(n)$? if not, what would be the correct way to show this?


texts: Optimise 1D cutting stock problem - maximum waste that can be removed with n cuts

texts:
The problem statement can be made as follows. There is a 1D length of raw material that contains "net" and "waste" intervals. Using 2n cuts, sections of material can be removed so that less waste has to be processed later. For a given value of n, where should the cuts be placed so that the amount of waste that is removed is maximised? No greater than a given length c of "net" material is permitted to be cut away in total.

I have a (j * 1) matrix of 0s and 1s. The data is clustered, i.e. values will tend to be found grouped into repeated sections.

I would like to find the largest n intervals of repeated 0s, with the condition that the total number of 1s contained within all intervals combined does not exceed some predefined constant c.

I have found a significant amount written already on efficiently finding a solution when c = 0 (that is, when an interval of digits must not contain 1).

However when a string of repeated 0s is permitted to be "contaminated" with a small amount of 1s my instinct tells me this significantly complicates the problem. It strikes me as a kind of cutting-stock problem, but I hope someone can nevertheless suggest an algorithm that will assist in finding a decent solution.


texts: When should I learn artificial intelligence?

texts:
Straight to the point: I would really like to learn AI.

But I want some advice from experienced CS guys as to when I should jump into Artificial Intelligence.

What prerequisites are needed in order for me to better grasp the AI concepts?


texts: Agents that estimate their own learning rate

texts:
I recently learned about Q-learning, a reinforcement learning technique that directly estimates the expected value of taking an action in a state.

One of the difficulties I see with iterative update techniques is how to set the learning rate hyper parameter. Depending on the environment, a high or low learning rate could be better for more quickly converging on the optimal policy.

I'm not sure how it would be formalized, but it seems like setting this parameter is just another optimization problem. I'm wondering if there exist techniques where the agent itself learns it's own learning rate for a given environment?


texts: Pumping Lemma for $L = \left \{ a^{c}\mid \text{c is a composite number} \right \}$

texts:
$L = \left \{ a^{c}\mid \text{c is a composite number} \right \}$
I feel that this is not a context-free language as checking this constraint requires divisibility checking, but I am facing a hard time in proving that $L$ is not a Context Free Language using Pumping Lemma.
Could please anybody please give me a hint?


texts: Height and depth of every node in Path Compression

texts:
If we have an union-find(disjoint-set) data structure and we are doing an union by rank and path compression for a find operation, how would the depth and height of every node change after the find operation?

I am trying to find the amortized cost of the find operation using the potential function:

$$phi(x) = \sum_{x} height(x) $$

I know this is not the right potential function, however, i am trying to learn more about amortized analysis and i am just practicing by analyzing more data structures.


texts: Laplace's Approximation for graphical models

texts:
A question about Laplace's approximation:

In Laplace's method, we need to find the mode of a function and take second order Taylor's expansion. The first order term will vanish (since the gradient is zero at local optimum), and the second order term will be used to give a covariance of the gaussian. I am wondering if I am doing MCMC and the "point" I found is not local optimum (a.k.a gradient is not zero), will that influence my covariance matrix? Will the matrix be non-positive-definite something like that ?


texts: How Can a Network Server Identify a Specific Computer, Is There a Computer Fingerprint?

texts:
Most of websites put some restrictions on how to use their services; the following paragraphs are taken from “Terms of Service” of such website:

Only one account per computer is allowed to view ads. If more than one account in a single computer view ads, all of those accounts will be permanently suspended.
User can only use a maximum of 3 distinct computers in a 10 days period to view ads. Any attempt to use more than that in that defined period will cause an account suspension.

Question:

No problem with such rules, they must be respected. But I want to know how can servers recognize a specific computer!
Is there a computer fingerprint that would be transferred through HTTP connection and can identify each computer?


texts: How can k-means be reduced to Integer Programming

texts:
The k-means algorithm reduces to computing the objective function:

$
\underset{\textbf{S}}{\operatorname{argmax}}  \sum_{i=1}^k \sum_{\textbf{x}_j\in\textbf{S}_i} \lVert \textbf{x}_j - \mathbf{\mu}_i \rVert
$

for some observations $\textbf{x}_1,\ldots\textbf{x}_n$ to be partitioned into sets $\textbf{S}_i$.

How can this problem be reduced to an Integer Programming problem, which like k-means, is NP-hard.


texts: Finding negative cycle using Bellman Ford

texts:
Given a graph with |V| vertexes and |E| edges, I have to find a negative cycle, if there is one, in a graph.
The wanted complexity is O(|V|*|E|).

I was thinking about using Bellman-Ford to solve the question doing this:
Do |V| iterations of Bellman-Ford, If there were no changes on the last iteration, there is no cycle of negative weight in the graph.
Otherwise take a vertex the distance to which has changed, and go from it via its ancestors until a cycle is found.
This cycle will be the desired cycle of negative weight.

The problem is, that no start vertex is given, and Bellman-Ford notes wether there is reachable negative cycle via the start vertex or not.
Assume that if we start from vertex a there won't be negative cycle and if the start vertex was b there will be one.
So if I choose a as a start vertex I'll miss the negative graph.

How can I solve that?
I thought about trying all the vertexes as start vertex but it won't be O(|E|*|V|).


texts: Minimum number of moves required to transfer items from source bins to target bins?

texts:
I have a set of source bins, each with some number of items, and a set of target bins.  I want to move all of the items from the source bins to the target bins, using the minimum number of moves.  Each move can move any number of items from one source bin to one target bin.

The bins do not have the same size, but the total capacity of source and target bins is the same.

I came up with a few possible formulations for this problem:

1) as a problem of finding the sparsest solution to an underdetermined system of linear equations with variables in $\mathbf N_0$. Lots of literature about this but very sparse (no pun intended) on $\mathbf N$.

2) I could also describe it as finding the min cost flow of a bi-partite network $G=\{U,V,E\}$, fully connected, with  $U$ supply nodes (source bins) and $V$ demand nodes (target bins) with $|U|$ not necessarily equal to $|V|$, edge cost given by

$$c_{uv} =
\begin{cases}
1 &\text{if link is used}\\
0 &\text{otherwise}
\end{cases}$$

and the total demand equal to the total supply.

However, the cost is non-linear so usual min cost flow algorithms do not work here.

3) and I also considered the Split Deliveries Vehicle Routing problem with vehicles (source bins), vehicle capacity (size of source bins) customer demand as the target bins, and a space where all inter customer location distances are 1.

All of these are NP-Hard problems.

My questions:

What is the complexity of this problem?  Can it be solved in polynomial time?  Is there any research literature covering this problem?


texts: How to choose a word to apply the Pumping Lemma?

texts:
I have some questions about the PUMPING LEMMA.
First of all, I do not study computer science, I still go to school, but I'm very interested, so I could make mistakes.
And sorry about my English :)

Now my questions.

What is the easiest way to find a word, to start the Pumping Lemma? Are there some tricks I have to know?
For example I wanted to prove the following language is non-regular:
$$A=\{a^nb^mc^k\mid n,m,k \in N \wedge n\ mod\ 2=0=m\ mod\ 2\ \wedge m<k\}$$

My idea is to choose the word $w=c^n$. But it seems like a bad idea, because if I choose the decomposition $w=xyz$ with $y\not= \lambda$ than I can not pump it up, so that it isn't in A anymore.
With the decomposition we get $x=c^i$,$y=c^j$ and ${c}^{n-i-j}$.
Now I have to choose an $k$ to pump it up, but there is no $k$, were $w$ is not in $A$ anymore, or am I wrong?

For example let $k$ be $0$.
Then we get $xy^0z = {c}^{n-j}. But $ m < k $ \Longleftrightarrow 0<n-j$ for $ j > 0 $ is not wrong, so its not working.

My goal is to find a smart word, so that I do not need a case distinction.

I hope my problem is understandable. If not just ask.


texts: Complete set of basic circuits for McLane's Theorem

texts:
I was assigned a project in which i had to implement some algorithms concerning graphs. The last one is the one described in the title. I have to make an algorithm that uses McLane's theorem (https://en.wikipedia.org/wiki/Mac_Lane%27s_planarity_criterion) to test whether a graph is planar or not. Now, to do that i have to find something called a 'Complete set of basic circuits', as our professor says. I have searched round a bit, and i could not find this term.

As noted in the book,
A complete set of basic circuits S is a set of circles in which:
1) Every circle in S can be expressed as the ring sum of some or all of the circles in S
2) No circle in S can be expressed as the ring sum of any circle that does not belong to S.

Does anyone know how a 'Complete set of basic cricuit' is calculated?
Any guidance would be appreciated.


texts: Hirschberg's algorithm for long strings of bits

texts:
Let $a$ be a large string of bits that is transmitted over a channel that introduces errors (insertions, deletions or substitutions) where the probability of an error happening is $p=0.01$ for each bit. Suppose also that each type of error has a probability of $1/3$ being chosen each time that an error is introduced to $a$. Let $b$ be the resulting string after transmission.

My question is: Given $a$ and an index $i$ in $a$, is there an efficient way to find the closest corresponding index $j$ in $b$? (Suppose that for a given $a$ we are going to request a large number indices $i$, so we must find an efficient way of determining $j$).

I have tried tackling this problem using the Levenshtein distance and trying to find the the optimal sequence alignment using Hirschberg's algorithm which takes $\mathcal{O}(nm)$ where $|a|=n$ and $|b|=m$. Then using this sequence alignment it doesn't matter how many requests you make, you can always find $j$ in $\mathcal{O}(1)$, i.e., each request takes $\mathcal{O}(1)$, but the algorithm still takes $\mathcal{O}(nm)$.

I think this approach might work, however, is there a more efficient way to do this given that $a$ and $b$ are just strings of $1$'s and $0$'s and that the probability of an error happening is relatively low?


texts: The reverse DFA is not working as expected

texts:
Assume a regular language contains all the strings that are ended with "01". We can draw the following DFA for it:

And I reversed the DFA according to this answer (designing a DFA and the reverse of it)

I expected this DFA to accept all strings that start with "10" but it is not. What is my mistake in drawing the reverse DFA?


texts: In what sense if any does java have multiple dispatch?

texts:
I'm trying to get my head around the difference between message passing (with which we are all familiar as by far the most common form of object orientation today) vs generic functions as implemented in CLOS (Common Lisp Object System).

In what sense is it possible to say java has a kind of multiple-dispatch system due to method overloading?

To sketch my understanding, in message passing you might do:

tell obja move objb
tell objb move obja

but where the function is first class and not in any object, you might do:

move obja objb

The part I do think I understand is that with generics there is no dilemma on where to place a function, whereas in message passing you may have to arbitrarily choose which class to put a function on, then just remember which one you put it on. With message passing, if you want to be able to call the behaviour from either, you have to duplicate the code (yes I know there are ways round that, but that's not the point).

I'm not sure I'm really getting the rest of how generics are different yet.

I just found a key reference on this point.

The wiki page on CLOS is also very good.

So, maybe best method is to hold off with the theory and just practice with clojure multi-methods at some point... unless anyone wishes to chip in.


texts:
Say you have two polynomials: $3 + x$ and $2x^2 + 2$.

I'm trying to understand how FFT helps us multiply these two polynomials. However, I can't find any worked out examples. Can someone show me how FFT algorithm would multiply these two polynomials. (Note: there is nothing special about these polynomials, but I wanted to keep it simple to make it easier to follow.)

I've looked at the algorithms in pseudocode, but all of them seem to be have problems (don't specify what the input should be, undefined variables). And surprisingly, I can't find where anyone has actually walked through (by hand) an example of multiplying polynomials using FFT.


texts: Bottom up chart parser adding active arc step

texts:
I am following Bottom up chart parsing algorithm from  Natural Language Understanding book by James Allen. It is

I couldn't understand the 3rd step. I thought that when active arc is added the dot is advanced. But dot is indroduced in the third step. The example says that

This example shows dot is advanced. But step 3 says otherwise


texts: Construct regular expression that contains the substring

texts:
I need to write a regular expression for the following set of strings on Σ = {a, b, c} in which the number of b’s is even, and contains abcba as a substring.

So far, the even number of b's can be constructed using like this:

   (aUb(aUc)*bUc)* or (cUa)*b(cUa)*b(cUa)*

to add the substring abcba, do I just attach it to the end of the regular expression and then repeat it or is there a better way?

Any help is appreciated!


texts: Limited lookahead pathfinding strategies on infinite graphs

texts:
I'm new to pathfinding algorithms and trying to find a good or even optimal heuristic for the following problem:

Say you have a 3D square-lattice cuboid graph with randomly removed edges (with probability $p$). The cuboid has a finite cross section of $n \times m$ nodes and a potentially infinite layer length $l$. Starting on any node in the first layer the agent only has a finite lookahead of the next $w$ layers. At each step: i) you must choose the node in the next layer to move to (you can access nodes on your current layer for this), ii) the layer you were previously on is removed, iii) you view the new layer $w$ steps ahead.

The task is to find a heuristic or strategy that maximises the probability of reaching the end (or for infinite length, the number of layers down the lattice).

I have searched the literature for this sort of algorithm, but most A* based algorithms do not seem to fit the problem (please correct me if I'm wrong).

Are there any standard algorithms for this problem or some good AI protocols that would fit this problem? Even advice on going about designing my own algorithm would be greatly appreciated.


texts: most efficient way to compute number of anagrams of a string

texts:
This is a question from Hackerrank.

Given a string S, find the number of "unordered anagrammatic pairs" of substrings. In other words, find the number of unordered pairs of substrings of S that are anagrams of each other.

Two strings are anagrams of each other if the letters of one string can be rearranged to form the other string.

Here is an example:

For S = "abba" , anagrammatic pairs are $$\{ S[1,1], S[4,4] \},\;\; \{ S[1,2], S[3,4] \},\;\; \{ S[1,3], S[2,4] \},\;\; \{ S[2,2], S[3,3] \}$$

where the $[i, j]$ represents the starting and ending index of each substring (indexing starts at 1)

My solution got accepted but I think it's really slow (I don't know how to analyse the time complexity of it). So I looked in the editorial, and I didn't understand the approach used by the problem setter

Editorial:

How to check anagrams
We need to check if string S1 and S2 are anagrams, we first build frequency table where frequency[i] stores the frequency of character i+a. If two strings have same frequency table they are anagrams.

Approach 1
Traverse over all $O(N \times N)$ substrings and for each substring in $O(N)$ build the frequency table and store after hashing. For each $key$ in hashtable, we add $\frac{value \times (value-1)}{2}$  pairs to answer. A factor of $26$ arrives in complexity due to hashing of frequency tables. Overall complexity: $O(N^3 \times 26)$

Approach 2
Starting for $i=1$ to $N$, we dynamically build frequency for substring $S[i, j]$ where $j$ ranges from $i$ to $N$. So, overall complexity here would be $O(N^2 \times 26)$.

Can someone explain both approach 1 and 2?


texts: How to optimally seperate a student body?

texts:
Students will identify certain students they want to work with. I have therefore decided to split them into two groups where I want to minimize the number of people in Group 1 who want to work with students from Group 2.

I was thinking about creating a source node s, and creating a node for each person ($p_i$) - followed by hooking up the s to each $p_i$. Then I would create, another series of nodes for each person ($q_i$) and hook up each $p_i$ to each $q_i$ if $p_i$ doesn't want to work with $q_i$. Then, I would hook up each $q_i$ to a terminal node t. Each of the edges would have weight 1.

I was thinking about running Edmonds–Karp on it. Now, the solution would yield the maximum bipartite matching of the group (see e.g. here). For each active arc from $p_i$  to $q_i$ in the final diagram, I would separate those two students.

However, I have a bad taste in my mouth after running this algorithm; the bad taste stems from modeling the instance with respect to my intention: If I maximize the complement (the desire not to work with someone), do I really minimize the desire of students to work with each other across the two groups?

If my hunch is correct (in that I'm wrong), please point me in the right direction.


texts: Prove an algorithm. Give directed graph edge weights such that weight of every cycle is 0

texts:
I need to construct a graph with the following properties:

$w(u, v)$ = $-w(v, u)$, for every edge $(u, v) \in E$
Weight of all $u \leadsto v$ paths is equal, for every $u, v \in V$ (this is zero weight cycle property from the title).
Weight of $s \leadsto t$ paths is maximal, for some input vertices $s$ and $t$

Yes, this originates from a flow problem.

And I know an algorithm that performs such construction.
Let $d(u)$ denote $|s \leadsto u|$, the length of every path from $s$ to $u$.

Initialization:

Let $d(s) \leftarrow 0$, $d(t) \leftarrow 1$ and $d(v) \leftarrow$ some real value from $[0, 1)$, for every other vertex.

Advance:

ITERATIONS ← some big value

perform ITERATIONs times:
  new_d ← array for zeros

  for ( vertex v in V )  # visit order is arbitrary
    sum ← 0
    for ( every edge (v, u) )
      sum ← sum + d[u]
    d[v] ← sum / degree[v]    # d[v] is an Arithmetic mean.

  d ← new_d
  d[s] ← 0
  d[t] ← 1
end

That's it. Weight of edge $(u, v)$ is equal to $d(u) - d(v)$. I mentioned maximization of $s \leadsto t$ paths, and they are indeed maximal, as $d(v) < 1$ for every $v \neq t$. Weight can now scaled.

An example of algorithm output:

$0.384 = \frac{(0.461 + 0.539 + 0.154)}{3}$ and $0.154 = \frac{(0 + 0 + 2.30 + 3.84)}{4}$
I didn't draw inverse edges for convenience.

I don't know why this algorithm works as I don't get why arithmetic mean should be picked. Could anyone explain the sequence of thought one could get to arrive at the idea that distance to vertex should be an arithmetic mean of neighbour distances for the graph to satisfy second property?


texts: Updating the Cheriton-Tarjan MST algorithm to use binomial heaps?

texts:
The Cheriton-Tarjan MST algorithm finds MSTs in time O(m log log n) in arbitrary graphs by using a cleverly-modified version of a leftist heap data structure to store edges. It was developed in 1976. The algorithm relies on the fact that leftist heaps can be merged in time O(log n), but also uses the fact that leftist heaps are binary trees and therefore that every node has at most two children.

In 1978, binomial heaps were invented as a cleaner type of heap that supports merging in O(log n) time. Since then, most algorithms that need mergable heaps either use binomial heaps or some other related structure. However, since binomial heaps don't use binary trees, the Cheriton-Tarjan algorithm's main optimization (namely, eliminating unnecessary edges by doing a top-down DFS over the heap) won't work in the same time bounds when run on a binomial heap rather than a leftist heap.

Has there been any work done to update the Cheriton-Tarjan MST algorithm to use binomial heaps rather than leftist heaps?

Thanks!


texts: Proving that $(A \cup B)^* = A^*(BA^*)^*$

texts:
I would like to prove that $(A \cup B)^* = A^*(BA^*)^*$, where * means the Kleene star.

I would like to use induction to prove this equality but I do not how to proceed and how is the best way to set the induction hypothesis.

Could someone please help? Thanks !


texts: Recurrence Substitution Method with multiple givens

texts:
Solve by using the substitution method $T(n)=T(n-1)+2T(n-2)+3$
Given $T(0)=3$ and $T(1)=5$

I kind of understand it with only one given and one recurrence call by expanding the call using what is inside.
ex. if it was $T(n)=T(n-1)+3$
Given $T(1)=5$
I would take the $n-1$ and plug it into the the first equation $T(n)=T(n-1)+3$
and repeat until I can find a general case. After that simplify it to get my answer.

My problem is when I have two givens and two recurrences. I first though about solving each one separately using the first recurrence and then the second but it wasn't making any sense to me.


texts: Trouble Understanding a Remark about Beta-Reduction in the Lambda Calculus

texts:
From page 15 of Lambda Calculus and Combinators an Introduction:

  Note 1.34 If $M \equiv aM_1 \ldots M_n$ where $a$ is an atom, and $M \triangleright_\beta N$, then $N$ must have form

  $$ N \equiv a N_1 \ldots N_n $$

  where $M_i \triangleright_\beta N_i$ for $i = 1, \ldots, n$. To see
  this, note that $M$ is really

  $$ (( \ldots ((aM_1)M_2) \ldots)M_n) $$

  when its parentheses are fully shown; hence each $\beta$-redex in $M$
  must be in $M_i$. Also the same holds for each subterm $\lambda x. P$
  whose bound variable might be changed in the reduction of$M$.

Question: Why is the following not a counter-example?

First let $M_1 = m_1 m_2 m_3$ for atomic constants $m_1$, $m_2$, $m_3$. Then let $N_1 = m_1$ and $N_2 = m_2 m_3$. Then:

$$
aM_1 \equiv a (m_1 m_2 m_3) \equiv (((am_1)m_2)m_3) \equiv ((a m_1)m_2 m_3) \triangleright_\beta a N_1 N_2
$$

Here, if I am correct, then we have a case where

$$
a M_1 \triangleright_\beta a N_1 N_2
$$

which seems to contradict the note.


texts: What is the set of all maximal 3CNF formulas?

texts:
Definition: A maximal 3CNF formula is satisfiable 3CNF formula, but if you conjuct it with another any new different 3 disjuctive literals clause, then the formula becomes unsatisfiable.

Please don't confuse with the definition of minimal 3CNF formula from my previous question What is the set of all minimal 3CNF formulas

This is not the same thing!

But my question about minimal 3CNF formulas in the above link is same for maximal 3CNF formulas here, i.e.

For some natural number n, where n is the number of atomic variables, what is the set of all maximal 3CNF formulas? Is it finite? If it is then what is it's cardinality, i.e. how many different maximal 3CNF formulas is possible?

Note that for k-cnf formula n≥k, so in 3CNF formula n≥3.


texts: Why is linear programming in P but integer programming NP-hard?

texts: Linear programming (LP) is in P and integer programming (IP) is NP-hard. But since computers can only manipulate numbers with finite precision, in practice a computer is using integers for linear programming. Because of this, shouldn't LP and IP be in the same complexity class?


texts: Difference between Normative annexes and Informative annexes in ADA 95

texts:
I was reading the ADA 95 reference manual. I came across these  two words in annexes
 Normative and informative . I couldnt find the difference between those. Your help will  be much appreciated.


texts: Maximize pairings subject to distance constraint

texts:
I have a list of people's locations on a world map and want to pair nearby people up such that the number of pairs is maximized.

For example, subject to the constraint that paired people are within d=10 miles of each other, I might find 742 pairs from a list of n=3000 people's locations.

Possible considerations:

alright to assume the world is a 2D Euclidean plane
alright to assume n < 100000
the distance constraint can be relaxed, for example to a cost function with a high value after 10
as in real life, people cluster in cities, so there might be many people "0 miles apart" in New York City while people in Wyoming are few and far apart.
any leads on the same problem above but for triplets would be great. That is, the same problem, but instead of two you take three people and group them together, preferably with the constraint still being that the three are contained in a d-diameter disc, though other similar constraints are fine.

A simple approach

calculate all-pairs distances.

in the process create an array of pairs sorted from closest to farthest
in the process, for each person, store a list of people within d miles

greedily pair together the closest unpaired people
repeat the following until no progress has been made for a certain number of loops

find an unpaired person p_1 with closest person p_2 <= d miles of them. person p_2 is currently paired to person p_3.
unpair p_2 and p_3 and pair p_1 and p_2. If any exist, pair p_3 to a closest person p_4 that is unpaired and within d miles.

I'm sure there are many interesting approaches to this problem, and would any love input on what research/search terms I could look into to learn more about it, any ideas for algorithms to solve this, and possibly bounds on how well the above algorithm would work on the problem.

Thank you


texts:
I'm resolving this question of Hopcroft and et al Book. Figure 1 below is a marble rolling-toy. A marble is dropped at A or B. Levers $x_1,x_2$ and $x_3$ cause the marble to fall either to the left or to the right. Whenever a marble encounters a lever, it causes the lever to reverse after the marble passes, so the next will take the opposite branch.

I got resolve the question ...

a)Model this toy by finite automaton: To model this toy, a state is represented as sequence of three bits followed by r or a (previous input rejected or accepted). For instance, 010a, means left, right, left, accepted. Then the Transition table is

b)Informally describe the language of the automaton

but not b) question. How I will be able to resolve this question?

EDIT
I see a solution here I modify my question using suggestions and that solution. According that solution exist a case:

Penultimate configuration interrupts is * \ / , where * means / or \; and the ending is 1 and X mod 4 = 0, or (X-3) mod 4 = 0 (X is the numbers of 0's and 1's).

For my question, from this case I get the subcase

Penultimate configuration interrupts is * \ / , where * means / or \; and the ending is 1 and X mod 4 = 0.

Then, the restrictions are: the number of 1's, without the ending, is even and the number of 0's is impar. I will be able to verify that configuration with that restrictions for few instances, but How I will be able to demonstrate that the $x_2$ interrupt configuration is \?


texts: What determines a hit/miss with cache memory?

texts:
I was taught that when a reference is mapped to a cache block, X, for the first time, the word is stored in the cache block, bearing a tag and index that helps identify it for future reads.  Then, when a later reference is deemed to have the same tag and index for cache block X, the value inside the cache block is returned as the read value. Is it the same process for multi-word caches?

I was given a direct-mapped cache: Four 4-word blocks, 32 bits per word, and these word address references...

Ref   Tag   Index   Hit/Miss
134   8     1       Miss
212   13    1       Miss
135   8     1       Hit
213   13    1       Hit

...were what I determine to be the hit/miss for the references because the tags and the index match, even if the value is wrong.  But the answer key tells me the hit/miss for the references are:

Ref   Tag   Index   Hit/Miss
134   8     1       Miss
212   13    1       Miss
135   8     1       Miss
213   13    1       Miss

...so there's more involved when it comes to multi-word caches?  ...or the answer key is wrong.  Can anyone clarify?


texts: Why don't these 2 algorithms take the same time to detect duplicate lines in a file?

texts:
I'm trying to write a small algorithm to detect and delete duplicate lines inside a subset of consecutive lines in a file.
I've come up with 2 similar solutions.
After some quick tests, I've noticed that one of them is much faster than the other, especially on large files.
But I don't understand why.

Here's the quick solution written in pseudocode, first_line and last_line are the first and last lines in the file where the algorithm looks for duplicate lines (I don't know exactly how to write pseudocode sorry):

i = last_line
while i > first_line
    j = i-1
    while j >= first_line
        if line i = line j
            delete line i
            break
        endif
        j = j-1
    endwhile
    i = i-1
endwhile

And here's the slow solution:

i = last_line
while i > first_line
    j = i-1
    while j >= first_line
        if line i = line j
            delete line j
        endif
        j = j-1
    endwhile
    i = i-1
endwhile

In the first solution, when 2 duplicate lines are detected and whose addresses are i and j,
line i is deleted, and the inner loop exits.
In the 2nd solution, line j is deleted, and the inner loop goes on without being broken.

At first, intuitively, I thought that choosing to delete i or j didn't matter.
But after some tests, it seems deleting i results in a much quicker process than deleting j.
I don't understand the asymmetry.
I suspect it's because the purpose of the outer loop is to test the uniqueness of the line whose address
is i, so it would make more sense to delete it as soon as we have an answer and not let the loop goes on.
But I still don't understand completely.

Deleting line i and exiting earlier in the inner loop of the first solution save comparison operations.
But by deleting line j in the 2nd solution, I also save comparison operations, since this j line won't
be processed by the outer loop later.

Why is the first saving of operations much more important than the 2nd one?

I'm sorry if the question is too simple for this site, but I don't know much about algorithms,
and I'm looking for a reasoning which I can understand and would prove that in the general case, deleting i
reduce the number of operations.

In case it matters, here's the real code I'm using, it's written in vimscript:

com! -range=% DelDup call s:del_dup(<line1>,<line2>)

fu! s:del_dup(line1, line2) abort
    let view = winsaveview()
    let p    = a:line2
    while p > a:line1
        let q = a:line1
        while q < p
            if getline(p) ==# getline(q)
                exe p . 'd_' | break
            endif
            let q += 1
        endwhile
        let p -= 1
    endwhile
    call winrestview(view)
endfu

Edit:

I've compared the 2 algorithms with this simple file:

apple
banana
grape
kiwi
orange
tangerine

Then, duplicate each line 256 times:

for i in range(1, 8) | sil %t$ | endfor

Which gives a file with 1536 lines.

Then, I've measured the time it takes for the :DelDup command to delete duplicate lines with the fast algorithm which I wrote earlier:

:Time DelDup

On my machine, the time reported is around 0.1s.

But if I replace the lines:

if getline(p) ==# getline(q)
    exe p . 'd_' | break
endif

With these lines:

if getline(p) ==# getline(q)
    exe q . 'd_'
endif

Then :Time DelDup reports that the command took more than 8s on average.

In case it matters, here's how the :Time command is defined:

com! -count=1 -nargs=+ -complete=command Time call s:time(<q-args>, <count>)

fu! s:time(cmd, cnt)
    let time = reltime()
    try
        if a:cnt > 1
        let i = 0
        while i < a:cnt
            exe a:cmd
            let i += 1
        endwhile
        else
            exe a:cmd
        endif
    finally
        redraw
        echomsg matchstr(reltimestr(reltime(time)), '\v.*\..{,3}') . ' seconds to run :' . a:cmd
    endtry
endfu


texts: Is it possible to transform this grammar into LL(1)?

texts:
This is the original grammar:

S -> ABe
A -> ab | a | ϵ
B -> b

I did try left factoring and this is what I got:

S -> ABe
A -> aX | ϵ
X -> b | ϵ
B -> b

But it still is not LL(1).


texts:
Suppose that we have $N$ integer points on coordinate line: $X = \{x_1, ..., x_N\}$ and we have to add $M$ more points (their coordinates can be rational).

Suppose that we chose some $Y = \{ y_1, ..., y_M \}$. Let's define distance between sets $X$ and $Y$ to be
$$d(X,Y) = \max_{i=1,...,N} ~~ \min_{k=1,...,M} ~ |x_i - y_k|$$

I would like to make $d(X,Y)$ minimum possible. Which algorithm should i use for choosing points $y_1, ..., y_M$ ?

Thanks in advance.

P.S. The original problem is taken from here:
http://www.e-olymp.com/en/problems/3208


texts:
We have a graph $G=(V,E)$ and we need to divide this graph into two clusters $A$ and $B$. Some pairs of vertices $u$, $v$ should not be in the same cluster, and we define an edge $(u,v) \in E$. The total cost of a solution is the total number of edges with endpoints both in the same cluster. My goal is to find an algorithm that returns the optimal solution that minimizes this total cost. The solution does not have to be balanced in the sense that the clusters should be of the same size.

I was wondering what the general name for this problem is and what a proper algorithm is that can solve this efficiently. By a colleague I was pointed into the direction of using a (nice) tree decomposition.


texts: How to design a finite state machine to detect 0110 in the input?

texts:
My task is to design a FSM whose output goes high for a single cycle whenever the pattern 0110 is detected on its input. The patterns may overlap, so an input 0110110 of would cause the output to go high twice- once for the first pattern (0110110), and once for the second pattern (0110110). a is used for the input and f is used for the output.

I am assuming I will need five state bubbles like this.

Is this correct or am I missing some cases based on the pattern going high twice if the pattern overlaps?


texts: Proving correctness of an AVL-Tree colouring algorithm

texts:
I came up with the following recursive algorithm to colour the nodes of an AVL tree so that the resulting tree is red-black. The logic is that the algorithm first colours the root and, recursively, the left and right subtrees black. Since it is an AVL tree, if the root has height h, one path to a leaf takes distance h, and another is h-1. If h is odd the two subtrees from the root have heights h-1 (even) and h-2 (odd), with the even subtree having an extra black node, hence to be coloured red.

(pseudocode)
colour_tree(root(T)):
r <- root(T)
if r = null:
    return
colour(r) = "black"

colour_tree(right(r))
colour_tree(left(r))

if isodd(height(r)):
    if right(r) != null and iseven(right(r)):
        colour(right(r)) = "red"
    if left(r) != null and iseven(left(r)):
        colour(left(r)) = "red"

I am having trouble starting on a proof of correctness for this algorithm. I know that for any tree with height h, there are at least $\lceil (h+1)/2 \rceil$ blacknodes, and intuitively it seems like I'd have to perform induction on the height, but I am not sure where to start. Thanks.


texts: Do expressions have much to do with referential transparency?

texts:
In other words, can a programming language be referentially transparent even if not everything is an expression?

And can you say that if in a programming language, everything is an expression, then it is referentially transparent?


texts: Find decidable sets such that $A$ reduces to $B$ but not vice versa

texts:
I am stuck in this problem, so any help is appreciated. The problem asks to show that there exists decidable sets $A$ and $B$ such that $A \leq_{m}^{p} B$ but $B \not \leq_{m}^{p} A$, and that $A$, $B$ and $\overline{A}$ and $\overline{B}$ are infinite. Here, $\leq_{m}^{p}$ refers to many-one polynomial time reducibility.

I have a hunch that this may have something to do with letting $A$ be a decidable set such that $A \in \mathsf{EXP}$, but $B \in \mathsf{P}$, so that the reduction cannot be done in polynomial time.


texts: Similarly structured loops with different big-O time complexities?

texts:
I have a function:

int sum = 0;
for (int i = 1; i < n; i*= 2)
  for (int j = 0; j < n; j++)
    sum++;

From my understanding this is $O(n\log(n))$ because the inner loop runs $n$ times for every time the outer loop runs, and the outer loop is running $\log(n)$ times. Putting them together gives me $O(n\log(n))$, which I understand. However, the following loop:

int sum = 0;
for (int i = n; i > 0; i/= 2)
  for (int j = 0; j < i; j++)
    sum++;

I see this as $O(n\log(n))$ because the outer loop is running $\log(n) + 1$ times still and the inner loop runs $n + n/2 + n/4...$ whose sum will be some coefficient $c$ times $n$. Together with the outer loop simplifying to $O(n\log(n))$ but it turns out it is actually $O(n)$ however I don't see how it is?


texts:
If I have reference section of a paper, with how much probability can I predict one of the authors of that paper ?
Any recommendations on suitable algorithm to build a model are appreciated.
Also how to construct the data set for building the model ?


texts: Parsing HTML from HTTP vs HTTPS websites

texts: Are there any alternative steps to receiving and then parsing the HTML of an unsecured site (HTTP) vs a secured site (HTTPS)? I am asking as I learnt that there is encryption involved in the HTTPS website.


texts:
I'm not sure if I understand the following definition of the (well-known apparently) Graphic TSP, also known as graph-TSP :

  ...graph-TSP, that is, the traveling salesman problem where distances between cities are given by any graphic metric, i. e., the distance between two cities is the length of the shortest path in a given (unweighted) graph.

this is from Mömke and Svensson's paper : https://arxiv.org/pdf/1104.3090.pdf

I understand this as follows :
- one is given an input graph, say G, that is unweighted (and supposedly connected).
- one then can construct a complete graph, say G', where cost of edge (u,v) is the minimum distance between u and v in G.
- obtaining an optimal TSP solution in G' results in an optimal solution for the graphic TSP on G.

Is this correct?


texts:
The book computers and Intractability mentions that Hamiltonian Path problem is not NP-complete in DAG.
But if Hamiltonian Cycle is NP-complete in digraph then I can split a vertex and create two vertices ${s,t}$ which will make the graph acyclic and then ask for $s\rightarrow t$ hamiltonian path in that DAG. These two problems are equivalent. Then why is one NP-complete and other is not ?


texts:
Definition: Well-Characterized also known as Good-Characterized is defined as follows:

  Problem that have Yes and No certificates i.e., are in NP $\cap$ co-NP, are
  said to be Well-Characterized. (Reference: V.Vazirani,
  Approximation Algorithm)

Does exist any Well-Chracterized problem that is also being NP-Complete? I don't looking for any proof, I just want a real-world example of such problem.