texts: Properties of the filtered preference list (phase 1) in the Stable Roommates problem

texts:
I'm currently working my way through An Efficient Algorithm for the “Stable Roommates” Problem by Robert Irving (Journal of Algorithms, 6:577–595, 1984).

On page 7 the paper starts with describing the algorithm for phase 2. The only thing that phase two does is reducing all-or-nothing cycles.  The paper seems to assume that after phase 1, the proposal and filter phase, the filtered preference lists can be divided into three categories:

One or more of the filtered preference lists is empty. Therefore no stable roommate assignment exists.
Each filtered preference list contains only one element. Therefore a stable roommate assignment exists.
The filtered preference list contains an all-or-nothing cycle (wikipedia calls this rotations).

But why can't you have filtered preference lists that contain more than one element but does not contain an all-or-nothing cycle.


texts: What's the difference between a reorder buffer and an instruction window?

texts:
In an out-of-order processor, what is the difference between a reorder buffer and an instruction window?

Wikipedia says:
"In particular, in a conventional design, the instruction window consists of all instructions which are in the Reorder Buffer (ROB)."

Does this mean that the instruction window isn't a seperate hardware structure?


texts: Does $\mathrm{SUBEXP}\subset \mathrm{P}/\mathrm{poly}$ imply anything?

texts: The assumption $\mathrm{SUBEXP}\subset \mathrm{P}/\mathrm{poly}$ seems to yield nothing interesting at all. Is that true?


texts: termination of two concurrent threads with shared variables

texts:
We're in a shared memory concurrency model where all reads and writes to integer variables are atomic.

do: $S_1$ in parallel with: $S_2$   means to execute $S_1$ and $S_2$ in separate threads, concurrently.
atomically($E$)   means to evaluate $E$ atomically, i.e. all other threads are stopped during the execution of $E$.

Consider the following program:

x = 0; y = 4
do:                 # thread T1
    while x != y:
        x = x + 1; y = y - 1
in parallel with:   # thread T2
    while not atomically (x == y): pass
    x = 0; y = 2

Does the program always terminate? When it does terminate, what are the possible values for x and y?

 Acknowledgement: this is a light rephrasing of exercise 2.19 in Foundations of Multithreaded, Parallel, and Distributed Programming by Gregory R. Andrews.


texts: What is the most efficient way to solve a workshop scheduling problem?

texts:
I am trying to design an algorithm to solve a workshop scheduling problem.

The problem is as follows:
I have to schedule a workshop consisting of a finite number of time slots, and a finite number of students. Each time slot has a capacity, which must be fulfilled. Each student has a list of preference corresponding to a set of time slots, where he/she wants to work.

For instance picture the following work shop:

where time slot 1,1 has capacity 3 and time slot 1,2 has capacity 4 and so on.

I want to optimize my scheduling so that students has the least overhead as possible. Overhead is defined as having to "wait" between work. For instance the following picture shows a student, that can work all three time slots in a day, but is only assigned to the first and the last, thus having one time slot overhead.

Thus: My objective function is to find a feasible solution while minimizing the students' total overhead.

My idea on how to solve it, is to construct a graph (see underneath), run a max-flow algorithm to determine a feasible solution, compute the total overhead (penalty), introduce some sort of randomization to change the schedule and compute the new overhead. Repeat the last 3 steps an arbitrary number of times to find the local minimum.

Graph:

Explanation of graph: The above graph shows 5 students, which each can be connected to up til 3 time slots. Each edge between a student and a time slot symbolizes that the student wants to work on that specific time slot. Each of these edges has a capacity of 1. The source node, S has edges to every student with the capacity of infinite, because each student can work as much as he/she wants. Each edge from a time slot to the sink node T, has a capacity, of the specific time slot's capacity.

Pseudo code

function solve-this(timeslots, students) {
    create graph from time slots and students
    run ford-folkerson max-flow algorithm to determine a feasible solution
    while(local optimal solution not found) {
        compute penalty / overhead
        if(computed penalty < current solution) {
            current solution = this solution
        }
        change schedule based on some sort of randomization factor
    }
    return solution
}

I also thought about modify the min-cost-max-flow algorithm, and then dynamically change my costs for non-directly-adjacent edges. For instance if we pass flow through student1 and time slot 1, then we should modify all other edges from student 1 to the non-directly-adjacent edges to have a cost or penalty.

Is there any smarter way to do this? Is this the best way to find an somewhat optimal solution, without checking every possible schedule?

Any help, comments and/or feedback is greatly appreciated.


texts: Simple examples of Artificial Intelligence

texts:
I am having trouble understanding the concept of AI.

Is AI just a software that uses Probability, Linear Algebra and some advanced Mathematics to make independent decision ?

Please give me some simple examples of AI.


texts: Both a language and its complement are not context free

texts: Is there a language $L \subseteq \{a\}^*$ such that both $L$ and its complement are not context free?


texts: Proving that EXP doesn't have polynomial-size circuits

texts:
How to prove for all $i\in\mathbb{N}$, there exists a language $A\in\mathrm{EXP}$ such that no family of boolean circuits of size $n^i$ decides $A$?

I have a reminder that says
$$ \mathrm{EXP} =\bigcup_{c\in\mathbb{N}} \mathrm{DTIME}\left(2^{n^c}\right). $$

Thought of building a TM that on input $x$ of size $n$, finds a function $f_{n}$ such that there is no circuit of size $n^k$ that calculates it. Go through all functions and for each one go through all the circuits and check whether they calculate the function. If none of them calculates it then it's what we want.

I don't know how to show this is $\mathrm{EXP}$ or how to prove this solves the problem.


texts:
There are many methods to prove that a language is not regular, but what do I need to do to prove that some language is regular?

For instance, if I am given that $L$ is regular,
how can I prove that the following $L'$ is regular, too?

$\qquad \displaystyle L' := \{w \in L: uv = w \text{ for } u \in \Sigma^* \setminus L \text{ and } v \in \Sigma^+ \}$

Can I draw a nondeterministic finite automaton to prove this?


texts: Which language families admit inductive definitions?

texts:
I am self-learning about formal languages. I learned that the family of the regular languages can be defined inductively, in terms of the operations they are closed under (namely the smallest fix-point). This definition doesn't rely on regular grammars or finite state machines.

I wonder which other families of formal languages can be defined inductively; in particular, I am interested in the classic classes of the Chomsky hierarchy but also the (semi-)decidable languages.


texts: Label groups of vertices in a graph in an efficient manner without BFS/DFS

texts:
I have a graph with a set of vertices $\mathcal{V}$ and a set of edges $\mathcal{E}$. There exists a path between every 2 vertices in the graph. To each edge there is an associated weight $w(e), e \in \mathcal{E}$. I define a (global) threshold $T$ such that if $w((u,v)) < T$ the two vertices $u,v \in \mathcal{V}$ are in the same group: $g \in \mathcal{V} \rightarrow \mathbb{Z},   g(v_1) = g(v_2)$. This behaviour is transitive. The goal is to label the distinct groups starting from zero (the order of the groups is irrelevant). I know that this can be achieved trivially with BFS or DFS, but I want to avoid using those.
The idea I came up with is to iterate over the vertices, go over their 1-ring neighbourhood, and create a new group every time that $w((u,v)) < T$ for any of the edges and neither $u$ nor $v$ have been assigned a group (for example $g(u) = g(v) = -1$). Additionally, each group is assigned a label, which is initially equal to the index of the group: $h:\mathbb{N} \rightarrow \mathbb{N}, h(g(u)) = g(u)$. If at some point $w((x,y)) < T$ and $w((y,z)) < T$, but $g(x) \ne g(z)$ then set $h(g(x)) \leftarrow \min(h(g(x)),h(g(z))$ and $h(g(z)) \leftarrow h(g(x))$. After this procedure it should hold: $h(g(u))=h(g(v)), u,v \in \mathcal{V}$ if there exists a path from $u$ to $v$: $\pi = e_1,...,e_n$ such that $w(e_i) < T$. Is the algorithm I came up with correct or did I miss something? As it is currently it requires $|\mathcal{V}|$ memory for each array $g,h$. Is there a way to optimize this further?


texts: Exhaustive search algorithms for np-complete problems

texts: Somewhere in the forum (a question about p vs np) I read that no exhaustive search algorithm exists for np-complete problems with better time complexity than $2^N$, however the subset sum problem has an algorithm with worst case complexity $O(2^{N/2}$), this looks much better than $2^N$, what is wrong with this?


texts:
I asked this question on stackoverflow, but was suggested to post to same here. So here goes.

The following problem was asked in the recent October 20-20 Hack on Hackerrank :

  Evil Nation A is angry and plans to launch N guided-missiles at the
  peaceful Nation B in an attempt to wipe out all of Nation B’s people.
  Nation A’s missile i will arrive in nation B at the time ti. Missile i
  communicates with its headquarters by unique radio signals with a
  frequency equal to fi. Can you help the peaceful Nation B survive by
  building a defensive system that will stop the missiles dead in the
  sky?

  Defensive system:

  The only way to defend Nation B from the attacking missile is by
  counter attacking them with a hackerX missile. You have a lot of
  hackerX missiles and each one of them has its own radio frequency. An
  individual hackerX missile can destroy Evil Nation A’s attacking
  missile if the radio frequency of both of the missiles match. Each
  hackerX missile can be used an indefinite number of times. Its
  invincible and doesn’t get destroyed in the collision.

  The good news is you can adjust the frequency of the hackerX missile
  to match the evil missiles’ frequency. When changing the hackerX
  missile’s initial frequency fA to the new defending frequency fB, you
  will need |fB - fA| units of time to do.

  If two evil missles with same
  frequency arrive at the same time, we can destroy them both with one
  hackerX missile. You can set the frequency of a hackerX missile to any
  value when its fired.

  What is the minimum number of hackerX missiles you must launch to keep
  Nation B safe?

  Input Format: The first line contains a single integer N denoting the
  number of missiles.  This is followed by N lines each containing two
  integers ti and fi denoting the time & frequency of the ith missile.

  Output Format: A single integer denoting the minimum number of
  hackerX’s you need to defend the nation.

  Constraints:
  1 <= N <= 100000

  0 <= ti <= 100000

  0 <= fi <= 100000

  t1 <= t2 <= … <= tN

The problem gets reduced to a Minimum Path Cover Problem which is to be solved in O(nlogn) time based on the constrainsts.
However the best solution to a Minimum Path Cover Problem is using the Hopcroft–Karp algorithm, that leads to the Maximal Matching Problem. The solution to which is O(n^2.5).
But the following solution by icyrhyme9733 solves the problem in O(nlogn) :

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int n;
    cin >> n;
    vector<pair<int, int> > vp;
    for(int i = 0; i < n; ++i) {
        int t, f;
        cin >> t >> f;
        vp.push_back(make_pair(t + f, t - f));
    }
    sort(vp.begin(), vp.end());
    reverse(vp.begin(), vp.end());
    vector<int> last(vp.size(), numeric_limits<int>::max());
    for(int i = 0; i < vp.size(); ++i) {
        *lower_bound(last.begin(), last.end(), vp[i].second) = vp[i].second;
    }
    cout << lower_bound(last.begin(), last.end(), numeric_limits<int>::max()) - last.begin() << endl;
    return 0;
}

Is it solving a Minimum Path Cover Problem in O(nlogn) time ?  Or is there an optimization that I am missing ?

I found a similar problem on this thread. They have taken advantage of the fact that the graph is an Interval Graph. Even though being very similar, the same solution cannot be implemented, as the intervals are inverted.


