0
votes
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 ...
-1
votes
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 ...
3
votes
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 ...
-1
votes
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
1
vote
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 ...
1
vote
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 ...
8
votes
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, ...
0
votes
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 ...
2
votes
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 ...
-1
votes
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
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
3
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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?
0
votes
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 ...
0
votes
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.
1
vote
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 ...
2
votes
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 ...
1
vote
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 ...
14
votes
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 ...
0
votes
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 ...
0
votes
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
6
votes
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: ...
1
vote
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: ...
-2
votes
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 ...
0
votes
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 ...
1
vote
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) ...
1
vote
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. ...
1
vote
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 ...
2
votes
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 ...
0
votes
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, ...
2
votes
1answer
56 views

Equivalence in finite sets of turing machines

I have this exercise and I really don't know how to complete it: ...
0
votes
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 ...
0
votes
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 ...
1
vote
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 ...
1
vote
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, ...
1
vote
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 ...
-2
votes
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 ...
2
votes
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 ...
2
votes
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 ...
-2
votes
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) ...
0
votes
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 ...
2
votes
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). ...
0
votes
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 ...
3
votes
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 ...
4
votes
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 ...
0
votes
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