# All Questions

1answer
8 views

### Question about set-associative cache mapping

I found a question: Let a two-way set-associative cache of 4 memory blocks, each block containing one word. What is the number of misses and hits considering the following sequence of block ...
0answers
15 views

### What is the best book for a 15 year old to start algorithms, and wants to go to the IOI 2017? [on hold]

I am currently 15 and I want to go to the ioi, in order to go to the ioi I need to learn about algorithms and data structures. I tried the CLRS book but sadly the maths in it was too hard. I am ...
1answer
56 views

### For every 'evil' regex, does there exist a non-evil alternative, or is the devil in the grammar?

Apparently, ReDos attacks exploit characteristics of some (otherwise useful) regular expressions ... essentially causing an explosion of possible paths through the graph defined by the NFA. Is it ...
0answers
16 views

### worst case time complexity [on hold]

For binary search i am able to calculate the average case complexity but i don't know how to find worst case complexity?Please help
1answer
28 views

### Difference between the two regular expression

I came across a question to create a regular expression to check whether there are even number of b's in a string of language {a,b}. The expression I came up with is (a+ba*b)*. However I found the ...
0answers
15 views

### Solving for Hit Ratio of a Theoretical Memory System

Long time lurker, first time poster. The book I am reading is William Stalling's "Operating Systems: Internals and Design Principles" Seventh Edition. Stalling's definition of hit ratio according to ...
3answers
396 views

### undecidable problem and its negation is undecidable

A lot of "famous" undecidable problems are nonetheless at least semidecidable, with their complement being undecidable. One example above all can be the halting problem and its complement. However, ...
0answers
11 views

### sheduling in parallel machines with machine delay and job constraints

Given m machines and n jobs ,we want to schedule jobs into machines ,such that lateness ie( idealCompletionTime- actualCompletionTime) is minimized .Also the machines are required to take a break ...
1answer
28 views

### Minimising sum of consecutive points distances Manhattan metric

I have set of points (two dimensions, $X, Y$). Coordinates are floating point numbers. Objective is to sort them in such way that sum of differences in distances of consecutive sorted points is ...
0answers
19 views

### Finite State Machine [on hold]

The number of states required by a Finite State Machine to simulate the behaviour of a computer with a memory capable of storing m words,with each word being n bits long is
1answer
19 views

### give potential function - binary heap - extract-min in amortized const time and insert in log amortized time

Consider an ordinary binary min-heap data structure with n elements supporting the instructions INSERT and EXTRACT-MIN in O($\lg n)$ worst-case time. Give a potential function $\Phi$ such that the ...
2answers
65 views

### How does a hard drive knows what bit is the beginning of of a byte/word?

I'm guessing I could replace the words "hard drive" with "random access medium" but let's be more specific here. Also for the sake of this question, let's not consider SSDs. Just plain old hard-drives ...
0answers
14 views

### Proving relationship between set complement, intersection and union [migrated]

Show that $S_1 \cup S_2 = \overline{\overline{S_1}\cap \overline{S_2}}$. So we want to show that the union of $S_1$ and $S_2$ is equal to the compliment of the intersection of the compliments of ...
0answers
32 views

### Any Natural Problems shown Easy by Reduction to Horn SAT?