texts: Is finding all valid nets of a polyhedron NP-hard?

texts:
Suppose I wanted to find all valid nets of a polyhedron. Is this kind of problem NP-Hard?

My guess is that it is. If you were to increase the "complexity" of the polyhedron (maybe this is the number of faces?), there is no "shortcut" to discovering all the nets; you would have to enumerate all combinations. This sort of "listing all combinations" without any shortcuts seems to be similar to other kind of NP problems I've seen. Is my thinking correct? Can someone else explain their thought process that helps them decide whether this problem is NP-Hard or not?

If this problem is not NP-Hard, how do you classify this and why?


texts: How to use XML format of graphs in Graph neural network?

texts:
I have manually labeled directed graphs that I need a GNN to train on and then predict when given a new directed graph, what the labels for the vertexes in the graph should be. My graphs are in the form of XML . How to use this format in graph neural network ?
Should I convert XML format into some specific format , If yes then what and how it could be done ?


texts: What does it mean that B-tree leaves carry no information?

texts:
According to Wikipedia B-tree page, Knuth's definition fifth property is "All leaves appear in the same level and carry no information.".
What does it mean that they carry no information?
Does that mean that there are no more pointers to children nodes? (kinda redundant to say that as they are the leaves no?)
In the more literal meaning I understand from it that there is actually no information there (AKA the nodes values vs. the key which is used to search) but that doesn't make sense as each  key in a B-tree appear only at one node and thus must have a value associated to it or at least a pointer to the data.
Please notice that I'm not referring to a B+ tree where indeed there is an extra layer just for the data/values/information and the keys are indeed duplicated between nodes levels.


texts: Filling Rows of a Matrix Subject to Conditions

texts:
I'm seeking to write an algorithm which, given a value of N, will fill a matrix consisting of (N+1)(N+2)(N+3)/6 rows and 4 columns with the integers from 0, ... , N, subject to the conditions that:

The sum of values in any row is N
No rows are repeated (this should ensure that every such possibility is listed)

For example, with N=2, we have 10 (=3*4*5/6) rows:

2 0  0 0
1 1  0 0
0 2  0 0
1 0  1 0
1 0  0 1
0 1  1 0
0 1  0 1
0 0  2 0
0 0  1 1
0 0  0 2

I've been trying for a while to program this (in R, for what it's worth), but I'm struggling to get anywhere. Any advice?


texts: Karp hardness of searching for a matching split

texts:
UPDATE: In 2 days, if no more convincing answer is posted, then bounty of 50 rep. will go to xskxzr. Due to lack of connectedness and a clean & clear cut, the bounty is still open for 2 days. (UTC is now 17 Sep 01:57)

This is yet another follow-up question in the series:

Karp hardness of searching for a matching cut

Karp hardness of searching for a matching erosion

In this question, we further restrict the notion of a matching erosion (which is already a restricted notion of a matching cut). Formally, our definition is as follows.

Given an undirected graph $G(V, E)$, a matching split $M=(A, B)$ is a partition of $V$ into two disjoint subsets, i.e. $A\cap B = \emptyset \land A\cup B = V$ that satisfies the following conditions:

$G[A]$ and $G[B]$ are two disjoint induced subgraphs
The edge set of the cut $M = \{uv\in E\vert u\in A \land v \in B\}$ is a matching (here, we abuse the notation a little bit, $M$ is both the partition $(A, B)$ and the edge set of the matching cut)
Each vertex $u\in A$ is incident to exactly one edge in $M$
Each vertex $u\in B$ is incident to exactly one edge in $M$

Clearly, we should have $|A|=|B|=|V|/2$, hence the name of this concept.

Our decision problem Matching Split naturally asks whether a given graph $G$ has a matching split.

Our question is: What is the complexity of deciding Matching Split?


texts:
I am trying to solve a 25k clauses 5k variables SAT problem. As it has been running for an hour (precosat) and I'd like to solve bigger ones afterwards, I'm looking for a multi-core SAT-Solver.

As there seem to be many SAT-Solvers, I'm quite lost.

Could anyone point me out the best one for my case?

I'd also be happy if someone could give me the approximate time (if possible).


texts:
Are there variations of the classic graph coloring problem that the number of neighbors in the same color is limited but not zero (in the original problem the limit is zero)?
Problem: Given a graph $G$ and two integers $c$ and $p$, is it possible to color the vertices of $G$ with $c$ colors such that for every vertex $v$ with color $\text{color}(v)$,
$$| \{ w \in N_G(v) \mid \text{color}(v) = \text{color}(w) \} | \leq p?$$


texts: Hash function to hash 6-digit positive integers

texts:
Let UID denote a unique identifier. UID's are represented as 6-digit positive integers.

I want to insert a collection of UID's in a hash table with $M$ buckets, where $M$ is a prime number (for example, 524309).

If I am not mistaken, since $M$ is prime, dividing an UID with $M$ generates a unique remainder, as there is no common factor, except 1.

Example 1: UID = 222222 and $M$ = 524309.

Example 2: UID = 524309 and $M$ = 524309. In this example, the UID is hashed to bucket number zero in the hash table. The hash function is h(UID) = UID % M.

The question is: can hash function h avoid collisions for any 6-digit UID?

If yes, what is the mathematical approach to prove it?


texts:
Let Two-Solutions-SAT be the language of Boolean formulas that have exactly two distinct satisfying assignments. Show Two-Solutions-SAT is co-NP-hard.

I know how to show that the complement of Two-Solutions-SAT is in NP, it's relatively easy to create a nondeterministic polynomial time TM that decides it.

My problem comes with reducing from SAT to the complement of Two-Solutions-SAT. I understand how to reduce from SAT to 3SAT, but in the case of 3SAT you will always have CNF's with 3 variables. With the complement of Two-Solutions-SAT, you have to somehow reduce to the case where you have 0 or 1 or >= 3 distinct satisfying assignments, and I'm not sure how to go about reducing to that.

Thanks


texts:
I have a graph $G$ with $m$ vertices $V$ and $n$ edges $E$. $G$ is weighted, directed, and cyclic. I want to select heaviest $k$ edges from $E$ such that all of the edges form a connected, undirected graph. Note that when selecting these edges, the graph is considered to be connected even when two vertices $v_1$ and $v_3$ are joined by otherwise directed edges through $v_2$.

N1 ----> N2 <---- N3

Note that I am not simply looking for the maximum spanning tree, because if there were edges $e_{v_1,v_2}, e_{v_2,v_1}, e_{v_1,v_3}, e_{v_3,v_1}$ with weights

$$w_{e_{v_1,v_2}} = \max(w_E)$$
$$w_{e_{v_2,v_1}} = \max(w_E)$$
$$w_{e_{v_1,v_3}} = \max(w_E)$$
$$w_{e_{v_3,v_1}} = \max(w_E)$$

Then I would want to include all of those edges in my subset  (provided of course that $k >4$).

My two big questions:

Is there a formal name for this problem?
Is there a polynomial time solution for this problem.

