Questions tagged [modelling]

Questions on how to represent real-world or non computer science problems with computer science tools.

Filter by
Sorted by
Tagged with
29 votes
4 answers
5k views

How to determine likely connections in a social network?

I am curious in determining an approach to tackling a "suggested friends" algorithm. Facebook has a feature in which it will recommended individuals to you which it thinks you may be acquainted with. ...
phwd's user avatar
  • 621
24 votes
8 answers
2k views

What randomness really is

I'm a Computer Science student and am currently enrolled in System Simulation & Modelling course. It involves dealing with everyday systems around us and simulating them in different scenarios by ...
MAK7's user avatar
  • 343
23 votes
1 answer
657 views

Clustering of Songs (The Joe Walsh Problem)

The Eagles are a rock supergroup from the 70s and 80s, responsible for such classics as Hotel California. They have two quite distinctive sounds, one where guitarist Joe Walsh is present (for example, ...
Dave Clarke's user avatar
  • 20.1k
16 votes
3 answers
1k views

Efficient encoding of sudoku puzzles

Specifying any arbitrary 9x9 grid requires giving the position and value of each square. A naïve encoding for this might give 81 (x, y, value) triplets, requiring 4 bits for each x, y, and value (1-9 =...
Kevin's user avatar
  • 1,062
15 votes
4 answers
4k views

How to devise an algorithm that suggests feasible cooking recipes?

I once had a veteran in my course that created an algorithm that would suggest cooking recipes. At first, all sort of crazy recipes would come out. Then, she would train the cooking algorithm with ...
Oeufcoque Penteano's user avatar
11 votes
2 answers
246 views

CCS process for a drink dispenser with two different prices

A drink dispenser requires the user to insert a coin ($\bar c$), then press one of three buttons: $\bar d_{\text{tea}}$ requests a cup of tea $e_{\text{tea}}$, ditto for coffee, and $\bar r$ requests ...
Gilles 'SO- stop being evil''s user avatar
10 votes
2 answers
502 views

Peer grading design - choosing a graph, to get accurate rankings/ratings

Background. I am writing some code for semi-automated grading, using peer grading as part of the grading process. Students are given pairs of essays at a time, and the students have a slider to choose ...
ismail's user avatar
  • 203
7 votes
2 answers
1k views

How to impose Euclidean distance constraint in a constraint satisfaction problem without quadratic constraints?

Best reference I could find is this one. However, I could not quite understand this one since there is no numerical example. What I am trying to achieve with one sentence How can I answer the ...
padawan's user avatar
  • 1,425
7 votes
1 answer
256 views

Efficient queriable data structure to represent a screen with windows on it

(this is related to my other question, see here) Imagine a screen, with 3 windows on it: I'd like to find an efficient data structure to represent this, while supporting these actions: return a ...
daniel.jackson's user avatar
7 votes
2 answers
140 views

CNF form of variable assignment problem

There are n variables $x_1$, $x_2$,..., $x_n$ and each one of them takes values from 1 to k (k>= n) and all are distinct. How can I represent this in the CNF form? (I tried the trivial way of trying ...
Gilfoyle's user avatar
7 votes
2 answers
268 views

Building probability distribution functions from observation

There are N players and M objects, each of the objects has a value. Each player has a strategy in choosing an object. Each round a player will choose an object, many players can choose the same object....
Mike G's user avatar
  • 451
6 votes
1 answer
173 views

How to represent the interests of a Facebook user

I'm trying to figure out a way I could represent a Facebook user as a vector. I decided to go with stacking the different attributes/parameters of the user into one big vector (i.e. age is a vector of ...
mabounassif's user avatar
6 votes
1 answer
121 views

How to score a given arrangement of windows on a screen to produce good layouts

(this is related to my other question, see here) I would like to write a function that scores a given arrangement of windows on a screen. The purpose of this function is to determine whether a ...
daniel.jackson's user avatar
5 votes
2 answers
735 views

Is $a^n b^n$ an artificial language or does it occur in the real world?

The classic example of a context-free grammar is $a^nb^n$. That is, $n$ occurrences of $a$ followed by an equal number of occurrences of $b$. Do such forms occur in the real world? Can you provide an ...
5 votes
3 answers
242 views

Terminology needed for the computational solution to the Rubik's Cube

I apologize if this question is out of the guidelines of this forum. If it is please let me know and I will abstain from requesting definitions and terminology. Hello! I am currently writing a ...
TestingTuring's user avatar
5 votes
1 answer
4k views

Set the parameters of a Erdos-Renyi graph generator to get a specific mean degree

I'm trying to reproduce the synthetic networks (graphs) described in some papers. The topic is the same as a previous question of mine, but with a different focus. It is stated that the Erdos-Renyi ...
Agostino's user avatar
  • 347
5 votes
3 answers
234 views

Formalizing self-propagating behaviour

Since reading Ken Thompson's Reflections on Trusting Trust I am trying to formalize the idea of a program which mutates its own behaviour; specifically, a program that would be self-reproducing except ...
Francesco Gramano's user avatar
4 votes
1 answer
169 views

What are the rudimentary types of information connectivity i.e. model types?

I am looking at a modelling tool and are trying to determine all the types of ways that you can model (at a rudimentary level) I remember seeing a list of ways in which you can connect or categorise ...
Hightower's user avatar
  • 141
4 votes
1 answer
45 views

How to model references in an ontology

I am interested in creating an ontology which will model arguments (among other things). For example, a triple in the ontology might be ...
Noah Santacruz's user avatar
4 votes
2 answers
586 views

Dynamic Shortest Path with Linear Programming

Consider a grid with $x=5$ columns, $y=5$ rows, and $T$ timesteps. There are $N=2$ agents in this grid, which can move vertically or horizontally. The positions of each agent $x$ at timestep $t$ is ...
BlueMoon93's user avatar
4 votes
0 answers
115 views

Solving an Interlacing Cords puzzle inside a Truncated Octahedron

My friend got me this really interesting puzzle Each node can be slided or docked around the Truncated Octahedron, creating knots and tangles in the middle of the puzzle. The idea is to move the ...
Alexandre's user avatar
  • 141
3 votes
2 answers
304 views

Matching two people. One has 7% in common with the other. The other has 70% in common. What's a fair match score?

I am exploring some ideas around dating site matching, and I can do with some ideas as to which is the better solution Senario: We have a boy and girl, the boy has completed his profile/bio ...
code511788465541441's user avatar
3 votes
3 answers
349 views

How to Determine Places, Transitions and Tokens in a Scenario when Modeling with Petri Nets?

When modeling a scenario with Petri nets how should I determine the places, transitions and tokens? Example: There are two exam assistants in an exam hall observing the exam. They stand in front of ...
Infinity's user avatar
  • 131
3 votes
1 answer
178 views

Is it viable to use an HMM to evaluate how well a catalogue is used?

I was interested on evaluating a catalogue that students would be using to observe how is it being used probabilistically. The catalogue works by choosing cells in a temporal sequence, so for ...
Oeufcoque Penteano's user avatar
3 votes
1 answer
735 views

Boat riddle as a combinatorial optimization problem?

I remember a riddle about a bunch of people on a river bank, and a boat with limited capacity (lets say the boat can transport 2 people at a time). There are various relations between the people like: ...
Smajl's user avatar
  • 1,035
3 votes
2 answers
2k views

Linear programming formulation for the single-source shortest path problem

In this course lecture; section 5.1, single-source shortest path (SSSP) is formulated as the following linear program (LP): \begin{align} \max &\sum d_u \\ \text{subject to} & \\ d_v &\le ...
hengxin's user avatar
  • 9,441
3 votes
1 answer
58 views

Finding a method to classify pixels according to how drastic their intensity change

I am looking for a method to classify pixels into three groups: (1) Pixels which does not change their intensity much in general (the slight changes may be due to noise only), (2) Pixels which change ...
GreenPenguin's user avatar
3 votes
1 answer
70 views

Develop a winning strategy for a game

Okay so I've been going crazy about this problem I was given. It is as follows: Given a pile of N matches, 2 people take turns removing matches from the pile. When it is your turn you are allowed ...
Eoghan Hogan's user avatar
3 votes
1 answer
203 views

Is this problem just an application of traveling salesman? If not is it some other already "solved" problem?

Description of the problem in question: Say I have a complete graph with positive weighted edges. 1 vertex is specified as the "end". A subset of the other vertices are designated as "start" vertices....
cwolf08's user avatar
  • 31
3 votes
3 answers
166 views

How do you have a type typed "Type" when implementing a programming language?

I am working on the base of a language model, and am wondering how to represent the base type, which is a type Type. I have heard of an "infinite chain of ...
Lance's user avatar
  • 2,103
3 votes
0 answers
364 views

Context-free grammar for DAGs?

I'm looking for a "safe" representation of DAGs. With "safe" representation I mean that it can be described by a context-free grammar. Ideally, this grammar would be suitable for a simple LR parser. ...
vog's user avatar
  • 135
3 votes
1 answer
333 views

Mathematical model for a webpage layout?

Getting layout right (even if only a structure is considered) with HTML5/CSS3 is still more like an art or black magic. On the other hand, there are other GUI systems (like wxWindows and Tcl/Tk) and ...
Roman Susi's user avatar
2 votes
3 answers
236 views

Integer linear programming formulation of formula in DNF

I have multiple sets, e.g., $$\{1, 2\}, \{2, 3, 4\}, \{1, 4\}$$ Each variable $1, 2, 3, 4$ is binary. I need to represent the following condition without additional variables $$(1 \land 2) \lor (2 \...
Tom's user avatar
  • 175
2 votes
2 answers
254 views

How can union-find algorithm be used with "real" data

In the beginning of the Princeton algorithms course the Dynamic connectivity problem is presented (quick-find, quick-union). Here is how it's described: The input is a sequence of pairs of integers,...
Max Koretskyi's user avatar
2 votes
1 answer
300 views

Why arrival process of packets at a switch is not a Poisson Process?

"Packet arrivals are not Poisson .... but some events are, such as web requests and new flow arrivals" I know since the network traffic is very bursty, they are not Poisson. But I am unable to ...
Romy's user avatar
  • 407
2 votes
1 answer
460 views

How to represent circles in x-y coordinates [closed]

I would like to be able to represent circles in x-y coordinates. Each circle contains an x and y coordinates and radius in double data type. My goal is to compare circles with each other whether ...
Sarp Kaya's user avatar
  • 381
2 votes
1 answer
60 views

How can I measure the usability of a catalogue?

This question might seems vague but heres the context: When we are focusing on HCI we would most likely be interested on knowing first how the user usually deals with a certain object. We then try to ...
Oeufcoque Penteano's user avatar
2 votes
1 answer
203 views

Pattern classification: what goes into the sample?

I am trying to compare the performance of a classification result with Bayes classifier, K-NN, Piece wise component analysis (PCA). I have doubts regarding the following (please excuse my lack of ...
user1214586's user avatar
2 votes
2 answers
269 views

Modelling a dependency of multiple transitions on data in one place

We are modeling our process using a colored Petri net. One of the limitations we have is that when multiple transitions depend on one place, only one of those transitions will fire because then the ...
user2609980's user avatar
2 votes
1 answer
61 views

A voting scheme where votes are scriptable

I am looking for literature on mathematical models of (political) voting schemes. Concretely, I am interested in models that allow votes of the following form: "I am voting for $X$, but only if $...
ComFreek's user avatar
  • 438
2 votes
1 answer
312 views

Expressing a logical constraint in integer programming

Let $x$ be an integer such that $x \in [ - 10,10]$ and $b$ a binary variable. Apply integer programming to express $b = 1 \leftrightarrow x \ge3$ My work: \begin{equation} \begin{cases} \...
user_777's user avatar
  • 142
2 votes
1 answer
442 views

Efficient formulation for binary integer linear programming

Problem: There are two types of balls, big (B) and small (S), which need to packed into boxes. One box can contain either: nothing, or 1 S, or 1 B, or 2 S, or 2 B, or 1 B and 2 S We are given the ...
Aditya's user avatar
  • 123
2 votes
1 answer
31 views

System Identification vs Machine Learning for dynamic system modelling

So I found another discussion regarding this, but the answers did not fully separate the differenced between SID and ML. Hopefully a discussion here can shed some light on some larger differences both ...
bullfighter's user avatar
2 votes
1 answer
480 views

Selective Background Updating in Running Gaussian Average Method for Background Subtraction

I am studying the Running Gaussian Average Method for background subtraction. One alternative, as described in Wikipedia, also known as Selective Background Updating, is to only update the ...
GreenPenguin's user avatar
2 votes
0 answers
73 views

Least squares fit of a rational function

I am fitting different 2D geometric transformations by least-squares. For instance quadratic, $$\begin{cases}a'x^2+b'xy+c'y^2+d'x+e'y+f'=X\\a''x^2+b''xy+c''y^2+d''x+e''y+f''=Y\end{cases}$$ which is ...
Yves Daoust's user avatar
  • 8,841
2 votes
0 answers
32 views

How to specify mutated types mathematically?

Say I have an object which I pass to a method, and the method returns that same object, just mutated. So it goes like this: ...
Lance's user avatar
  • 2,103
2 votes
0 answers
287 views

The meaning of ontology in computer science

I am reading a paper and ran into this word Ontology-based, What does it really mean? I did searching about it but still ambiguous to me, can someone elaborate this ...
Mike's user avatar
  • 121
2 votes
0 answers
58 views

An alternative to the object paradigm

I've been playing around with an alternative to the standard object-oriented paradigm for modeling data, and I would like to know if there is any research or already existing systems along the same ...
Roland's user avatar
  • 153
2 votes
1 answer
126 views

How does the Weibull distribution work as fault model in wireless sensor networks?

I am a little bit confused with the concept of using the Weibull distribution or other distribution for fault model. As I understand, in simulation this distribution is often used for modelling a ...
Anahita k's user avatar
2 votes
0 answers
32 views

A* orientation discretization

I have a space with obstacles I wish to find a path through. What I can do is discretize the space into a grid and use A* (or D* or whatever) to find a path through it. I wish to now add orientation ...
Damjan Dakic's user avatar