# All Questions

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

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

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

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