All Questions

Filter by
Sorted by
Tagged with
1
vote
1answer
15 views

How do web browsers find out the MAC address?

While reading through my textbook, I discovered that if you want to access a particular web page, your web browser will find out the IP address of the web server that hosts the web page and try and ...
0
votes
0answers
7 views

How do you derive a type $∃e(e)$ in terms of universally quantified types, without invoking Void initially?

I wrote a "proof" for this, and though it was enough to convince myself, there are a few things that bother me about it. Primarily I'm not sure about the loose way in which I'm swapping between first-...
0
votes
1answer
12 views

Why does arithmetic left shift of negative number leads to positive number?

According to this Wikipedia article, when arithmetic left shift operation is applied to a signed number, the number is multiplied by 2. But there are certain situations where a negative number becomes ...
0
votes
0answers
10 views

How are hardware interrupts handled?

I have read that a hardware interrupt is handled asynchronously by the CPU, which means that the interrupt signal may arrive at any point of time with respect to the CPU clock cycle. Now, this means ...
0
votes
1answer
11 views

Showing that $BPP \subseteq EXP$?

I am trying to understand why $BPP \subseteq EXP$. This question almost gives the answer (simulate $BPP$ machine on all possible toin cosses and then "act accordingly"). However, it is not clear to me ...
-1
votes
0answers
7 views

regression DNN: gradient checking doesn't match with backpropagation derivatives

I think the problem lies within a bad implementation of back propagation, it's the only way i could explain this (gradient checking that doesn't match backprop derivatives), but i'm not able to find ...
0
votes
0answers
7 views

Restricting randomisation in Gambit

I am trying to use Gambit (specifically, gambit-enumpoly) to the compute the mixed strategy Nash equilibria of some very large games. To make this computationally feasible, I would like to place some ...
0
votes
0answers
12 views

Number of nodes in a BST between two given numbers

Suppose there is a balanced binary search tree with $n$ nodes, where at each node, in addition to the key, we store the number of elements in the sub tree rooted at that node. Now, given two elements ...
0
votes
0answers
13 views

How to measure the length of the program on Turing Machine?

In Kolmogorov complexity, there is a notion: length of the shortest program that describes the data. I can use Lempel-Ziv compression to estimate this value. What if I want to estimate this value by ...
2
votes
1answer
14 views

Network density vs connectivity

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

Software management of TLB misses?

I'm reading an OS textbook and it was talking about TLB misses being handled by software. I'm very new to all this by the way. So there's a context switch to some kernel procedure. But surely in this ...
0
votes
1answer
13 views

Could following be a counter example to Church-Rosser (Confluence) theorem?

According to the "Type Theory and Formal Proof" book, Church-Rosser theorem (confluence) is as follow: Suppose that for a given term $M$, we have $M \twoheadrightarrow_\beta N_1$ and $M\...
0
votes
0answers
13 views

Cache mapping calculation

A cache has following specifications: Block size = 16 Bytes Set size = 2 way set associative Number of sets = 128 Physical address = 23 bits, byte addressable My Questions are: 1) How many blocks ...
0
votes
2answers
34 views

An example of a computable problem that is not in P

I am trying to find a simple example of a problem that is computable but not in P, I know very well that it would be enough to get one in NEXTIME-complete however the problems that I find in this set ...
0
votes
0answers
16 views

Find pair with maximum Appeal value

Find pair with maximum Appeal value. Input: Array Output: index {i, j} ( i = j allowed) with maximum Appeal Appeal = A[i] +A[j] + abs(i-j) Example 1: Input: [1, 3, -1] Output: [1, 1] Explanation: ...
0
votes
0answers
7 views

How to generate all combinations given an array of elements using backtracking?

Given an array, generate all combinations For example: Input: {1,2,3} Output: {1}, {2}, {3}, {1,2}, {2,1}, {1,3}, {3,1}, {2,3}, {3,2}, {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1} I am ...
1
vote
1answer
19 views

Is this set computable?

Let be $B$ a Busy Beaver function and set $W=\{\langle M \rangle :\text{$M$ stops in less than $B(10^{1000})$ steps on an empty tape}\}$. Is this set computable? I'm not sure how to approach this ...
-2
votes
1answer
16 views

Question about complexity of TSP Optimization problem

Is this statement true? Optimization TSP problems are known to be NP-hard, as we do not have a minimum cost to compare against, and in order to verify a solution is optimal, we need to iterate ...
1
vote
1answer
17 views

