Questions tagged [computer-science]
Computer science or computing science (abbreviated CS or CompSci) is the scientific approach to computation and its applications.
199 questions
2
votes
1
answer
1k
views
Relation and difference between recursively enumerable languages and Turing complete languages?
From https://en.wikipedia.org/wiki/Recursively_enumerable_language
a formal language is called recursively enumerable (also
recognizable, partially decidable, semidecidable, Turing-acceptable or
...
- 5,495
1
vote
2
answers
2k
views
How to Create a Parser that Operates in Reverse
I've got my answer to this in the comment of the one I checked. Which Algorithm Approach Should I Take to Generate Lambda Expressions in Java? but I don't exactly know where to look in terms of ...
0
votes
1
answer
697
views
Computational limits for huge k-th permutation?
Would it be feasible to calculate directly a k-permutation like k = 10^200000000?
If not,
What would be the computational limit to calculate huge k-th permutation in a today computer? How can I ...
- 67
1
vote
2
answers
2k
views
Having trouble with AP computer science sample test problem
I am currently taking AP Computer Science at my high school and while looking at some sample AP test problems I came across one that really confused me.
Sample Problem
The answer to the problem is ...
- 31
-1
votes
1
answer
179
views
Why do we use 'assert not' in this example?
My code takes 2 dates and finds the age of those dates in days. In my daysBetweenDates method the instructor uses an assert statement:
assert not dateIsBefore(year2, month2, day2, year1, month1, day1)...
- 131
29
votes
2
answers
11k
views
How does sleeping a thread work?
When you sleep a thread, what is actually going on?
I see that sleeping a thread "pauses the current thread for a given period of time". But just how does it work?
According to How Thread.sleep() ...
- 3,478
18
votes
3
answers
3k
views
Why did Ruby creator chose to use the concept of Symbols?
tl;dr: Would there be a language-agnostic definition of Symbols and a reason to have them in other languages?
So, why did the Ruby creator use the concept of symbols in the language?
I ask this ...
- 291
3
votes
3
answers
639
views
Is it faster to make a dedicated variable instead of calling deeply nested object several times?
In a JavaScript app, suppose I have a nested object like this:
var myObject = {
someProp: {
someOtherProp: {
anotherOne: {
yetAnother: {
...
- 315
1
vote
1
answer
172
views
Cyclomatic complexity - what exactly does the word "cyclomatic" mean?
I understand what cyclomatic complexity is, but I was trying to find the origin/meaning behind the word "cyclomatic" and could not find anything that wasn't about cyclomatic complexity. Does this ...
- 284
0
votes
1
answer
48
views
What relationship describes two different abstractions of the same dataset
I am wondering if there is a specific term for when multiple representations are data equivalent. Meaning that you can transfer the data from one representation to the other without any loss of data.
...
- 369
1
vote
2
answers
99
views
Language interaction
How does a program composed of several languages work? How do the languages work together or interact with each other? How do they understand stand each other? How do you know when to use any given ...
- 21
-1
votes
1
answer
509
views
Floating point absorption phenomena and ULP
Numerical analysis text books talks about the absorption phenomena (Introduction to Numerical Analysis and Scientific Computing; Nabil Nassif; Dolly Khoueiri Fayyad; CRC Press; 2014) when adding ...
- 1
32
votes
13
answers
5k
views
Help in understanding computer science, programming and abstraction [duplicate]
Until now, I always believed that you should learn programming languages that make you do low-level stuff (e.g. C) to understand what's really happening under the hood and how the computer really ...
5
votes
2
answers
819
views
Why are semantics and type systems are so important?
I heard that semantics and type systems are very important for all programmers! But I why are they so important? I don't understand. Maybe they are imortant only for theoreticians and compiler ...
0
votes
1
answer
142
views
Foundations of computation, and relation to modern computers [closed]
I want to understand how the theoretical foundations of computation relate to real-world computers. As far as my knowledge goes, Turing machines, recursive functions, finite state machines, lambda ...
- 439
2
votes
2
answers
144
views
From a set of rules, derive the implications? [closed]
I've only just become interested in this domain, so sorry if I'm not using the correct terminologies.
What I want is the following: Say I have a set of rules (or constraints), I want to derive some ...
- 283
4
votes
2
answers
7k
views
How do Symbol Tables, Lexers and Parsers work together in a modern design? [closed]
I'm working on creating my own scripting language for learning purposes. I've been reading through the Dragon Book and some things are a little unclear to me regarding the Symbol Table as well as ...
- 361
1
vote
0
answers
316
views
What is this compression algorithm? (Similar to RLE)
In Run Length Encoding (RLE), a large set of information is encoded by storing the quantity of consecutive sequences. A canonical example is:
...
39
votes
2
answers
3k
views
What is the meaning of "doesn't compose"?
I see a lot of texts, especially functional programming texts, claim that certain CS concepts "don't compose". Examples are: locks don't compose, monads don't compose.
I've been having a hard time ...
- 972
10
votes
4
answers
4k
views
How is a state machine different from any other computer program?
I have seen several implementations of "State Machines" on github. As far as I understand, a state machine takes input that may or may not transform its state into one of a finite set of other states. ...
- 5,712
1
vote
2
answers
5k
views
Is studying algorithms important for game development? [closed]
I am fairly new in the programming world, I have a 1-year experience and I learned by watching online courses, and I made few iOS apps.
Now I am moving into game development and I already ...
- 121
1
vote
1
answer
221
views
Find all factors(prime and composite) of a number
We can find all the prime factors using a Sieve of Erastothenes. But how do we find ALL the factors of a number?
For instance, 24 = 2x2x2x3
But the complete factor list is - 1,2,3,4,6,8,12,24.
I am ...
- 121
12
votes
5
answers
2k
views
How come the computer doesn't have to read the entire table when the column is indexed? [duplicate]
Let's say a table with two columns has 100 quadrillion records. And I want to find a record that has column #2 equal something.
If column #2 is indexed it returns the result immediately, but if it's ...
- 167
5
votes
2
answers
3k
views
Looking for a DP algorithm for a specific packing problem
I have the following problem to solve:
Given a ferry with length d and a list of n cars conataining their length we must load the cars on the ferry in an order in which they appear in the list on 2 ...
- 205
4
votes
3
answers
3k
views
Finding common prefixes for a set of strings
I am trying to find common prefixes for a sorted set of strings. i.e. if the following strings are given:
AB123456
AB123457
ABCDEFGH
ABCDEFGX1
ABCDEFGY
XXXX
then my function should return three ...
- 141
2
votes
4
answers
498
views
Should all programmers know how to solve algorithms, etc [closed]
I'm 15 and have been programming for about 3-4 years. I mostly program in Java as it was my first language.
I would like to be a programmer when I'm older, but I'm not sure about the differences. I'...
14
votes
2
answers
6k
views
What is the relationship between lambda calculus and programming languages? [closed]
I am starting my first year (in college) in Computer Science next year and I write mostly in C (if that is to matter). I have tried searching but most of what I find assumes knowledge of lambda ...
- 701
5
votes
2
answers
14k
views
What does 'upper bound' mean in context of BigO?
My computer science teacher says Big O has an upper bound but no lower bound. When I look at a graph of an algorithm mapped out using BigO though, there isn't an upper bound at all. The upper limit ...
11
votes
1
answer
738
views
What Is λ-calculus essentially?
I have what I would call a philosophical question about λ-calculus.
When you explore λ-calculus you will be surprised to see all the things that you can do there. You can define integers, arithmetic ...
- 1,137
-1
votes
2
answers
163
views
Is 'lazy' the correct term for timestamp-based skipping? [closed]
(1)
The oldmakeutility looks at timestamps, and if the output is newer than the input, it skips (pointless, time-consuming) re-compilation of e.g. C files.
The same is true for many languages and ...
- 131
0
votes
1
answer
354
views
How are the conceptual pairs Abstract/Concrete, Generic/Specific, and Complex/Simple related to one another in software architecture?
(= 2 (+ 1 1))
take the above. The requirement of the '=' predicate is that its arguments be comparable. Any two structures are comparable in this case, and so the contract/requirement is pretty ...
- 249
3
votes
3
answers
7k
views
What is Atomicity?
I'm really struggling to find a concrete, easy to grasp, explanation of Atomicity.
My understanding thus far is that to ensure an operation is atomic you wrap the critical code in a locker. But that'...
- 730
1
vote
1
answer
737
views
Which Computer Vision / Image Processing technique would solve light imbalance in images?
Given a colour image whose light intensity is dim at the edges and bright in the middle, such as [dim bright dim], which computer vision technique would be recommended to correct this imbalance? ...
- 145
1
vote
1
answer
534
views
Can we still consider that Moore's law still holds true regarding the consequence on CPU speed? [closed]
Moore's law is an empirical law and in simple terms states that the number of transistors on integrated circuits doubles approximately every two years.
One of the consequences of Moore's law is that ...
- 127
1
vote
4
answers
788
views
What do you call a tree that grows in both directions? [closed]
What would be the technical term for a tree that grows in both the directions, starting from the root in the middle?
The central idea being that new elements can be added to the tree (Now, I am not ...
- 197
16
votes
6
answers
3k
views
What is an example of a computationally impossible business problem?
I have coworker who refuses to accept the reality that Turing machines (and Von Neuman machines by extension) cannot solve their own halting problem stating:
You can do anything with enough time ...
- 271
-2
votes
1
answer
5k
views
what is the difference between a software engineer and project manager? [closed]
I understand that a software engineers job is to work with all aspects of developing and supporting a software system. How does a project manager fit/work with a software engineer in a small team (5 ...
12
votes
1
answer
563
views
What intermediate representations can be used to reason about concurrency?
I am trying to better understand what would be required for a compiler to be able to make intelligent choices regarding concurrency on behalf of the programmer. I realize that there are many difficult ...
Samsdram
3
votes
2
answers
996
views
Implementation of chess endgame engine without Endgame Tablebases
I'm interested in creating an chess endgame solving engine.
The endgames in chess are usually solved using the endgame table-bases generated by retrograde algorithm.
I have found that Artificial ...
- 273
10
votes
2
answers
3k
views
Are there alternatives to stack+heap+static memory model?
All programs I have seen organize their data memory into one or more call stacks (usually fixed size, but sometimes not), the heap, and static memory. Lately thread-local static storage has been ...
- 928
2
votes
2
answers
293
views
How is indirection different from aliasing?
Take from wikipedia, aliasing is defined as accessing a data location through different names.
Also taken from wikipedia, indirection is defined as referencing something "using a name, reference, or ...
- 179
3
votes
4
answers
2k
views
Why do some compilers generate direct machine code?
I was taking this course - CMU 18-447, Computer Architecture at Carnegie Mellon to brush my knowledge and concepts.
They say that most of the machine level details and implementations are taken care ...
- 141
2
votes
1
answer
307
views
Resources for understanding a programming language and its specifications and grammar deeply [closed]
I'm a computer engineer and all the courses we have had about programming and computer languages were an introduction to C/Java and OOP. Now I feel like reading Java language specification to learn a ...
- 311
85
votes
11
answers
8k
views
How can I make sure that I'm actually learning how to program rather than simply learning the details of a language? [closed]
I often hear that a real programmer can easily learn any language within a week. Languages are just tools for getting things done, I'm told. Programming is the ultimate skill that must be learned and ...
- 1,261
-1
votes
3
answers
8k
views
Why are algorithms and data structures important? [duplicate]
It seems like a lot of university-level computer science programs and programmer job interviews focus heavily on algorithms and data structures. I'm curious as to why universities and employers put so ...
- 1,261
0
votes
1
answer
416
views
Generic name for types and values [closed]
In computer science, what is the abstract common name of types and values (I mean an abstract "something" that can be a type or a value) ?
To be more specific:
If we have template <typename X> ...
- 169
1
vote
1
answer
387
views
Converting a DFA to an NFA
I have an assignment to convert various language descriptions into NFAs and DFAs.
Having graduated with my CompSci B.S. years ago and not touching the topic until my M.S. program, I am racking my ...
user22815
15
votes
9
answers
6k
views
Is learning C essential for Computer Science? [closed]
I am a front-end developer who barely even see a file with .h or .c extension.
I know basic C syntax, I've learned it in Unreality but never was interested in such
low level programming because it ...
- 1,990
2
votes
4
answers
462
views
Generic term for "objects" vs "fundamental types"?
What are the exact terms to call data types with a logic structure (like C structures, C++ or Java objects) versus fundamental data types (like numeric types, characters, booleans...) independently of ...
- 169
0
votes
2
answers
160
views
By the definition of a Tree(ADT), is it "wrong" for a node to add a sibling?
The title pretty much says it all. I'm just having a little computer science exercise and am building a Tree. I want a node to be able to add a sibling which requires one to first get a reference to ...
- 79