10 ms·

Problem Solving with Algorithms and Data Structures Using Python

294 points by samrohn 8y ago

asicsp 8y ago
and for beginners to programming and Python, the same site provides this excellent course: https://interactivepython.org/runestone/static/thinkcspy/index.html https://interactivepython.org/runestone/static/thinkcspy/ind...
qwerty456127 8y ago
Is there an alike book that would provide functional implementations of the algorithms alongside or instead of imperative ones? In Python preferably but I don't mind any other language. I would like to learn implementing algorithms and solving problems the functional way.
- Puer 8y ago
  Elements of Programming Interviews in Python is excellent imo. The authors give a crash course in all of the data structures and all of the code is written extremely cleanly. Most of the problems give standard solutions and also idiomatic ones using iter/functools. I've been programming Python for years and felt like I gained a lot from it as a developer even though I bought it to interview prep. Quick example of the "look and say" problem: def look_and_say(n: int) -> str: s = '1' for _ in range(n - 1): s = ''.join( str(len(list(group))) + key for key, group in groupby(s)) return s
  - ultrasounder 8y ago
    I am using this book for interview prep as well. Code is pythonic and a joy to read.
  - mixedmath 8y ago
    I hadn't heard of this before, so I went and checked this out this morning. I haven't read too much, but I've liked what I saw. And I notice that there are java and C++ variants for those interested in those languages. Thank you for your suggestion.
  - johntam 8y ago
    +1 for EPI. Using it now myself. It's great stuff.
- ummonk 8y ago
  A lot of imperative algorithms don't really have functional analogues. Sometimes you need to mutate in place to achieve optimal algorithmic complexity. That said, I think this might be what you're looking for: https://cs.uwaterloo.ca/~plragde/flaneries/FDS/ https://cs.uwaterloo.ca/~plragde/flaneries/FDS/
  - qwerty456127 8y ago
    > A lot of imperative algorithms don't really have functional analogues. But there are to be the ways functional programmers solve the same task? Thank you for the link.
    - disgruntledphd2 8y ago
      Definitely. But unless special care is taken, these will use (normally) more space, and potentially more time. I think Chris Osaki did a bunch of work on functional data structures for handling immutability efficiently (still less efficiently) and that some of this was implemented in Clojure.
    - ascar 8y ago
      Functional programming is not supposed to be a golden hammer. That's the pragmatic solution for this problem ;).
  - Puer 8y ago
    Nice resource, thank you for sharing. It's been a why since I've used Ocaml but this will be a good opportunity to review.
- flafla2 8y ago
  You can check out [1], which is used to teach 15-210 [2], the parallel data structures / algorithms course at CMU. The most recent version of the book is students-only it seems, on a private site (I took the course last semester), however this version is close and comprehensive. [1] http://www.parallel-algorithms-book.com http://www.parallel-algorithms-book.com [2] http://www.cs.cmu.edu/~15210 http://www.cs.cmu.edu/~15210
- scns 8y ago
  https://github.com/liuxinyu95/AlgoXY https://github.com/liuxinyu95/AlgoXY In this book the author shows brute force, improved and functional implementations in python, c and haskell.
notafraudster 8y ago
I opened 1.8.1 because I thought it'd be the first section with code and the code was not PEP-8 compliant. Having a brief scan, the authors seem to have a pretty severe aversion to putting spaces after commas, which is a bummer because it really impacts code readability. It's inconsistent even from line to line, so it's not a style thing. They're also inconsistent about using single and double quotes for strings. I skipped ahead to "implementing a stack in python", which is a little weird because the stack class they implement is just a thin wrapper around lists with append aliased to push and "self.items[len(self.items)-1]" aliased to peek (note: in python you can just use negative indexing to access items near the end of a list) This might seem pedantic, but, like, if the book isn't leveraging Python and it's not particularly clean code then I don't really understand what's on offer here.
- all_factz 8y ago
  I don't think that's fair. I thought the discussion of AVL trees was quite readable. The code is basic and straightforward, and that's what you want for something like that. It's about the algorithms, not about being pythonic -- it's about fundamentals. For that, this seems good to me (though I'll admit I haven't read a lot of it yet.)
  - Rainymood 8y ago
    "I don't want to read something because I don't like the writing style." I personally can get behind that argument. As an author you have to incentivize the reader to engage with what you've written, that's the job of the writer, not the reader. If you, in this way, alienate some users (like the one you replied to) so be it, this is also a choice of the author. I personally can't read `def fun(a,b): ...`, I strongly prefer `def fun(a, b): ...` and hence I stopped reading as well.
    - kkarakk 8y ago
      the amazon comment section for any technical books are littered with comments like yours(and i have declined to purchase books based on these comments).
djaychela 8y ago
Previous discussion (March 2017, with link dated 2015): https://news.ycombinator.com/item?id=13854087 https://news.ycombinator.com/item?id=13854087
monk_e_boy 8y ago
Sweet! That covers a lot of what I'm about to teach :)
jammygit 8y ago
In school I was quite confused about how merge sorts worked until I got a deck of cards and walked through the algorithm a few times. This site made it dead simple though. If only I'd had it instead of my textbook
raymondh 8y ago
Ironically, the provided implementations for Queue and Deque are algorithmically terrible, giving O(n) performance for operations that should be O(1). Queue and Deque could easily be developed from first principles by building on dictionaries or linked lists. It was a mistake to use list operations like s.pop(0) and s.insert(0, x).
easythings 8y ago
Hey, here the some key points to know about algorithms, machine learning and python. Just check it out https://www.easythings.xyz/2018/07/machine-learning-algorithms-develop-sounds.html https://www.easythings.xyz/2018/07/machine-learning-algorith...