To show that a problem is polynomial-time solvable, an often-successful technique is to reduce it to 2SAT (that is the problem of deciding satisfiability of CNF formulas with every clause containing ...
1answer
30 views

### How Can we make $O(N)$ order statistic queries with Fibonacci heap in $O(N)$?

We have a Fibonacci heap with $N$ unique elements we want to make $O(N)$ order statistic queries (e.g., what is the element number 7 in this collection if it was sorted). Moreover, we know that the ...
0answers
18 views

### What is the best-case and worst-case Time complexity in terms of n,in the form “O(…)” of the following code? [duplicate]

I've Asked this question ..... What is the best-case and worst-case Time complexity in terms of n,in the form "O(...)" of the following code ...
1answer
34 views

### What does atomicity mean in distributed systems?

In a distributed system, how are atomic operations are done when network connections inherently have the Two Generals problem? Does atomicity have a different meaning in this context?
0answers
33 views

### How do you calculate when effective access time is greater than cache access time?

I'm having trouble understanding how to calculate effective access time, hit ratios and cache access times. I'm unfamiliar with the concepts and would love help, or an explanation on how to solve this ...
0answers
9 views

### Memory storage capacity of Bienenstock-Cooper-Munro rule

I would like to know the memory storage capacity of the BCM learning rule when it is implemented on a Hopfield network. I understand that it will be a function of n where n is the number of neurons.
1answer
58 views

### Understanding the one-writer, many-readers problem?

I need some help understanding the implementation of the one-writer many-readers problem shown below as I am new to this concept: I have a rough idea that there will be starvation/deadlock among ...
0answers
33 views

### Algorithm to group two-dimensional data points

I feel like there should be a known algorithm to the following problem, but I am short of ideas how to construct or search for it. Suppose as an input you have a list of two-dimensional data points ...
0answers
45 views

### Converting this DFA to RE using the Brzozowski Algebraic Method [on hold]

Hello people, I'm trying to convert this DFA to RE using the Brzozowski Algebraic Method. (DFA created with JFlap) My Attempt Write down equations R1 = bR1 + aR2 + ɛ R2 = bR2 + aR3 ...
6answers
3k views

### How does a computer determine the data type of a byte?

For example, if the computer has 10111100 stored on one particular byte of RAM, how does the computer know to interpret this byte as an integer, ASCII character, or ...
1answer
32 views

### Raptor Algorithm: Differences between trip and route

I'm reading Microsoft's paper about algorithm in public transit named Round-Based Public Transit Routing, short name is ...
1answer
31 views

### Recurrence Relation(with Square root)

I came across a very peculiar recurrence relation : $\sqrt {T(n)} = \sqrt {T(n-1)} + 2 \sqrt {T(n-2)}$ with initial values $T(0) = T(1) = 1$ Any helps on how to find it
2answers
91 views

### Binary code with constraint

Suppose I have an alphabet of n symbols. I can efficiently encode them with $\lceil \log_2n\rceil$-bits strings. For instance if n=8: A: 0 0 0 B: 0 0 1 C: 0 1 0 D: 0 1 1 E: 1 0 0 F: 1 0 1 G: 1 1 0 H: ...
1answer
26 views

### Differences between SISD, SIMD and MIMD architecture (Flynn classification)

I have a problem with classifying certain CPUs to the proper classes of Flynn's Taxonomy. 1. Zilog Z80 According to this article on Sega Retro, Z80 has limited abilities to be classified as SIMD: ...
0answers
17 views

### starting android [on hold]

I have installed Android SDK studio and eclipse platform. The two have been integrated as per the instructions. Now how to check if the integration was proper? Basically how am I supposed to run a ...
0answers
16 views

### doubt about phones present in the dictionary [on hold]

I am using KALDI speech recognition toolkit to train my system for speech recognition and I am using ILSL12 naming convention to represent various sounds. I am facing a challenge in dictionary ...
1answer
32 views

### Does removal of unit production from the grammar may increase number of total production?

I have doubt ! Problem is There are m variable in a grammar. The number of productions after removal of unit productions in the worst case is ,(Assume there are no null productions) (a) O(m) ...
1answer
25 views

### Bottleneck TSP with MST

There is a problem I don't know the answer too. The 3 approximation for the bottleneck TSP that involves first getting the MST. I have not been able to come up with the right "shortcut" method so far. ...
0answers
37 views

### Graph having exactly K Minimum Spanning Trees

Can we construct a weighted graph having exactly k minimum spanning trees given the number of vertices ?.There is no restriction on the allocation of weight to the edges. k can be any number between ...
1answer
34 views

### Does a reentrant list for signal queue in a single-thread environment exist?

I need to handle Unix signals in a single-threaded application with the following goals: Signals doesn't mask on receive (thus, the signal handler must be reentrant). I am not allowed to lose signal ...
1answer
35 views

### recursive function as circular funciton

I recently learnt that a recursive function is also referred to as a circular function. See, the recursive function cannot be a circular function because even if there is a call to function itself, ...
1answer
56 views

### Equivalence in finite sets of turing machines

I have this exercise and I really don't know how to complete it: ...
0answers
20 views

### Two versions of arithmetic instructions in RISC. One modifies the flags and the other doesn't [duplicate]

I've read that in RISC architecture most arithmetic instructions have two "versions": one that modifies the flags after calculations one that doesn't modify any flags. My question is: why is it ...
1answer
50 views

### Help interpreting this deadlock question

I have this assignment question but I am a bit unsure how to go about answering it. The question is as follows and accompanied by the image below: Three processes are competing for six resources ...
1answer
98 views

### Provide some help regarding the “Dining Philosophers Problem”?

I have an assignment based on operating systems and the question is divided into two sub-questions. The first is: Prove any seating arrangement of lefties and righties, with at least one of each ...
1answer
31 views

### How to determine how many dots are in a resource in a resource allocation graph?

I understand most concepts regard a resource allocation graph but I see that some resources have more dots (not sure what they are actually referred to) in them than others such as the example below, ...
1answer
22 views

### Algorithm for Filling Regions with Small Gaps

I am looking for an algorithm that fills a region with one color, but the edge of the region is not completely closed (i.e. one or more gaps are being left). The result is like the use of the Paint ...
0answers
16 views

### Finding longest paths between any two vertices in a undirected graph (simple graph) [on hold]

I need matlab code for computation of detour matrix. definition of detour matrix: The detour matrix Delta, sometimes also called the maximum path matrix or maximal topological distances matrix, of a ...
0answers
15 views

### Artifact when generating Fibonacci numbers [migrated]

In preperation for an exam, I was studying Haskell. Therefore I was solving an old assignment where you had to define the fibonacci series. After solving the task (see 1] for source code) and ...
1answer
106 views