My gut reaction to how to solve this (and I'm pretty sure this is $O($$)$ is:

Sort the edges by weight.
Select the top $k$ edges by weight.
Cluster the edges to determine whether they are connected.
If after clustering the edges they are not all connected and instead form $c$ clusters, then drop the bottom $c - 1$ edges from the initial set of $k$.
Repeat this clustering and dropping process until $c$ is not changing.
Find the maximally weighted paths that connect all clusters using $c - 1$ edges. If no paths exist, drop another edge and restart the clustering process.

Another possibility I have considered (which I don't think gives the right solution, but I'll throw it out there)

Sort the edges by weight.
Select the top $k$ edges by weight.
Cluster the edges into $c$ clusters.
Now without removing any edges, find the shortest paths between all clusters, or really the smallest number of additional edges that can be added to connect the clusters.
If we added $x$ edges, then we must now remove $x$ edges from the $k$ that were selected before, but we can only remove edges such that the graph remains connected.


texts: What's the complexity of Spearman's rank correlation coefficient computation?

texts:
I've been studying the Spearman's rank correlation coefficient

$\qquad \displaystyle \rho = \frac{\sum_i(x_i-\bar{x})(y_i-\bar{y})}{\sqrt{\sum_i (x_i-\bar{x})^2 \sum_i(y_i-\bar{y})^2}}$.

for two lists $x_1, \dots, x_n$ and $y_1, \dots, y_n$. What's the complexity of the algorithm?

Since the algorithm should just compute $n$ subtractions, is it possible to be $O(n)$ ?


texts:
I encountered this problem which asks whether $DSPACE(n^8) \subset NSPACE(n^5)$ is sure to hold.
I know from Savitch's Theorem that:
$$
NSPACE(n^5) \subseteq DSPACE((n^5)^2)
 = DSPACE(n^{10})$$
If the Savitch Theorem is tight, I could use the space-hierarchy theorem to conclude that the containment is proper... However, I have not yet seen any result which says that Savitch's result is tight. Does this mean that $DSPACE(n^8) \subset NSPACE(n^5)$ is not certain ?


texts: Concatenation of language to itself zero times

texts:
I was solving this question:

  Which of the following statement(s) is/are false?

  $L^0=\{\epsilon\}$
  $|L^0|=0$

The answer given was None. That is, none of these statements are false and both are true. However, I feel both are wrong. I feel

$L^1=L$  and
$L^0=\phi$

Also

$|L^0|=|\phi|=0$

Am I wrong with this?


texts: In a $k$-way set associative cache,main memory block mapping in range?

texts:
In a $k$-way set associative cache, the cache is divided into $v$ sets, each of which consists of $k$ lines. The lines of a set are placed in sequence one after another. The lines in set $s$ are sequenced before the lines in set $(s+1)$. The main memory blocks are numbered 0 onwards. The main memory block numbered $j$ must be mapped to any one of the cache lines from:

$(j\text{ mod }v) * k \text{ to } (j \text{ mod } v) * k + (k-1) $
$(j \text{ mod } v) \text{ to } (j \text{ mod } v) + (k-1) $
$(j \text{ mod } k) \text{ to } (j \text{ mod } k) + (v-1) $
$(j \text{ mod } k) * v \text{ to } (j \text{ mod } k) * v + (v-1) $

My attempt:
Somewhere it explained as : Number of sets in cache = v. So, main memory block j will be mapped to set (j mod v), which will be any one of the cache lines from (j mod v) * k to (j mod v) * k + (k-1).
(Associativity plays no role in mapping- k-way associativity means there are k spaces for a block and hence reduces the chances of replacement.)

Can you explain it in a formal way, please?


texts: DP for Weighted Interval Scheduling: why is sorting by finish time necessary?

texts:
Problem :
In the weighted interval scheduling problem, we want to find the maximum-weight subset of nonoverlapping jobs, given a set $J$ of jobs that have weights associated with them. Job $i \in J$ has a start time $s_i$, a finish time $f_i$, and a weight $w_i > 0$. We seek to find an optimal schedule — a subset $\cal{O}$ of non-overlapping jobs in $J$ with the maximum possible sum of weights.
Dynamic Programming Solution: In almost all textbooks or materials I could get access to, a DP algorithm is given as follows: First all jobs are sorted in order of ascending finish time: $f_1\le f_2 \le \dots \le f_n$. Let $OPT(i)$ be the maximum total weight of non-overlapping jobs in $\{1,2, \cdots ,i\}$, $p_i$ be the largest index $j < i$ such that job $j$ and $i$ are compatible. Then we see that
$$OPT(i) = \max\{{w_i + OPT(p_i), OPT(i-1)}\}$$
My question: I think I could understand why this DP algorithm works. However I didn't see the necessasity for the sorting step. What if we sort the finish time in ascending order instead?  As far as I can see, it's also correct.


texts:
As I understand, you can build the the word -> pages index in Google or large SQL database since indexed search has complexity O(1) -- lookup gives you a billion-page result at once

сomputer -> About 2.14 bln results
science -> About 1.93 bln results

computer science -> About 377 mln results
"computer science" -> About 147 mln results
science computer -> About 0.97 bln results
"science computer" -> About 452k results

So, you have got 2 billion pages immediately. To find out the pages which contain both words, you seem to need to make an intersection. How do they make it immediately? I do not believe that they try all 10^18 matches

for p in pages(word1):
 for q in pages(word2):
  if p == q yield p


texts: Is there a way to combine linear equation and inequalities into same equation in order to optimise software calculations?

texts:
I’m programming web application which has some tricky calculations and I would need some help with mathematical calculations.
What I'm trying to calculate:
I have number of items. Lets call items a1, a2, ..., an. Each item consists of three components (let's call them x, y and z). Components have a ratio which is percentage. Sum of that ratio is always 1 (or 100%).
There is individual amount of each item and each item has unique tolerance/range +- % (min - max).
Then I have target ratio (x, y and z). I need to figure out what amount of each item must be to find combination which forms target ratio. Items amount must be between their minimum and maximum values. Combined items forms overall x, y and z values with should match target x, y and z
Here is an example how I started to solve the problem:
Item 1:
Amount: 100
Tolerance: +-30%
x = 0.25, y = 0.50 and z = 0.25
Minimum amount: 100% - 30% = 70% -> 100 x 0.7 = 70
Maximum amount: 100% + 30% = 130% -> 100 x 1.3 = 130
(Here 70% and 130% are coming from tolerances and after that min and max amounts can be calculated
Item 2:
Amount: 250
Tolerance: +-25%
x = 0.15, y = 0.30 and z = 0.55
Minimum amount: 100% - 25% = 75% -> 250 x 0.75 = 187.5
Maximum amount: 100% + 25% = 125% -> 250 x 1.25 = 390.6
Item 3:
Amount: 180
Tolerance: +-40%
x = 0.40, y = 0.40 and z = 0.20
Minimum amount: 100% - 40% = 60% -> 180 x 0.6 = 108
Maximum amount: 100% + 40% = 140% -> 180 x 1.4= 252
I have a target ratio.
In this example let the target ratio be:
x = 0.25, y = 0.40 and z = 0.35
I need to find what the amount of each items should be in order to form the target ratio and the items must be in their tolerance ranges (between min and max).
Because of each items has 3 components, without min/max amount the combination can be easily calculated (multiplier for each item) with 3 equations below by using linear equation.
Item 1 = a1, item 2 = a2 and item 3 = a3:
0.25 a1 + 0.50 a2 + 0.25 a3 = 0.25      <- target x = 0.25
0.15 a1 + 0.30 a2 + 0.55 a3 = 0.40      <- target y = 0.40
0.40 a1 + 0.40 a2 + 0.20 a3 = 0.35      <- target z = 0.35
After calculating linear equation I get ratio of items:
a1 = 0.375, a2 = 0.375 and a3 = 0.25 meaning that a1 = 37.5%, a2 = 37.5% and a3 = 25.0% of overall amount of items. Now x, y and z match with target ratio. At this point I haven't used the minimum or maximum values.
Below is the link to online calculator which I now used to calculate factors using linear equation for test purposes:
(Also note that I used a, b and c for item/variable names instead of a1, a2 and a3 in online calculator).
Link to online calculator
In this example there are 3 variables/items and 3 equations. Two problems: min/max is not included and there can be for example 10 items/variables in equation. Then the linear equation doesn't work anymore because there are much more items/variables than equations.
I'm not sure how but these min and max amount's must be added to the same equation (and is it possible to form a matrix):
a1 >= 70       <- item 1 minimum amount
a1 <= 130      <- item 1 maximum amount
a2 >= 187.5    <- item 2 minimum amount
a2 <= 390.6    <- item 2 maximum amount
a3 >= 108      <- item 3 minimum amount
a3 <= 252      <- item 3 maximum amount
And this is my problem. I have no idea how to combine these together (inequalities and linear equations or am I going totally wrong direction?). I need to be able to get values for a1, a2, a3, …, an. And I need at least one suitable solution (combination) if there is any solution also when there are multiple or infinite amount of solutions.
If someone can help I would be very grateful! Thanks for your time!


texts: Big o of for loop with multiplication iteration

texts:
For(int i=1;i<=n;i*=2)
    Statement
I'm making notes for competitive exam and made this problem. But I'm not getting solution. Is it O( log n)? If so why?


texts: Deterministic Turing Machine with infine tape in both directions

texts:
Consider a deterministic Turing Machine $D$ which has an infinite tape in both directions. We don't have exact information about it; what we know is that its alphabet is $\{a, b, c\}$ and there are at least three states $q_1, q_s, q_f$ where $q_s$ is the start state, $q_f$ is the final state. At some step of the computation, all the tape is blank except one cell containing the symbol $a$, the state is $q_1$ and the head is currently at a blank cell.

I need to write states and transitions that will guarantee to enter to final state from state $q_1$ but I have difficulties since $D$ is both deterministic and with infinite tape in both directions.


texts: If P is a property of turing machines, does P $\leq_T$ COUNT_P imply that P $\in$ RE $\cup$ coRE?

texts:
Fix an input and tape alphabet $\Sigma$ and $\Gamma$. Let P be a property of turing machines over these alphabets, i.e., a subset of $\{\langle M \rangle \mid M \text{ is a TM over the alphabets } \Sigma \text{ and } \Gamma\}$. Define COUNT_P to be the function $\mathbb{N} \to \mathbb{N}$ describing the number of $n$-state turing machines over these alphabets which satisfy property $P$ (here, we also fix the states to be $\{1, 2, \dots, n\}$, so that we can't have two turing machines which are the same but with differently named states. Basically, we want the set of $n$-state turing machines to be finite).

One can show that if P is a recognizable (or co-recognizable) property, then P $\leq_T$ COUNT_P (here $\leq_T$ denotes Turing-reducibility). What can be said about the converse of this statement? Indeed, if P $\leq_T$ COUNT_P, is P either recognizable or co-recognizable? I don't have any real reason to believe that this is true or false, but just would like to know an answer in either direction (seems difficult to find a counter-example or to prove it to be true).


texts:
Where is program counter stored? CPU caches?

Also how big are these counters?

What happens if that memory has been filled up?

I know that it's a value that stores the next instruction for the CPU to process, as well as it increments with the size of the next instruction to cycle for the next instruction for the CPU to process, and the cycle continues, that's as far as I know, right?


texts: Reduce factoring to solving quadratic equations

texts:
The problem of solving quadratic equations is as follows:

  Suppose you are given a set of quadratic equations and are asked to
  find $0$-$1$ values for the variables such that all equations are
  satisfied. For example, consider the system $$x_1x_2-x_3 = 0$$
  $$x_1x_3-x_1x_4+x_3x_4 = 1$$ $$x_1x_4-x_2x_3+x_1x_3 = 0$$ You may
  easily verify that the setting $$x_1=x_2=x_3=1$$ and $$x_4=0$$
  satisfies all requirements.

I need to show that if we suppose that this problem is in P then the problem of integer factorization is also in P. I have no idea how to start. Please help me.

I know that the problem is in NP, because there is a polynomial verifier to it. I got stuck when I tried to find a polynomial reduction from the quadratic equation problem to integer factorization. I don't figure out how to "connect" from quadratic equations to integer factorization. I have tried to simplify the problem and construct a polynomial reduction from this problem to the problem of finding only one divisor of $n$, and if I do so, I could simply run this algorithm polynomial number of times to find the other divisors of $n$. So far I have failed at this.


texts: A < HPL < Complement(A) What can you say about A and Complement(A)?

texts:
Suppose we have the language

$ \overline L = \{x∈\{0,1\}*:x∉L\}$

And we know that

$A ≤ HPL ≤ \overline A$

where HPL is the Halting problem.

We need to state whether A is finite, countably infinite and whether $A$ and $ \overline A$ is recursive or not or re or not.

We know that A reduces to HPL and HPL is re and therefore A is re. Since HPL reduces to $\overline A$ and HPL is not recursive then $\overline A$ is not recursive. Furthermore, if we know that a language is not recursive but its complement is re then the language is not re. We know so far that $\overline A$ is not recurisve but $A$ is re then it means that $\overline A$ is not re. Furthermore if you know that a language L is not re then either $\overline L$ is not re or $\overline L$ is re but not recursive. We know that $\overline A$ is not re but A is re and therefore, we can say that A is not recursive.

Can anybody tell me if my deduction is any good? Also, how can I know if A is finite/ count infinite? Any tip would be greatly appreciated!


texts:
Im trying to prove that $L=\{w\#s : |w|=|s|, w \neq s\} \notin CFL$ using the pumping lemma.
So I said, let say $L \in CFL$ so by the pumping exists $p$ which is the pumping length of language $L$, I think $ s = 0^{m}1^{p}\#1^{m}0^{p} \in L$  would be a good word to start with, I can write $s = uvxyz$ and i want $uv^{i}xy^{i}z\notin L$  i want somehow to force the new word to
Not contain $'\#'$ or $|w|\neq |s|$.
The first option could be achived if ill make sure $'\# \in v\cup y$ and ill just choose $i=0$. And for the second option, i want to force $|v|\neq |y|$ and then for every $i$ it will be good.

But i cant see how to analyize the word fulfills the requirements.

Edit:

I think it isnt a duplicate question, This language isnt context free as mention in the comments.

The $"\#"$ char is the thing that make the difference between the language that was suggested as a duplicate post.

I've succsed to prove it by the pumping lemma when choosing the word $w = 0^{p!+p}1^{p}\#0^{p}1^{p!+p}$ and $i=1+\frac{p!}{t}$ to pump with in the non trivial part where $w=uvxyz$ is the partition and $|v|=|y|, v\subseteq w $ and $ y\subseteq s$ , this way ill get that $uv^{i}xy^{i}z=w\#s$ where $w=s$

Full proof : (more rigorous proof to this question than mine)

Assume by way of contradiction that $L ∈ CFL$. Let $p > 0$ be the pumping constant for $L$
guaranteed by the pumping lemma for context-free languages. We consider the word
$s = 0^{m}1^{p}\#0^{p}1^{m}$ where $m=p!+p$ so $s ∈ L$.
Since $|s| > p$, according to the pumping lemma there exists a representation $s = uvxyz$, such that
$|vy| > 0$, $|vxy| ≤ p$ , and $uv^{j}xy^{j}
z ∈ L$ for each $j ≥ 0$.

We get a contradiction by cases:

If $v$ or $y$ contain $\#$: Then for $i = 0$, we get that $uxz$ does
not contain $\#$, so $uxz \notin L$ in contradiction.
If both $v$ and $y$ are left to $\#$: Then for $i = 0$, we get that
$uxz$ is of the form $w\#x$, where $|w| < |x|$, so $uxz \notin L$.
If both $v$ and $y$ are right to $\#$: Similar to the last case.
If $v$ is left to $\#$, $y$ is right to it, and $|v| < |y|$: Then
for $i = 0$, we get that $uxz$ is of the form $w\#x$, where $|w| >
   |x|$, so $uxz \notin L$.
If $v$ is left to $\#$, $y$ is right to it, and $|v| > |y|$: Similar
to the last case.
If $v$ is left to $\#$, $y$ is right to it, and $|v| = |y|$: This is
the most interesting case. Since $|vxy| ≤ p$, $v$ must be contained
in the $1^{p}$ part of $s$, and $y$ in the $0^{p}$ part. So it holds
that $v = 1^{k}$ and $y = 0^{k}$ for the same $1 ≤ k ≤ p$  (in fact,
it must be that $k < p/2$). For each $j ≥ 0$, it holds that
$uv^{j+1}xy^{j+1}z = 0^{m}1^{p+j·k}\#0^{p+j·k}1^{m}$, so if it
happens that $m = p + j · k$, then it holds that $uv^{j+1}xy^{j+1}z
   \notin L$ in contradiction. To achieve this, we must take $j =
   (m-p)/k$, which is valid only if $m − p$ is divisible by $k$. Recall
that we chose $m = p + p!$, so $m − p = p!$, and $p!$ is divisible by
any $1 ≤ k ≤ p$ as wanted.


texts:
Common algorithms for creating bounding-volume-hierarchies (BVH) rely on grouping primitives together that are not necessarily adjacent in memory. This is either done by rearranging the primitives directly or using an index which is then sorted. What if we are not allowed to change the order of the primitives? More formally:
Let $P=\{p_1, p_2, ..., p_k\}$ be an ordered set of primitives. A BVH can be constructed by splitting the set of indices $I=\{1,2,...,k\}$ into two subsets $I_l$ and $I_r$ so that $I_l\cap I_r=\emptyset$ and $I_l \cup I_r=I$. $I_l$ and $I_r$ correspond to the indices of all primitives in the left and right child node of the root node. This procedure then repeats recursively for $I_l$ and $I_r$ and so on.
Now add the additional constraint that $\forall i \in I_l \forall j \in I_r(i<j)$. This prevents rearranging and makes the problem quite interesting in my opinion.
The quality of the best achievable BVH without rearranging primitives depends heavily on the initial order of the primitives. Instead of choosing a spatial split position, for example using the surface area heuristic, we are restricted to choosing a split index instead. My guess is that this would make agglomerative clustering algorithms much more attractive, as only adjacent primitives can be clustered together, not arbitrary pairs of primitives.
Has this problem been studied in the literature before?


texts: Measuring the difficulty of a sequence-to-sequence problem using automata theory

texts:
Automata theory measures the difficulty of language recognition problems by using an automaton that can accept or reject for the given string.
However, I want to measure the difficulty of a sequence-to-sequence (seq2seq) problem.
For instance, what is the difficulty of the following seq2seq problem associated with counting as follows:
$\Sigma = \{a, b, 1, 2, 3, T \}$ where $T$ is a terminal symbol.
$A = \{xT \}_{x \in \{a1, a2, a3, b1, b2, b3\}^*}$
$B = \{sT \}_{s \in \{a, b\}^*}$
A seq2seq function $f:A \to B: w_1d_1 \cdots w_nd_n T \mapsto \underbrace{w_1 \cdots w_1}_{d_1} \cdots \underbrace{w_n \cdots w_n}_{d_n}T$ where $w_i \in \{a, b\}$ and $d_i \in \{1, 2, 3\}$.
To go further, is there any way to convert a seq2seq problem into a language recognition problem?
Moore machine or Mealy machine equipped with an output function deals with similar problem where  the length of the output is equal or less than that of the input.


texts: What is the difference between a microoperation, microinstruction and control word?

texts:
I've seen a few lectures interchangeably use the two words (microinstruction and microoperation). I've found a source that explains the difference between a microoperation and microinstruction, but I have not been able to associate the two to a control word. Books I have referred to have provided definitions of each, but no explanation about the relation amongst the three.

Edit: Could I also get a few examples to help differentiate the three ?


texts: Why does the recurrence equation for QuickSort consider all the elements in the array?

texts:
I have been taught that QuickSort has the following recurrence equation in the best case:

$T(n) = \begin{cases} c & \text{if } n=1 \\ 2\ T(\frac{n}{2}) + c \cdot n & \text{if } n>1 \end{cases}$

where $c \in \Theta(1)$ and $c \cdot n \in \Theta(n)$. As well for the general case:

$T(n) = \begin{cases} c & \text{if } n=1 \\ T(q) + T(n-q) + c \cdot n & \text{if } n>1 \end{cases}$

Moreover, the algorithm used in the lecture was the following:

Procedure QuickSort(A[p,...,r])
    if p < r
        q = Partition(A, p, r)
        QuickSort(A, p, q-1)
        QuickSort(A, q+1, r)

As you can see, the recursive calls don't take care of the pivot element $q$. I understand this occurs as Partition moves elements around until the pivot is where it should be is the array ordered. The following is the Partition algorithm:

Function Partition(A[p,...,r], p, r)
    x = A[r]
    i = p-1
    for j = p to j = r-1 do
        if A[j] <= x
            i = i+1
            Exchange(A[i], A[j])
    Exchange(A[i+1], A[r])
    return i+1

My question is: Why do the recurrence equations assume the algorithm takes all the elements of the array (let it be $n$) if the actual algorithm only takes $n-1$ elements?

Why can't it be the following?

$T(n) = \begin{cases} c & \text{if } n=1 \\ 2\ T(\frac{n-1}{2}) + c \cdot n & \text{if } n>1 \end{cases}$

Or, more generally, this one?

$T(n) = \begin{cases} c & \text{if } n=1 \\ T(q) + T(n-q-1) + c \cdot n & \text{if } n>1 \end{cases}$


texts:
Alex writes down the decimal representations of all natural numbers between and including m and n, (m ≤ n). How many zeroes will he write down?

My one friend said to me that this problem can be solved by dynamic programming.But I can't understand how to solve it by dynamic programming .Can someone explain it with great details.Here is some input and output.

1.input:m=10, n=11 and output:1

2.input:m=100,n=200 and output:22


texts: Is Q-Learning ever better than Brute Force?

texts:
I am currently learning about the Q-learning algorithm, so I therefore assume that it has some use or purpose. However I currently cannot see how it is in any way useful. In terms of complexity class, it appears to perform equal to or worse than brute force, which as far as I am aware, is the lowest you ever need to go to compute something computable.

What, if anything, have I missed?


texts: On certificates in BPP (avoiding majority vote)

texts:
Assume that we have a $BPP$ algorithm $A$ for a problem $\Pi$. Given input $x$ we run $A$ on $\Pi$ polynomially many times and take majority output.

However if the problem $\Pi$ is also in $NP$ instead of running $A$ so many times why cant we after every run verify the certificate that $A$ produces is correct? If correct after a particular run and the answer is $Yes$ and the certificate is accepted then declare answer as $Yes$ else if the answer is $Yes$ and the certificate is not accepted then declare answer as $No$.

This should be much faster than taking majority vote.


texts: Implications of Halting Problem being unsolvable?

texts:
I came across a confusing situation when reducing the Halting Problem (HP) to the Blank Tape Accepting Problem (BP).

We know that since HP can be reduced to BP, BP is decidable $\implies$ HP is solvable. By contrapositive, we get that if HP is undecidable, then BP is undecidable as well. But now this creates an issue.

BP is just a special case of HP where the input to HP is a Turing Machine and a blank tape. Also, HP is a harder version of BP since we can get all possible tapes as input. So, just because a harder problem is unsolvable, how can we conclude that the more general form is also unsolvable.

It might be possible that we have some TM that can solve BP but cannot solve HP.

I know that both BP and HP are undecidable, but my main question is that how can we conclude via reduction that BP $\implies$ HP?


texts: Prove that every thin AVL tree may be converted to red-black tree

texts:
Let's define thin AVL tree as AVL tree $t'$ such that contains minimal possible number of nodes among all AVL tree $t$ such that $height(t)=height(t')$.

I am trying to prove that every thin AVL tree may be colored to be red-black tree. I would like to use induction. I tried to do induction by height - but as you could see Every AVL tree may be red black tree I didn't managed to (I have very similar problem).

Could you give me a hint ?

I can see following thing:
thin avl tree of height $h$ has exactly one vertex on height $h$ - contrary avl tree wouldn't be thin.   Moreover this node must be red (property of black height).
Example:


texts: Unsupervised Learning: BCM or Oja's Rule

texts:
I am learning about unsupervised machine learning, and am a bit confused regarding different algorithms to update weights. So, I understand that both Oja's Rule and BCM can be used.

In Oja's rule:

dw/dt = k*x*y - w*y^2

Where x is the value at the input neuron, y is the value at the output neuron and w is the connection strength between the two. The idea is that this prevents weights from growing out of proportion.

In BCM:

dw/dt = k*(y-theta)*x

Where the idea is that unless my postsynaptic strength exceeds a threshold theta then I don't want my connectio to be strenghtened.

Studying competitive learning, which is yet another type of unsupervised learning I cam across another rule:

dw/dt = n*(x-y)

In this case however x is the full input vector and y is the vector representation of the output vector. The idea being that we move the prototype that responded the strongest to a given input closer to it, making the two more similar.

However, I don't understand when should I use which rule? For example, why couldn't I use a rule that combines both Oja's and BCM, hence only increasing connection weights when the output exceeds a given threshold, and preventing weights from growing out of proportion?


texts: Combining two infinite algorithms to create a single infinite algortihm

texts:
Suppose I have an algorithm $F$ that, given a numeric input $x$, generates an infinite sequence of numbers that converges to a $f(x)$, where $f$ is some continuous real-valued function.

Similarly, I have an algorithm $G$ that, given a numeric input $y$, generates an infinite sequence of numbers that converges to $g(y)$, where $g$ is another continuous real-valued function.

I would like to have an algorithm $H$ that, given $x$, generates an infinite sequence of numbers that converges to $g(f(x))$. How can I do this?

My current idea is as follows. For every algorithm $A$ and integer $i$, let $A_i(x)$ be the $i$-th value in the sequence returned by algorithm $A$ when run on input $x$.

Then, the algorithm $H$ should return the sequence:

$$G_i(F_i(x))$$

Initially, $H$ runs a single step of $F$ on $x$ and runs a single step of $G$ on the result. Then, $H$ runs two steps of $F$ on $x$ and runs two steps of $G$ on the result. This goes on infinitely.

Is this idea correct? Is there a better idea?


texts:
I recently started self studying about algorithms and decision problem, so I don't have a firm grasp on this particular area. In this context I found myself thinking about the following .

If $L_1$ is semidecidable and $L_2$ is decidable, what can one say about the language set defined by their difference $L_3 = L_1 \text{ \ }L_2$ ?

I'm inclined to believ that $L_3$ is semidecidable, but I can't think of a way to prove it.

Any ideas?


texts:
Suppose I have an AVL tree with a pointer to the minimal element. I'd like to conduct a search for some key x, which is the $k$-smallest key in the entire tree.
I can do this by "climbing" up the tree's left branch, comparing x with the current key. As long as

  (x > curr.key) && (x > curr.parent.key)

I keep climbing up, but once the second condition is violated, I slide down to the current right-subtree, and from there on it's just a standard BST search.

The claim is that the worst case complexity is always $O(\log k)$, for any $k$. But I can't convince myself this is accurate: if x is larger than the tree's root's key (the median, or equivalently $k > {n\over 2}$), that implies I must have traversed the entire left branch, which for a balanced tree is $O(\log n)$ - and only then I can find x in depth of $O(\log k)$.

Am I looking at this the wrong way?


texts:
I have a test about the branch and bound algorithm. I understand theoretically how this algorithm works but I couldn't find examples that illustrates how this algorithm can be implemented practically.

I found some examples such as this one
but I'm still confused about it. I also looked for travelling salesman problem and I couldn't understand it.

What I need is some problems and how can these problems solved by using branch and bound.


texts:
Suppose I have a set $A$ of elements in $\{1, \ldots, n\}$, given as an unordered list.
I would like to compute the complement of $A$, i.e., I would like to produce an unordered list of entries in $\{1, \ldots, n\}$ but not in $A$.

One way to do this is to sort the entries of $A$ and then go through them and list all the entries I do not see. This takes $O(n \log n)$ in the unit cost RAM model. My question is whether there exists a linear time $O(n)$ algorithm in the same model.


texts:
I'm working on the following exercise and can't get the calculations right:

Assume an OS uses:

33 bits for physical address
34 bits for logical address
2KB frame size

Calculate:

How many bits are used for the offset
How many bits are used to identify a frame
How many bits are used to identify a page

And then:
Assuming the page tables include the valid and dirty(edit) bit, calculate the size (in bits) of a process' page table using all pages.

I have a hard time understanding this type of calculation and will greatly appreciate any help.


texts: PTAS vs. exact-time sub-exponential algorithms

texts:
I have recently summarized several algorithms for the maximum disjoint set problem. This problem is NP-hard, but it has both PTAS and sub-exponential algorithms. These algorithms seem to me closely related. The details vary, but the general idea is:

For a PTAS: remove a small fraction of the input set (e.g. $O(\sqrt{n})$ shapes). Partition the remaining input set to two subsets. Recursively find an approximate maximum set on each subset, and return the union of these two sets as the approximate solution.
For a sub-exponential algorithm: instead of removing those $O(\sqrt{n})$ shapes, check all possible subsets of them. For each subset, do the recursive step as in the PTAS. Return the best solution found. The runtime is dominated by the number of all possible subsets, which is $O(2^\sqrt{n})$.

Initially I thought that maybe every problem with a PTAS has a sub-exponential exact algorithm, but I haven't found such a relation so I assume it is not true. My questions are therefore:

Are there problems with PTAS but provably no subexponential algorithms (no algorithms with runtime $O(2^{n^e})$ with $e<1$)?
Are there problems with subexponential algorithms but provably no PTAS?


texts:
Are unguarded affine programs Turing-Complete?
Are affine programs with affine guards Turing-Complete?

Unguarded program: all branches are taken

Affine program: only assignments like $x:=x_1+5x_2-x_3+4 $(Affine equations as right hand)

Affine guards: all conditional branches have only affine guards, for instance $x_1+x_2-3x_3>2$


texts:
Is there a problem with this proof that NP = coNP?

It suffices to show that Satisfiability can be solved efficiently with at most a polynomial number of queries to an oracle for Tautology. The algorithm for a problem P is, pick a variable X in P and fix it to T to obtain a problem P'. Submit ~P' to the oracle for Tautology. If ~P' is a tautology, then X is a "no go" for the problem P. If the oracle accepts ~P', then fix X to T in the result, otherwise fix X to F. Then proceed to the next variable. This requires linear queries in the size of the problem. An analogous result reduces Tautology to Satisfiability. Therefore NP = coNP.

My only doubt is that maybe when you're using an oracle you only get to find out if it accepts, not if it rejects. That would block this proof.


texts: Adjacency matrix and recognizing hierarchy?

texts:
I'm currently learning about graphs and I have some questions regarding adjacency matrices. Given an arbitrary adjacency matrix:

Is there any way to tell if that matrix represents a hierarchal graph structure? Obviously in the above case it's not.

Something like:

I know the rows of and i x i  adjacency matrix represent the out-degree of ith vertex and columns represent the in-degree of the ith vertex. But is there any way to tell just by looking at the general structure of the adjacency matrix if the graph is hierarchical (At least, for smaller matrices as above) ?


texts: Reducing one variant of Hamiltonian path to another

texts:
Define

$A = \{<G,s,t> :G$  is un directed graph that has a Hamilton path from $s$ to $t\}$

$B = \{<G> :G$  is un directed graph that has a Hamilton path$\}$

I would like to show that $A \le_p B$.

My attempt:

Given $<G,s,t>$ , the reduction outputs $<G'>$ where $G'$ defines as follows:

we take $v_s$ and $v_t$ s.t there is an edge $e_s$ between $s$ and$v_s$ and an edge $e_t$ between $v_t$ and $t$.

Now we define $G' = (V',E')$ where $V' = V \cup \{v_0 , v_1\}$ and $E' = (E-\{e' :e' \ne e_s , s\in e'\} -\{e' :e' \ne e_t , t\in e'\}) \cup \{ \{v_0,v \} :\{v,s\} \in E \} \cup  \{ \{v_1,v \} :\{v,t\} \in E \} \cup \{ \{v_0,s \}\ , \{v_1,t\} \}$.

Now, if $<G,s,t> \in A$  , let $s , u_1,\dots ,u_n ,t$ be the Hamilton path , then $s , v_0 , u_1 , \dots , u_n, v_1 ,t$ is a Hamilton path in $G'$.

The other direction does not work for me , if $G'$ has a Hamilton path then I want to say that the "end points" must be around $s,t$ but i'm not sure how to do that.


texts: QuickSort Dijkstra 3-Way Partitioning: why the extra swapping?

texts:
Given the algorithm above (taken from the slides (p. 35) of the Coursera course “Algorithms Part I” by Robert Sedgewick and Kevin Wayne), look at the scenario where i is at "X", the following happens:

Scenario: i -> "X", "X" > "P"

1. swap("X", "Z"), gt--;   // the value at i is now "Z", which is still > "P"
2. swap("Z", "Y"), gt--;   // the value at i is now "Y", which is still > "P"
3. swap("Y", "C"), gt--;    // Now we finally get a value at i "C" which is < "P"
// Now we can swap values at i and lt, and increrement them
4. swap("P", "C"), i++, lt++;

Why don't we just decrement gt until gt points to a value that is < the value at lt ("P" in this case), then we swap this value with the value at i. This will save swapping operations.

So if we do that for the scenario mentioned above, we'll do:

1. gt--
2. gt--
3. swap("X", "C"), gt--;
// Now we can swap values at i and lt, and increrement them
4. swap("P", "C"), i++, lt++;

Is this excessive swapping needed for the algorithm? does it improve performance in some way?
If it does improve performance, how?

If it doesn't affect performance, please give a proper explanation or a proof as to why this it does not affect performance.

Also, would the second method I mentioned affect performance in any way? please explain why.

P.S. "Affect performance" as used above means either improve/degrade performance.


texts: Branch & Bound: Avoiding equivalent solutions

texts:
There is a certain family of typical branch & bound problems in which we have to put $n$ objects into $m$ indistinguishable bags.

Usually solutions are represented by $n$-size vectors in which $V[i]$ means that the $i$-th element is in the $V[i]$-th bag.

Is there a way to avoid generating equivalent solutions without performing an $\mathcal{O}(n)$ time check once the potentially equivalent solution has been built?

I was trying to do something similar as when avoiding circular permutations, but no adaptations seems to work.


texts:
The algorithm that is used by gcc and llvm is that of Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy (page 9).  We start with the immediate dominators of each control-flow graph node B already calculated and stored in idom[B]:

for each B in all basic blocks
    if size of Predecessors(B) >= 2
        for each P in Predecessors(B)
            runner = P
            while runner != idom[B]    # idom is the immediate dominator
                DF(runner) += B
                runner = idom[runner]

My question is about the Predecessors set. Do they refer to the direct predecessors ("fathers") of B or to all of them that lead to B?


texts: Oracle machine solving halting problem for other oracle machines

texts:
Could someone give me a simple explanation why an oracle machine that can solve the halting problem for standard Turing machines, is however unable to solve the halting problem for other such oracle machines?

I have tried searching for the answer online but could not find any that really answered the question.


texts: Representation of the number in two's complement

texts:
We have that MIMA (Neumann MInimal MAchine) has the following commands:

I want to write a MIMA program that takes the value $2^{23}-24=8.388.584$ to the memory cell $y$.
We have to take attention at the number of the bits, that we need for the representation of the number in two's complement.

I have done the following:

We have that $2^{n+1}=2\cdot 2^n=2^n+2^n$.

So, $$2^1=2^0+2^0=1+1 \\ 2^2=2^1+2^1=(1+1)+(1+1) \\ 2^3=2^2+2^2=[(1+1)+(1+1)]+[(1+1)+(1+1)] \\ \text{etc} $$

And we have that $24=2^3\cdot 3=2^3+2^3+2^3$.

We initialize the memory cell $y$ with $1$ and we repeat $23$ times to add the value of $y$ by itself and the result we put it at $y$.

Then we have to subtract three times $2^3$.

How do we do this? Do we have to compute again the $2^3$'s, then compute the inverse and add it to the value that is at $y$ ?

But where do we do these operations? To calculate $2^3$ as above, we have to save the results at each step, or not? But where? Do we consider for that an other memory cell?


texts:
I am trying to use BNF to describe its own grammar to get used to it. What I can not find any information about is whether BNF must consist of zero or more rules or one or more rules. The difference would be:

<grammar> ::= <grammar> <rule> | <rule>

vs.

<grammar> ::= <grammar> <rule> | ""

The only difference I can see is that an empty language can be described by an emtpy BNF in the second case, but must use <grammar> ::= "" in the first case.


texts: Are there any research papers rethinking browser architecture?

texts:
I am interested in any research that reviews the state of affairs when it comes to browsers today, be it their concurrency models, their performance, or anything relevant to such topics. Specifically, I am interested in whether any effors are being taken in academia to take on the shortcomings of browser design currently used in the wild.

[Update, some more context]: This question stemmed from a reading of the original Erlang paper, in which the descriptions provided for fault-tolerance and strong process isolation made me think of how browers work (some do provide process/tab isolation, but this is inherently tied to their own implementations, most of which can only do process isolation that relies on OS primitives). So, another way of way of answering parts of my question is pointing me to any implementations that might have gone a different way, be it adopting functional languages or some similar. Now that I clarified my question a bit more I found this link [1], which actually does not mention any other implementation but merely describes why C++ rules the browser field. Therefore I am still interested in any theoretical takes on the topic.

Perhaps I am asking in the wrong SE forum, in which case please advise me on where to post my question.

[1] https://softwareengineering.stackexchange.com/questions/41883/why-are-most-browsers-developed-in-c


texts: Why is this function computable in $O(n^{1.5})$ time?

texts:
My textbook says: "We define the function $f\colon \mathbb{N}\to\mathbb{N}$ as follows: $f(1)=2$ and $f(i+1)=2^{f(i)^{1.2}}$. Note that given $n$, we can easily find in $O(n^{1.5})$ time the number $i$ such that $n$ is sandwiched between $f(i)$ and $f(i+1)$."

How can I convince myself that we can in fact easily find $i$ in $O(n^{1.5})$ time? As $f$ is defined recursively, I think we have to compute $f(1),f(2),f(3)\dots f(j)$ until $f(j)\geq n$. In order to find out the time that these computations take, I think we have to find a suitable upper bound for $i$ dependent on $n$ and we have to find an upper bound on the execution time of the function $x\to2^{x^{1.2}}$. In the end, we can hopefully show the quoted proposition. Unfortunately, I don't see neither one thing nor the other.

I forgot to mention: Please note that we are in a nondeterministic context. So $f$ is claimed to be computable in $O(n^{1.5})$ by a nondeterministic Turing machine.

As quite a few people have already read this question, with some of them finding it useful and interesting too, but nobody answered so far, I want to provide some more information on the context: The quoted claim is an integral part of the proof of the nondeterministic time hierarchy theorem. The proof (with the claim) can be found e. g. in the book by Arora and Barak, but I have found quite a few other resources on the Web too which present the same proof. Each of those calls the claim easy or trivial and does not elaborate on how to find $i$ in $O(n^{1.5})$ time. So either all these resources just copied from Arora and Barak or the claim is in fact not so difficult.


texts: Bellman-Ford algorthm and negative cycle proof

texts:
I  found the algorithm for finding the negative cycle in a graph after running Bellman-Ford algorithm.

The algorithm is to perform another relax iteration over all the edges. Than if we find an edge to relax we stop and start to follow it parent vertex starting from $V$ that $u$ is its parent until we close a cycle.

I'm having little problem proving this. I want to prove now that no matter when I stop the algorithm - if $p[v] = u$ always $d[v]\le d[u]+w(u,v)$ and to prove that a cycle in parent pointer is necessarily a negative cycle.


texts: Context-free grammar how to have same number of variables within a language

texts:
I am trying to get a CFG for the language:

  The set $A$ of odd-length strings in $\{a,b\}^*$ whose first, middle and last symbols are all the same.

(some example of correct answers would be: a, aaa, ababa, aababba, some incorrect answers include: ɛ, aaaa, abbaa)

This is what I've done so far:

S = a|b|aTaTa|bTbTb
T = aT|bT|ɛ

However the problem is, I need T to be a string of any combination of 'a's and 'b's but of the same length, but I'm not sure how to express this. As you can see above, I can get strings made up of any combination, but they won't be the same length when passed to S.
Any help is appreciated!


texts: Example of a simple recognizable language, whose complement is not recognizable

texts:
Can any one provide me with a simple language that is recognizable, but that it's complement is not?

I have read that recognizable languages may have this property but I am yet to find an example to think about. If you could provide the recognizable proof for both language and complement I would be very thankful, but just the language itself would be a nice help.

Thank you


texts: IPL2025 Algorithm problem ? largest sum of n positive number without choosing 3 consecutive number

texts:
This question is already asked:

To find a subsequence having largest sum among n positive integers by not choosing 3 consecutive elements

https://stackoverflow.com/questions/29249104/maximum-sum-in-ipl-matches

Problem Statement: https://www.codechef.com/ZCOPRAC/problems/ZCO14004/

Bonus/Similar link: https://discuss.codechef.com/questions/55874/iplzco-2014

Prerequisite: I am beginner in dynamic programming and algorithm.

  As I understand till now solving a problem via dynamic programming require
  breaking into sub-problems and reusing the result of the problem
  solved.

The problem is solved via DP based on the comment and answers on various links related to the same context.

There is a complete & working solution for the problem :

SOURCE OF SOLUTION

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int arr[] = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = sc.nextInt();
    }
    int sum = 0;
    for (int i = 0; i < n; i++)
        sum = sum + arr[i];

    int min[] = new int[n];
    min[0] = arr[0];
    min[1] = arr[1];
    min[2] = arr[2];
    for (int i = 3; i < n; i++)
        min[i] = arr[i] + minimum(min[i - 1], min[i - 2], min[i - 3]);

    int val = sum - minimum(min[n - 1], min[n - 2], min[n - 3]);
    System.out.println(val);

Note: function minimum(a, b, c) returns minimal number of parameters passed.

I don't understand how this solution works (Proof of solution). How does it break into subproblems and compute result (if it is DP)?

How should we propose the solution of the problem via DP (if possible)?

SOURCE: ANOTHER SOLUTION

  Let $X_k$ be the largest sum up to the k-th element that follows the rules and doesn't include the k-th element itself. Let $Y_k$ be the largest sum up to the k-th element that follows the rules and includes the k-th element itself, but not the one before. Let $Z_k$ be the largest sum up to the k-th element that follows the rules and includes the k-th element itself, and the one before as well. Let $a_k$ be the array elements.
  Then $X_{k+1} = max (X_k, Y_k, Z_k)$, $Y_{k+1} = X_k + a_{k+1}$, and $Z_{k+1} = Y_k + a_{k+1}$. Start with $X_0 = Y_0 = Z_0 = 0$, calculate $X_n, Y_n, Z_n$ and the solution is $max (X_n, Y_n, Z_n)$.

How this solves the problem/works/breakdowns-into-subproblem?


texts: If an algorithm runs in $O(|V||E|)$, is its running time bounded by some polynomial of $|V|+|E|$? If not, what is its running time called?


texts: Big O complexity of algorithm with a nested for loop only running once

texts:
I have been debating with someone about the big O complexity of the following algorithm. We have a different understanding of the theory. Basically one of us thinks that this algo is automatically O(N^2) since there is a loop over N elements and another potential other loop over N elements inside the loop. The other one thinks that since the second loop over N will only ever be executed once, the complexity is O(N). Help!

Here is the algorithm in Python:

def get_indexes(numbers, sum):
    s = set(numbers)
    for n in numbers:
        if n >= sum:
            continue
        if (sum - n) in s:
            return [numbers.find(n), numbers.find(sum - n)]
    return []


texts: Puzzle/game of NP class for a high school student

texts:
Is there any puzzle or game which cannot be decided in polynomial time and whose problem description can be easily understood by a kid? If it is a fun puzzle so much the better.

I want to demonstrate to a high school student the difference between P and NP class of problems using an example. Also, if there's some simple algorithm to show that it can be decided in polynomial time by a non-deterministic machine that would be a great bonus.


texts: How to find examples of best cases for sorting algorithms?

texts:
I am asked to give a table of 8 elements that are to be sorted by the following algorithms and to produce their best cases.
1) Selection sort
2) Bubble sort
3) Insertion sort
4) Fusion sort

If I give an already sorted table ex: {1,2,3,4,5,6,7,8} shouldn't it already be the best case for all of them? If I can be considered a best case for each?


texts: Is quadratic nonresiduosity in $\textbf{NP}$?

texts:
The paper "The Knowledge Complexity of Interactive Proof Systems" uses the language of quadratic nonresidues defined via the following excerpt from page 293 as an example of constructing an interactive proof system.

Example 1: Let $Z_m^*$ denote the set of integers
between $1$ and $m$ that are relatively prime with $m$.
An element $a \in Z_m^*$ is a quadratic residue mod $n$ [sic] if
$ a = x^2 \mod{m}$ for some $x \in Z_m^*$, else it is a quadratic
nonresidue. Now let $L = \{(m, x) | x \in \mathbb{Z}_m^* \text{is a quadratic nonresidue\}}$. Notice that $L \in \textbf{NP}$: a prover needs only to compute the factorization of $m$ and send it to the verifier without any further interaction.

Given that $n$ is not defined in the context of the example, I assume this to be a typo and that the authors meant $m$. My question is about the last sentence. The authors provide no further detail afterwards about what the verifier would do with this factorization to verify quadratic nonresiduosity. In pursuit of more details, I cracked open Arora-Barak where the following treatment of the above is given in section 8.1 example 8.9.

Here is another example for an interactive proof for a language not known to be in
$\textbf{NP}$. We say that a number $a$ is a quadratic residue mod $p$ if there is another number $b$
such that $a \cong b^2 \mod{p}$. Such a $b$ is called the square root of $a \mod{p}$. ...
the language QNR of pairs $(a, p)$ such that $p$ is a prime and $a$ is
not a quadratic residue modulo $p$ has no natural short membership proof and is not
known to be in $\textbf{NP}$. But it does have a simple interactive proof if the verifier is
probabilistic.

Now if the language QNR described in Arora-Barak is not in $\textbf{NP}$, how could its "superset" the language $L$ described in the paper be in $\textbf{NP}$? If the paper is correct then we could easily construct a verifier which would prove that QNR is in $\textbf{NP}$: for any $(a, p)$ the certificate would consist of the certificate of the membership of $(p, a)$ in $L$ in addition to a certificate for the primality of $p$.


texts:
I've implemented the Dyna-Q reinforcement learning algorithm and it works perfectly on a discrete deterministic environment, the cliff. However, when applying it to a continuous environment (mountain car) with discretized states (which introduces non-determinism), it fails everytime (using function approximation is not in question here).

My question is: Sutton's description of Dyna-Q explicitly mentions its applicability to deterministic domains. Are there necessary tweaks for it to work in non-deterministic domains?


texts:
Say I have a grammar e.g,

$$\begin{align}S&\to AB\mid abc\\
A&\to aAb \mid \lambda\\
B&\to bBa \mid ba
\end{align}$$

Now it is obvious the notation for this would be something like,
$$L(G) = \{a^{i}b^{i}b^{k}a^{k} |  i \ge 0, k > 0\}$$

My question is how do I account for the starting state going to abc. How can I represent this in set notation? My only thought would be to append $(abc)^{m}$ to the statement and then say something like if i,k == 0 then m = 1. Though I'm not sure if that is allowed?


texts:
I need to design a Turing Machine that accepts the (context-free) language: $L(M)=\{0^{n}1^{n+1}: n\ge1$}.

$$Q=\{q_0,q_1,q_2,q_3,q_4\} ,Σ = \{0,1\}, Γ =\{0,1,X,Y,B\}, F=\{q_4\}$$

X- processed 0
Y- processed 1
B- blank
P-move right
L-move left
So far I've succeeded to create a table for languages $\{0^n1^n\}$(without the red entry) and $\{0^n1^k:k\ge n\}$.

What should it look for case in which there is minimal superiority of "1's"?

@EDIT

Meanwhile I've finally hit on an idea for L(M)

Is it correct?


texts: Splay trees offer armotized O(log n) access to tree elements. However, if you keep repeatedly appending elements to a splay tree, without splaying any other elements, it degrades into a linked list with O(n) access. Is there a way to avoid that? I have the idea of splaying a random element during an append, but will that do any help?


texts:
I'm currently programming a go game, and I'm struggling with some aspect of the game, especially how to handle the end game, how to count points and how to detect dead stones ?
I thought of doing a BFS on an empty intersection (to get all the empty intersections connected) and if all the stones connected to the BFS (Group of empty intersections) are of one color, then give that score to the player. If the stones connected are of both color, then the territory is neutral.
But I'm unable to detect dead stones on ennemy territory. Is there a trick, algorithm to detect these stones ?
In this image if I run the BFS on the red dot it will be neutral territory, while the desired behaviour is to detect the two dead stones and give the score to white


texts: Finding pair of non-adjacent cliques in a dense graph

texts: I have a graph consisting of about 5000 vertices, with density around 0.5. I'm trying to find two disjoint 6-cliques, which are not connected by an edge. I have tried bruteforcing this, by firstly looking for any 6-cliques, and then checking pairs for being non-adjacent. However, although it finds a lot of 6-cliques it is too slow to find a non-adjacent pair. Is there a faster way to do this?


texts: How was the σ function chosen to extend the perceptron?

texts:
I am just reading about perceptrons in more depth, and now onto Sigmoid Neurons.
Some quotes:

A small change in the weights or bias of any single perceptron in the network can sometimes cause the output of that perceptron to completely flip, say from 0 to 1..... That makes it difficult to see how to gradually modify the weights and biases so that the network gets closer to the desired behaviour. Perhaps there's some clever way of getting around this problem. But it's not immediately obvious how we can get a network of perceptrons to learn. We can overcome this problem by introducing a new type of artificial neuron called a sigmoid neuron. Sigmoid neurons are similar to perceptrons, but modified so that small changes in their weights and bias cause only a small change in their output. That's the crucial fact which will allow a network of sigmoid neurons to learn.
Just like a perceptron, the sigmoid neuron has weights for each input, $w1,w2,…$, and an overall bias, b. But the output is not 0 or 1. Instead, it's $σ(w⋅x+b)$, where σ is called the sigmoid function and is defined by: $σ(z)≡\frac{1}{1+e^{−z}}$.
If σ had in fact been a step function, then the sigmoid neuron would be a perceptron, since the output would be 1 or 0 depending on whether w⋅x+b was positive or negative. By using the actual σ function we get, as already implied above, a smoothed out perceptron. The smoothness of σ means that small changes Δwj in the weights and Δb in the bias will produce a small change Δoutput in the output from the neuron. In fact, calculus tells us that Δoutput is well approximated by:
$$Δoutput≈∑_j\frac{∂output}{∂w_j}Δw_j+\frac{∂output}{∂b}Δb$$
Don't panic if you're not comfortable with partial derivatives!
Δoutput is a linear function of the changes $Δw_j$ and $Δb$ in the weights and bias.  This linearity makes it easy to choose small changes in the weights and biases to achieve any desired small change in the output. So while sigmoid neurons have much of the same qualitative behaviour as perceptrons, they make it much easier to figure out how changing the weights and biases will change the output.
In fact, later in the book we will occasionally consider neurons where the output is f(w⋅x+b) for some other activation function f(⋅). The main thing that changes when we use a different activation function is that the particular values for the partial derivatives in Equation (5) change. It turns out that when we compute those partial derivatives later, using σ will simplify the algebra, simply because exponentials have lovely properties when differentiated. In any case, σ is commonly-used in work on neural nets, and is the activation function we'll use most often in this book. [END]

The first part of my question is, how did they know to pick this "sigmoid shaped" function/equation in the first place? How did they know to pick this one over every other curved or not-curved function? Is that just standard practice for these types of problems in Math class? If I were to try and explain why the sigmoid function was chosen, I would say "because it means you can make small changes to the input correspond to small changes to the output." But how? I don't follow the partial derivative math and don't have a background in partial derivatives (and neither does my audience). Knowing why and how th esigma function was chosen would help demystify why neural networks work.
Unfortunately the partial derivatives weren't explained (maybe they will be somewhere else).
The second part of my question is, How is $Δoutput$ a "linear function"? Why not just a flat slope instead of the sigmoid shape. Why does it have to be so fancy? How does "using σ will simplify the algebra"? Where can I find research papers on the original thinking behind this, or if you know the answer then how can you explain why using sigma will simplify the algebra? This seems like an important part of the explanation on why we are using sigma functions in the first place, so having a laymans explanation would really help.


texts: Proof of composition of one way function is not one way in general

texts:
In this How to show composition of one way function is not such? question, the accepted answer uses g(x,y) as a one way function.
But, for a given output of g(x,y) = 0|x| of length l (say), isn't the output of g(any x of length l, 0l) the same as the earlier output? Isn't this a possible preimage of 0|x|?


texts: Is the Rice's theorem applicable to $\{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) = H_{all} \mbox{ } \}$?

texts:
Until just now I thought that I have fully understood Rice's theorem but this example irritates me:

$L^* = \{ \langle M \rangle \mid M \mbox{ is a Turing machine such that }L(M) = H_{all} \mbox{ } \}$
where $H_{all}$ denotes the totality problem. Correct me if I'm wrong but in my opinion this is not the same as $L' = \{ \langle M \rangle \mid M \mbox{ is a Turing machine that halts on every input} \mbox{ } \}$. Here, I could apply Rice's theorem and conclude that L' is not decidable but in the other case, L* is actually empty so the theorem is not helpful.


texts:
We all know in the case of web sites, to make update just means opening the code, editing it and saving it. And to view the changes we just have to refresh the browser.
But what about in the case of compiled programs like a game or other apps or even an OS. How does it work? What happens to the code?


texts: Strong polynomial time algorithm for deciding LP feasibility

texts:
Let
$$A \cdot X + B \preceq 0$$ be a system of linear inequalities with $X \in \mathbb{R}^n$ $A\in \mathbb{R}^{m\times n}$ and $B \in \mathbb{R}^m$ where $m \geq n$. According to Farkas lemma, exactly one of the following two is true:

$\exists X \in \mathbb{R}^n$ such that $A\cdot X + B \preceq 0$
$\exists y \in \mathbb{R}^m_+$ such that $y^T \cdot A = 0$ and $y^T \cdot B > 0$

Then lets define the convex optimization problem:
$$ d^{\star} = \min q^T \cdot A \cdot A^T \cdot q \\ s.t \begin{cases} q \succeq 0\\ B^T \cdot q > 0\\ \| q\| \leq 1 \end{cases}$$  Let $q^{\star}$ be the solution to the above problem.
We have two possible outcomes:
a) $d^{\star} = 0$ hence $q^{\star} \cdot A = 0$, $B^T \cdot q^{\star} > 0$ therefore the system is NOT feasible
b) $d^{\star} > 0$ hence $\not \exists q \succeq 0$ with $q^T \cdot B > 0$ and $q^T \cdot A = 0$ otherwise  $\frac{q}{\| q \|}$ would vanish the above function, therefore yielding a smaller value than $d^{\star}$. It follows that the linear system HAS a solution
Question
The above optimization problem can be solved with ellipsoid algorithm without dependency on the problem data, right? Of course, this does not yield the solution (to LP) but can decide if the LP is feasible or not, in polynomial complexity for real coefficients LP ?! What am I missing ?
Update
In the above optimization problem we have $B^T\cdot q > 0$ generating an open set. It is obviously, not possible to ask just $B^T \cdot q \geq 0$ since this would automatically generate the trivial solution $q = 0$. Instead, I think that
$$ d^{\star} = \min q^T \cdot A \cdot A^T \cdot q \\
s.t \begin{cases} q \succeq 0\\ B^T \cdot q \geq 0 \\ \textbf{1}^T \cdot q \geq 1\\ \|q\| \leq \sqrt{m} \end{cases}$$ should solve some of the complaints. This prevents the solution $q = 0$ and has closed contraints set. However, here take $\frac{q}{1^T \cdot q}$ instead of $\frac{q}{\|q\|}$ in the interpretation of $d^{\star} > 0$. Am I missing something ?


