0
votes
1answer
5 views

What is the rationale behind implicitly widening integer types in numeric operations?

Languages such as Java and C specify implicit widening of integer types for numeric operators, especially arithmetic operators, to a minimum of 32 bits. What is the rationale behind doing this? My ...
2
votes
1answer
18 views

Proving that if $L=\{ a^n b^n c^n \colon n\ge 0 \}$ than $L\notin CFL$

I'm going over "Introduction to the Theory of Computation" by Michael Sipser in which there's an example of using the pumping lemma for CFLs to prove that $L=\{ a^n b^n c^n \colon n\ge 0 \}$ is not a ...
-2
votes
0answers
14 views

how to calculate bits in cache?

A cache holds 16 words where each word is 4 bytes. Assuming a 32-bit address, give A direct-mapped cache with block size = 2 words what is total # bits for word & byte offset? number of bits ...
-1
votes
0answers
18 views

How to be a cloud security architect? [on hold]

I am computer science major and I am working hard on many aspects. I tried to do research in many areas in computer sincere with some professor but the things were difficult. Recently I'v a chance to ...
0
votes
0answers
15 views

CFG. Ensure that $n\neq m$ twice in $L=\{a^m b^n c^m d^n, m\neq n\}$

During the formal language exam, the professor allowed to find a CFG to following language: $\{a^m b^n c^p d^q, m\neq n\wedge p\neq q\}(1)$, because neither he saw a solution (He passed a test without ...
3
votes
0answers
31 views

Computing the “at least k friends in common” graph

Suppose we have the graph of a social network with symmetric connections (e.g. Facebook or LinkedIn). Suppose we would like to find all pairs of people who have at least k friends in common, in order ...
4
votes
3answers
160 views

Why is the addition function exponential for k-bit integers providing only zero, equality and the successor functions?

I'm currently reading the elements of programming book and have come across a section I don't quite understand A computational basis for a type is a finite set of procedures that enable the ...
-2
votes
0answers
20 views

True random number generator C++ [migrated]

Questions Do these codes generate true random numbers? If not: can you prove their pseudo-randomness? For computers with more than two CPUs ...
2
votes
1answer
27 views

Radix sort and changing bases

I have recently learned about radix sort. I am aware that you can change the base of the numbers you need to sort but I don't really understand why this is good for the radix sort. Radix sort runtime ...
0
votes
0answers
48 views

Dynamic Programming problem: A number as a sum of squares

Following is the problem I am trying to solve: Problem Statement Find the number of $n$-tuples $(a_1,a_2,a_3,\cdots,a_n)$ such that ...
1
vote
1answer
20 views

Data versioning in a relational database

I've been working on an industrial project where my job was to design a data model in-memory and in a relational database in such a way, that can capture the time-varying nature of the production ...
0
votes
0answers
7 views

Hierholzer's algorithm for finding Eulerian Path in Semi-directed multigraph

Background: There is an Android game called One Touch Drawing which is based on finding Eulerian Paths (or Circuits) in graphs. As the game progresses, there are several conditions introduced to ...
-1
votes
0answers
19 views

why audio and video are in unstructured form [on hold]

what i need to know is: why audio and video files are stored in unstructured form in computers. Why they cant also be stored like you can say: employee records in database as for instance: if i want ...
0
votes
1answer
25 views

computer architecture and organization [on hold]

As constantly from the periods of evolution of computers we are evolving from numbers to text to graphics to audio to video etc etc... as we are moving, the complexity and demand of computers get ...
-2
votes
1answer
28 views

Using dynamic programming to find the number ofl increasing subsequences

I got this question today and I'm nowhere near the solution, Given a sequence of real numbers (X1, X2, ..,Xn). write an algorithm as efficient there is, that finds the number of strictly increasing ...
0
votes
2answers
36 views

How to get the intersection of two regular languages?

I was trying to figure out the value of the following expression. (0 | 1)*00 ∩ (0 | 1)*01 I tried drawing DFAs for(0 | 1)*00 ...
0
votes
0answers
12 views

Starting point and references for studying computer networks [on hold]

I'm trying to determine where I should begin studying in order to eventually have a solid understanding of how computer networks work. I majored in mathematics in college. Here's a list of some of my ...
1
vote
1answer
20 views

Combinatorial optimization - is there a formal name for this problem?

I am looking for a formal name and an algorithmic approach to the following problem. Given is a set of services each coming with a price: {s1, 300} {s2, 400} {s3, 800} Additionally there is a ...
-1
votes
0answers
6 views

Weka class question [on hold]

We are trying to run J48 on a classified data set. Our class attribute has two possible values ( 0,1) when running J48 the tree terminates at the very first node and doesnt process any further. ...
-1
votes
1answer
35 views

Why decision problem definition ignores Gödel incompleteness theorem?

The following question assume that the decision problem definition (syntactic) has been written (and could be changed if it isn't able) to catch a concept (meaning, semantic) which has both nice ...
1
vote
3answers
241 views

Formula for sufficiently lengthy encryption key?

As you add length to an encryption key, at some point the message becomes impossible to brute-force decrypt. This is because at that point, if you go through all the possible keys, you'll get many ...
0
votes
0answers
43 views

How do binary trees use memory to store its data?

So I know that arrays use a block on contiguous memory addresses to store data to memory, and lists (not linked lists) make use of static arrays and when data is appended to the list, if there is no ...
1
vote
3answers
63 views

What techniques can I use to hand-write a parser for an ambiguous grammar?

I'm writing a compiler, and I've built a recursive-descent parser to handle the syntax analysis. I'd like to enhance the type system to support functions as a valid variable type, but I'm building a ...
0
votes
1answer
15 views

How do I see SSL/TLS packet data in clear? [on hold]

Hey all I have a weird question (first time poster so forgive me if this is super newb)... I am wanting to see the inner workings of a SSL/TLS connection between a client and a server at the packet ...
1
vote
1answer
21 views

SimRank on a weighted directed graph (how to calculate node similarity)

I have a weighted directed graph (it's sparse, 35,000 nodes and 19 million edges) and would like to calculate similarity scores for pairs of nodes. SimRank would be ideal for this purpose, except that ...
3
votes
0answers
19 views

How much bigger can an LR(1) automaton for a language be than the corresponding LR(0) automaton?

In an LR(0) parser, each state consists of a collection of LR(0) items, which are productions annotated with a position. In an LR(1) parser, each state consists of a collection of LR(1) items, which ...
0
votes
0answers
15 views

Declarative and Procedural problem solutions [on hold]

Program solutions are structured and desigend based on the type of problem at hand. While looking up on when to apply OOD principles to a solution, I came across an article which states... ...
0
votes
0answers
18 views

Learning the principles of Petri nets [on hold]

While studying concurrency in one of my programming modules I came across the concept of Petri nets and I am keen on learning more in debt about the subject. What I am looking for is a serious place ...
1
vote
0answers
37 views

How to select the maximum weight value for a bias node in a neural network?

I'm programming a neural network. I know that I should initialize the network by picking random weights. How do I pick a random weight for the connections to bias nodes? What distribution should I ...
3
votes
1answer
50 views

Symmetric Difference of Turing Recognizable and Finite Languages

Let A be a Turing Recognizable Language and B a finite Language. I want to prove that their symmetric difference is Turing Recognizable. My reasoning: B is finite, therefore the finite number of ...
1
vote
1answer
37 views

DTM that halts on a minimum one input

I am trying to show that this is Turing Recognizable. The language A, that is a DTM, T, that halts on a minimum of one input. My justification is that of course it is because, you just need to check ...
2
votes
1answer
33 views

Find the subset of k element between n that maximize the total distance

Given a set $Q\subset \mathbb{N}^m $ of $n$ points, we want to find the subset $S_{max}\subset Q$ of $k$ elements that maximize the total distance between them, according to the $\ell^1$ norm. ...
0
votes
2answers
29 views

Push down automata what to do when there is no suitable transition

This is a question that has emerged from a recent quiz I have taken. In short Consider the following transitions on a push down automaton. Assume the starting state is q. Which one of the ...
0
votes
0answers
34 views

Computing MD5 hashes of huge numbers [on hold]

I need to solve this riddle: So I need to compute $\operatorname{MD5}(2^{1024^2})$. I know what MD5 is and I tried to compute the number inside the parantheses and insert it into an MD5 generator, ...
-2
votes
1answer
45 views

How to convert this type of languages to Context Free grammar?

As I've already asked my Question about the solving Context Free Grammar $L = \{a^n b^m c^p \mid n = m + p + 2\}$ Can this language be defined by a Context Free Grammar? Now i have just changed ...
1
vote
1answer
37 views

Shortest Path problem(Single Source&Destination)

Given: A completely connected directed acyclic graph. What would be the most efficient(Least Time complexity) way to find a shortest path among a very large number of nodes? Constraint: 1)The result ...
0
votes
1answer
101 views

Why is O(n log n) the best runtime there is?

I am taking a course on Coursera about algorithm design. The course said that a time of $O(n \log n)$ is considered to be good. However, there are faster runtimes such as (from now on just assume it ...
-1
votes
1answer
43 views

How is the micro code executed within a processor?

How does the microprocessor convert the machine code to micro code? What part of the processor is at play?
1
vote
1answer
51 views

How can a set offer better search performance than an array

While reading the following tutorial on iOS development Working with Foundation (section on Sets near the bottom), I came across the following statement: "Because sets don’t maintain order, they offer ...
-1
votes
1answer
126 views

Does every language that fulfills the regular Pumping conditions also fulfill the context-free ones?

Let L be a language that fulfills the properties implies by the Pumping lemma for regular languages. Does L necessarily fulfill the corresponding properties of the Pumping lemma for context-free ...
-1
votes
0answers
18 views

How to port forward? [on hold]

how can I port forwand on my modem if I have lost my password. It is a Netgear DGN2200v4. I need to host a minecraft from home and I need to port forward on port 25565 to let other people join my ...
-1
votes
0answers
17 views

What is an adaptive cache prefetching policy?

what is meant by the term "adaptive cache prefetching policy" and how is it different from regular methods of prefetching a cache? what are the advantages of adaptive cache prefetching?
-2
votes
0answers
8 views

ASP.Net MVC JavaScript error [on hold]

I attached the pictures regarding mistakes, View and Controller. When I select the country in the field of ‘Country’, JavaScript code which is supposed to bring the city names does not work (p.s. ...
2
votes
0answers
32 views

Uniform Sampling on Intersection of Faces of Simplices

I'm trying to sample uniformly on the intersections of the faces of several simplicies, with all coordinates being non-negative. That is, given $$A\vec{x}=\vec{b} \ \ and \ \ \vec{x} \geq \vec{0},$$ ...
2
votes
1answer
97 views

Graph Families that are easy to color

What are the non-trivial graph families that have a known chromatic number, or an easy way (polynomial-time algorithm) to compute the latter. Examples would be: Kneser graphs Chordal graphs Do ...
3
votes
0answers
45 views

What are the strongest known type systems for which inference is decidable?

It's well known that Hindley-Milner type inference (the simply-typed $\lambda$-calculus with polymorphism) has decidable type inference: you can reconstruct principle types for any programs without ...
1
vote
0answers
14 views

How does fread work? [migrated]

I understand that in various programming languages, such as MatLab and C++, fread is used as a way to read in a binary file. I was wondering how exactly this worked? In particular, how does fread know ...
3
votes
1answer
58 views

Data structure for ordered counted set

Is there a name for a counted set (multiset) that is ordered? For example lets say this data structure represents a shopping cart (or basket if you're British). The shopping cart shows the order the ...
3
votes
1answer
357 views

The control in the Turing Machine

My question is about the control in the Turing Machine. As far as I know, the control of the Turing Machine is just a set of states. If the Machine needs to record something, it needs to write on the ...
0
votes
0answers
10 views

Construction of NPDA with inequality check [duplicate]

I'm currently struggling to construct a nondeterministic PDA with an amount of states in $O(n)$ that accepts the following language: $L = \{wcx \, | \, w,x \in \{a,b\}^n \land w \not= x\}$ with c ...

15 30 50 per page