# All Questions

48,921 questions
Filter by
Sorted by
Tagged with
2 views

### Find effective memory access time in a system with TLB as well as physical address cache

The problem statement: I have a simple paging system with a TLB and a Physical Address Cache. Here's the flow: CPU generates logical address=(p,d) Given "p", CPU seeks in its TLB cache if ...
2 views

### Looking for references that can teach me some of the fundamentals of computer science (from Peter Norvig's TYPITY page)

I am looking for resources/books/blogs etc from which it can tell me "how long it takes your computer to execute an instruction, fetch a word from memory (with and without a cache miss), read ...
• 11
7 views

### Picking from a categorical distribution such that the selection is stable

Let's say I have a random variable $V$ which takes values from the finite set $V = \{v_1, v_2,...,v_N \}$. I want to pick one value randomly based on given probabilities $p_i = \Pr(V=v_i)$. Let's call ...
• 101
7 views

### How to find Broadcast ID

Suppose i have an IP address 192.168.1.0/26, the subnet mask for this IP will be 255.255.255.192 with 64 hosts and an Network ID of 192.168.1.0. The broadcast ID in the solution is 192.168.1.63 for ...
14 views

### why i am able to access private member of inner class with object of main public class,i am new can somebody please tell me

public class Encapsulation { public static class Enc { private int x; ...
25 views

### Vertex cover approximation: what's wrong with max-degree heuristic?

For context: the usual greedy approximation algorithm for the minimum vertex cover problem (given a graph, find the smallest set of vertices such that every edge is incident to at least one selected ...
• 121
8 views

### Sliding Window Subarray Question - TLE

Question: Given an integer array arr[] of size n. Your task is to count the number of good subarrays of the given array arr. Here any subarray arr[l ... r] is considered to be good if it satisfies the ...
12 views

### Let A be the language of strings such that every character in an even position is a 0 [duplicate]

Let A be the language of strings such that every character in an even position is a 0. Give a regular expression for A.
14 views

### Best Search Algorithim

In Microsoft Power Bi there are formulas that can be used in visualizations called measures. These measures can be used within the formulas of other measures. As a result, a measure can have a complex ...
324 views

### Accelerating semidecision of halting problem

There is a naive semidecision algorithm for the halting problem: simply simulate the program and see if it halts. Is there an algorithm that is asymptotically faster? More precisely, suppose the naive ...
• 220
1 vote
62 views

### Why can one define a Turing Machine by its "description"?

I read Sipser's "Introduction to the Theory of Computation" a while ago. I am confused that in the book it is stated that a Turing machine can be defined by its "description" such ...
• 113
12 views

### Why is it not possible to recognize a self-complementary graph just by searching for a self-complementary graph on $8$ vertices?

From the paper by Gibbs (1974) it is known that every self-complementary graph on $4n$ vertices has $n$ disjoint induced $P_4$ subgraphs. Let's call the collection of these subgraphs a $P_4$ cover. ...
• 1,781
1 vote
24 views

• 255
1 vote
23 views

### Sliding-window string/substring algorithm based on endpoints of substring

While there are various known algorithms to check if a string contains a substring (with the simplest but least efficient one being a brute-force sliding window, and one of the most efficient but ...
• 111
48 views

### Is the definition of "computational problem" on Wikipedia correct?

In the https://en.wikipedia.org/wiki/Computational_problem, the first line states: "A computational problem is a problem that may be solved by an algorithm." However, I have doubts about the ...
38 views

### Proof for Gas Refills on Circular Route Problem

The circular route gas station problem asks: If given a car with an unlimited gas tank, find the gas station on a circular road that if started from would allow you to travel station to station ...
54 views

### How many states does a 2-symbol turing machine need on average to compute a N bit number?

The busy beaver problem asks what is the largest number computable by a 2-symbol N-state Turing machine, however, most numbers however are not re-presentable by a smaller program. For a sufficiently ...
• 166
1 vote
11 views

### Are $\#Clique$ and $\#Coloring$ $\#\mathsf P$-hard on perfect graphs?

It is known that decision variants of these problems on perfect graphs are decidable in polynomial time. But is counting the number of maximum cliques or optimal colorings $\#\mathsf P$-hard on ...
• 1,781
19 views

### Is my characterisation of KVM and QEMU accurate?

I usually write essays on topics I am studying to help my understanding. Below are excerpts from my study of Virtualisation. I would like comments from real professionals on their accuracy. KVM is a ...
1 vote
22 views

### Help required for an example of a restricted 3,3-SAT problem instance?

"Let r,s-SAT denote the class of instances with exactly r variables per clause and at most s occurrences per variable. We prove the 3,4-SAT result to be the strongest possible and show that 3,3-...
• 745
32 views

### Minimum unsat core and generalization

I have a problem that has been in my head for some time, it might be already well known but i cannot find ressources on something similar : The idea came from the will to identify the minimal unsat ...
63 views

### Interactive Proof for Graphs with No Non-Trivial Automorphisms

I am looking for an interactive proof for the language $AUTO^C= \{𝐺∣\text{𝐺 is an undirected graph that has no non-trivial automorphisms} \}$. I am interested in a method similar to the interactive ...
1 vote
53 views

### Possible mistake in a book regarding parsing and lexical analysis

I was just reading a book (Algorithms and Theory of Computation Handbook, Volume 1) and I came across the following passage : "From a practical point of view, for each grammar G = (Σ,V, S, P) ...
22 views

### Knapsack problem with at least 1 item of two categories, no boundary on total items, unique items

Let's say we want to maximize the caloric intake of a person. One person MUST pick AT LEAST ONE steak and AT LEAST ONE vegetable (no limit of how many steaks or veggies he can pick, as long as they ...
51 views

### Are these two definitions related to strong NP-hardness equivalent?

Let $P$ be a computational problem whose inputs are integers. Consider the following properties: (a) There exists a polynomial-time reduction from some strongly-NP-hard problem $Q$ to $P$. (b) $P$ is ...
• 6,132
47 views

### What is the the maximum and minimum amount of nodes in a heap

The title of my question says all that is needed. Some may argue that this is a duplicate question, because some years ago, this same question was made, but I couldn't understand the explanation, then ...
41 views

### Decomposing a general polygon into simple ones

This is a question about splitting a very general kind of polygon into a list of simple polygons. Let me introduce some notions: Let an 'edge class' $E$ be a set of homeomorphic images of the unit ...
• 161
2k views

### Is this a potentially more intuitive approach to MergeSort?

I have read at least one other post (perhaps not on this stackexchange) that asks essentially: Why do we have to break up the array into successively smaller arrays until we finally reach the bottom (...
• 141