texts: Binary heap: prove that number of nodes of height h is not bigger than $\lceil \frac{n}{2^{h+1}} \rceil$

texts:
My thoughts process: let number of elements in heap be $n$, total height of binary heap be $H$, height of node be $h$, and let number of nodes with height $h$ be $x$.

Then number of nodes with height $H-1 \le 2^1, H-2 \le 2^2, ... => x \le 2^{H-h} = 2^{\lfloor \lg n \rfloor - h} = \frac{2^{\lfloor \lg n \rfloor }}{2^h}$

However, I don't see how this can be transformed to $\lceil \frac{n}{2^{h+1}} \rceil$, as $n/2$ is less than $2^{\lfloor \lg n \rfloor }$


texts: Why is string concatenation not distributive over intersection?

texts:
Background: This is to be seen in the context of formal languages, very beginner-level.

My professor claims that concatenation is not distributive over intersection, meaning that $L \circ (L_1 \cap L_2) \neq (L \circ L_1) \cap (L \circ L_2)$ and $(L_1 \cap L_2) \circ L \neq (L_1 \circ L) \cap (L_2 \circ L)$.

While it seems silly of me to doubt what he says, I personally have trouble explaining this to myself and am looking for a counter example.

If I concatenate only with the intersection of $L_1, L_2$ it ought to be the same as concatenating first and then finding the duplicates, so to speak.


