texts:
I am lost in formulating a mathematical model for my linear integer program. My problem is; how to include inventory and backlogging.

The following is given:

1100 units can be produced each month
Unit production cost = \$7
Inventory unit cost = \$2
Annual expense = \$10.000
Sales unit price \$12
We have given the demand for 12 month and need to plan for 12 month
If demand is not met in one month, it will be transferred to next month (backlogging)
All demand should be met in the end of the year
The sum of all demand = 12.345 unit

We want to maximize the profit

\begin{align}
\max \sum_{i=1}^{12} x_i 12 - 10.000-\sum_{i=1}^{12} x_i 7 - \sum_{i=1}^{12} y_i 2
\end{align}
where $x_i$ is the amount produced each month, for i=1,...,12 and $y_i$ is the amount of inventory each month. I have defined the following constraints:

\begin{align}
x_i \leq 1100 \\
\sum_{i=1}^{12} x_i = 12345
\end{align}

So if we have $d_i\geq x_i$ we backlog the demand, and if $x_i \geq d_i$ we put it in inventory.
\begin{align}
if: d_i \geq x_i : b_i = d_i-x_i+b_{i+1} \\
if: x_i \geq d_i : y_i = x_i - d_i + y_{i-1}
\end{align}
where $b_i$ is the amount backlogged and $d_i$ is the demand.

But this is not correct, since the inventory constraint should be smaller if we take some of it to meet the demand that exceeds the amount we can produce (if we have something backlogged), and if we have some inventory, then we don't need to backlog it. I really hope that someone can help me formulate it correctly.


texts: Counting the number of squares in a graph

texts:
Given an undirected graph, how would one go about calculating the number of squares in the graph? That is, a square is a cycle of length 4.

I know that it is possible to count the number of triangles (cycles with length 3) in polynomial time. Is it possible to calculate the number of squares in polynomial time as well, and how would one go about doing this?


texts:
Is there a class of formal grammars that generate Recursive Languages only?
(ie with which it is not possible to generate non recursive languages.)

If so what kind of production rules/restrictions do they have?

And why are they not a part of Chomsky Hierarchy?


texts: Can a Turing Machine have infinite accept states?

texts:
I'm still fairly new to Turing Machines, but I've been doing some research.

I know that a Turing Machine can have an infinite tape and that it requires a finite number of states, but does it necessarily follow that a Turing Machine can have an infinite number of accept states?

I keep seeing different layouts when formally defining Turing Machines, for example:

M = (Q, Σ, Γ, τ, s, F).

1) F ⊆ Q is the set of final or accepting states. (plural)

2) F ⊆ Q is the accept state. (singular)

So I'm just wondering which one is correct?

Any help would be greatly appreciated.


texts: Recovering a point embedding from a graph with edges weighted by point distance

