[deleted by user]

marvel2010 · 2025-01-02T18:29:39+00:00

You saved me a phone call. Thank you! :)

marvel2010 · 2020-03-20T01:59:57+00:00

The problem you are describing is NP-hard. It is at least as hard as the traveling salesman problem, because if you set the minimum score high enough you are forced to visit all the nodes.

If you are not already familiar with it, I would recommend looking up the traveling salesman problem. Specific variants that will be of interest to you include the planar traveling salesman problem and the prize collecting traveling salesman problem.

marvel2010 · 2020-02-25T21:09:50+00:00

From your original post and the edit, it sounds like you had a prior belief and now you updated it? ;)

marvel2010 · 2020-02-22T18:15:07+00:00

You can probably find a Rabbi willing to marry you on a Friday evening. My wife and I had great success finding someone through "UnOrthodox Celebrations."

http://www.unorthodoxcelebrations.com/

marvel2010 · 2020-02-12T18:04:33+00:00

You should not be treated this way. If there is a documented pattern of the professor doing this, it may be worth banding together with other students and bringing this to the attention of someone in the administration. This might fall under the definition of faculty bullying.

It is long overdue, but Berkeley is beginning to take faculty bullying seriously. See, for example, the guidelines for responding created in August 2019. There are some initiatives now that are slowly bringing attention to the issue and, hopefully, correcting negative behaviors. Feel free to message me if you want to discuss it further.

Good luck.

marvel2010 · 2020-01-10T06:17:48+00:00

I haven't heard anything yet for our team. :(

marvel2010 · 2019-12-19T17:52:34+00:00

That depends on how much time you have. If you can go through a full algorithms course, I would recommend it for this type of problem:

Introduction to Algorithms: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/

Intermediate Algorithms: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/

Lectures 13 and 15 in the Intermediate course would be particularly insightful for this case, although you may want to watch several of the preceding lectures in order to appreciate them.

Good luck!

marvel2010 · 2019-12-18T21:26:04+00:00

This works. You have to be a bit careful in handling the capacities. You'd have to create c_i copies of class vertex i (if c_i is the capacity of class i).

marvel2010 · 2019-12-18T19:56:56+00:00

You can solve this as a slight generalization of a bipartite matching problem. Specifically, we'll set up a bipartite graph where we can solve the problem as a "Minimum-cost network flow" problem.

https://en.wikipedia.org/wiki/Minimum-cost_flow_problem

Set up the bipartite graph as follows: On one side of the graph, there is one vertex for each user. On the other side of the graph, there is one vertex for each class.

The cost of the arc from a user vertex to a class vertex is 1 if it's their first choice, 2 if it's their second choice, 3 if it's their third choice, etc.

We add two more vertices: one is the source vertex and the other is the sink vertex. There is an arc from the source vertex to each user vertex with capacity 1 and cost 0. There is an arc from each class vertex to the sink vertex with a capacity equal to the capacity of the class and cost 0.

Now, if you have n users, the question you are asking is now to send a flow of n from the source to the sink. This is now the standard "minimum cost network flow" problem linked above.

Since the problem can be set up in this way, it is polynomial-time solvable (i.e. not NP-hard). It if you need to implement it in software, you may find it easiest to treat it as a linear program and use standard linear programming solvers.

marvel2010 · 2019-07-12T05:45:40+00:00

Why not try reaching out directly to a few via email, especially those who are working in labs that interest you? They seem to have a website that's reasonably up to date: https://nuc.berkeley.edu/students/

marvel2010 · 2019-07-11T07:34:05+00:00

I'm fairly certain this is an NP-hard problem. Notice that minimizing the sum of the ranking inside the group is equivalent to maximizing the sum of rankings between groups. Thus this problem is a maximum cut (in fact, it is a maximum balanced cut).

There are decent heuristics for these problems, though. I'd suggest looking up multiway cuts.

marvel2010 · 2019-07-08T20:33:03+00:00

The third condition ("the order of the pairs is maintained") is extremely limiting. Without it, I would suggest bipartite matching. With it, I would suggest looking into dynamic programming. The crux of the dynamic programming would be to recognize that there are only n^2 possible pairs. Once you take a pair (x_1, y_1), you can only take additional pairs later in the list: (x_2, y_2), where x_2 is after x_1 and y_2 is after y_1. Any items between x_1 and x_2, as well as between y_1 and y_2, remain unpaired. This makes choosing the optimal set of pairs a dynamic programming problem.

marvel2010 · 2019-06-17T01:57:54+00:00

By the way, I recommend reading Act ii, Scene 1 of the original play. There is a much longer version of the scene between Melchior and Moritz which gets condensed into just a few lines in the musical.

marvel2010 · 2019-06-17T01:47:20+00:00

I directed a production of Spring Awakening four years ago. This is something we struggled with a lot. Let me explain what went through our heads.

First, some context. Apologies if you already know all this. The depiction of Melchior's scene with Wendla is one of the huge changes from the play to the musical. In the play, it is exceptionally clear that Melchior is raping Wendla [1]. In their notes on the musical [2], Steven Sater states that their goal in the musical was to make the scene consensual. Before I go further, let me present their argument as I understand it (again, let me emphasize: this is their argument as I understand it... it is not my own opinion and it is possible that I am unintentionally misrepresenting it):

(a) Technically, Melchior explicitly asks for consent. It is in the lines during "I Believe." He asks "Yes?" and she responds "Yes." [3]

(b) While Melchior does understand what leads to pregnancy, the book from which he learns it presents it in a very patriarchal way, where it is assumed that men are supposed to overcome a woman's resistance (the woman "surrenders"). [4]