texts: is little-o notation correct after being powered by a number?

texts:
I just wanted an example in which the  equation given below is not correct.

$f(n) = o(g(n)) \Leftrightarrow 2^{f(n)} = o(2^{g(n)})$


texts:
lw  $4, 40($4)
sw  $4, 50($4)
add $4, $4, $4

Suppose the above code was to be executed using 5 stage pipelining. I want to determine the data hazards but I am confused about which pipelining-stages are used for each command. For example, doesn't 'sw' use WB ?


texts: Probability of having a log(n) length monotone subsequence in a random permutation of {1,...,n}

texts:
How can I compute the probability of having a $\log(n)$ length monotone consecutive subsequence in a random permutation of $\{1,...,n\}$.

I wish to upperbound it with $1/n$.


texts: Given a vertex, find a path between it and each other vertex that minimizes the maximum weight in the path

texts:
I'm revising for an upcoming exam and was wondering if someone could help me with a practice problem:

  We model a set of cities and highways as an undirected weighted graph $G = (V,E,l)$, where the vertices $V$ represent cities, edges $E$ represent highways connecting cities, and for every undirected edge $e = \{v, w\}\in E$ the number $\ell[e]$ denotes the number of litres of fuel that your motorcycle needs in order to ride the distance between cities $v$ and $w$.
  There are fuel stations in every city but none on the highways between the cities. Therefore, if the capacity of your motorcycle's fuel tank is $L$ litres, then you can only follow a path (a sequence of adjacent highways), if for every highway $e$ on this path, we have $L\geq \ell[e]$, because you can only refuel in the cities.

  Design an algorithm with a running of time of $O(m\log n)$ that, given an undirected weighted graph $G=(V,E,\ell)$ modelling a setting of cities and highways, and a city $s \in V$ as inputs, computes for every other city $v \in V$, the smallest fuel tank capacity $M[v]$ that your motorcycle needs in order to be able to reach city $v$ from city $s$.