Use Fact to decompose a given number

Let Fact be the following decision problem. Given two natural numbers $k \le n$ the machine accepts if and only if $n$ has a non-trivial divisor that is less than or equal to $k$. Prove that if Fact $\...
0
votes
1answer
11 views

Loop invariant initialisation confusion

Consider the algorithm LastMatch below, which returns the offset (shift) of the last occurrence of the pattern P in text T, or -1 if P does not occur in T: ...
0
votes
0answers
6 views

Observational Determinism using HyperPCTL

I've found no material on HyperPCTL, so if you know please help me. This is the definition of Observational Determinism expressed using HyperPCTL and i have some questions. $\forall \sigma \, \forall ...
0
votes
0answers
7 views

what is the right strategy for labelling images to recognize table and understand data

I am trying to build a model to detect tables from images of machine plates(PFA) and create key/value pairs of the information present in the table. But I am not very sure that what is the best way to ...
0
votes
0answers
34 views

What complexity does this 'how many ways to climb' algorithm have?

I have a solution to the following problem: Given a stairway of $n$ stairs, which you can climb from $1$ to $m$ at the time ($1 \leq m \leq n$), return all the ways you can climb the stairway. ...
2
votes
1answer
25 views

Finding the closest visible vertex among line segments

Given a set $S$ of line segments (possibly sharing endpoints) and a query point $q$, how fast can we find the closest visible endpoint from $q$? If $p$ is the closest visible endpoint to $q$, then, in ...
1
vote
1answer
14 views

What is known about the sets enumerated by primitive recursive functions?

Let's say that a set of natural numbers $S \subseteq \mathbb{N}$ is primitive recursively enumerable if there exists some primitive recursive function $f$ such that $S$ is the range of $f$. That is, ...
0
votes
0answers
8 views

Using FFT in the following convolution in a simulation

I have the following convolution as part of a numerical simulation. $$T(r)=\int d^3r_2 p(r_2)f(r_2)\alpha(r-r_2)$$ My problem is that the analytical expressions for $f$ and $p$ do exist but, I have ...
0
votes
1answer
11 views

What can't guarded fragment of FO express?

I have some basic confusions about the definition of the guarded fragment of first-order logic. Hopefully someone can tell me where I'm wrong. GF in FO is defined by: Atomic formulas, $x=y$ and $R(...
2
votes
0answers
17 views

What is the purpose of standardization in machine learning?

I'm just getting started with learning about K-nearest neighbor and am having a hard time understanding why standardization is required. Reading through, I came across a section saying When ...
0
votes
0answers
37 views

How to compress a table knowning what queries will be executed on it?

There's table with four different fields: location, category, type, price. There's hundreds of locations and categories, but only four types and six hundred prices. A single query is used for this ...
0
votes
0answers
19 views

Why is it that Btrees most of the times have a degree that is odd? What happens if they are even?

I was watching a lecture video and the Professor states that it would be very rare to see the order of a Btree to be even. I was hoping for an explanation but he cut it off there and moved on with the ...
0
votes
1answer
34 views

Are there techniques to know how many times loops like these will run?

How do you evaluate how many times some loops will run, when you start to complicate the boundaries conditions? For example, take this function: ...
0
votes
0answers
30 views

How to prove this language is not regular?

I am currently learning Pumping Lemma and found this question. But I am not able to prove it not regular. L = { $0^n$ | n is power of 2}. So, here I considered w = $0^{2^n}$ where n is constant of ...
1
vote
1answer
24 views

Injectivity verification in o(n) space and O(n) time

The problem I want to solve is this: Given a list $A$ of $n$ elements, I want to verify that they are all distinct. If I were to do this "myself", I would need $O(n)$ space and $O(n\log n)$ time to ...
0
votes
0answers
9 views

Greedy algorithm for feedback vertex set / greedy algorithms vs local ratio in general

