This page is not created by, affiliated with, or supported by Slack Technologies, Inc.
2019-07-01
Channels
- # 100-days-of-code (2)
- # beginners (83)
- # calva (3)
- # cider (98)
- # clara (3)
- # clj-kondo (2)
- # clojure (84)
- # clojure-dev (59)
- # clojure-europe (11)
- # clojure-italy (22)
- # clojure-madison (4)
- # clojure-nl (3)
- # clojure-spec (24)
- # clojure-uk (80)
- # clojurescript (33)
- # clr (3)
- # datomic (59)
- # events (2)
- # fulcro (20)
- # interop (35)
- # jobs (6)
- # jobs-rus (1)
- # joker (3)
- # kaocha (2)
- # luminus (3)
- # off-topic (16)
- # other-languages (2)
- # pathom (17)
- # planck (2)
- # reagent (1)
- # shadow-cljs (1)
- # test-check (1)
- # tools-deps (49)
- # vim (16)
does the term "optimality" have a specific meaning in the field of discrete optimization? e.g dynamic programming proved optimality for the knapsack problem.
ah, ok. this might be the answer https://stackoverflow.com/questions/38896231/what-is-the-difference-between-optimality-and-efficiency
One use of the word optimality for such problems is: is a particular algorithm guaranteed to return an optimal solution to the problem? Or does it sometimes return a best solution, but other times return a feasible solution that might be worse?
For some problems, like shortest path through a graph of nodes and edges, there are well-known algorithms that are both provably fast (e.g. run time is order of (# edges) * (log(# of nodes)) in the worst case) and guaranteed to find an optimal solution, i.e. a path that is shortest among all possible.
so optimal means correct? if the requirement is to find the shortest path, then anything that isn't the shortest past would be incorrect.
If the requirement is to find the shortest path, then only a shortest path is correct.
If the goal is "find a 'good enough' path, hopefully short" then an algorithm that, say, returns a path guaranteed to be at most twice as long as the shortest path, might be good enough, for your purposes.
There are many computationally hard optimization problems where people have figured out how to write a fast algorithm that is guaranteed to return a solution that is "at most A times worse than the best", but no one has figured out a fast algorithm with A=1.
i think i understand. I was working through a problem on a discrete optimization class and they required you mark if your algorithm proved optimal. I looked at some existing solutions and people just hard coded this flag . in the lectures they talk around it but never specifically define it. At one point they say DP is optimal for knapsack, but then later say it depends on the input. I'm going to hardcode it as well, as it seem to be a bit of a distraction.
knapsack is one of those hard computational problems where, for the general problem with arbitrarily large pieces sizes, there is no known "fast" (i.e. guaranteed worst case polynomial run time in the size of the input). If the piece sizes are limited to be small, then there are.
You should probably ask the professor/TA to be sure what they mean, but my guess is when they say "mark if your algorithm proved optimal", they mean "tell us if the program you wrote implements an algorithm that is guaranteed to return a best possible solution". There are certainly algorithms for the problem that are guaranteed to return a solution, but not necessarily a best one.
There are algorithms that are not guaranteed to return a best solution, but they might still for some inputs return a solution that is a best one. Whether or not it is easy to determine that a particular solution is a best one or not, depends a lot upon the problem.
Thanks Andy, i did ask on the class forums. I know i'm constant with other solutions so far and maybe specifics are made clear later. 🙂
There are a bunch of problems where the best known algorithms fall into a spectrum where you have to choose between fast run times, or guaranteed optimal solutions.
Not sure if that addresses your question, exactly.
----- warning type stuff ------------- Is there a better place for type specific discussions then off-topic? Tim's old gist on "what he wants from a Type System" is currently trending on HN https://news.ycombinator.com/item?id=20322704. Most likely because of the recent attention it got on here and the Future of Coding slack channel (just a guess though). Some quick thoughts about the discussions i see so far. I think the top comment by UFO is informative. It's possible the type error problem of type A != type B could be made more clear by giving that information in realtime to the developer and letting them assign blame. Some reference to a library called Hlist which quickly leads me down a rabbit hole. Yogthos tries to motivate a defence for building a scope in which its ok to not prove things for the sake of conciseness. I find it interesting that a lot of the more advanced uses of Types to augment the developer experience seem to reach all the way to the run time and interact with the user as they build the program. Hazel and Lamdu are two examples i'm aware of. This approach seems to bridge the gap for me and doesn't seem dis similar to how and why i enjoy using clojure.