I'm not sure how to solve this problem, but I do have a few ideas. I thought of possibly running Kruskal's algorithm since that would give me the MST of the graph. I'm not sure how I would then efficiently get the answer I need to produce.

Alternatively, I was thinking of using dynamic programming in some way since that's one of the things that we use a lot in the course, but I'm not really sure how to go about it.


texts:
I tried to make a 4-bit adder, but it ain't working.
When I do this:

a 0000
b 1111
+ _____
s 0101

but s should be 1111!

And this is my 1bit-adder:

What am I doing wrong? Is it possible to put a0123, and b0123 in just two 4-bit inputs instead of 8 separate inputs?


texts: Topology vs sigma-algebra's as a framework for approximate information?

texts:
In the book "topology via logic" by Steven Vickers, topology is introduced for computer scientists, with the idea that topology captures the idea of approximate information.

I am somewhat confused by the explanation. In particular, I'm confused by how it relates to sigma-algebra's, which are also a way to express approximate information. In the case of sigma-algebra's, we can think of each set in the sigma-algebra as the sigma as a "signal" that we may receive, and the elements of that set as the "possible worlds" in which we would receive that signal. The sigma algebra then denotes the fact that we don't know in which exact world we are, but we know what subset of possible worlds we are. The axiom of closure under complementation follows intuitively from this: If we don't get the signal that we're in subset of worlds $A$ then we must be in $A^c$.

