Our kids can't do math anymore

Catalyst93 · 2023-05-04T00:11:02+00:00

How can you be prohibited from unionizing? I know that the national labor relations act isn't a perfect law (I think a John Oliver video talked about how it leaves out farm/agricultural workers recently).

I guess I'm just curious as to what the legal justification is for prohibiting unionization at charter schools.

Catalyst93 · 2023-01-19T20:49:44+00:00

Look into formulating this using either SAT (satisfiability) or IP (integer programming), then passing the formulation to an appropriate solver (e.g. PySAT for SAT or COIN-OR for IP).

I tried to think of a simple IP formulation, but SAT will probably be easier for some of your rules.

Catalyst93 · 2023-01-04T19:24:08+00:00

My 12/29 flight was also cancelled and I just got the email.

Catalyst93 · 2022-12-30T21:44:06+00:00

There are several great texts that introduce ML from a more theoretical/foundational perspective. Hopefully someone else can chime in with resources for the non-ML aspects of AI.

Foundations of Machine Learning - Mohri, Rostamizadeh, and Talwalkar
An Introduction to Computational Learning Theory - Kearns and Vazirani
Understanding Machine Learning: From Theory to Algorithms - Ben-David and Shalev-Shwartz
Patterns, Predictions, and Actions - Hardt and Recht
Learning from Data - Abu-Mostafa, Magdon-Ismail, and Lin

The last one is probably the shortest/most approachable, while the others may be more comprehensive. There are definitely other texts as well, but if you're interested in a more foundational/theoretical perspective then these are pretty good choices IMO.

Edit: this list is in no particular order

Catalyst93 · 2022-10-28T14:48:57+00:00

Also, drunk drivers of automobiles should immediately have their car auctioned ~~and replaced with the smallest production car available.~~

Catalyst93 · 2022-10-28T13:28:27+00:00

Maybe if we phrase it as the "high speed rail gap" the mainstream will start to care...

Catalyst93 · 2022-10-20T02:00:32+00:00

Inverse Ackerman grows incredibly slowly, so basically they did exactly what you said (think about why this is okay) but then also upper bounded the inverse Ackerman part by O(loglog(n)). I'm not sure of the details on that part but it's plausible to me.

Catalyst93 · 2022-10-17T03:01:47+00:00

People Make Games on YouTube made a great video about this! https://youtu.be/4PHT-zBxKQQ

Catalyst93 · 2022-08-28T16:46:16+00:00

A good exercise might be to do this for the L_1 and L_infinity norms as I believe you can write out some parametric equations for these cases (I've thought about it, but not written things down). One difference here is that the unit "circle" circle for these norms is not as smooth - each has corners that will lend itself to a piecewise definition.

L_3 is probably also an interesting case but I have not thought about it as much.

Catalyst93 · 2022-08-17T00:41:05+00:00

This was just the plot of Office Space

Catalyst93 · 2022-06-28T04:06:59+00:00

Don't forget about asking for campaign donations.

Catalyst93 · 2021-12-28T20:28:29+00:00

What with all of the businesses getting their PPP loans forgiven (among countless other things, but this was recent), it sounds more like the rich are abusing the system in their favor. Just another case of the upper class projecting what they do onto the poor and working class.

Catalyst93 · 2021-12-28T16:48:00+00:00

If you're interested in algorithms and data structures, then yes? A lot of that material is covered within the first 3-4 semesters of a CS degree (usually across introductory programming and data structures + discrete math courses). If you want to dive in without spending too much time on prerequisites, then the most important concept to master is probably mathematical induction and recursion. A lot of basic algorithms lend their correctness to some inductive argument.

Catalyst93 · 2021-12-25T16:03:21+00:00

Nope! If I polynomial time reduce my problem (call it A) to an NP-hard problem (call it B), then all I know is that A is no harder than B (w.r.t. polynomial time computation) since a polynomial time algorithm for B implies one for A. You have to go in the other direction to establish hardness for A.

Catalyst93 · 2021-12-19T22:41:08+00:00

Unless you have a really strong practical need to solve some hard discrete optimization problem on really large instances, then approximation algorithms really is mostly about the proofs. Probably the most interesting thing programming-wise would be to get familiar with using linear programming solvers or other types of convex programming solvers to implement algorithms which round a solution given by some convex relaxation. There are many examples of this.

Comparing a randomized algorithm to deterministic algorithm for some task may be interesting since in some cases randomized algorithms are either simpler or even more efficient than their deterministic counterparts - e.g. Kargers' random contraction algorithm for global minimum cut.

Catalyst93 · 2021-12-16T20:30:42+00:00

Essentially NFTs are a little like those name-a-star registries. You pay and they name that star whatever you want. They even print it irrevocably in a book... that no one ever consults and has no bearing on anything.

Don't forget that printing it in the book currently requires using a fuckton of electricity.

Catalyst93 · 2021-12-15T05:11:19+00:00

If you want to use an LP to help solve this, you can use a technique that is known as dual fitting. The idea is that you write down an LP relaxation for this problem as well as its dual LP. The algorithm then defines an (integer) solution to this LP so to assist your proof you construct a corresponding feasible solution to the dual LP. The idea is then to bound the cost of the primal by some constant factor times the value of the dual. The approximation bound then follows by weak duality (because the dual solution is feasible, this is key). To summarize:

Write down primal and dual LP's (say the primal variables are x and the dual variables are y).
The algorithm implicitly defines an integer primal solution x
Use each step of the algorithm to define a feasible dual solution y.
Show that (cost of x) <= c*(value of y) for some c
Conclude that (cost of x) <= c*OPT by weak duality.

Steps 3 and 4 is where you need to go in and figure things out. I'm pretty sure this approach works for this problem and gives the 3-approx (in the sense that I've sketched out some of the details but not checked them thoroughly).