texts:
Suppose I give you an undirected graph with weighted edges, and tell you that each node corresponds to a point in 3d space. Whenever there's an edge between two nodes, the weight of the edge is the distance between the points.
Your goal is to reconstruct the relative positions of the points, given only the available distances (represented by the edge weights). For example, if I gave you $d_{0,1} = d_{0,2} = d_{0,3} = d_{1,2} = d_{1,3} = d_{2,3} = 1$, then you know the points are the vertices of a tetrahedron. You don't know where it is relative to the origin, or its orientation, or if it's been mirrored, but you can tell it's a tetrahedron.
In general, the problem is easy if I give you all of the edge lengths. Just arbitrarily pick a point $p_0$ to be at $(0,0,0)$, then pick a neighboring point $p_1$ and place it at $(d_{0,1},0,0)$, then a common neighbor $p_2$ gets triangulated onto the XY plane, then a final common neighbor $p_3$ gets triangulated into the half-space $z > 0$ and breaks the remaining symmetry (assuming you didn't pick degenerate points). You can use those four points to triangulate all the remaining ones.
On the other hand, when some edge lengths are missing it may not be possible to recover the embedding. For example, if there's a vertex that disconnects the graph when cut, then the two components it would separate if removed can swing around relative to each other.
Which raises the questions:

How expensive is it to find a solution?
How do you determine if a solution is unique, up to translation/rotation/mirroring? Is 3-connectedness sufficient? Necessary?
What sorts of conditions make the problem trivial?
If I don't promise the edge weights actually correspond to point distances in 3d, how expensive is it to determine if an embedding is possible at all?


texts: What is the height of an empty BST when using it in context for balancing?

texts:
Suppose the datatype for a BST is defined as follows (in SML)
datatype 'a bst_Tree =
   Empty
 | Node of (int * 'a) * 'a bst_Tree * 'a bst_Tree;

So there are two cases one in which the BST is Empty or it can have a (key,value) as well as two children.
Now, for the case of an AVL where the condition is

In an AVL tree, the heights of the two child subtrees of any node differ by at most one
- AVL tree Wikipedia

I want to able to create a height function for use to check whether the tree is balanced. My current setup is as follows
fun height (Empty) = ~1
  | height (Node(v, Empty, Empty)) = 0 (* Redundant matching because of third case *)
  | height (Node(v, L, R)) = 1 + Int.max(height(L),height(R))

I tried to separate the Tree into three conditions

A empty Tree
A Tree with a root node
A populated tree

The reason for this is that there does not seem to be a canonical source on what the value is for the height of an Empty Tree as opposed to one in which only has a root. For the purposes of my balance function it did the job, but I rather try to understand why there isn't a canonical answer for the height of an Empty Tree.
There is a canonical answer, in a matter of speaking on Wikipedia but while initially doing research on this on Stack Overflow I arrived at many comments stating this to be wrong/incorrect/unconventional

Conventionally, the value −1 corresponds to a subtree with no nodes, whereas zero corresponds to a subtree with one node.)

I grabbed the question from which my uncertainty appeared
What is the definition for the height of a tree?

I think you should take a look at the Dictionary of Algorithms and Data Structures at the NIST website. There definition for height says a single node is height 0.
The definition of a valid tree does include an empty structure. The site doesn't mention the height of such a tree, but based on the definition of the height, it should also be 0.


texts: Understanding details of NP-Hard definition

texts:
I am learning from this video: https://www.youtube.com/watch?v=eHZifpgyH_4
at 21:17 he talks about his definition of NP-Hard.

The definition is: X is NP-Hard if every problem y which belongs to NP reduces to X.

I watched that part of the video several times but don't understand it. In particular, here's one thing I don't get:

P is also a part of NP so when we say every problem y which belongs to NP we are saying we can take a problem in P and reduce to some X. Then X is NP-Hard? That would mean that y we just converted would have an NP-Hard solution but it is actually polynomial? Sorry if this is confusing. I hope I can word it better but it to me that definition only makes sense if they talk about NP problems that are not part of P


texts: Necessities for two undirected graphs being isomorphic

texts:
As far as I know, for two undirected graphs $G = (V, E) $ and $H = (V', E')$, the following criteria is necessary for them to be isomorphic:

$|V| = |V'|$
$|E| = |E'|$
$G$ has $j$ nodes of degree $k$ $\Leftrightarrow $ $H$ has $j$ nodes of degree $k$

Are there more that are that obvious? Thanks in advance for your help!


texts:
I was reading this paper where they mention about undirected networks:

  "The total connectivity of a network is defined as
  $C=\frac{E}{N(N-1)}$ where E is the number of edges and N the total
  number of nodes."

However, this is just another way of talking about network density is it not? You could just change the denominator and refer to network density for directed and undirected networks.

Or is this "total connectivity" anything different than density?


texts: Whats exact definition of 'atomicity' in programming?

texts:
the definition of 'atomicity' says that a transaction should be able to be terminated without being touched or manipulated by possibly concurrent running actions during its process. But does that also mean that a program should not run concurrent when it is supposed to be atomic?
let's say we have 2 program as an example:
example_program1:

counts int i = 1 to 100 every second
every number is printed in new line

example_program2:

just prints "hi"

and a parent program that includes both of these program and run them once receiving a signal to start a specific program (e.g via sigaction in linux) with 2 version:
version 1:

runs the program (even concurrent) anytime once receiving the signal
which means program2 can print "hi" while program1 is still printing out the numbers

version 2:

only run one program at a time
signal for other program is blocked until program in progress has terminated

in this example, can only version 2 be considered atomic or both? Would this program be non-atomic only if e.g program2 would increment i by 1 during its process?


texts: Find a minimum-cardinality Hall-violator

texts:
Given a bipartite graph $(X,Y，E)$, in which there is no perfect matching, I want to find a smallest subset that violates Hall's condition, i.e., a minimum-cardinality set
$S \subseteq X$ for which $|N(S)|<|S|$.

This problem is the optimization version of a former question Finding a subset in bipartite graph violating Hall's condition, from which I know there exists a polynomial-time algorithm for finding such $S \subseteq X$. Does there exists a polynomial algorithm for the optimization problem?


texts: Given an array $A$ and an index $c$, prove there always exists a subarray whose sum $\pmod {i} = 0$

texts:
Given an array $A$ of positive integers with size $m$ and an array index $c$ (indexing starts at $1$). Prove using mathematical induction over $m$ that there always exists a contiguous subarray $S$ in $A$ such that the (sum of the elements of $S$) $\pmod {i} = 0.$

I'm unable to find the correct approach to solve this. I'm sure the Pigeonhole Principle will be useful here, but I don't know how to correctly apply it within the proof. Can someone point me in the right direction?


texts: Local search: Problem with neighborhood definition

texts:
I have question on understanding the following neighborhood relation within a local-search approximation scheme.
Let $M$ be a legal matching on any bipartite graph.
Let $U_k$ be the neighborhood defined as follows:
$$U_k := \{M' : |(M' \backslash M) \cup (M \backslash M')| \leq k\}$$

Can somebody give me an example or explain this to me?

If i choose a small k-value, the cardinality of $M'$ will be small as well, but how does an algorithm decide which matching pair of nodes to take?

If we define node-values and make it a weighted matching,let say we define a weight function $w_e \in \mathbb{R}$ for any edge e in our graph, now the algorithm may use greedy method and take the best possible pair of nodes (with greatest weight).

But I still don't understand the exact set definition of our neighborhood.

I would be grateful for an example, because I'm stumped on this one.


texts:
Show that if the transitive closure can be computed in T(|V |) time then
BMM can be solved in O(T(3n)) time.
I didn't understand the proof in the context of building edges. I added the proof

i tried to write an example

Michael P. Kim, Editted by: Bill Kuszmaul people.csail.mit.edu/virgi/6.890/lecture3.pdf

Thanks


texts:
What is the complexity of the following problem? I can see it's in NP for reasonable definitions of closed form, is there anything else one can say about it?

Given a recurrence relation $R_0 = \alpha_0,... ,R_n = \alpha_n, R_{f_2(n)} = g(R_{f_1(n)})$, $f_1(n) < f_2(n)$, where $f_1, f_2$, and $g$ are in closed form (for some reasonable definition of closed form, you pick; for example one could consider a solution in terms of $H_n$ closed form) and an integer $k$, find a closed form expression for $R_n$ expressible in less than k bits


texts: NP-complete problems not "obviously" in NP

texts: It occurred to many that in all the $\textbf{NP}$-completeness proofs I've read (that I can remember), it's always trivial to show that a problem is in $\textbf{NP}$, and showing that it is $\textbf{NP}$-hard is the... hard part. What $\textbf{NP}$-complete problems are these whose polynomial-time verifiers are highly non-trivial?


texts: Time complexity analysis of 2 arbitrary algorithms - prove or disprove

texts:
We are given 2 algorithms A and B such that for each input size, algorithm A performs half the number of steps algorithm B performs on the same input size.

We denote the worst time complexity of each one by $g_A(n),g_B(n)$

Also, we know there's a positive function $f(n)$ such that $g_A(n)\in\Omega(f(n))$

Is it possible that $g_B(n)\in\Omega(f(n))$? Is it necessary?

It seems naive to think that it's necessary, but I can't figure out to contradict it.


texts:
it's a well known statement that

"Cryptographic security must rely on a secret key instead of a secret algorithm."

I would like to ask about some details about it. And which are their differences?

I see the obvious thing that for a multi user system, generating a key is overwhelmingly easier than generating a distinct alghorithm for every user pair, (and even for a single pair of users one could argue that updating the key is easier)

But, Is it the only argument?

I mean, if we define

AlgorithmA = AlgorithmX + key A
AlgorithmB = AlgorithmX + key B

Then a change on the key is not different from a change in the algorithm.

The only different I see is that for a new pair of users/keys

Most of the Algorithm structure remains constant in the case of secret key,
Most of Algorithm structure need to change in the case of secret Algorithm

But where is the limit? "most of" meaning?

I would like to have more views and clues to understand why this distinction is usually mentioned.


texts: Computing exam averages in less than linear time

texts:
This is the question:

A spreadsheet keeps track of student scores on all the exams in a course.  Each row of the spreadsheet corresponds to one student, and each column in a row corresponds to his/her score on one of the exams.  There are r students and c exams, so the spreadsheet has r rows and c columns. Devise an algorithm to compute the exam averages for each student and the class average for each exam.

(It's from an ungraded practice problem set, not homework).

It seems fairly straightforward to me to do this in linear time($O(c*r)$), but I suspect there is a faster way to do it. Is there a reasonable way to do this with better O()?

My thoughts: At first I thought I could do this by storing the average values and  updating them, but I don't think this would really satisfy the requirements of the problem: given just the exam scores, getting the averages would take at least  as much time, if not more.

Any help is appreciated! In particular, helpful hints are welcomed, and a helpful hint leading me to the answer will be accepted as an answer.


texts:
I am reading some notes about interval scheduling. I gives the following diagram:

and states that:

r2 is compatible with r3, while r2 and r1 are conflicting. Similarly, the set {r1, r3, r4} is compatible, while {r2, r3, r4} is not compatible.

I can understand that set (r1, r3, r4) is compatible. How (r2, r3, r4) are not compatible. Since they are not overlapping, isn't they are compatible?


texts: Need help understanding the tuple relational calculus

texts:
We say that a query in a TRC is a statement of the form $\{T: P(T)\}$, where $T$ is a tuple variable and $P(T)$ is a formula.

Now my question is, what are the possible tuples $T$ to be tested i.e., what are the types and values for tested tuples.

As far as I know in set theory and in particular in set builder notation the variables should come from another well-defined set.


texts: Question regarding the one and two level paging system

texts:
I am studying for my OS final exam and I am solving some problems related to virtual memory . however , I have faced a problem which I need to test my understanding regarding it :
Suppose that virtual page numbers are 36 bits, and page table entries, as well as pointers to other page tables are 4 bytes each.
1)  How much memory would a single level page table require?
2)  How much memory would a two level page table require (Assume the bits are divided evenly between the two levels)?

My solution is as follows :

memory required = 2^36*4.
Now every page level has 18 bits since he mention in the question that assumes the bits are divided evenly between the two level. So for the outer page table we need 2^18 *4 bits and the same for the second level 2^18 4 bits , so the total memory required in this case is 2(2^18 *4) bits. Note : In this part I have assumed that each entry in the outer level has a pointer that points to a page table in the second level, this assumption is according to my understanding for two level paging system.

Please let me know if there is something wrong to correct my understanding . Thanks guys.


texts: Approximate Subset Sum with negative numbers

texts:
I am interested in the approximation version of the Subset Sum problem with negative numbers.
Wikipedia says there is an FPTAS algorithm for SS. That Wikipedia page states:

  If all numbers are non-negative, the approximate subset sum is solvable in time polynomial in N and 1/c.

Similarly, in the CLRS version of the algorithm, the numbers are required to be positive. For the exact version there is this reduction that makes
all numbers positive but I believe that it cannot be applied to the
approximation version.
Because the approximation algorithm behaves differently for larger numbers it would not give the same results if instead of -10 I have 10000. The trim function would cut a lot more numbers
in the new, all positive version than in the original.

My question: Is there a FTPAS for General-SS, as defined below?

General-SS:
Given an input set $S=\{a_1,\dots,a_n\}$, where $a_i$ are possibly negative numbers, and a target $C$ find a subset $S'\subseteq S$ that sums to $C$.

All-positive-SS (defined below) has an FTPAS. Does this algorithm remains an FPTAS for General-SS?

All-positive-SS:
The same as General-SS, but where we restrict $a_i\geq 0$.

Alternatively, if we transform General-SS to All-positive-SS with
the above reduction and then run the FPTAS algorithm for the new instance, does this also give an FTPAS for General-SS?


texts: How is the Subset Sum Problem NP-Complete?

texts: You can't find a solution online for it that doesn't run in polynomial time complexity, when using dynamic programming. Have all these sites secretly solved P=NP, and no one knows about it?


texts: Given matrix $A$, find vector $x$ such that every entry of $Ax$ is nonzero

texts:
Given a matrix $A \in \mathbb{R}^{n \times n}$ with no zero rows, what is the complexity of deterministically finding a vector $x \in \mathbb{R}^n$ such that every entry of $Ax$ is nonzero?

It is easy to see that a vector whose entries are realizations of Gaussian random variables works. Indeed, in this case every entry of $Ax$ is a realization of a continuous Gaussian random variable and, hence, is nonzero with probability $1$. Thus, the probability that all entries of $Ax$ are nonzero is $1$.  Thus if "generate a Gaussian" (or any other continuous random variable) is an allowed operation, then this takes $O(n)$ operations.

In the deterministic case, you probably need at least $O(n^2)$ operations since every entry of the matrix $A$ probably needs to be read. I'm wondering if you could do it in $O(n^2)$ or, if not, what the best time that you can do this in is.

Edit: I don't seem to have enough reputation to post comments on my own question. In any case, let us suppose that the entries of $A$ are all rational, and we are looking for a vector $x$ with rational entries.


texts: In what sense are dataflow architectures non-deterministic?

texts:
The Wikipedia article mentions non-determinism in the context of dataflow architectures. Arthur Veen's paper mentions non-determinism when it elaborates on MERGE nodes as conditional constructs.

Are dataflow architectures non-deterministic in the sense of Non-Deterministic Turing Machine?

For any program which deterministically runs on a von Neumann architecture, can we guarantee that it runs deterministically on a data flow architecture?


texts: Direct Mapped Cache, textbook excerpt clarification, identifying block field

texts:
I have an excerpt from my textbook concerning direct mapped cache that I would like further clarification on, the text reads.....

"Consider the following example: Assume memory consists of 2^14 words, cache has 16 blocks, and each block has 8 words. From this we determine that memory has 2^14/2^13 = 2^11 blocks.

We know that each main memory address requires 14 bits.
Of this 14-bit address field, the rightmost 3 bits reflect the word field (we need 3 bits to uniquely identify one of 8 words in a block).
We need 4 bits to select a specific block in cache, so the block field consists of the middle 4 bits.

The remaining 7 bits make up the tag field."

My questions are:

Where does the 2^13 come from when they calculated how many blocks in the first paragraph?

How did they go about identifying that the block field should contain 4 bits?
Is this because the cache has 16 blocks and 2^4 is 16?

Thank you for your time!


texts: Falsifying the "Circular Wait" Condition - Deadlock Prevention

texts:
In the Circular Wait condition for Deadlock Prevention section of this, it is described as follows:

  One
  way to ensure that this condition never holds is to impose a total ordering of
  all resource types and to require that each process requests resources in an
  increasing order of enumeration.
  To illustrate, we let R = {R1, R2, ..., Rm} be the set of resource types. We
  assign to each resource type a unique integer number, which allows us to
  compare two resources and to determine whether one precedes another in our
  ordering. Formally, we define a one-to-one function F: R → N, where N is the
  set of natural numbers.

  For example, if the set of resource types R includes
  tape drives, disk drives, and printers, then the function F might be defined as
  follows:
      F (tape drive) = 1
      F (disk drive) = 5
      F (printer) = 12
  We can now consider the following protocol to prevent deadlocks: Each
  process can request resources only in an increasing order of enumeration.

My question is that whether these numbers are assigned as fixed for all processes or when each process is called, it assigns a new number to each resource each time that process is called?

Because if these are fixed, then let suppose there is a process which requires disk drive first (whose number is let's say 5) and then it requires tape drive (whose number is 1 and which is less than 5); then how can it access tape drive? Because whenever it will run, it will find the same ordering / numbering of resources and it will never be able to access the tape drive.


texts:
I'm trying to identify communities in a direct graph.
I only know how to use Spectral clustering and Girvan-Newman method but the both the methods work only with undirect graph. Am I wrong?
So what method could I use to solve the following problem?
The text of the problem is the following:

Trawling - Identify the communities of the following webgraph with a minimum support of two and a minimum itemset size of two. Plot the resulting bipartite graphs.

What I tried to do was  using Spectral Clustering: I transcribed the graph but what I obtained was a squared non-symmetric Adjacency matrix (A).
When there is an arrow from 1 to 2  the value a12 in the matrix is 1 instead the value a21 is 0.
Now I've problems calculating the Degree Matrix (D). All its values are 0 except for the ones along the main diagonal that are the sum of the values in their rows. Is it correct?
Finally I calculate the Laplacian Matrix (L) computing: L=D-A
Now I'm stuck I don't know how to go on, how do I calculate Eigenvalues and Eigenvectors?


texts:
Say that a language $C$ is a separator for disjoint languages $A$ and $B$ if $A \subseteq C$ and $B \subseteq \bar{C}$.

I need to find two languages $A,B\in \mathrm{RE}$ that have no recursive separator $C$.


texts: Weighted Set covering problem with a fixed number of colors

texts:
I have a set of elements U = {1, 2, .... , n} and a set S of k sets whose union form the whole universe. Each of these sets is associated with a cost.

I have a fixed number of colors, C = {1 , 2, ... , m}. Some of the sets mentioned above interfere with each other. I cannot assign same color to both those sets together.

I want to pick the sets and color them from my available color list in the following way:

**Objective: Minimize the total cost of the selected sets

Constraints:

All elements of the universe are covered
No two sets that interfere with each other is assigned the same color**

If the second constraint, i.e., coloring constraint, is taken out, the problem reduces to standard weighted set covering problem. I can solve that using a greedy manner. For example, greedy unweighted set covering will work in the following way: -- 1. pick the set with the highest number of elements at first, 2. Remove that set and the associated elements from the universe, 3. Repeat step 1 until all elements of the universe are covered.

But the coloring constraint in the presence of interference among sets and a fixed number of colors complicates the issue.

For example, let's assume,

U = {1, 2, 3, 4, 5}.

There are three sets, {1, 2, 3}; {2, 3, 4, 5} ; {4, 5}.

Assume {2, 3, 4, 5} interferes with both {1, 2, 3} and {4, 5}. {1, 2, 3} and {4, 5} do not interfere with each other. Assume that there is only one color in the system.

A standard greedy unweighted set coloring solution will pick {2, 3, 4, 5} at first and {1, 2, 3} in the second round. But that is an infeasible solution to my problem since they interfere with each other and I have only one color in my system. A feasible solution will be the selection of {1, 2, 3} and {4, 5}.

I wonder how I can minimize the total cost while meeting the color constraint. Any hint on the unweighted version of the problem (where all sets have equal cost) will be very helpful, too.

Thanks,

Nazmul

Additional information: The coloring of the sets and the interference can be understood by my application scenario.

I am looking at a wireless cell. I have a set of frequencies, possible base station locations and their associated users. Each set is associated with a station and it shows the set of users that the base station can serve.

"Interference" from one set to the other means that the users' signals of one set reaches the other set's base station. In a wireless setting, this interference is not symmetric. But assumption of symmetry is OK in the algorithm because if set A interferes with set B, A & B both should get different colors if they are selected.

The interference among sets is not transitive. Set A may interfere with set B (A's users may interfere with B's base station) and set B may interfere with set C (B's users may interfere with C' base station) but that does not mean that set A will interfere with set C.

The current example is showing that two sets interfere if they intersect. This is just a coincidence. I will have a pre-generated look up table that shows which set interferes with which set before the algorithm starts. This pre-generated table will be an input to the optimization problem


texts:
If $NP \neq co-NP$ then no $NP-complete$ problem can be in $co-NP$.

I found a proof on Wikipedia that I didn't fully get:
https://en.wikipedia.org/wiki/Co-NP

In the line "from this it follows that the set of complements..". Why does it follow? It seems like the author took a complement from both sides of the equation, but that can't be right, can it?


texts: Finding a parallel algorithm to transpose a matrix

texts:
Write a parallel algorithm which runs in $\Theta(n)$ time and transposes an $n \times n$ matrix on the $2D$ mesh SIMD Model with wraparound connections. Processing element $P(i, j)$ has local variables $A(i, j)$ and $T(i, j)$, where $1 \leq i, j \leq n$. When the algorithm begins execution $A(i, j) = a(i, j)$. After execution $T(i, j) = a(j, i)$. No processing element should use more than a constant number of variables. Prove that the cost of the algorithm is $\Theta(n)$.

(Question adapted from MJ Quinn book, Parallel Computing Theory and Practice 2nd Edition, Chapter 7).


texts: AVL Tree rotations : How to balance below AVL Tree with imbalance at root node

texts:
How to balance this AVL tree after inserting node 5, using left/right rotations as indicated in the AVL tree tutorial. I have tried applying both double rotations but with no luck. Either of the double rotations still ends up producing a tree with imbalance as indicated above.

Do you mean the below solution?


texts: Is there any way that I, a CLI PHP developer, could "hook into" some kind of AI blackbox?

texts:
For many years now, I have heard about "AI" and "neural networks" and all these buzzwords, and it is regularly claimed on Slashdot that this or that open source program is able to "do AI". But then I go to its website and I have no idea what I'm even looking at, let alone how to actually use it. I give up and forget about it... until the next time I hear something about "AI" and how it's now apparently seen as something as fundamental and crucial as a variable or function or constant.

Is this just utter fiction, made up nonsense, vaporware, or is it concretely possible to "hook into AI" like a "turn-key blackbox"?

I imagine that, from CLI PHP, I send a command such as:

ai_blackbox.exe --input="What are 1 + 1?"

And the ai-blackbox.exe then calculates my input, by spinning up a whole "neutral net" or whatever AI does internally, and quickly spits out:

2

Is that "a thing"? Is there something fundamentally wrong with my understanding of this?

Of course, in reality, I assume that the input is much more advanced than that. Something which would be unbearably slow to calculate in PHP but goes super fast with the ai-blackbox.exe?

Every single time I have asked anyone about this, I have never got a clear answer or reply. They either agree with me that it's just nonsense and doesn't actually exist, or they link me to some massive manual which I'm utterly unable to comprehend.

Can I actually use this, today, for anything meaningful, in a simple way?

Or is this exclusively useful for a handful of scientists doing some very specific work and who need to "train" the AI in all kinds of ways before it can answer anything?


texts: Is the MinMax/optimization/search variant of a decision problem always easier/equal?

texts:
Is the MinMax/optimization/search variant of a decision problem always easier/equal in complexity because we can always reduce them to their decision variant?

From Wikipedia:

  If the longest path problem could be solved in polynomial time, it could be used to solve this decision problem, by finding a longest path and then comparing its length to the number k. Therefore, the longest path problem is NP-hard. It is not NP-complete, because it is not a decision problem.

Is the max-variant of this problem only NP-hard because the decision-variant is also NP-hard (and NP-complete)? (and not because it is harder)

What about polynomial time problems? If the decision variant of a problem is in P, I would assume that the optimization variant is not NP-hard, because that would imply P = NP. Do we say that it is in P then, or is it in another class/no class?


texts: Canonical representation of finite maps on non-overlapping finite rational intervals

texts:
I would like to have a canonical representation of a map from rational intervals (f, t] with f, t ∈ ℚ to some irrelevant value type. These intervals are non-overlapping and there exist only finitely many such keys in the map. I would like to be able to implement the following functions on this representation:

Lookup by rationals (not by ranges, as it is unclear what exactly that would mean)
Insertion by ranges. This will partial overwrite existing intervals (which are split in the process)
Compare two maps for equality by comparing their representation.
Create an empty map.

Particularly interesting are cases such as inserting two adjacent intervals with the same value V. I think for the map to be canonical, this case would have to be indistinguishable from inserting the joined interval with value V.

As always with (me and) canonical representations, I have failed to come up with any good leads on google (scholar). Is anyone aware of a result for this particular problem? I would be very thankful for any pointers to papers or implementations.


texts:
I'm reading a paper by David Monniaux An encoding of array verification problems into array-free Horn clauses.
Second page Line 10:
"Very often, desirable properties over arrays are universally quantified; e.g. sortedness may be expressed as :
$\forall k1,k2\, k1 < k2 \supset a[k1] \leq a[k2]$
Formulas with universal quantification and linear arithmetic over integers and at least one predicate symbol (a predicate being a function to the Booleans) are so expressive that one can define the execution of a Turing machine as a model to such a formula, whence this class is undecidable. There is, therefore, no general algorithm for checking that such invariants hold, let alone inferring them."
But as far as I can understand universal quantifier at outside should not be a problem. We can always eliminate quantifier if it is the only one (excluding the case where an alternative quantifier is present). Can someone help?


texts: Polynomial-time algorithm with exponential space is eligible?

texts:
I'm curious about two things.

When we define the class called "probabilistic polynomial-time algorithm" in computer science, does it include polynomial-time algorithm with exponential space?
For example, when algorithm is considered to be given a input from domain $\{0,1\}^n$,
what if the algorithm internally queries its exponential sized table (ex. $0^n\to0,0^{n-1}1\to1$ and so on..) and outputs the result? Does it still polynomial-time algorithm?
In theoretical cryptography, one-way function $f:\{0,1\}^*\to\{0,1\}^*$ has a requirement, which is related with hard-to-invert property, as following block.
If the answer to above question is yes, is it possible to construct algorithm $A'$ to simulate exactly same as $f$ for every value in $\{0,1\}^n$ using exponential table as described in above question? If then, it implies that it's impossible to design one-way function which is definitely not true. So what have i missed?

  For every probabilistic polynomial-time algorithm $A'$, every positive polynomial $p(\cdot)$, and all sufficiently large $n$'s,

  $Pr[A'(f(U_n),1^n)\in f^{-1}(f(U_n))]<\frac{1}{p(n)}$

  where $U_n$ is random variable uniformly distributed over $\{0,1\}^n$


texts: I've got a question. How can i simulate Turing machine with a double-sided infinite tape by a Turing machine with one-sided infinite tape? The condition is, that the simulation of one step of the first machine must be equal to O(1) steps of second machine. Do you have any idea, how to do this?


texts:
In the case of LBAs (Linear Bounded Automaton), in writing a decider for the language

$\qquad A = \{ \langle M,w\rangle \mid M\ \mathrm{LBA}, w \in \mathcal{L}(M) \}$

we reject the input after a specific number (number of possible different configurations) of computation steps.
We say that the machine must be looping after this many steps.
Why don't we just check in every step to see if there is a loop (repetition of the same configuration) and if it is the case then just reject the input?


texts: Travelling salesman problem with small edge weights

texts:
Are there any advantages in finding the shortest tour for the problem if edge weights are much smaller than the number of vertices?

Let's say the maximum edge weight is $n$, and the number of vertices is $n!$, and the adjacency matrix is dense and all distances $d_{ij}$ satisfy $0 \le d_{ij} \le n$. Are there any known methods which work well in similar cases?


texts: An algorithm to find the maximum profitable assignment

texts:
Given a set of workers $w_1,...,w_m$ and and a set of tasks $t_1,...,t_n$, and a  $m\times n$ matrix $P$ s.t. $P(i,j)$ is the profit of assigning worker $i$ to task $j$. One worker can only be assigned to one task, and one task can only have one worker. We want to find the maximum profit of all possible assignments.

Does anyone knows an algorithm or approach that can efficiently solve this problem and help provide a name or reference? Thank you.


texts:
I am aware the convex hull algorithm known as Graham Scan can be computed by sorting the derived vectors from points given in a 2D plane. One then iterates through a series of Cross Product calculations to find the determinant of a pair of vectors derived from the sequence of given points. This determine whether to move clockwise of counter clockwise with respect to drawing a convex hull in an efficient manner.

How do I represent that using sigma notation?

I was thinking along the line of:
$\sum_{i=1}^{N} Det(V_i,V_{i+1})...Det(V_n,V_{n-1}),$
where $V_i$ is the initial vector.


texts: How to convert a Complete Binary Tree to a Priority Search Tree in O(n)

texts:
There doesn't seem to be any resources on this.
I would like to know if there is a linear-time algorithm to convert a Complete Binary Tree with data left-to-right increasing stored in external nodes, to a Priority Search Tree.

edit: Convert = create a priority search tree with all of the elements of some complete binary tree

edit 2: or modify the original Complete Binary Tree such that it has all of the properties of a Priority Search Tree


texts: Can cognitive architectures (CLARION, SOAR, ACT-R) be used for creative mathematical reasoning?

texts:
Can cognitive architectures (CLARION, SOAR, ACT-R, others) be used for creative mathematical reasoning? As far as I understand, then it is the best to encode formal mathematical knowledge in the languages of proof assistants like Coq (CIC - Calculus of Inductive Constructions), Lean, Isabelle/HOL, Mizar. But those proof assistants require manual/creative human invovlement for the tasks like:

concept/new definition creation, creation of theories;
formulation of theorems and lemmas (to be proved by proof assistant);
selection of arguments, selection of proof tactics, invention of new proof tactics;
goal definition and direction definition in forward reasoning/chaining, e.g. in creating more or less expanded full consequence set from selected set of theorems.

All these tasks require creativity, human-level determination and goal evaluation/selection. So - can these listed activies be done by the cognitive architectures or other computational creativity tools? Is such integration of hard/soft formal/creative proof-assistant/cognitive-architecture tools and approaches under research and development? Is there scientific literature about such integration specifically and about application of cognitive architectures to doing math generally?

Such integration and application can be of immense benefit to humanity. E.g. for the automatic generation and analysis of the algorithms for the optimization, robotics, scheduling etc. For the automatic search of new logics and for the automatic self-improvement of proof assistants and cognitive architectures themselves.


texts: Should i work with tree representation as an array of nodes and an array of edges

texts:
Here is the problem, i have a graphical component that displays a tree. It takes as input an array of nodes and array of edges(eg:an edge has a source and target).
I will be performing complex tasks, such as building the tree dynamically from user input, removing nodes adding nodes, hiding a node's children, i would need to traverse certain paths and collect information, and all things of tree such as getting children of a node or get all leafs etc.
I have two solutions: either manipulate directly both arrays i already tried with hiding a node's children and it was fine.
Or map the two array into a tree structure and manipulate the tree to do what i want since there will lots of ready algorithms then map it back to the two arrays.
The first solution sounds better and easier at first, however if  things get more complex i will implement each function i need (such getting leafs etc) and the diffculty is manupilating a tree in a non tree representstion.
The second solution is better since its a tree there are a lot of algorithms but there is more work on mapping back and forth on each addition or deletion.
What do you think is better? (A compromise between being it easier fof me and performance)


texts: How does a co-NP problem differ from an NP (its complement) one?

texts:
I have quite a hard time understanding co-NP problems.

If we can reduce every problem to decision problem. NP problems should accept YES instances -> instances where the answer is yes. So for example for Traveling Salesman problem, we would ask "Is there a path that visits every city, and is shorter than N" ?

For co-NP problem, they should accept NO instance -> answer to them is NO. But given this, how would we formulate co-NP problem to Traveling Salesman problem I mentioned earlier? if we formulate it "Isn't there a path that visits every city and is shorter than N"? If there wasn't the path, the answer would be YES -> so it would be YES problem, if the answer was NO, we would have to try the path which would be same as YES problem.

So what is the difference? Was my co-NP decision problem to said TSP correct?

I have read wiki and tried to find some sources but nothing helped...

Thanks for help!


texts: Constant terms at each level of a recursion tree

texts:
In CLRS, exercise 4.4-5 the following question is asked:

Use a recursion tree to determine a good asymptotic upper bound on the recurrence $$T(n) = T(n-1) + T(n/2) + n$$

In my recursion tree, the sum of level 0 is $$n$$ level 1 is $$(3/2)n - 2/2^1$$ level 2 $$(3/2)^2n-14/2^2$$ level 3 is $$(3/2)^3n - 74/2^3$$
and so on. My issues is that the rule governing the constants 2, 14, 74 etc. is difficult to express as a function of the level so that I can create a sum for all levels of the tree.
Would it be correct to say that the cost at each level of the tree is $$(3/2)^in - O(1)$$
and thus avoid the problem of having to sum all of the constant terms via big O notation, or is this approach incorrect? If so, why and what should I do instead?


texts: What is the time complexity in solving a polynomial equation of degree N in one variable?

texts:
How easy/difficult(in terms of big-O) is it to solve polynomial equations of high degrees of N?

Do apps like Desmos actually solve equations to get roots or do they approximate roots by iterating through a range of values for x?

What mechanisms are at play in solving a univariate polynomial equation algorithmically?


texts:
Let L1, L2 be regular languages. And let A1=〈Σ,Q,q0,1,F1), A2=〈Σ,P,p0,2,F2) be their DFA.

Prove that the following language is regular, by making an appropriate NFA for it:

3={11′22′…′ |12…∈1,1′2′…′ ∈2} (Meaning, the language of all words in which the letters on the even positions (starting from 0) form a word from L2 and the letters on the odd positions form a word from L1.

Would appreciate help with that. Thank you.


texts: Problems with Θ(n³) complexity on TMs with lower bounds by communication complexity arguments

texts:
One of the most used simple examples of application of Communication Complexity is the $\Omega(n^2)$ lower bound for recognizing palindromes of length $2n$ on a single tape Turing machine.

Is there a similarly simple example that

proves a lower bound of $\Omega(n^3)$ for another problem
that can be decided in time $O(n^3)$
on a single tape Turing machine
using arguments from communication complexity?


texts: Strong normalization and concatenative programming language

texts: Are there some references about concatenative programming languages with the normalization property?


texts: What is the behavior of the given counter?

texts:
I found the following question -

For the circuit shown in the figure, the delay of the bubbled NAND gate is 2ns and that of the counter is assumed to be zero

If the clock (Clk) frequency is 1GHz, then the counter behaves as a

(A) mod-5 counter
(B) mod-6 counter
(C) mod-7 counter
(D) mod-8 counter

What I can see is, in this particular case clock time period is smaller than the delay in the NAND gate. But I am unable to see how it will affect the counter exactly!


texts: Using B trees to search inside dynamically changing array segments

texts:
Let $A$ be a sorted array. Suppose that this array is huge and can only be stored in a disk. In the I/O model and algorithms built in this model, every time we access the disk we spend an I/O and we get $B$ elements to the RAM. Since accessing the disk is much more expensive than accessing the main memory, we assume that what ever operations we perform in main memory, they come for free. So even if you scan 1 million times the entire RAM, in the I/O model, this would cost $O(1)$ I/Os, and that's the only thing we care about.

Suppose that you now receive queries in the form $[l,r, key]$ where $l$ and $r$ are indices which define a continguous chunk of the array $A$, and $key$ is a value that you want to search inside this chunk. So you want to know whether the key is somewhere in that chunk or not.

If you expect many queries to come, and we will make this assumption as well, it might be worth spending $O(\frac{N}{B})$ I/Os to build a B tree on top of the array $A$, and use the $B$ tree for your searches. Since the height of a B tree is $O(\log_{B}(N))$ each search will require $O(\log_{B}(N))$ I/Os.

However I was wondering, if the size of the chunk defined by the query is $n$, is it possible to use the same B tree to achieve $O(\log_{B}(n))$ I/Os? Because if we always start searching from the root of the B tree, we would first have to find where our chunk is, and then search inside the chunk, which is why the total number of I/Os would be $O(\log_{B}(N))$.

My idea would be to spend 1 I/O to access the leaf block in the B tree containing element $A[l]$, 1 I/O to access the leaf block in the B tree containing element $A[r]$, and then spend $O(\log_{B}(n))$ I/Os to find the least common ancestor block in the B tree of these two leaf blocks.  Then since we found the least common ancestor block in the B tree, we can start searching from there, spending in total $2 + O(\log_{B}(n)) + \log_{B}(n)$ I/Os.

Unfortunately I am very novice in the I/O model and this approach sounds too good to be correct. Is it really that easy for this problem or am I missing something?


texts: Bin packing with given bin sizes, not necessarily same

texts: I was thinking about variants of bin packing and thought of this variant wherein the given $m$ bins have size specified(not necessarily same) and we need to put $n$ objects in them. Is this still NP Hard, considering that bin packing is NP hard?


texts: Algorithm to split a grid into different shapes of similar area

texts:
I was wondering if any of you know of any algorithm which allows me to split a grid into smaller shapes of a similar area.

I have a grid and a few points, these points determine the center of the shape. For example, in a 100x100 grid, if I have 4 points at the following coordinates:
(25,25),(25,7) ,(75,25), (75,75)
I will have 4 square shapes of equal size in 4 corners of the grid.

However, there are instances where I would have less/more than 4 points and at locations that may be trickier, for example, 6 points at the following coordinates:
(14,12), (18,24), (74,41), (82,31), (04,72), (37,12)

I am aware that if the above was the case, the shapes won't be of equal sizes, but my goal is to try to have a similar area between all shapes.

Thank you for the help


texts: About independent set in triangle free graphs

texts:
From Wikipedia :

  An independent set of $\sqrt{n}$ vertices in an $n$-vertex triangle-free graph is easy to find: either there is a vertex with more than $\sqrt{n}$ neighbors (in which case those neighbors are an independent set) or all vertices have less than $\sqrt{n}$ neighbors (in which case any maximal independent set must have at least $\sqrt{n}$ vertices)

Why does any maximal stable set have at least square root of $n$ vertices?

Thanks.


texts: Giving a regular expression for a situation of a question

texts:
I have the following question regarding a situation given and we are then required to derive a regular expression out of it.

What i have to do now i to give a regular expression for this language described by the knob movement from A,B and C. Because i have to go through B if i were to traverse to C, and vice versa, i know that B must be present as part of the expression.

Here's what i attempted:

ABC U ABA U BAB U BCB U CBA U CBC

Simplifying it:

AB(C U A) U B(AB U CB) U CB(A U C)

I'm not entirely sure if I'm doing it right as I find out that I'm brute forcing. I'm terrible at deriving regular expressions so I'll appreciate some corrections.


texts: Chromatic number of a graph with $10$ vertices each of degree $8$?

texts: I have simple graph G on 10 vertices the degree of each vertex is 8. I need to determine the chromatic number of G. I tried drawing and all but it seems there is a trick needs to be used.


texts:
Why is the threshold for detecting errors $2d+1$?
I am aware that the question has been asked before, for example here, but the answers provided didn't really justify why the formula contains $+1$.

So why is there $+1$ in the equation?


texts: In which direction should I carry out a reduction when proving decidability/recognizability?

texts:
Definition:

  $\text{A fuction}\ f: \Sigma^* \to \Sigma^*\ \text{is a reduction from
Language A to language B if}\ w\in A \iff f(w) \in B\ \text{for every}\ w \in \Sigma^*$.

My question is which direction should I take in order to reduce a problem to another the other?

From what I've been reading I concluded we can prove that $A \leq_m B$ is we can use the TM of $B$ in order define the operation of the TM of $A$.

Let suppose I want to show that any co-recognizable language $L_k$ reduces to $\overline{HALT} = \{(\langle M \rangle, w): M(w)\ \text{doesn't halt}\}$, that is $L_k \leq_m \overline{HALT}$.

Then if $T$ is the machine working on $w \in L_k$ then I think we can make it work in this way

T on input w
  Run M on w;
     If M(w) = Halt
        Then Halt;
     Else
        Loop;

So if $w \notin \overline{HALT}$, then $M(w)$ halts and $T(w)$ halts $\implies w\notin L_k$.

If $w \in \overline{HALT}$, then $M(w)$ doesn't halt and $T(w)$ doesn't halt $\implies w\in L_k$.

Now suppose I want to prove that any co-recognizable language $L_k$ reduces to $L_{all} = \{\langle N \rangle: N\ \text{halts on every input}\}$.

My idea was to show that $\overline{HALT} \leq_m L_{all}$ and then by transitivity follows that $L_k \leq_m L_{all}$.

So I have to ''use'' the machine $R$ operating on $L_{all}$ to define a machine $P$ operating on $\overline{HALT}$.

Bu then I found this post Is the language of Turing Machines that halt on every input recognizable? which confused me a bit. There is shown that, indeed, $\overline{HALT} \leq_m L_{all}$ $(\overline{H} \leq_m AH$ in the notation of the cited post), but using the machine operating on $\overline{HALT}$ (with its corresponding input) to define the machine operating on $L_{all}$. To my eyes, it looks like the other way around.

So I'm lost.

One thing that gives peace to my soul is that all $m$-complete language are isomorphic. So probably I could shield myself behind this, assume that $L_{all}$ is $m$-complete in the class of co-recognizable language just as $\overline{HALT}$, and show what was shown in the post above. I mean, loosely speaking, assume the direction of reduction doesn't matter.

But if I don't want make this assuptiom (that $L_{all}$ is m-complete and therefore isomorphic) and just show that $\overline{HALT} \leq_m L_{all}$. Is valid to go from $(\langle P\rangle, w) \to R$


texts:
As the question states, how do we prove that $\textbf{NTIME}(f(n)) \subseteq \textbf{DSPACE}(f(n))$?

Can anyone point me to a proof or outline it here? Thanks!


texts: Maximal minimal DFA for some language of n-bit strings

texts:
Notation: $M$ is a DFA; $L(M)$ is the language accepted by $M$; $\min(M)$ is the minimal automaton equivalent to $M$ derived from a minimization algorithm such as the Hopcroft algorithm; and $|M|$ is the size of $M$: the number of states in $M$.
We are given the alphabet $\{0,1\}$ and some $n \in \mathbb{N}$.
Let's define some sets to set up the question.
$$ A = \{M \mid L(M) \subseteq \{0,1\}^n\}$$
So $A$ is the set of all automata that accept some language whose words are composed of $n$-bit binary strings. My intention here is also to require that all members of $A$ reject strings of other lengths. Building from this, consider
$$ A_{\min} = \{ \min(M) \mid M \in A \}  $$
So $A_{\min}$ is the set of all minimized automata from $A$. Building further, let
$$ x = \max \{ |M| \mid M \in A_{\min}\} $$
So $x$ is the size of the largest automaton from $A_{\min}$. Now we can specify the automaton or automata we're looking for:
$$S = \{ M \mid M \in A_{\min} \, \, \text{and} \, \, |M| = x  \} $$
How would one go about constructing a member (or members) of $S$? Any will do, but simpler constructions are preferred.
My initial naive attempt to do this failed. I tried building it up by induction, starting from a basis state which had two states: an accepting state and a non-accepting state. For the inductive step, I tried to build a binary tree composed of two different subtrees built from the previous step. This failed because minimization still merged common subtrees together.


texts: Is there any data structure that can't be represented or described inside a computer?

texts:
We all know that, at least theoretically, there are several possible models of computation, varying in structure.

Strictly speaking, there are several (not just one) models of computation that exist or have been implemented in real life. Some machines (for example, amplifier circuits), though inexact, can be considered analog computers, but that's not what we commonly think of as 'computers', is it?

The machines that we usually think of as 'computers' are implementations of a computation model with discrete parts (discrete memory slots, discrete instructions and clock cycles, etc.) I've always wondered if there's some form of data that can't be represented/stored inside these discrete structures.

I've brought up this question in many websites, but I usually only find people who approach this issue with an incomplete picture of the problem, and without the required logical rigor.

I've been told that nothing with a continuous structure can be stored inside a computer, but from what I've gathered, this is not always true. Take the example of a circle (a geometrical shape). It's true that it has an infinite number of points in its circumference, but I can't say that they represent an infinite amount of information, since they can be derived from a very small number of parameters (center and radius) and a bunch of simple laws (algebra and symbolic math). My intuition tells me that this is the case for any geometrical shape, unless it has an infinite number of parameters, in which case I don't really know what to think.

Is my intuition accurate? Is this the case for any structure with a finite number of parameters? Are Von-Neumann/Harvard/... computers unfit to store certain data structure(s)? Has this been mathematically proven? Is the proof constructive? Are there any data structures that can't be stored in any known model of computation (or, for that matter, any model of computation)?

Note: I'm asking all of this from intuition. Even though I write code for a living, and harbor a great interest in Computer Science (and have a little knowledge of it through self-study), I am not a CS or Math graduate. From my limited, newbie perspective, I would think that this question belongs to the Theoretical Computer Science Stack Exchange, but I genuinely don't know if it's too basic, so I'll just play it safe for now.


texts: Will the Ford-Fulkerson algorithm always find the max flow if we start from a valid flow?

texts:
I stumbled across this question and answer (source):

  Question: Suppose someone presents you with a solution to a max-flow problem on some network. Give a linear
  time algorithm to determine whether the solution does indeed give a maximum flow.

  Answer: First, verify that the solution is a valid flow by comparing the flow on each edge to the capacity of
  each edge, for cost O(|E|). If the solution is a valid flow, then compose the residual graph (O(|E|))
  and look for an augmenting path, which using BFS is O(|V | + |E|). The existence of an augmenting
  path would mean the solution is not a maximum flow.

Does this mean that the Ford-Fulkerson algorithm will reach max flow if given any valid flow as input, instead of initializing all edges to 0 at the start?


texts: Computing Nash equilibria in discrete auctions

texts:
I am trying to compute the (pure strategy) Nash equilibria of some discrete auctions.

More precisely, let us define the strategy of each player as a function mapping from every valuation that they might have to their bid (i.e. the 'bidding function'). Let us suppose that each player's valuation is drawn from some finite set and that their bid must belong to this same (finite) set. I am interested in finding the set of bidding functions, one for each player, such that each player's bidding function is optimal given the bidding functions of all the other players.

If it makes things easier, we can assume that valuations are symmetric (i.e. each player's valuation is generated by the same probability distribution) and that there are only two bidders. Ideally, however, we would proceed without these simplifications. I am interested in computing the equilibrium for the first price sealed bid and all pay auctions (in the latter, you pay your bid even if you lose; in the former, you don't.)

I have considered writing down the discrete auction game in normal form and finding the equilibria using software like Gambit. However, this would seem tricky since the strategy space is so large.  For example, if a player chooses bids from $ \{1,...,10\} $ and draws values from $ \{1,...,10\} $, then already they have $10^{10}$ pure strategies.

Does anyone have any ideas about how to proceed here?


texts: Difference between Time-sharing computers and computers which use Round Robin scheduling algorithm?

texts:
So maybe I'm confused in these concepts

but i thought that time sharing computer is a computer which the processor switches between different processes quickly to achieve a good response time

but isn't this the same as Round Robin algorithm?! i mean aren't we scheduling between different processes   in Time sharing computer just like Round robin? or am i missing something here? what is the difference?


texts: Is it possible that the subtraction between two undecidable languages is regular?

texts:
If $L_1$ and $L_2$ are both non-decidable languages (Not decidable, so can be SD
or $\lnot$SD), is it possible that $L_1-L_2$ is regular and $L_1-L_2\neq\phi$, where $\phi$ is the empty set?

What's a good way of tackling this question? Me and some classmates have been stuck on this question for a while, and this was the best we've got:

It should be possible given the following example:

Let $L_1=H\cup a^*$ and $L_2=H$, where $H=\{<M,w>:$ Turing machine $M$ halts on $w$$\}$, so $L_1-L_2=L_1\cap \lnot L_2=(H\cup a^*)\cap \lnot H=\lnot H\cap a^* = a^*$ which is regular. (we are saying $H$ does not contain $a^*$, so $\lnot H$ must contain $a^*$, hence why the intersection gives $a^*$.)

But we are not confident this is correct due to the last part with the intersection does not feel right. What's the answer to this question?


texts: Universal Turing Machine run on Universal Turing Machine

texts: I am curious, what happens if we run Universal Turing Machine on itself?


texts: Oven cooking queue problem: need help to determine its nature

texts:
CS community!

I'm more of a practical programmer than a computer scientist, so I need your help to find a solution (or at least point me into the right direction) to an extremely practical problem related to cooking food in the oven.

Problem

I have N ovens and I have multiple various ingredients to cook in them.
Each ingredient has certain preparation (e.g. peel the potato, cut the meat, etc.) time and oven cooking time. At time 0 we start preparing ingredients and putting them into the oven to cook. I need an algorithm to find the most optimal arrangement for the queues of these N ovens, so that it takes minimum time to finish cooking all of the ingredients.

Additional note: each ingredient is cooked at specific temperature, so no 2 ingredients can be cooked simultaneously.

Example

2 ovens: O1, O2

7 ingredients:

A (PT 200, CT 400)

B (PT 180, CT 380)

C (PT 80, CT 240)

D (PT 60, CT 180)

E (PT 40, CT 120)

F (PT 20, CT 60)

G (PT 0, CT 20)

Where: PT - preparation time, minutes; CT - cooking time, minutes.

I solved it simply visually and found that optimal solution looks like this:

Time: action

0: put G in O1
20: take G from O1, put F in O1
40: put E in O2
80: take F from O1, put C in O1
160: put take E from O2, put D in O2
320: take C from O1, put A in O1
340: take D from O2, put B in O2
720, take A from O1, take B from O2 -- finished in 720 min!

Visually it looks like this:

Conclusion

In a search for an answer I found that problem cannot be solved by simply sorting ingredients in some order, as changing the timing on one of the ingredients can dramatically change the cooking order: sometimes ingredients need to wait for certain time, even though they are prepared and ready to be cooked -- the priority queue can change completely!

Question

Whoever sees any similarities with certain mathematical or CS problems (Knapsack? Packing?), please point me in the right direction. Or, preferably, point me to the solution, which surely must exist for such an obvious problem.

Thank you!


texts: How many minimal spanning trees are there when all edge costs are distinct?

texts:
Suppose all costs on edges are distinct. How many minimal spanning trees are possible?

I dont know if this question is supposed to be easy or hard, but all I can come up with is one, because Kruskal's, and any other greedy algorithm should choose all the smallest weighted edges first. Then, if all weights on all edges are distinct, then there are no two equivalently weighted minimum spanning trees if a greedy algorithm is used.


texts: Circuit complexity of random Boolean functions

texts: I just saw a YouTube video where Ryan Williams gives a talk about circuit complexity. He stated that random Boolean functions require exponential size circuits to compute, but I don't understand why this would be so. Can someone explain this aspect of circuit complexity for me? Thank you.


texts: What does it mean to "strengthen the precondition and weaken the postcondition" in Hoare logic?

texts:
Having learned a rough summary of Hoare logic (i.e. learning just the basic concept of Hoare triples and a few of the rules) I kept seeing a statement along these lines:

  The rule of consquence allows us to strengthen the precondition and weaken the postcondition. (paraphrased)

What does it actually mean to strengthen the precondition and to weaken the postcondition?
Is and used in its strict logical meaning in this sense, i.e. if we apply the rule of consequence we will always do both? Or can it be read as allowing us to choose to strengthen the precondition or weaken the postcondition?

I get the (very basic) idea of the rule, but this statement implies the rule can be applied for a strategic reason that isn't clearly explained.

Thanks.


texts: Equivalence of two approximation algorithms for min Steiner tree

texts:
I learned two approximation algorithms for the min Steiner tree:
The first algorithm:
1- Compute the metric closure G' of G.
2- Compute a min spanning tree T' of G'
3- Construct the union U of the shortest paths in G which correspond to edges in T'
4- Output the Steiner tree T contained in U.
The second algorithm:
1-Find a cheapest path that connected two required vertices which are not yet connected.
2-Repeat until all required vertices are connected.
My question is: can we write a proof to show that the equivalence of the two algorithms?
I think that the 2 algorithms are equivalent since the second one is based on Prim's algorithm for min spanning tree; it directly connects required vertices without explicitly doing metric closure.. But can we write a mathematical proof to show the equivalence?
Note: I encountered this question in these slides (last slide)
https://www.slideserve.com/una/approximation-algorithms-combinatorial-approaches


texts: Complexity of testing membership in a disjoint set

texts:
I have a disjoint set data structure (sometimes known as a union-find data structure) where I store a value in each "node".  I want to look up a node by value.  How can I do this?

The representations normally discussed in literature, both linked list and forests, deal with operations being given nodes (of the linked list or forest), not values contained therein, which avoids any difficulty caused by having to find the node that contains a given value. From what I can see, the question of whether a given disjoint set contains in any subset a given value, or finding the node that contains a given value if one exists, is scarcely touched by the literature.

However, given values, this question needs to be addressed for an implementation of what the CLRS Introduction to Algorithms calls Make-Set(x) if one wishes to not trust the user of the API to always know what is and is not in the set, as it has a prerequisite that x does not already exist in the set.

With both representations, I see no way better than $O(n)$ to check membership, as one must always check all nodes for equality. Obviously one could maintain a separate mapping of values to nodes for the set, with $O(log n)$ lookup given an ordered value type, but this means duplicating the whole set in memory. Is there any way to represent a disjoint set while being able to test set membership in less than $O(n)$ time without duplicating the data?


texts: Smallest integer with k 1-bits that is the sum of two integers with g,h 1-bits respectively

texts:
Given integers $g, h, k, n$ how to find the smallest integer with $k\ 1$-bits that is the sum of two integers with $g, h\ 1$-bits respectively. Moreover, all three numbers (summands and sum) can have at most $n$ bits, i.e. the result is the n-bit number with $k\ 1$'s  and $(k - n)$ zeros, for instance $\underbrace{0...0}_\text{n -k}\underbrace{1...1}_\text{k}$. These $1$-bits don't have to be consecutive. Of course, such a number may not exist at all. You can think of this output integer (if it exists) as a permutation of a set of $n - k$ zeroes and $k$ ones.

I have a strong feeling that this is a dynamic programming problem but I can't get what is a subproblem here. I actually have no clue about DP relation for this problem. Could anyone give me some hints?

UPDATE. I've came up with the following plan:

Let $dp(g, h, k, n, carry)$ be such a sum, where $carry$ is an optional bit for carrying.
Then $dp(g, h, k, n + 1, 0)$ = $min\{dp(g,h,k, n,0),\ \ \ \ \  \ \ \ \ \ \ \ \ \ \ :(0, 0) \\2^n + dp(g,h,k - 1, n,1)\\ 2^n + dp(g - 1, h, k-1, n, 0), \ \ :(1, 0) \\ 2^n + dp(g, h - 1, k - 1, n, 0), \ \ :(0, 1)  \}$

$dp(g, h, k, n + 1, 1)$ = $min\{dp(g - 1, h, k, n, 1),\  \ \ \ \ \  \ \ \ \ \ \ \ \ \ \  \ :(1, 0) \\ dp(g, h - 1, k , n, 1),\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ :(0, 1) \\  dp(g-1,h-1,k, n,0)\ \ \ \ \ \ \ \ \ \ \  \ \ \  :(1, 1)\\
2^n + dp(g - 1, h - 1, k - 1, n, 1)\}$

I realized that this is too complex for me to handle on my own. I don't know what are the initial values (or base case of recursion in top-down approach) of this DP-table should be. Provided $g + h = k \leq n$ it is obvious that $dp(g, h, k, n, ?) = 2^k - 1$. As the question mark indicates, I don't understand what to do with the optional carrying bit in this case. I do not really understand how I should indicate there is no such sum, etc. Also, how to fill this DP-table? Should I use top-down approach? I need further help to proceed.


texts:
The intervals are represented as two numbers, e.g. $(4.3, 5.6)$. The intervals are unique.

If for $(x,y)$ and $(u,v)$, $x≤u$ and $v≤y$, $(u,v)$ is nested in $(x,y)$

How do I find out which intervals are nested in others efficiently?

The hint is to use two induction hypotheses: one to assume you can solve the problem for $n-1$ intervals, another that you can find the largest right endpoint for the $n-1$ intervals.

How do I use this information to do the inductive step in constant time?


texts: So for a project I am working on. I need to take a string representation of a floating point number, lets say "1.5" and do arithmetic on it with another floating point number. The catch is I cannot use floats to do this, since it specifically says in the requirements for my homework that I can't do this. How I am supposed to do something like add or subtract these numbers is break the string apart into it's characteristic (1) and it's mantissa(5). so in the program, the program will be represented as 1/2. However, if I wanted to add 1.5 with 1.3, 1/3 goes on forever. Thus making it impossible to convert 1/3 to 1/(some power of 10) and figure out how to add everything together. Is there an algorithm that can deal with cases of division like 1/3?


texts: Propositional truncation of excluded middle

texts:
It is clear to me that it should be impossible to prove :

exclMidl = isProp A → ((A) ⊎ (¬ A))

Because it would give deciding oracle for every Proposition.

My question is about the following Types:

exclMidl' = isProp A → ∥ ((A) ⊎ (¬ A)) ∥

or

exclMidl'' = isProp A → ∥ ((A ≡ Unit) ⊎ (A ≡ Empty)) ∥

Are they provable in cubical Agda?
What HoTT can say about them?

Those types would only state that propositions are either True or False but would hide information about actual Truthness of A, preventing us from constructing universal oracle, but allowing, for example, to do a proof for both cases even for undecidable propositions.

Is my intuition about such types correct?


texts:
I have a problem that I am working on an algorithm for:
I have $k$ sets of distinct positive integers (each set is distinct, not necessarily across sets)
$S=\{A_1,A_2,A_3,...,A_k\}$ where $\forall A_i\in S,\ A_i=\{a_{i1},a_{i2},a_{i3},...,a_{in_i}\},\ a_{ik}\in \mathbb{Z}^+, a_{ip}=a_{iq}\iff\ p=q$
(so $n_i$ would be the amount of numbers in each set)
The algorithm should find 5 sets in $S$ I will call $B_1,B_2,B_3,B_4,B_5$ where the following pairs of sets share an element:
$B_1,B_2$
$B_1,B_3$
$B_1,B_4$
$B_1,B_5$
$B_2,B_3$
$B_3,B_4$
$B_4,B_5$
$B_5,B_2$
where the element each of these pairs share is distinct
So if $A_2=\{4,5,7,37\},\ A_5=\{8,11,37\},\ A_7=\{4,11,21\},\ A_{12}=\{7,21,131\},\ A_{19}=\{5,8,131\}$
Then those 5 sets would be a potential output of the algorithm.

The way I would do it currently would seem very inefficient which would be to iterate through the sets of $S$. I would take $A_1$ and find all the sets in S that share an element with it. I would take one of those sets, $A_m$, find the sets that share an element with it that isn't that element that $A_1$ and $A_m$ shared. And continue that until I found 5 sets that worked.
There must be a more efficient solution but I am unaware of this type of problem and googling didn't help much. So if anyone knows a good way to do this or can point me in the right direction with analogous problems or topics I should learn about that would be very appreciated.


texts: How to use adversary arguments for selection and insertion sort?

texts:
I was asked to find the adversary arguments necessary for finding the lower bounds for selection and insertion sort. I could not find a reference to it anywhere.

I have some doubts regarding this. I understand that adversary arguments are usually used for finding lower bounds for certain "problems" rather than "algorithms".

I understand the merging problem. But how could I write one for selection and insertion sort?


texts: When is Huffman code the most unoptimal?

texts: By giving an Huffman coding tree and the total frequency of the characters. how can I find the most unoptimal frequencies for each character such that the size of the code will require the most possible of bits?


texts: Implications of polynomial time reductions

texts:
I'm reviewing for finals and have a sample problem that I think I understand, but would like someone to bless my understanding or smack me and tell me why I'm wrong.

I'm presented with a problem $\Pi$  of unknown complexity class.  If I can transform $\Pi$ to some problem $X$, where $X  \in {\sf P}$, what does that tell me about $\Pi$?

I think allows me to conclude that $\Pi \in {\sf P}$, right? If I can reduce $\Pi$ to another problem that's deterministically solvable in polynomial time, and the transformation itself can be done "easily" in polynomial time, then I can conclude that $\Pi$ is deterministically solvable in polynomial time, and therefore that $\Pi \in {\sf P}$ correct?

Conversely, given the same input, transforming $X$ to $\Pi$ in polynomial time allows me to conclude nothing meaningful, since nothing is known about  $\Pi$ right?


texts: maximizing inner product of vectors in an ellipsoid and a given vector

texts:
I have been wrestling with this for quite a long time but couldn't convince myself that the following is true:

What I do understand: $\theta_a$ denotes the set of points that are within the ellipsoid. Also, $A_{t, a}$ is a matrix that "describes" the shape of the ellipsoid. $\hat{\theta}_{t,a}$ is the red point that is the center of the ellipsoid, and $c_t$ is the "radius" of the ellipsoid.

I cannot show to myself that $\displaystyle\max_{\theta_{a}} x_{t,a}^{T} \theta_{a}$ can be derived into the LHS form: $x_{t,a}^{T} \hat{\theta}_{t,a} + c_t \sqrt{x_{t,a}^{T} A_{t,a}^{-1} x_{t,a}}$

Can anyone show me how this is true?

Thanks!

For more context, you can view it here: http://www.yisongyue.com/courses/cs159/lectures/LinUCB.pdf


texts: Solve the following recurrence-relations: $T(n)=5T(n/3)+T(2n/3)+1,T(n)=2T(\sqrt{n})+\log_2(n)$

texts:
Solve the following recurrence-relations:
my attempet for the first one was doing upper bound and lower bound by changing for lower $6T(n/3)+1$ and for upper $6T(2n/3)+1$  but i didn't get the same order for $\Theta$
$T(n)=5T(n/3)+T(2n/3)+1,T(1)=c$
$T(n)=2T(\sqrt{n})+\log_2(n),T(4)=2$
I'm not sure if I solved this right but:
setting $y(n)=T(2^n)$ we get
$y(n)=2T(\sqrt{2^n})+\log_2(2^n)=2y(n/2)+n$ using the master's theorem we get that $y(n)=\Theta(nlogn)$ and therefore $T(n)=\Theta(log(n)loglog(n))$
And for the first recurrence i still don't know


texts: Complete examples of program correctness proofs

texts:
Does anyone have any complete example of a proof of program correctness? I'm talking about something that includes the usual predicate, base case, inductive hypothesis, and inductive step. But also important is the loop invariant, and termination. I'm just not sure what the proper format for something like this is.

The only things I've been able to find are powerpoint slides from random schools, but they are for teaching purposes, and all over the place. I'm looking for something from start to finish, easy to follow, and formatted nicely that it can be submitted academically.

I wish to understand what a program proof looks like when (if) it is used for real, rather than as a proof sketch for a toy example in the classroom.


texts: How does changing cache size and/or block size affect the hit rate of the for loops in the following code?

texts:
I am working on practice problems to study for an upcoming exam. I am given the following piece of code:
#define LEAP 4
#define SIZE 64
int foo[SIZE];
// Assume foo has been initialized to contain values.
// Assume the cache starts empty at this point.
for (int i = 0; i < SIZE; i += LEAP) { // Loop 1
  foo[i] = foo[i] + i * (i + 2);
}
for (int j = 1; j < SIZE; j += (LEAP * 2)) { // Loop 2
  foo[j] = foo[j] + j * 5;
}

I have a direct-mapped cache containing 128 bytes with a cache block size of 32 bytes. The cache uses LRU replacement and write-allocate and write-back policies. I also need to assume i and j are stored in registers, the array foo starts at address 0x0, and the cache starts out empty. I already determined the hit rate for both Loop 1 and Loop 2, however, I am exploring more into this problem than what is asked as an exercise.
Assuming that all factors remain the same as shown in the original code, how would changing cache size (say from 128 bytes to 256 bytes) affect the hit rate of both loops? Similarly, how would changing the block size (say from 32 bytes to 16 bytes) affect the hit rate of both loops?
My initial assumption would be that if we increased the cache size, then that would increase the hit rate of both loop 1 and loop 2 because it would reduce misses. For decreasing block size, then the hit rate would increase for both loop 1 and loop 2 because if block size was increased, then there would be a decreased number of entries in the cache and it will take more time to fetch block size from memory.
Is my logic incorrect? If so, can someone explain what would happen in terms of the hit rate in both loops by implementing the changes I am suggesting. I am still a little unsure of what I claim would be true. Any feedback or suggestion in helping me answer this conceptual question would be greatly appreciated.


texts: The solution to my wind farm layout optimization using GA produces different results every time i run it. Is their a way to curb it?

texts:
Each layout consists of 1000 turbines or more and is ranked based on power produced.
The way my algorithm works is:-

>>Initial parents created(2 layouts)
>>Crossover and Mutation of Initial Parents and population is created
>>Calculation of power produced by each layout
>>Sorting of layouts using power values
>>Top 2 layouts producing max power selected for next generation
>>The steps are repeated till termination criteria is reached

each time I run the algorithm, I get a different configuration of layout.
Can anyone help me out in reducing the ambiguity in the output?


texts: Why is there no contradiction when using pumping lemma on a^N b^N a^2N, when k=2?

texts:
I have question where it asks:
Using the pumping lemma on a^N b^N a^2N, why can you not reach a contradiction when k=2?
Here's what I've done, but I do reach a contradiction...
u=a^r
v=a^s
x=a^t b^N a^2N
Where r+t+s=N.
When k=2, then uv^2x=a^N+s b^N a^2N
Therefore, this is a contradiction as N+s>N.
Is this a contradiction?
Thanks


texts:
I am reading Automata Theory book by Hopcroft, Motwani and Ullman 2nd ed.
In this book, there are these sentences:

  In general, if we have an algorithm to convert instances of a problem $P_1$ to instances of a problem $P_2$ that have the same answer, then we say that $P_1$ * reduces to *$P_2$. We can use this proof to show that $P_2$ is at least as hard as $P_1$. Thus, if $P_1$ is not recursive, then $P_2$ cannot be recursive. If $P_2$ is non-RE, then $P_1$ cannot be RE.

I am quite confused due to last statement above because the book further states the following theorem:

  If there is a reduction from $P_1$ to $P_2$, then:

  If $P_1$  is undecidable then so is $P_2$.
  If $P_1$ is non-RE, then so is $P_2$.

I dont know whether I should feel that the last statement above contradicts with the last statement in the first paragraph. So whats true?

  If $P_2$ is non-RE, then $P_1$ cannot be RE.

Or

  If $P_1$ is non-RE, then so is $P_2$.

Or both mean the same and I am unnecessarily thinking that they are contradicting each other unnecessarily? Or the book is wrong?


texts: Reducing Coin Change Problem running time to depend on the denominations, not sum being changed

texts:
I asked my Advanced Algorithms professor recently if we could solve the coin change problem (least number of coins necessary to make change for S cents using denominations d1, d2, ... dk). I thought this might be possible using something like the least common multiple of the denominations to find a subset of answer that could be used to determine the whole answer, independent of the size of S.

My professor said that this is actually a very complicated problem, and there was a paper in the 90's or 2000's to that demonstrated this solution. He couldn't remember the reference for this paper, though. Could anyone provide the reference? I would be very appreciative.


texts: Does Kernighan-Lin algorithm guarantee its partitions to be a connected graph?

texts:
Currently I am experimenting with Kernighan-Lin algorithm to produce coarse representation of navigation mesh for hierarchical pathfinding.

Based on the use case, my requirement is that partitions produced are a connected graph on its own.

For example, a bisection of the below grid

x--x--x--x--x--x
|  |  |  |  |  |
x--x--x--x--x--x
|  |  |  |  |  |
x--x--x--x--x--x

Should produce something along the lines of

a--a--a--b--b--b
|  |  |  |  |  |
a--a--a--b--b--b
|  |  |  |  |  |
a--a--a--b--b--b

where all nodes in partition A can be reached from a node in partition A without crossing a node in partition B.

However in quite a number of tests, I am getting disconnected partitions such as.

a--b--b--b--a--a
|  |  |  |  |  |
a--b--b--b--a--a
|  |  |  |  |  |
b--b--b--a--a--a

I am not able to judge if this is a bug in my code or whether the Kernighan-Lin algorithm by nature does not guarantee connected partitions.

I know that KL algorithm works towards a locally optimal solution for minimum cut, but does the algorithm not guarantee connected partitions?


texts:
I am trying to implement a trigram HMM tagger for a language that has over 1000 tags. In my training data I have 459 tags. Now if we consider that states of the HMM are all possible bigrams of tags, that would leave us with $459^2$ states and $(459^2)^2$ transitions between them, which would require a massive amount of memory.

Are there any workarounds around this?
What I thought of is considering only bigrams seen in the data, but it is still a lot of memory.


texts: Regular Expression from Context Free Grammar

texts:
The purpose of this exercise is to write a program that recognize all the words derived from this grammar.
The time complexity of this program must be O(n) hence i must be able to derive a regular expression from the grammar

  $S\rightarrow ASA\mid A$
  $A\rightarrow aAa\mid aAab\mid bA\mid\epsilon$

By intuition I guessed that this grammar generates words in the form of
$\left \{ a^ia^jb^*a^jb^ja^i \right \}^*$ and, correct me if I'm wrong, this doesn't seems like a regular language.

My problem with this type of exercise (I've tried a lot like this) is that there is no automatic way to find the regular expression from the grammar even if it generates indeed a regular language. Any advice on how to proceed on exercises like this?


texts: Number of processes needed to maximize CPU utilization under I/O wait conditions

texts:
A computer has 2 GB of RAM of which the operating system occupies 256 MB. The processes
are all 128 MB (for simplicity) and have the same characteristics. If the goal is 99% CPU
utilization, what is the maximum I/O wait that can be tolerated?

My professor said that there are 14 processes in the memory before proceeding with the solution. Why are there 14 processes?


texts: Difference between *device descriptor* and *device handler*

texts:
I am studying Computer Architecture,
and am a bit confused about the difference between device descriptors and device handlers in operating systems. Am I correct in saying that a device handler is actually a device driver?

What confuse me is that while the terms
device handler and device handler appear in the course slides,
I couldn't find then in the course textbook.
The closest term I could find there is device driver.


texts: The math behind converting from any base to any base without going through base 10?

texts:
I've been looking into the math behind converting from any base to any base. This is more about confirming my results than anything. I found what seems to be my answer on mathforum.org  but I'm still not sure if I have it right. I have the converting from a larger base to a smaller base down okay because it is simply take first digit multiply by base you want add next digit repeat. My problem comes when converting from a smaller base to a larger base. When doing this they talk about how you need to convert the larger base you want into the smaller base you have. An example would be going from base 4 to base 6 you need to convert the number 6 into base 4 getting 12. You then just do the same thing as you did when you were converting from large to small. The difficulty I have with this is it seems you need to know what one number is in the other base. So I would of needed to know what 6 is in base 4. This creates a big problem in my mind because then I would need a table. Does anyone know a way of doing this in a better fashion.

I thought a base conversion would help but I can't find any that work. And from the site I found it seems to allow you to convert from base to base without going through base 10 but you first need to know how to convert the first number from base to base. That makes it kinda pointless.

Commenters are saying I need to be able to convert a letter into a number. If so I already know that. That isn't my problem however.
My problem is in order to convert a big base to a small base I need to first convert the base number I have into the base number I want. In doing this I defeat the purpose because if I have the ability to convert these bases to other bases I've already solved my problem.

Edit: I have figured out how to convert from bases less than or equal to 10 into other bases less than or equal to 10. I can also go from a base greater than 10 to any base that is 10 or less. The problem starts when converting from a base greater than 10 to another base greater than 10. Or going from a base smaller than 10 to a base greater than 10. I don't need code I just need the basic math behind it that can be applied to code.


texts: Example where overall running time of Boyer-Moore is faster than KMP

texts:
Consider the following claim: the pre-processing time of KMP algorithm is more efficient than the pre-processing time of Boyer-Moore algorithm, and the overall running time of KMP is rather more efficient than Boyer-Moore.

Is there an example Pattern p and text T to illustrate why one should not agree with this statement?


texts: Path of maximum value with bounded cost in DAG

texts:
Consider a Directed Acyclic Graph in which every node has a value and a cost and edges do not have any weight. I need to find a path containing nodes such that sum of values of these nodes is maximized, but sum of cost over all these nodes must be at most C.

I am thinking of some modification of Dijkstra's algorithm. Any ideas? Is there any standard algorithm for this?


texts: Why do most scientists believe that P≠NP?

texts: I read that most scientists don't believe that P=NP. It might be subjective but can you simplify why not? I'm not informed enough to have an opinion but I'd like to know the definitions and some "pretty simple" explanation why to believe one or the other case, for instance why even believe that it can be proved?


texts: Is it possible to reduce a SAT problem to it's simplest form with no assumed variables in P time?

texts:
So as you read in the title I want to know if it is possible in polynomial time to reduce a SAT problem to it's simplest version in CNF format with no assumed variables?

The simplest form is with minimal gates in the circuit, assumed variable is not important it was assuming the value of a variable.

An example, I have a problem which has only one solution and it is phrased in CNF/SAT but a simpler version in CNF would be a list of conjunct clauses with only one var is it possible to simplify to that.

What if i already know the problem has a solution can simplification run in P time?


texts: Confusing equivalence $\Phi(n,n)\downarrow \Leftrightarrow \text{HALT}(n,n)$

texts:
Let $B$ be a recursive enumerable set and $B = W_n$, where $W_n = \{x \in \mathbb N \mid \Phi(x,n)\downarrow\}$ and $\Phi^{(n)}(x_1, \ldots, x_n, y)$ is the value of the function at the terminal snaphot.

There is a definition that leaves me really confused:
$$n \in W_n \Leftrightarrow \Phi(n,n)\downarrow \Leftrightarrow \text{HALT}(n,n)$$

the thing is we know that $\text{HALT}$ is not computable, therefore is is undefined so how is it possible that it is equivalent to $\Phi(n,n)\downarrow$ which is actually a defined function? What am I missing here?


texts:
I can't find this anywhere online. Is bitcoin mining NP-Hard?
If so, how would we be able to prove a reduction from a known NP-hard problem? I am a bit lost.


texts:
Is there an example of a sum of squares (SOS) hardness proof where the constraint is something non-trivial (like with some polynomial constraint) rather than just imposing the the typical $x_i^2 =1$ constraint? (which corresponds to working on the hypercube $\{-1,1\}^n$)

Anything which is directly formulated as a CSP will always be of this "simple" type where the only constraint is the Boolean hypercube constraint. But lets say the question is such that one can't see that being immediately writable as a CSP and hence one has non-trivial constraints.


texts: Clarification about conclusion of $Θ(nlogn)$?

texts:
Why the first part of formula is equal to $2 * 2^2 + ... +  2^{log(n)} = 2^2 + 2^3 +...+  2^{log(n)} = 2^3 +...+  2^{log(n)} =... +2^{log(n)}$
What is the logic behind ($2^{log n +1} - 2{log n}$)  ?
I don't understand why $2n.log - (2^{log (n+1)} - 2)=Θ(nlogn)$ ? (Please explain what is math logic bihind it)


texts: Algorithm for creating n-multiset out of x?

texts:
I have a problem that can be modelled by 15 undistinguishable balls to 21 boxes. The state of a node is defined by indices from 1 to 21 and corresponding values from 0 to 15, with the constraint that the sum of all values is 15. Those are the nodes of my (sparse) graph, the edges are defined by the rule: diminish the (non-null) value of an index by 1 and add 1 to (index +1). The values are the balls, the indices are the boxes.

Following the twelvefold way, i find that i have to create 15-multisets out of 21 and that there are $\binom{n + x - 1}{k}$ possibilities. In my case, those are 3.2E10 which is small compared to 21 to the 15th power (6.8E20) and can be kept in the memory of my machine.

What i now need is an algorithm for the creation of all nodes. The primitive way would be 15 nested loops counting from 1 to 21, inside of all doing some tests if the node is a permutation of (and so identical with) an already created node, but that would be too time-consuming (6E20 possibilities). Is there a faster way, looking only at the 3E10 "real" states?


texts:
Preparing for an interview.

I see two cases where each one is specially suited

BFS:  When you need to find shortest path between vertices (if one exists).

DFS:  If you need to find cycles in a directed graph:

Uses-case where both can be used:  Finding cycle in undirected graph, Is there a path from one vertex to another

Are there any other specialized or common cases?

In general DFS is considered to be simpler (though if graph is very deep, I am assuming we can have a stack overflow due to excessive recursion). So, if both can be used for a use-case, use DFS?


texts: What are some decidable problems which cannot be solved in real life(due to time and memory constraints)?

texts:
The first line of Sipser book for the Chapter- 'Time complexity', says that:

Even when a problem is decidable and thus computationally solvable in principle, it may not be solvable in practice if the solution requires an inordinate amount of time or memory.

My question is, yes we do have limited space and time, so the above statement makes the whole P and PSPACE concept as vague, right? If it so, what are these problems? Are such huge inputs acceptable in practice?


texts: Question related to Hilbert's 10th problem

texts:
Given $n \in \mathbb{N}$ and  $p,q \in \mathbb{N}[x_1,\ldots,x_n]$  one can define the following formula in the language of formal arithmetics

$$\varphi(n,p,q) = \forall x_1 \cdots \forall x_n : \neg (p(x_1,\ldots,x_n) = q(x_1,\ldots,x_n))$$

I would like to show that there are infinitely many triples $(n,p,q)$ such that neither $\varphi(n,p,q)$ nor $\neg \varphi(n,p,q)$ is a theorem of formal arithmetic.

In showing this I can use the fact that the problem of deciding if a polynomial $r \in \mathbb{Z}[x_1,\ldots,x_n]$ has a natural zero is undecidable.

Knowing the above fact we know that there is a polynomial $r \in \mathbb{Z}[x_1,\ldots,x_n]$ such that neither $$\varphi' = \forall x_1 \cdots \forall x_n : \neg (r(x) = 0)$$ nor $\neg \varphi'$ is a theorem. (Here the quantifiers are over the naturals which I am not sure if I can use deliberately?)

Once we have such $r$ we can write it as $$r(x_1,\ldots,x_n) = p(x_1,\ldots,x_r) - q(x_1,\ldots,x_n)$$ for $p,q \in \mathbb{N}[x_1,\ldots,x_n]$ and hence $\varphi(n,p,q)$ and $\neg \varphi(n,p,q)$ are also not theorems since $\varphi$ is logically equivalent to $\varphi'$ and we have shown that this is not a theorem.

Once we have one such triple $(n,p,q)$ we have infinitely many of them since we can just take $(n,p+k,q+k)$ for $k \in \mathbb{N}.$

Since I never did such things before I am wondering if the above reasoning is correct?


texts: maze solving algorithms (pledge algorithm)

texts:
I saw this maze, and tried to apply pledge algorithms to it. But I am not able to solve this maze using this algorithm. What am I missing/doing incorrectly?

PLEDGE ALGORITHM: in both cases we don't get to exit.

you can read about these algorithms at:

http://en.wikipedia.org/wiki/Maze_solving_algorithm

http://www.astrolog.org/labyrnth/algrithm.htm


texts:
What layer of OSI model does define the route of information transmission between sender and receiver computers?

A) Session layer
B) Physical layer
C) Data link layer
D) Network layer
E) Transport layer

