All Questions

1
vote
1answer
10 views

How does the equation for min heap array indexing work?

I've been reading about min heaps, currently looking at this article, and I am very confused by something. The article makes the following statement: If a given node is located at index 'x' in the ...
0
votes
0answers
8 views

forming recurrence equations from code

Please could someone help me with understanding how to form recurrence equations when reading code? I'm having some trouble in my class: ...
-1
votes
1answer
39 views

Computer Networks, OSI model

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 ...
0
votes
1answer
24 views

Doubt regarding foreign key and referential integrity

I am studying database from Database System Concepts. The author was explaining foreign keys and referential integrity with the help of following schemas: $$ instructor(\underline{ID},\space name,\...
0
votes
0answers
9 views

Does Quadratically-Constrainted Quadratic Programming get easier if all constraints are equalities?

A Quadratically-Constrainted Quadratic Program consists of optimizing a quadratic objective function while imposing quadratic constraints, which can be inequalities or equalities. Obviously, ...
1
vote
1answer
27 views

Proof of the master thorem case with floors and b = 2

This question is related to my previous one. Let the following recurrence relation be given: $T(n)=aT(\lfloor n/b \rfloor)+f(n)$ where $a\geq 1, b > 1$ and $f(n) = \Theta(n^{\log_ba})$. Then $T(n)...
1
vote
1answer
20 views

Bachmair and Ganzinger, ordering of equations

Bachmair and Ganzinger (1991), 'Rewrite-Based Equational Theorem Proving With Selection and Simplification', page 4, defines an order on equations. (This is an arcane piece of machinery but a critical ...
0
votes
1answer
23 views

Is There An Established Way To Send Code Over a Network?

Let's say I have two computers on a network. I want to write code in some language on machine A, send the code in an efficient way over a network, and run the code on machine B. It seems to me that ...
0
votes
1answer
14 views

Removing max number of edges while keeping minimum distances

Suppose we have a graph with vertices from 1 to n.The graph is undirected and the starting point is 1 and we have path from 1 to any other vertex.We also have positive weight on each edge and there ...
0
votes
0answers
27 views

Data read vs instruction fetch

Why it is important for computer's security to differenciate between data read and instruction fetch memory access. As far as I know the processor have to know what is instruction and what is not ...
1
vote
2answers
29 views

Why it is not a Huffman code

I have been given several examples I the aim is to explain why it is not a Huffman code. So, for instance, the first one was: $\{00,01,10,110\}$ This code is not Huffman becuase it has just one ...
0
votes
0answers
8 views

Where can I find the algorithm in pseudocode for deleting a key from a B-Tree?

I am reading the chapter on B-Trees in Introduction to Algorithms (3rd edition) by Cormen and found the deletion procedure very confusing. I could understand the algorithm for insertion because it ...
1
vote
1answer
21 views

Lambda term satisfying two equations using Bohm Trees

Hi I'm trying to solve this exercise but I can't find any material online, it's not an homework I actually have sort of a solution (it looks incomplete though), but from that I can't really understand ...
-1
votes
0answers
13 views

RAM or SSD to improve the performance of Parallel Computing Toolbox Matlab [closed]

My laptop model is Omen Bang & Olufsen with 4GB RAM and 1TB HDD. When I run programs (47927632 no. of arrays) in Matlab Parallel Computing Toolbox, the laptop freezes and I was forced to hit the ...
-1
votes
0answers
16 views

How TO write a context-free grammar for this Language? [closed]

How can I write a context-free grammar and not context-free grammar for this Language : L:={a^n c b^n−1:n∈N*} Thanks
0
votes
0answers
14 views

What are some differences between regex (FSM) in computer science with regex in programming? [duplicate]

Computer science has automata theory with lessons on regular expressions and FSM. How are these different from regex engines used in programming such as C++, Perl, PHP etc.? I would like to know some ...
2
votes
1answer
32 views

Why 2 different edge min-cuts in an undirected multigraph must be completely disjoint?

For the proof of a maximum of (n 2) min-cuts in any n-vertex undirected multigraph using the random contraction algorithm, we need to know that no min-cut shares an edge with another different one. ...
1
vote
1answer
15 views

Multi-variate complexity semplification

I developed an algorithm with the following multi-variate complexity: $$O((k^n+kn)l^{kn}),$$ where $n,k,l$ are variables. I have very little knowledge of complexity theory, and I'm not sure whether ...
0
votes
0answers
14 views

Understanding acknowledgement mechanism in sliding window protocol

I came across following problem: Node A sends packets to B through router R. The link A-R is instantaneous , but the R->B link transmits only 1 packet each second , one at a time . Assume A sends ...
1
vote
0answers
20 views

Karp hardness of two vertex sets in a digraph

Given a digraph $G(V,A)$ and a number $k$, we want to find two vertex subsets $S,T\subseteq V$ such that: $|S|+|T|=k$ For every $v\notin S\cup T$, $v$ has no arcs coming to $S$, and no arcs coming ...
0
votes
3answers
48 views

Which is better ? Iterations or Recursions?

I've heard that any algorithm using iterations can be changed into one that uses recursions and vice-versa. But which type of repetition is preferable for minimum amount of computational effort and ...
1
vote
1answer
34 views

Why do I get different results from two calculation methods?

I am wondering what the reason for the following is We know that , exponential has a taylor representation : $$exp(x)=1+x+\frac{x^{2}}{2!}+\frac{x^{3}}{3!}+...$$ Using the first n terms , in R , ...
0
votes
0answers
8 views

Will putting computer to sleep wreck an installation? [closed]

I was installing Unity on the computer, and for some reason it appeared to shut off. When I woke it up, the installation looked to be fine. Did the installation get ruined somehow, or is it fine? Help ...
0
votes
2answers
19 views

Beta reduction order in Lambda calulus

Will it be wrong to use g for reducing (λx.λy.x) first in step (2) instead of using to reduce λg? Is there a rule against it?
0
votes
1answer
20 views

additive hash function

Do functions with the following properties exists for x being arbitrary stream of bytes: op(f(x1), f(x2))=f(x1+x2) and op(f(x1), f(x2))!=f(x2+x1) given that x1!=x2 where plus denotes concatenation ...
1
vote
2answers
45 views

Recognizer for decidable language and words it doesn't halt on

Suppose we have a decidable language B (there exists some TM that decides it). Suppose we have another TM M which only ...
0
votes
0answers
15 views

How to sort a woven shuffled stack

Say you have sort of a "woven shuffling situation" going on, sort of like this. Or that just looks like a regular shuffle for the most part. I'm trying to show the situation where something can be ...
1
vote
2answers
40 views

How can I efficiently find the largest positive interval in an unsorted array? [duplicate]

Given a set of values like [4, 8, 1, 5, 2, 6, 9, 2, 3, 5, 11, 9], how can I find the largest positive interval between any two of them? For example in the one I just listed, index 0 to index 1 has an ...
0
votes
0answers
11 views

How to identify the final set of “contours” when combining multiple primitive contours

This problem is in relation to how fonts work. Say you have a "glyph" that is composed of of these 5 "contours", or enclosed loops. On their own, each of them is a unified whole. The easiest thing we ...
0
votes
1answer
28 views

How to transform a Infinite decimal of $\frac{23}{6}$ into binary?

How to transform a decimal of $\frac{23}{6}$ into binary? $\frac{23}{6}$ is equal to $3.83333\bar{33}$, where the digit $3$s are repeated forever. I do know how to translate finite decimal into ...
-3
votes
0answers
29 views

Lenovo G500 shuts down exactly after 30 minutes! [closed]

We face next problem at our PC service: Lenovo G500 laptop shuts down exactly after 30 minutes! the problem is not related with OS (Windows) because laptop shuts down without HDD also (only BIOS ...
1
vote
0answers
9 views

Structure of numbers in descriptive complexity

Descriptive complexity is a useful way to free yourself from computational considerations when studying complexity. One of those considerations is the encoding of the structures you are working on. ...
1
vote
2answers
36 views

What's the right way to think about a CFG symbol with an infinite null derivation?

I'm curious about the right way to characterize symbol $A$ in a CFG like this one: $$ \begin{align*} A &\to A B\\ A &\to x\\ B &\to y\\ B &\to \varepsilon \end{align*} $$ $B$ is ...
2
votes
1answer
29 views

Word-hyphenation algorithm for monospaced fonts

I have seen a few standard hyphenation algorithms for non-monospaced fonts, where you are free to squeeze and separate words and letters, but I haven't seen any related to monospaced fonts ...
0
votes
1answer
40 views

Find value of $a$ or $b$ of two XOR equations

Is it possible to find $a$ or $b$ given that $a \oplus b = c$ and $c \oplus b = a$ when I only have the value of $b$?
1
vote
1answer
27 views

PRNG for a gaussian distribution?

I need suggestions for algorithm for Pseudo random number generators that will produce a near gaussian distribution (bell curve) for automatically generating test data. I know that PRNG produce ...
0
votes
0answers
9 views

How do I remove a particular element from an array in JavaScript? [closed]

I have an array of integers, and I'm using the .push() method to add elements to it. Is there a simple way to remove a specific element from an array? The equivalent of something like ...
1
vote
1answer
14 views

If you have a smallest grammar approximation, do you immediately have a CFG inference algorithm?

The smallest grammar problem is to find a single-string CFG. So given a finite list of language samples, known to all lie in some CFG, can we, using the smallest grammars (approximated) of each ...
0
votes
0answers
9 views

Performance of smooting vs viterbi algorithm with HMMs

To experiment, I implemented a discrete HMM; the transition matrix and emission model are randomly, uniformly generated. Then, a sequence of random states and emissions are produced by the HMM. Then I ...
-1
votes
0answers
4 views

Read a string(ex:“gejdk738€;!&;&”) i assembly tasm [closed]

How can I read a large string i tasm? What would tipically be the stop condition supposing I have to use a loop(if I have to). Are there other methods?
0
votes
0answers
29 views

Multiple Knapsack Problem, but with exact weight/capacity? (All knapsacks have to be filled completely)

I have a few knapsacks of given capacities. Also, much more items of given weights and values. As usual, items have to be put into knapsacks to maximize profit. What is different from a standard ...
2
votes
1answer
62 views

Confused about the correctness proof of Dijkstra's algorithm

In the proof of the correctness of Dijkstra algorithm, there is a lemma stating as follow: Let u be v's predecessor on a shortest path P:s->...->u->v from s to v. Then, If d(u) = δ(s,u) and edge (...
2
votes
3answers
101 views

N subsets with a given sum?

How to efficiently ¹⁾ choose from a set of numbers $S$, a given number $n$ of disjoint subsets, each with a given sum $K$ of chosen elements? ¹⁾ Not as in $P$, I just want something smarter than $O(n^...
0
votes
0answers
22 views

N-Queens problem - maximum number of function calls

N-Queens problem - maximum number of function calls. We say, that a backtracking algorithm (code below) 'checks' a setup of N queens, when the function isFree(n-1, y) is called for $0\leq y < n$ ...
1
vote
2answers
47 views

Is there a name for this type of Turing machine?

I'm considering turing machines with tape alphabet equal to $\{0,1\}$ and the blank symbol equal to $0$. Is there a name for this type of Turing machines? Isn't this type the one computers are based ...
0
votes
1answer
26 views

Which address bits are used for set selection/tag check in a cache?

If Capacity = 24 KiB Associativity = 6 Line Size = 32 B As far as I know: $$Capacity = Associtivity * Line Size * Sets$$ so $24576 = 32 * 6 * Sets$ $Sets = 128 = 2^7$ thus 7 least significant ...
0
votes
1answer
20 views

Give a Context Free Language, is the complement of this language always recursive(REC)?

I have seen some people make an argument that given the fact that Context Free Languages are proper subset of REC which is closed under complementation thus complement of a CFL must be in REC. I ...
0
votes
0answers
35 views

Show that if the transitive closure can be computed in T(|V |) time then BMM can be solved in O(T(3n)) time

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 ...
0
votes
0answers
8 views

Finding the 'capacity' of a network by treating it as a channel

Let's say I have a fairly basic network with two senders and two receivers. I'm wondering if I can treat this network as an effective communication channel that takes an input alphabet made up of the ...
0
votes
0answers
15 views

Johnson-Lindenstrauss and k-means

I have a question about Johnson-Lindenstrauss and k-means. I m study a resource that explain a link between Johnson-Lindenstrauss and k-means. From what I understand, Johnson-Lindenstrauss helps us ...

15 30 50 per page