What is the rationale behind using topology instead of sigma-algebra's for capturing approximate information in computer science?

In particular, how are the differences between topology and sigma-algebra's imply for how they are used as frameworks for talking about approximate information?

closure under complementation in sigma-algebra's but not in topology
closure under countable unions in sigma-algebra but arbitrary unions in topology.
closure under countable intersections in sigma-algebra but finite intersections in topology.


texts: Reduction from a further constrained problem

texts:
If I find an NP Hard problem that is equivalent to my problem with an additional constraint or bound, can I still prove that my problem is NP Hard?

Generally, this is probably not the case. For example, the NP Hard TSP is just a further constrained version of the shortest path problem.

Specifically, I have the problem:

  Given a universe $\mathcal{U}$ and a family $\mathcal{S}$ of subsets of $\mathcal{U}$, select $k$ sets from $\mathcal{S}$  such that the sum of the number of repeated times that each element is covered is maximized.
  Number of repeats are defined as one less than the number of instances.

If the number of repeated times for each element has an upper bound at 1, this is equivalent the densest k-subgraph problem (edges are elements and nodes are sets),

  Given a graph $G$ and an integer $k$, find a subgraph of $G$ on $k$ nodes with maximum number of edges.

Since the densest k-subgraph problem is strongly NP Hard, can I prove that my problem is also NP Hard?


