Computer Science: Theory and Application

Subscribe to Computer Science: Theory and Application feed
Computer Science Theory and Application. We share and discuss any content that computer scientists find interesting. People from all walks of life welcome, including hackers, hobbyists, professionals, and academics.Computer Science: Theory and Application
Updated: 10 min 15 sec ago

CompSci Weekend SuperThread (November 16, 2018)

Thu, 11/15/2018 - 20:06

/r/compsci strives to be the best online community for computer scientists. We moderate posts to keep things on topic.

This Weekend SuperThread provides a discussion area for posts that might be off-topic normally. Anything Goes: post your questions, ideas, requests for help, musings, or whatever comes to mind as comments in this thread.

  • If you're looking to answer questions, sort by new comments.
  • If you're looking for answers, sort by top comment.
  • Upvote a question you've answered for visibility.
  • Downvoting is discouraged. Save it for discourteous content only.
  • It's not truly "Anything Goes". Please follow Reddiquette and use common sense.
  • Homework help questions are discouraged.
submitted by /u/AutoModerator
[link] [comments]

TSP variation: Only visit a specific fraction of the nodes

Thu, 11/15/2018 - 18:56

I recently started implementing a small python framework that needs to solve (or get a good solution for) the Travelling Salesman Problem, until I realized what I want is not exactly a TSP.

The main difference between my problem and the actual TSP is that, instead of having a standard set of nodes, I have a set of triplets of subnodes like V={(A1, A2, A3), (B1, B2, B3), (C1, C2, C3), (D1, D2, D3)}. In this vertex set, we'll call 'A', 'B', 'C', and 'D' "node types".

And instead of having to find the shortest path going through all the nodes of graph, I want to find the smallest path that goes through one (and only one) subnode of every type present in the graph. For example, in a graph that would be made of my previously mentioned vertex set V, a path like A3->D1->B2->C3 is a feasible solution, but A2->B3->D1->B1->C1 is not because it visits two nodes of type 'B'.

Like the TSP, this is NP-Hard. My google searches remain unsuccessful about it. Is there any known problem that looks like that ? And in particular, do you know of any heuristic that solves this problem (or similar) ?

submitted by /u/brurrito_
[link] [comments]

Regex with lookahead and lookbehind still type3?

Thu, 11/15/2018 - 11:56

Disclamer: I don't study CS (or linguistic), so I might not even fathom how stupid this question is.

In some regex implementations it is possible to have lookahead and behind tokens. But wouldn't that make the grammar described context sensitive, thus not truly a regex anymore?

submitted by /u/RomanRiesen
[link] [comments]

Weak entity and identifying entity

Thu, 11/15/2018 - 03:16

To illustrate some diagrams, I have posted the complete question Here on stackexchange site. But for quick reference for answering, my major points I'd like to ask about the diagram are:

  • Can the relationship also be one to one?
  • How do we indicate a many to one relationship from weak to strong entity and also, do we have to indicate the total participation of the strong entity in the identifying relationship? If so how in the case of many to one relationship from weak to strong entity?
  • Is it possible to have a one to one relationship instead of many to one?
  • Can the weak entity have a partial relationship?
  • Can the relationship between a weak and a strong entity be many to many? [Please see this reference in part 2, no.7 are the weak entity representations
submitted by /u/bzarnal
[link] [comments]

15 yr old student asking for advice

Wed, 11/14/2018 - 20:14


I'm currently a 15 year old freshmen in highschool and I love computers!

I love building computers and everything and I'm currently taking classes in Web Design (HTML/CSS) and dominating in them.

I would like to know what the next step might be in this Computer Science field.

Nowadays, there are a lot of computer/ tech related job opportunities out there and I do want to be involved in this field.

If this community doesn't mind, I would love to be given some advice on what to study and pursue next.

Thank you!

submitted by /u/eughwhatisthat
[link] [comments]

Cache speeds

Wed, 11/14/2018 - 15:34

I am trying to find out what is the speed of cache in different computer components, but i am not really sure where I can find this data.

I found this site where it says that usually the speed of SRAM is between 7 ns and 20 ns, however I am not sure where to look to get information about cache speeds in different computer components.

For example here I see that the Cache size in this hard drive is 128 MB, but I dont where I can find the speed of this cache.

My question is, where can I find the information for cache speeds in different computer components.

submitted by /u/GermanOfficer
[link] [comments]

Will Business Analysis become an obsolete job soon?

Wed, 11/14/2018 - 12:19

I was having a discussion with a colleague and they had mentioned that they think the job of a Business Analyst will become automated very soon. I cannot see this happening for a while, but I wanted to get other people's thoughts on this. I will be starting my job as an analyst soon, so it is something I am curious about.

submitted by /u/foam_frank
[link] [comments]

Beginning C Program question

Tue, 11/13/2018 - 17:16

We are told to do the following:

Write 2 loops fragments using correct loops

Allow user to enter 100 ints- For loop

Print out how many are positive, negative, or zero.

(We will also be given a sample output, Dont know the use of this)

Any Help is greatly appreciated


submitted by /u/CopperBlanket
[link] [comments]

Simple Queueing Problem has me stumped (xpost /r/statistics)

Tue, 11/13/2018 - 15:12

I posted this over at /r/statistics, but was advised to post it to this sub...

Allow me to preface with the face that I am no statistician/mathmetician. I came up with a toy problem I was eager to solve, but I've spent some time on it and am falling short of a satisfactory solution.

I often have to run scripts against a large number of inputs, or collect data from various databases, and using parallel processing in my code to get the job done faster.

When running long jobs, though, I am unable to produce a reliable estimate of how long it will take to complete the full batch. So, the problem I wanted to solve was:


  • n inputs ("customers")
  • m threads ("workers", "servers")
  • Average job duration of t seconds.

... how long would it take the entire operation to complete? Or, how many threads are necessary to complete an operation given in under t seconds given n inputs.

I ran some simulations and used the data to build a multiple regression model:

``` lm( log(Runtime) ~ log(Workers) + log(Inputs) + log(AvgJobTime) )

Residuals: Min 1Q Median 3Q Max -0.26248 -0.05670 0.00007 0.05412 0.45140

Coefficients: Estimate Std. Error t value Pr(>|t|)
(Intercept) 0.377567 0.026665 14.16 <2e-16 *** log(Workers) -0.949641 0.005678 -167.25 <2e-16 *** log(Inputs) 0.907596 0.006153 147.50 <2e-16 *** log(AvgJobTime) 0.965165 0.006422 150.29 <2e-16 ***

Residual standard error: 0.09941 on 728 degrees of freedom Multiple R-squared: 0.99, Adjusted R-squared: 0.9899 F-statistic: 2.394e+04 on 3 and 728 DF, p-value: < 2.2e-16 ```

After some algebra, I get:

Runtime = e^0.378 * workers^-0.95 * inputs^0.908 * jobtime^0.965

However, this model fails to generalize well when the input size gets very large.

At this point, I'm convinced there exists some mathematical exactness to this problem that I am using simulations to merely approximate. My search led me to a plethora of information about Queueing Theory and pages 22-24 of these lecture slides, which (I think) detail a solution to my original problem. However, I'm having a hard time understanding pieces of it. Namely, in my scenario, there is no interarrival time; simply n inputs to process. Given this simplification, is there a simpler solution to this problem that I'm missing?

submitted by /u/_dm3ll3n_
[link] [comments]