# All Questions

31,820 questions
Filter by
Sorted by
Tagged with
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 ...
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-...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
1answer
13 views

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: ...
0answers
6 views

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 ...
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 ...
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 ...
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: ...
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 ...
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 ...
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. (...
1answer
20 views

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 ...
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 ...
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 ...
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 ...
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) = ∅ ∨...
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 ...
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 ...
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 ...
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", "...
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 ...
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