### Difference between regular expression and grammar in automata

I am new to automata, and I have been given a brief introduction to regular expressions only yesterday. I have read the various rules which to define a regular expression. But I am unable to ...
0answers
15 views

### WiFi Card limited to 150, getting 60 [on hold]

my WiFi card (Trend-Net TEW-641PC) is limited to 150 Mbps internet speed, however I am only getting 50-75. My ISP has given me a limit of 350 Mbps, and it works on my dad's laptop. Other (important) ...
1answer
72 views

### what does term “emit” in compiler mean?

In lots of textbooks and papers, authors often state: compiler emits ... I want to know why they prefer to use emit? (not return, not produce) Does this have anything to do with the emitter of a ...
0answers
16 views

### State of the art in multi-modal command recognition

I'm currently researching various fusion methods in a multi-modal (video, audio, identity, user position and gesture) human-computer interaction environment (think in terms of a smart-home system). ...
0answers
9 views

### Minimum path cover problem to maximum bipartite matching [on hold]

I read this link http://stackoverflow.com/questions/10303800/minimum-number-of-days-required-to-solve-a-list-of-questions But I couldnt understand how to transform the graph for which minimum path ...
1answer
26 views

### Search problem when the effects of actions are not deterministic

The standard search problem studied in AI contains: An initial state $A$; A final (goal) state $Z$; A set of actions that can change the state; each action takes as input a certain state and returns ...
1answer
29 views

### Prove or disprove that $NL$ is closed under polynomial many-one reductions

If $B \in NL$ and there exists a Karp reduction (polynomial-time many-one reduction) from $A$ to $B$, then $A \in NL$. Prove that the above claim is correct, incorrect, or equivalent to an open ...
0answers
15 views

### DDoS detection-Only script or software/program (open-source) [on hold]

My testbed needs a DDoS detection script or program/software. After detection I will use my solution to do measurements after. Does anybody have any idea/information about which softwares/scripts are ...

15 30 50 per page