# All Questions

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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... ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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, ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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?
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. ...
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},$$ ...
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 ...
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 ...
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 ...
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 ...
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 ...