In this question I think answer must be Network layer.But my teacher insists that answer is Transport layer.Even though i have shown in so many books it was written like that:

"Path Determination. The network layer must determine the route or path taken by packets as they flow from a
sender to a receiver. The algorithms that calculate these paths are referred to as routing algorithms."

this is from book that name is "Computer Networking: Top-Down approach, 5th edition,James Kurose",

chapter 4.1.Introduction and Network Service Models


texts: Does the rebalancing propagate upwards only to update the height of the nodes in an AVL tree?

texts:
I was studying AVL trees and was wondering if the only reason one propagates upwards to the node in an insert is to change the height. It seems to me that rebalancing does not recursively propagate back with only inserts but one might have to go back to change heights (since only nodes on the path from insertion point to root node have possibly changed in height, so we need to make sure we update them).

However, I was trying to form some type of proof that we don't actually recurse to the root and actually perform rebalancing. The proof I sort of had was the following:

The only way to recurse back to fix a unbalanced node is if we have two violations due to an insertion. One at some point down the tree and another one higher up the tree. When we do an insert the node increased height which caused these two unbalances. For us to have to recurse back we need to make sure even after the rebalancing of the lowest node, that the height doesn't decrease due to the rebalancing. This is unfortunately unavoidable because for that to happen, we'd need to be in one of the cases of rebalancing where the node's height doesn't change. Since the height of a node always decreases in an insert, then we don't actually need to rebalance.

