6 ms·

I can't imagine that's what they meant? The text very specifically says: "Indeed, it is hard to imagine doing much better than that, since for any nontrivial pr

I can't imagine that's what they meant? The text very specifically says: "Indeed, it is hard to imagine doing much better than that, since for any nontrivial problem, it would seem that an algorithm must consider all of the input in order to make a decision." For them to be thinking of binary search, they would have to be effectively saying "it is hard to think of binary search", which would be a rather absurd position from a CS professor, especially given binary search is quite literally the first algorithm every programmer learns. So I took it to mean there's something interesting here where the inputs could literally be anything, not heavily constrained. But I can't imagine what that might be.

kadoban 2y ago
> especially given binary search is quite literally the first algorithm every programmer learns. I get what you're saying, and it doesn't change your point, but: no _way_ is binary search the first algorithm people learn. For binary search to even be intelligible you already have to know, at a minumum linear search and the concept of sorting (you probably know a sorting algorithm first). You also learn dozens of other really simple algorithms first in practice.
- bee_rider 2y ago
  Agreed, WRT the bigger picture; lots of little algorithms could come before binary search. But, giving them binary search before sorting kinda works. It is motivating. If you do sorting first, it just seems like a weird high-effort excursion into a niche bookkeeping thing about lists. Once they see how fast binary search is (just give them pre-sorted lists to run it on), sorting becomes interesting, right?
  - kadoban 2y ago
    Yeah, it does work as something you learn with/right-before/right-after a sorting algorithm, depending on the teaching style.
  - linguae 2y ago
    This is what I do in my introductory data structures and algorithms course at a Bay Area community college: I teach binary search as part of my introduction to recursion, and then the following lectures are a series of lessons on sorting algorithms, beginning with selection sort and then insertion sort. After teaching these O(n^2) algorithms, I spend a lecture on merge sort and then have a lecture on quicksort, both for covering O(n lg n) sorts and for introducing my students to divide-and-conquer recursive algorithms.
    - bee_rider 2y ago
      It is a shame that quicksort has to be covered. I mean, it does have to be covered. But it has an O(n^2) cost for a particular input, despite being generally considered nlog(n), seems to me to introduce some fuzziness in an otherwise solid concept. But it does need to be covered. Unfortunately. (Mergesort is best).
      - chongli 2y ago
        But it has an O(n^2) cost for a particular input Even worse is the fact for naive implementations (such as students might come up with) the worst case behaviour occurs in very common cases such as sorting already sorted lists or reverse-sorted lists.
        ykonstant 2y ago
        We have different notions of "covered", then. When I teach algorithms and introduce quicksort, the majority of the time is spent discussing strategies for choosing the pivot. I expect none of my students to implement a quicksort with bad pivot selection; if they do, that's my failure as a teacher and definitely failure in "coverage" of the algorithm.
      - ncruces 2y ago
        Quicksort is an important, extremely flexible, and very hard to beat unstable comparison sort. It's based on a very simple but powerful idea/strategy (divide & conquer). Its flexibility means it can be adapted to partially sort, find top-N, find the median or any other rank, all optimally. And it's so much faster in practice than everything else (why?), that even after mitigating its worse case, it often comes out ahead. Also, it is relevant/necessary to teach the concept of average, best and worse cases in complexity analysis. What best way to do it than “the best sorting algorithm is terrible for some inputs”? You can also use it to teach/learn adaptive algorithms (you're almost expected too): switch to something else on the base case; or on the worst case; can we do better for low cardinality; etc. So, of course it needs to be covered. There's more to learn from 200 lines of Quicksort than from Mergesort: https://github.com/ncruces/sort/blob/main/quick/quick.go https://github.com/ncruces/sort/blob/main/quick/quick.go
- ssivark 2y ago
  > no _way_ is binary search the first algorithm people learn. For binary search to even be intelligible you already have to know, at a minumum linear search and the concept of sorting Almost every 6-10 year old kid who had to use physical dictionaries intuitively learned (probably even discovered by themselves) something like binary search. It's a different matter whether they could formalize that into an algorithm and write code to handle all the edge cases. But the basic idea is very intuitive. Kids can also pick up the intuition to incorporate improvements even beyond balanced binary search eg. there might be a lot of words starting with "S" so split into two groups at a little less than the middle, etc.
  - karparov 2y ago
    Moving the goal post? If you are asking which is the "first algorithm" a human learns in their life then it's likely more related to movement (crawl? walk? move food towards mouth?) or selection (which item can I eat? who are my parents?) rather than a physical dictionary. Even considering that it's been a while since kids encountered a physical dictionary. If you are asking about formal algorithms then we're talking about the beginning of a programmers or computer scientists education and then it's usually some form of O(n^2) sort that they will encounter first, if we don't count things like "how to add two multi-digit integers" which is typically an algorithm every kid learns in primary school. Binary search tends to be one of the first recursive algorithms that are taught which is another level entirely regarding intellectual development.
    - ssivark 2y ago
      I guess my response was to how I read your comment fitting in with the higher level discussion. My main point is that many of these algorithms are intuitive, and kids learn these much earlier than when they learn formal programming (which might typically be in their teens). Looking over your comment again, I also don't dispute that linear search and sorting are simpler -- even toddlers learn these.
  - smokel 2y ago
    > Almost every 6-10 year old kid who had to use physical dictionaries intuitively learned (probably even discovered by themselves) something like binary search. I find this highly unlikely. It might be true for those children who grow up to study computer science, though.
- Aardwolf 2y ago
  > no _way_ is binary search the first algorithm people learn It legit was the first one we learned, the first algorithm written on the blackboard by the professor (this was in the 2000s but the first algorithm lessons were on blackboard and paper!) Probably because something simpler linear like "find the minimum value in a list" is too dull as an algorithm example
- globnomulous 2y ago
  It was actually the first algorithm I discovered and learned in a technical environment, when I was debugging my Skyrim mods list and realized I needed an efficient way to discover which of my hundreds of active mods were interacting, causing the dreaded neck-seam issue (It was Ethereal Elven overhaul and another whose name escapes me.) It's an unusually intuitive algorithm, so it wouldn't surprise me if it were one many people learn first.
deleted 2y ago
[deleted]
dzaima 2y ago
I read that as saying that binary search isn't among those "nontrivial problem"s, along with most other things with known exact deterministic sublinear time algorithms. And your first quote is followed by "However, for most natural problems", which further indicates that the known exact algorithms are for trivial problems.
FreakLegion 2y ago
They say a little ways down: > there are classical optimization problems whose values can be approximated in sublinear time This can actually be quite useful if the approximation is guaranteed, or even if it isn't, as long as it works well in practice. https://en.wikipedia.org/wiki/Hardness_of_approximation https://en.wikipedia.org/wiki/Hardness_of_approximation
lqet 2y ago
Here a a few examples, linked in the article: https://www.dcs.warwick.ac.uk/~czumaj/PUBLICATIONS/DRAFTS/Draft-Survey-Sublinear.pdf https://www.dcs.warwick.ac.uk/~czumaj/PUBLICATIONS/DRAFTS/Dr... Searching in sorted lists is the first example, although they acknowledge that "the assumption that the input array is sorted is not natural in typical applications." They then give an non-trivial variant of this problem, where the sorted list is stored as a linked list, so that you cannot directly jump to some element at position i. Another example for a sublinear algorithm they give is to check whether 2 convex polygons intersect, using the algorithm by Chazelle and Dobkin.
HelloNurse 2y ago
It is obvious that binary search leverages the property that the input is sorted in order to ignore part of the input, but it is less obvious to see it abstractly as an exotic specimen of sublinear exact algorithm rather than merely as a simple special case of search, and it is even less obvious to investigate what weaker (and hopefully cheaper to guarantee) input constraints allow sublinear search algorithms.

kadoban 2y ago

> especially given binary search is quite literally the first algorithm every programmer learns. I get what you're saying, and it doesn't change your point, but: no _way_ is binary search the first algorithm people learn. For binary search to even be intelligible you already have to know, at a minumum linear search and the concept of sorting (you probably know a sorting algorithm first). You also learn dozens of other really simple algorithms first in practice.

bee_rider 2y ago
Agreed, WRT the bigger picture; lots of little algorithms could come before binary search. But, giving them binary search before sorting kinda works. It is motivating. If you do sorting first, it just seems like a weird high-effort excursion into a niche bookkeeping thing about lists. Once they see how fast binary search is (just give them pre-sorted lists to run it on), sorting becomes interesting, right?
- kadoban 2y ago
  Yeah, it does work as something you learn with/right-before/right-after a sorting algorithm, depending on the teaching style.
- linguae 2y ago
  This is what I do in my introductory data structures and algorithms course at a Bay Area community college: I teach binary search as part of my introduction to recursion, and then the following lectures are a series of lessons on sorting algorithms, beginning with selection sort and then insertion sort. After teaching these O(n^2) algorithms, I spend a lecture on merge sort and then have a lecture on quicksort, both for covering O(n lg n) sorts and for introducing my students to divide-and-conquer recursive algorithms.
  - bee_rider 2y ago
    It is a shame that quicksort has to be covered. I mean, it does have to be covered. But it has an O(n^2) cost for a particular input, despite being generally considered nlog(n), seems to me to introduce some fuzziness in an otherwise solid concept. But it does need to be covered. Unfortunately. (Mergesort is best).
    - chongli 2y ago
      But it has an O(n^2) cost for a particular input Even worse is the fact for naive implementations (such as students might come up with) the worst case behaviour occurs in very common cases such as sorting already sorted lists or reverse-sorted lists.
      - ykonstant 2y ago
        We have different notions of "covered", then. When I teach algorithms and introduce quicksort, the majority of the time is spent discussing strategies for choosing the pivot. I expect none of my students to implement a quicksort with bad pivot selection; if they do, that's my failure as a teacher and definitely failure in "coverage" of the algorithm.
    - ncruces 2y ago
      Quicksort is an important, extremely flexible, and very hard to beat unstable comparison sort. It's based on a very simple but powerful idea/strategy (divide & conquer). Its flexibility means it can be adapted to partially sort, find top-N, find the median or any other rank, all optimally. And it's so much faster in practice than everything else (why?), that even after mitigating its worse case, it often comes out ahead. Also, it is relevant/necessary to teach the concept of average, best and worse cases in complexity analysis. What best way to do it than “the best sorting algorithm is terrible for some inputs”? You can also use it to teach/learn adaptive algorithms (you're almost expected too): switch to something else on the base case; or on the worst case; can we do better for low cardinality; etc. So, of course it needs to be covered. There's more to learn from 200 lines of Quicksort than from Mergesort: https://github.com/ncruces/sort/blob/main/quick/quick.go https://github.com/ncruces/sort/blob/main/quick/quick.go
ssivark 2y ago
> no _way_ is binary search the first algorithm people learn. For binary search to even be intelligible you already have to know, at a minumum linear search and the concept of sorting Almost every 6-10 year old kid who had to use physical dictionaries intuitively learned (probably even discovered by themselves) something like binary search. It's a different matter whether they could formalize that into an algorithm and write code to handle all the edge cases. But the basic idea is very intuitive. Kids can also pick up the intuition to incorporate improvements even beyond balanced binary search eg. there might be a lot of words starting with "S" so split into two groups at a little less than the middle, etc.
- karparov 2y ago
  Moving the goal post? If you are asking which is the "first algorithm" a human learns in their life then it's likely more related to movement (crawl? walk? move food towards mouth?) or selection (which item can I eat? who are my parents?) rather than a physical dictionary. Even considering that it's been a while since kids encountered a physical dictionary. If you are asking about formal algorithms then we're talking about the beginning of a programmers or computer scientists education and then it's usually some form of O(n^2) sort that they will encounter first, if we don't count things like "how to add two multi-digit integers" which is typically an algorithm every kid learns in primary school. Binary search tends to be one of the first recursive algorithms that are taught which is another level entirely regarding intellectual development.
  - ssivark 2y ago
    I guess my response was to how I read your comment fitting in with the higher level discussion. My main point is that many of these algorithms are intuitive, and kids learn these much earlier than when they learn formal programming (which might typically be in their teens). Looking over your comment again, I also don't dispute that linear search and sorting are simpler -- even toddlers learn these.
- smokel 2y ago
  > Almost every 6-10 year old kid who had to use physical dictionaries intuitively learned (probably even discovered by themselves) something like binary search. I find this highly unlikely. It might be true for those children who grow up to study computer science, though.
Aardwolf 2y ago
> no _way_ is binary search the first algorithm people learn It legit was the first one we learned, the first algorithm written on the blackboard by the professor (this was in the 2000s but the first algorithm lessons were on blackboard and paper!) Probably because something simpler linear like "find the minimum value in a list" is too dull as an algorithm example
globnomulous 2y ago
It was actually the first algorithm I discovered and learned in a technical environment, when I was debugging my Skyrim mods list and realized I needed an efficient way to discover which of my hundreds of active mods were interacting, causing the dreaded neck-seam issue (It was Ethereal Elven overhaul and another whose name escapes me.) It's an unusually intuitive algorithm, so it wouldn't surprise me if it were one many people learn first.

deleted 2y ago

[deleted]

dzaima 2y ago

I read that as saying that binary search isn't among those "nontrivial problem"s, along with most other things with known exact deterministic sublinear time algorithms. And your first quote is followed by "However, for most natural problems", which further indicates that the known exact algorithms are for trivial problems.

FreakLegion 2y ago

They say a little ways down: > there are classical optimization problems whose values can be approximated in sublinear time This can actually be quite useful if the approximation is guaranteed, or even if it isn't, as long as it works well in practice. https://en.wikipedia.org/wiki/Hardness_of_approximation https://en.wikipedia.org/wiki/Hardness_of_approximation

lqet 2y ago

Here a a few examples, linked in the article: https://www.dcs.warwick.ac.uk/~czumaj/PUBLICATIONS/DRAFTS/Draft-Survey-Sublinear.pdf https://www.dcs.warwick.ac.uk/~czumaj/PUBLICATIONS/DRAFTS/Dr... Searching in sorted lists is the first example, although they acknowledge that "the assumption that the input array is sorted is not natural in typical applications." They then give an non-trivial variant of this problem, where the sorted list is stored as a linked list, so that you cannot directly jump to some element at position i. Another example for a sublinear algorithm they give is to check whether 2 convex polygons intersect, using the algorithm by Chazelle and Dobkin.

HelloNurse 2y ago

It is obvious that binary search leverages the property that the input is sorted in order to ignore part of the input, but it is less obvious to see it abstractly as an exotic specimen of sublinear exact algorithm rather than merely as a simple special case of search, and it is even less obvious to investigate what weaker (and hopefully cheaper to guarantee) input constraints allow sublinear search algorithms.