texts:
The problem

A loan graph is a directed weighted graph $\mathcal{G} = (V, A),$ where $A \subseteq V \times V.$ If we have a directed arc $(u, v)$, we interpret it as the node $u$ gave a loan of $w(u, v)$ money units to the node $v$. Now, suppose all debtors want to pay all their debts at the same instant. Even if we disallow self-loops, a loan graph may have as much arcs (loans) as $n^2 - n$. Since paying back every debt requires both time and energy, what we want to do is to find an isomorphic graph $\mathcal{G}'$ with as little arcs as possible.

Before we define the concept of loan graph isomorphism, we need to define the equity function:

$$e(u) = \sum_{(u, v) \in A} w(u, v) - \sum_{(v, u) \in A} w(v, u).$$

Or in other words, an equity of a node is the sum of the loans it gave minus the sum of debts it has.

Now, two loan graphs $\mathcal{G} = (V, A)$ and $\mathcal{G}' = (V, A')$ are isomorphic if and only if there exists a bijection $f \colon V \to V$ such that $e(u) = e(f(u))$ for all $u \in V$.

There is a trivial algorithm that guarantees no more than $n - 1$ directed arcs in the result graph: split $V$ into two subsets $V_- = \{ u \in V \colon e(u) < 0 \}$ and $V_+ = \{ u \in V \colon e(u) > 0 \}$. Next, take two pointers for the two subsets: $f_-$ and $f_+$. Create the arc $(V_+[f_+], V_-[f_-]$ and set its weight to $w = \min(|e(V_+[f_+]|, |e(V_-[f_-]|)$. Then subtract $w$ from both the equities of the nodes currently pointed at. Whichever node gets the equity of zero, omit it and go point to the next node in the subset. (Basically, this procedure resembles merging two sorted lists.)

Actually, we need to define a group $\mathfrak{G} \neq \varnothing$ to be a subset of $V$ such that
$$
\sum_{u \in \mathfrak{G}} e(u) = 0.
$$
A group is proper if and only if there exist no nonempty subset $A \subsetneq \mathfrak{G}$ such that both $A$ and $\mathfrak{G} \setminus A$ are groups.

Since a loan graph with $k$ proper groups can be reconnected with $|V| - k$ arcs, we want to maximize $k$.

At this stage, the problem simplifies to the following:

Given a bunch of numbers that sum to zero, partition them in as many groups as possible.

Question

I would not be surprised if the problem is already studied, yet I have absolutely no idea how it may be called.

So finally, what is the name of the problem I specified?

Algorithm request

As of now, I tried three different algorithms [1]:

Combinatorial: find a group from input, recur to find out whether it is possible to split it into subgroups, and so on.
Partitional: generate all partitions of positive and negative lists, and check whether they may be paired into groups.
Greedy: find as small a group as possible, remove it and repeat the search.

1 and 2 are brute force but exact. 3 is fast whenever there is a large number of small groups. Also, 3 is not optimal in general, yet it is most of the times.

Can you improve any of them?


texts: Quick Clarification Question about Time Complexity in CLRS

texts:
I'm reading about the Hiring Problem in "Introduction to Algorithms" and read

  Interviewing has a low cost, say $c_i$, whereas hiring is expensive, costing $c_h$. Letting $m$ be the number of people hired, the total cost associated with this algorithm is $O(c_in+c_hm)$.

For clarification, this is the algorithm being referred to

HIRE-ASSISTANT(n)
    best = 0 // candidate 0 is a least-qualified dummy candidate
    for i = 1 to n
    interview candidate i
    if candidate i is better than candidate best
        best = i
        hire candidate i

My question is, why does the book say the total cost is $O(c_in+c_hm)$ and not $\Theta(c_in+c_hm)$? For any input, since we must iterate over all $n$ candidates and given that $m$ are hired, couldn't we also say that the asymptotic lower bound is $\Omega(c_in+c_hm)$ therefore saying the cost for any input is $\Theta(c_in+c_hm)$?


texts: Assign few binary variables to make all polynomials identically zero

texts:
I have 50 polynomials $f_i$ over binary variables $(x_1,\ldots,x_{100})$. Also $f_i(0,0,\ldots,0)=0$
for any $i \in [1,50]$. I want to assign few variables so that all  $f_i$ will be
identically zero. I want to assign number of variables as small as possible.
Here assign means we will fix some variable either 0 or 1. Other will be binary variables. All are binary polynomial ring.
If we fix all are zero, all polynomials will be zero identically. I want to reduce number of such assignment.
Is there
any way for this like using SMT etc? Kindly give your idea.


texts:
Problem:
Input : $n$, $k$

Check : Is $\frac{k}{4h -1} = n^{\frac{1}{h}}$? for any $  0 \le h <= n$.

Question: What is the fastest algorithm for the above problem assuming the model of computation is RAM?


texts: Algorithm to efficiently determine whether a magazine contains all the letters in a search string

texts:
Title pretty much states the question, I was looking for some assistance with the following:

You are given a search string and a magazine. You seek to generate all the characters in a search string by cutting them out form the magazine. Give an algorithm to efficiently determine whether a magazine contains all the letters in a search string.

I wrote: "Create a count sort which just buckets every occurrence of each specific letter in the magazine down the line. Then use that to compare vs. the search string. If the magazine contains all the letters in the search string, then great you're done; otherwise you need a new magazine."

I feel like that's not enough of an answer for this problem, can someone help?
Thanks!


texts: Pre-requisite knowledge before diving into algorithms

texts:
I'm having some difficulty trying to follow what the authors of some of the more highly recommended books on algorithms. I ran into the same problem when trying out some online courses. My goal is to prepare myself to start learning fundamental algorithms for use in low-level languages by means of understanding them mathematically. So far, a guide on wiki is a good resource to decipher the symbols, but I'm not sure that will suffice.

Is there anything besides this page that a person would need before learning algorithms besides basic algebra concepts?


texts:
Given an NFA, to decide if it accepts a word w, one could use the following algorithm:
Transform the NFA into a DFA. Then, run w on the DFA and accept/reject if the DFA accepts/rejects.

Could this be done on a linear bounded automata? How do I know for sure that the encoding of the DFA won't go over the input space?


texts: How to answer multiple queries efficiently?

texts:
I am given a $N$-length integer array. For each integer, I am given 4 values:

$$[\mathit{left},\mathit{right},t,\mathit{value}]$$
$$1\leq \mathit{left},\mathit{right},t\leq N$$

For each query, I have to find the sum of values which have $x$ in the range $[\mathit{left},\mathit{right}]$ and that satisfy $t\leq t_1$.

Example query: $x=5$, $t_1=4$.

So I have to find out sum of all the values satisfying $\mathit{left} \leq 5 \leq \mathit{right}$ and $t \leq 4$.


texts:
Do you know where Can I find an algorithm to sort a set of binary strings in colex order?

Recall, that two k−element subsets A and B
of a set with strict linear ordering $<$ are said to be in co-lexicographical order (colex order) if, for the sequences, a and b of their elements sorted in ascending order, there exists index$ i$ such that $a_i < b_i$ and $(\forall_j )_j > i \Rightarrow a_j = b_j$.


texts: Context free grammar for {a^mb^n | m ≠ n}

texts:
I need to find a context-free grammar for the above expression, $a^{m}b^{n}$ for the set $L = \left\{{a, b}\right\}$, but I am having difficulty accounting for the condition $m \neq n$.

This is what I have so far, but it clearly doesn't satisfy the above condition:

$\begin{align}
   &S \rightarrow aAb &\\
   &S \rightarrow a &\\
   &S \rightarrow b &\\
   &A \rightarrow aA &\\
   &A \rightarrow bA &\\
   &A \rightarrow \lambda \\
\end{align}$

I have spent about an hour on this, and haven't found a solution. Any ideas?


texts: Multi Agent Sokoban Solvers state of the art

texts:
I am researching into coding a solver for a variant of the Sokoban game with multiple agents, restrictions (eg. colors of stones, goals) and relaxations (push AND pull possible etc.)

By researching online I have found classic papers in the field, like the Rolling Stone paper (by Andreas Junghanns and Jonathan Schaeffer) and Sokoban: Enhancing general single-agent search methods using domain knowledge from the same authors.

These solutions seem to be outdated and I am currently structuring my solver per the notes of the two most performant solvers: YASS and Sokolution.

From the research I've done these two seem to be my best bet.

It is apparent that they are not enough by themselves to solve a multi-agent environment. Those solvers are made for a single agent. So far, I have failed to find useful multi-agent proposals.

In this context, my question is: What can be considered state-of-the-art in order to (1) coordinate multiple agents with different goals and (2) plug a solver's solution in and validate/edit it? What are some search terms I can use to research this further?

Thank you very much


texts:
There is an array with $n$ places. There is a stream of $n$ unique numbers that arrive at a random order (permutation selected uniformly at random).

Whenever a number arrives, we must put it somewhere in the array, and we are not allowed to move it later. The goal is to have as many numbers as possible (in expectation) in their correct location in the final array. The "correct location" is defined as the location where it would appear if the numbers were sorted.

What is known about this problem? What is the best expected success rate, and what algorithm attains it?

Notes:

A related question is: What is the fastest online sorting algorithm? . It discusses a situation in which items can be moved when new items arrive, and the goal is to minimize the running time.
I am mainly interested in maximizing the expected number of the correct positions. However, it is also interesting if there is a way to improve the probability that all numbers are in the correct position, above O(1/n!)


texts: Term for expected randomized given advice string?

texts:
Problems which run in deterministic polynomial time given polynomial sized advice are in class P/poly.

Problems which run in probabilistic polynomial time given polynomial sized advice are still in class P/poly.

What about problems which have an expected randomized polynomial time given polynomial sized advice under uniform distribution of inputs where expected here signifies average in the sense that a very small portion of inputs are allowed to run in exponential time using the algorithm?


texts:
This may not be strictly a computer science question but is related.

Whenever there is some function that computes more than two elements, is it possible that all elements are computed at once? Or is computing in composite/series a required limitation of the brain?

For instance, to add three numbers, we add two and then and the third to the result of the first addition. Is it possible for the brain to take all three numbers and process them at once with no intermediate step? Is it possible for machines? Is it possible with quantum computing?

In the case of the brain's inability to make this computation, is it because we are trained to compute in a certain way or is it an inherent limitation?