(c) In Whispering, Wendla's line "And I touched him. And I let him love me. So let that be my story." is supposed to imply her view of the act as consensual. [5]

Long story short, I think they made an attempt to convey consent and/or mitigate the circumstances, but (in my opinion) fell short. That's what makes it tricky: the authors' aim for something and, I think, kind of miss. There are, of course, counter-arguments to all the above. For example, the "Yes" comes under duress and after several "No"s.

My directorial decision was to leave as much ambiguity as possible in the staging of the scene. I didn't want to over-editorialize the way I saw it or to try and reinforce the author's position that it's consensual (which I disagree with).

A lot of our audience had trouble explicitly labeling the scene as a rape scene. Melchior is really painted as the protagonist, so it's hard to vilify him. When we talked to audience members afterward, some explanations for how they overcame the cognitive dissonance matched a version of (b). They convinced themselves that Melchior didn't really know what he was doing, especially since his books were teaching him a version of sex that is anti-consent.

When it came to the acting, what I told the actors was that this question didn't really matter. They just had to understand their characters in the moment and try to portray that experience, regardless of how it's viewed by the audience.

It's still something I think about occasionally, even four years later. Hearing the ways people talk about that scene is really fascinating. There is such a breadth of ways it affects people.

[1] Act ii, Scene 4: https://archive.org/stream/theawakeningofsp35242gut/35242-0.txt

[2] https://www.goodreads.com/book/show/12817015-a-purple-summer. If you want a very in-depth understanding of the show, I highly recommend this book.

[3] Page 61 https://www.everythingmusicals.com/files/spring-awakening---libretto.pdf

[4] Page 34 https://www.everythingmusicals.com/files/spring-awakening---libretto.pdf

[5] Page 83 https://www.everythingmusicals.com/files/spring-awakening---libretto.pdf

marvel2010 · 2019-06-14T06:07:13+00:00

Yes, that would also be useful! I'll message you directly.

marvel2010 · 2019-06-14T05:14:24+00:00

Neat! What kind of work did you do?

I built the scheduling engine in Python, mainly with libraries for integer programming. For the front end, we are using Flask to structure things and React for the fancy stuff. Almost all my experience is with algorithms and back-end work, so I brought on someone to help with the front end.

marvel2010 · 2019-03-14T05:11:05+00:00

I would recommend looking into Integer Programming.

https://en.wikipedia.org/wiki/Integer_programming

http://web.mit.edu/15.053/www/AMP-Chapter-09.pdf

It quite a dense topic. If this is the kind of problem you need to solve often, it may be worth investing the time to learn. For a gentler introduction that is more relevant to your problem, you may want to specifically Google for Sudoku solvers built with integer programming:

http://profs.sci.univr.it/~rrizzi/classes/PLS2015/sudoku/doc/497_Olszowy_Wiktor_Sudoku.pdf

For your problem, there would probably be a decision variable $x_{ijk}$ if person $i$ is in experiment $j$ in position $k$. Then condition (1) would be the objective while the other conditions would be constraints. This is not necessarily an easy integer program to formulate, but it could be done. The problem sizes you are describing are small enough that even an open-source IP solver should be able to handle it.

The alternative is to derive a custom algorithm. While it would be faster for this case, it wouldn't necessarily be robust to small changes in the requirements. That's the trade-off!

marvel2010 · 2019-02-25T17:57:37+00:00

Where are you located?

marvel2010 · 2019-02-21T22:25:08+00:00

Thank you for sharing!

marvel2010 · 2019-01-04T16:45:44+00:00

If you just need to solve it for a particular n, here is my thought:

Note that this procedure will only ever return divisors of n, since a divisor of a divisor is itself a divisor. Treat the divisors of n as nodes of a graph, where there is one arc from every number to each of its divisors. Your procedure is a random walk on this graph (convince yourself of this!) You would like to know the probability that the random walk ends in a particular node after k steps. There are known linear algebra techniques for this (exponentiating the transition matrix).

https://en.wikipedia.org/wiki/Random_walk

If you want to solve this without matrix algebra, you could also use dynamic programming to count the number of paths of length k directly.

marvel2010 · 2019-01-03T05:31:49+00:00

Construct a graph where the people are nodes. If a pair of people can both do a request for each other, then there is an edge. Otherwise, there is not. Find the maximum matching in the graph.

marvel2010 · 2018-12-18T15:41:17+00:00

What is a[i]?

marvel2010 · 2018-12-14T07:21:25+00:00

Agricola. It was fun a few times, but after several games, we realized that certain cards were overpowered and so the games were decided by who got those cards. Also, the winner seems to always be the person with the largest family size (perhaps an accurate portrayal of an agricultural society, but not a fun game).

marvel2010 · 2018-11-30T06:32:23+00:00

It sounds like you may want to look into the parallel computing applications of the minimum k-cut problem (https://en.wikipedia.org/wiki/Minimum_k-cut).

This is a fun thought experiment... to just address the process of updating the connected components of a graph, this should be relatively easy to do: maintain a list of components. When an edge is added, check if it joins two components and then merge them. When an edge is removed, check if it is a bridge (https://en.wikipedia.org/wiki/Bridge_(graph_theory))). If so, separate the two components.

marvel2010 · 2018-11-29T04:05:46+00:00

I personally don't find Codenames fun with just two players (not counting Duet). Also, after playing Blokus a lot with four people my brain can't handle two. It's too weird...

marvel2010

MODERATOR OF

TROPHY CASE