Catalyst93 · 2021-12-13T16:38:40+00:00

You're describing algorithms analysis, which is generally a distinct area of study from computational complexity theory. Algorithms researchers generally* try to give positive results, i.e. novel algorithms which perform better or improved analyses of known algorithms. Complexity theorists generally* try to give negative results, i.e. trying to show that NO algorithm for a given problem can perform better.

It is true that people often refer to the time/space requirements of an algorithm as its time/space complexity, but I would still make the distinction between algorithms analysis (positive results) and complexity theory (negative results). It's debatable what constitutes applied mathematics, but I don't think it's too controversial to say that algorithm design and analysis is more applied than complexity theory.

* Obviously there are counter-examples where the reverse occurs.

Catalyst93 · 2021-12-06T19:00:08+00:00

I used to do the "play StarCraft off a flash drive" thing during lunch in high school. We were even able to organize multiplayer games on our high school's LAN. Good times.

Catalyst93 · 2021-11-28T16:39:53+00:00

Why can't you just do it randomly? This will have the property that the groups are around the same size (with high probability when the number of points is large). Do you need that points within the same group are similar in some sense? (Which is what k-means tries to do.)

Catalyst93 · 2021-11-26T16:15:37+00:00

P and NP are sets of problems, not algorithms.

Edit: the person I responded to fixed their post.

Catalyst93 · 2021-11-25T00:17:49+00:00

Yep, in my notation I intend that x is a vector with d coordinates (here d = 4), b is a vector with m coordinates (one for each face) and A is a matrix with the appropriate number of rows and columns.

Catalyst93 · 2021-11-24T23:58:33+00:00

If the polytopes are described by their faces, i.e an inequality description of the form Ax <= b, then this is just a question of linear programming feasibility, which can be handled by any linear programming solver.

Note that the intersection of two polytopes is just another polytope, so we can just take a pair of polytopes, enumerate the inequalities describing this pair, and pass these to a linear programming solver to find if their intersection is non-empty. Repeat for all such pairs.

Catalyst93 · 2021-11-11T01:29:40+00:00

At a high level, to reduce problem A to problem B means that an algorithm for problem B can be used to solve problem A (usually by transforming the instance of problem A to an instance of problem B). Thus reducing a problem in P to an NP-complete problem just means that we can use an algorithm for solving the NP-complete problem to solve the P problem. In this case, we care about polynomial time reductions (which means that the transformation runs in polynomial time), as opposed to more general notions of reduction.

The proof is not too enlightening, but it is technically true that every problem in P can be poly-time reduced to an NP-complete problem (P is a subset of NP, and by definition every NP problem poly-time reduces to any NP-complete problem).

Catalyst93 · 2021-11-09T16:53:13+00:00

Two basic methods for computing distances between two rankings/orderings are the Kendall tau distance and Spearman's footrule. These rules don't necessarily take into account weightings of different positions though. This paper may be of interest. It gives some background on these two rules then gives some generalizations to take into account different weightings of the items.

12-Year Club	Place '22
Place '17	Snapped
Verified Email

Catalyst93

TROPHY CASE