A greedy algorithm for finding a minimum feedback vertex set is to pick and remove a vertex with minimum $w(v)/\delta_H(v)$, where $H$ is the current graph, until there are no more cycles left. (...
1
vote
1answer
20 views

Question about proof of $NTIME(n) \subseteq DTIME(n^{1.2})$ implies $\Sigma_2-TIME(n^{8}) \subseteq NTIME(n^{9.6})$

In "Computational Complexity, A modern approach", Arora & Barak proof the following claim (Claim 5.11.2): Suppose that $NTIME(n) \subseteq DTIME(n^{1.2})$. Then $\Sigma_2TIME(n^{8}) \subseteq ...
0
votes
0answers
14 views

More information about the 10 types of information that can be useful for WSD (Word Sense Disambiguation)

Agirre and Martinez (Knowledge Sources for Word Sense Disambiguation) distinguish ten different types of information that can be useful for WSD (Word Sense Disambiguation): Part of speech (POS) ...
0
votes
0answers
10 views

What is the approximation for odd cycle transversal?

What is the best approximation for odd cycle transversal? (on general graphs) Sorry if this is easily found everything I found about odd cycles is about paramaterized complexity and kernels
-1
votes
0answers
15 views

I bought a new computer and would like to transfer data. Windows 10 to windows 10. can I use an old 2.0 transfer cable, or do I need a 3.0 cable [on hold]

I bought a new computer and would like to transfer data. Windows 10 to windows 10. can I use an old 2.0 transfer cable, or do I need a new 3.0 cable? The old belkin cable says for transfer windows 8.
-1
votes
0answers
29 views

Strongly connected components in a directed graph

Let $G$ be an arbitrary directed graph. Does $G$ always have the same strongly connected components on $G$ as on $G^*$? Here, $G^*$ is the inverted graph of $G$ (i.e., $(u,v)\in E \rightarrow (v,u) \...
0
votes
0answers
11 views

Optimizing Appointment Placement Algorithm

I am searching for an algorithm which might help me solve an optimization problem for appointments/time slots. Given a set of appointments each with the following parameters: dollar amount start ...
1
vote
1answer
19 views

On a number axis(One dimension), there are a bunch of points, each point have speed(to left or to right). Compute minumum time that two point meet

I have question about this question. How can I compute the minimum time for two points to meet in O(N) time. All I can think is brutely compute point pair and get the minimum. Can anyone give me ...
-2
votes
0answers
28 views

Binary representation [on hold]

John was not happy with the rating he got for the annual year 2017-18.He asked his boss Jim about ratings. Jim asked him to solve a puzzle and it is giving ‘N’ ,find if in the binary representation of ...
0
votes
0answers
5 views

How to define the stability (or convergence) of a ordering of a list of node

I have a problem which requires ordering nodes in a graph based on some given statistics. However, the given statistics of each node may be very hard to compute. Thus, I will use some sampling ...
0
votes
0answers
22 views

Which of the following languages a decidable? [on hold]

I have a question about the decidability of the following languages: 1. L = { | ab ∈ L(M) and M accept only w with |w| >= 10} 2. L = { | M only accept a finite number of words} 3. L = { | L(M) = ∅ ∨...
1
vote
1answer
23 views

Weird implementation of quicksort

I met a wired question from the algorithm test of my school. For the first time I thought it is a normal quick-sort problem and feel confident to solve it but as I read the algorithm carefully, it is ...
0
votes
0answers
12 views

What is a batch based interface?

I came across this description of Batch Interface: "commands and directives are used to manage those commands that are entered into files and those files get executed. " I would really appreciate if ...
2
votes
1answer
54 views

HamiltonianCycles in Random Graphs

Lets say we consider the Erdős-Renyi undirected random graph $G(n,p)$ with $V(G) = \{1,2,\cdots,n\}$ and $\displaystyle{P((u,v)\in E(G)) = p} \quad \forall u,v \in V $. Is there anything we can say ...
0
votes
1answer
31 views

Finding the last substring in lexicographical order in O(n) time

Given a string s, return the last substring of s in lexicographical order. Example 1: Input: "abab" Output: "bab" Explanation: The substrings are ["a", "ab", "aba", "abab", "b", "ba", "...
0
votes
0answers
4 views

DEs with fixed solution involving difference of ratios with tiny denominators

I'm trying to numerically solve coupled DEs of the form: a'(t) = b(t) / b0(t) - a(t) / a0(t) b'(t) = a(t) / a0(t) - b(t) / b0(0) where the functions ...
0
votes
1answer
17 views

AVL tree balance property states for the two subtrees of a node, their height can differ at most one. Why can't it be zero?

I was thinking that if they were equal, say they are required to be zero this would be enforce the balance property more effectively. Can anyone explain why 1 is a satisfactory rather than just them ...

15 30 50 per page