294 points by samrohn 8y ago

and for beginners to programming and Python, the same site provides this excellent course: https://interactivepython.org/runestone/static/thinkcspy/index.html https://interactivepython.org/runestone/static/thinkcspy/ind...

qwerty456127 8y ago

Is there an alike book that would provide functional implementations of the algorithms alongside or instead of imperative ones? In Python preferably but I don't mind any other language. I would like to learn implementing algorithms and solving problems the functional way.

Puer 8y ago
Elements of Programming Interviews in Python is excellent imo. The authors give a crash course in all of the data structures and all of the code is written extremely cleanly. Most of the problems give standard solutions and also idiomatic ones using iter/functools. I've been programming Python for years and felt like I gained a lot from it as a developer even though I bought it to interview prep. Quick example of the "look and say" problem: def look_and_say(n: int) -> str: s = '1' for _ in range(n - 1): s = ''.join( str(len(list(group))) + key for key, group in groupby(s)) return s
- ultrasounder 8y ago
  I am using this book for interview prep as well. Code is pythonic and a joy to read.
- mixedmath 8y ago
  I hadn't heard of this before, so I went and checked this out this morning. I haven't read too much, but I've liked what I saw. And I notice that there are java and C++ variants for those interested in those languages. Thank you for your suggestion.
- johntam 8y ago
  +1 for EPI. Using it now myself. It's great stuff.
ummonk 8y ago
A lot of imperative algorithms don't really have functional analogues. Sometimes you need to mutate in place to achieve optimal algorithmic complexity. That said, I think this might be what you're looking for: https://cs.uwaterloo.ca/~plragde/flaneries/FDS/ https://cs.uwaterloo.ca/~plragde/flaneries/FDS/
- qwerty456127 8y ago
  > A lot of imperative algorithms don't really have functional analogues. But there are to be the ways functional programmers solve the same task? Thank you for the link.
  - disgruntledphd2 8y ago
    Definitely. But unless special care is taken, these will use (normally) more space, and potentially more time. I think Chris Osaki did a bunch of work on functional data structures for handling immutability efficiently (still less efficiently) and that some of this was implemented in Clojure.
  - ascar 8y ago
    Functional programming is not supposed to be a golden hammer. That's the pragmatic solution for this problem ;).
- Puer 8y ago
  Nice resource, thank you for sharing. It's been a why since I've used Ocaml but this will be a good opportunity to review.
flafla2 8y ago
You can check out [1], which is used to teach 15-210 [2], the parallel data structures / algorithms course at CMU. The most recent version of the book is students-only it seems, on a private site (I took the course last semester), however this version is close and comprehensive. [1] http://www.parallel-algorithms-book.com http://www.parallel-algorithms-book.com [2] http://www.cs.cmu.edu/~15210 http://www.cs.cmu.edu/~15210
scns 8y ago
https://github.com/liuxinyu95/AlgoXY https://github.com/liuxinyu95/AlgoXY In this book the author shows brute force, improved and functional implementations in python, c and haskell.

notafraudster 8y ago

I opened 1.8.1 because I thought it'd be the first section with code and the code was not PEP-8 compliant. Having a brief scan, the authors seem to have a pretty severe aversion to putting spaces after commas, which is a bummer because it really impacts code readability. It's inconsistent even from line to line, so it's not a style thing. They're also inconsistent about using single and double quotes for strings. I skipped ahead to "implementing a stack in python", which is a little weird because the stack class they implement is just a thin wrapper around lists with append aliased to push and "self.items[len(self.items)-1]" aliased to peek (note: in python you can just use negative indexing to access items near the end of a list) This might seem pedantic, but, like, if the book isn't leveraging Python and it's not particularly clean code then I don't really understand what's on offer here.

all_factz 8y ago
I don't think that's fair. I thought the discussion of AVL trees was quite readable. The code is basic and straightforward, and that's what you want for something like that. It's about the algorithms, not about being pythonic -- it's about fundamentals. For that, this seems good to me (though I'll admit I haven't read a lot of it yet.)
- Rainymood 8y ago
  "I don't want to read something because I don't like the writing style." I personally can get behind that argument. As an author you have to incentivize the reader to engage with what you've written, that's the job of the writer, not the reader. If you, in this way, alienate some users (like the one you replied to) so be it, this is also a choice of the author. I personally can't read `def fun(a,b): ...`, I strongly prefer `def fun(a, b): ...` and hence I stopped reading as well.
  - kkarakk 8y ago
    the amazon comment section for any technical books are littered with comments like yours(and i have declined to purchase books based on these comments).

djaychela 8y ago

Previous discussion (March 2017, with link dated 2015): https://news.ycombinator.com/item?id=13854087 https://news.ycombinator.com/item?id=13854087

monk_e_boy 8y ago

Sweet! That covers a lot of what I'm about to teach :)

jammygit 8y ago

In school I was quite confused about how merge sorts worked until I got a deck of cards and walked through the algorithm a few times. This site made it dead simple though. If only I'd had it instead of my textbook

raymondh 8y ago

Ironically, the provided implementations for Queue and Deque are algorithmically terrible, giving O(n) performance for operations that should be O(1). Queue and Deque could easily be developed from first principles by building on dictionaries or linked lists. It was a mistake to use list operations like s.pop(0) and s.insert(0, x).

easythings 8y ago

Hey, here the some key points to know about algorithms, machine learning and python. Just check it out https://www.easythings.xyz/2018/07/machine-learning-algorithms-develop-sounds.html https://www.easythings.xyz/2018/07/machine-learning-algorith...