Why don't we need to rebalance? That is because the only time we need to rebalance and the height doesn't change is when the right child of the lowest violating node $x$ has two subtrees that are balanced. That is not possible to happen because for that to happen, you need two inserts to cause that unbalance, but a single insert would cause the imbalance already, so the second insert won't make the right child of $x$ have two balanced subtrees.


texts:
If CFL are not closed under complementation, it means that if a language '$L$' is CFL then its compliment $L^C$ is not CFL. Then how can we discuss about $L^C$ being recursive?

My doubt arose because I think if a language cannot be decided CFL or not then how can it be declared Recursive ?


texts: Language to define perfectly a programming problem

texts:
Is there any language, which can be used to define all programming problems perfectly?

By perfectly, I mean with these two properties:

p is the problem.
d is the definition in the language.
P(d, p): "d is the definition of the problem p"

$$
\forall p\exists d(P(d, p))
$$
$$
\forall p\exists d1,d2((P(d1, p) \land P(d2, p)) \rightarrow (d1  \Leftrightarrow d2))
$$

Example: The simple problem to output the first N numbers, can be defined in many ways, for example in the english language. I want a language which restricts the number of definitions to 1 for every problem. In other words, no 2 distinct definitions can define the same problem, and every problem has a definition.

 1. This language exists?

 2. If such language does not exists, is it possible to create one?