• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Jeanne Boyarsky
  • Ron McLeod
  • Tim Cooke
Sheriffs:
  • Devaka Cooray
  • paul wheaton
  • Mark Herschberg
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Stephan van Hulst
  • Frits Walraven
  • Jj Roberts
Bartenders:
  • Carey Brown
  • salvin francis
  • Piet Souris

Algorithmic Thinking - A story and a question (or two)

 
Ranch Hand
Posts: 158
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
When I was in college (at Georgia Tech - Go Jackets!) the language of choice for all but one of my CS classes was Pascal. Yes, I'm old!
I remember one professor, who seemed irritated that he was required to teach lowly undergrads, going over a fairly complex algorithm for a homework
problem in class. At the very end, he said "Well, you can't do this step - he pointed to a line - in Pascal, so I'm not sure what you're going to do". That's my funny story.

Now a question. GT required 2 classes of computing theory, purely on algorithms and also how to make algorithms more efficient (a lot of time on sorting) so they'd
compute in O(n) vs. O(log n). Does the Algorithmic Thinking book go into this kind of detail? Also, perhaps the pros/cons of B-trees vs. B+-trees?

Just the title of this book brings back many memories of a lot of late nights.

Thanks!
 
Marshal
Posts: 72059
312
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Lanny Gilbert wrote:. . . compute in O(n) vs. O(log n). . . .

Those numbers seem very optimistic for sorting; did you mean nlogn(n) as opposed to n²?
 
Lanny Gilbert
Ranch Hand
Posts: 158
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You're right! I was just mentioning that we talked a lot about sorting *and* a lot about O(n) vs. O(log n), not that - as a 2nd year undergrad - I could write a sort in anything less than N(log n).  
 
Campbell Ritchie
Marshal
Posts: 72059
312
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Have you found anybody else who can write a sort algorithm simpler than big‑O(nlog(n))?
 
Lanny Gilbert
Ranch Hand
Posts: 158
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Not as such...  
 
Author
Posts: 34
3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Lanny and all,

Oh shoot I'm old too, then. I used Pascal too in my college courses. I liked using it. So many old DOS and BBS games were written using Turbo Pascal. I wonder who uses it these days.

":
compute in O(n) vs. O(log n)
:"

Dan: that's the book in a nutshell. How do we make our code faster?

One thing I do a lot of in the book is work through solutions that are too slow. I can picture some readers being like, "Dan, come on, I know this isn't going to work... just jump to the super slick solution already!". But I really wanted to make sure that the readers were motivated to learn this new material. I feel like some books just start throwing fancy stuff around without first trying to convince/show the reader that less sophisticated techniques won't work.

So yeah, I blew my page limit estimate out of the water, but, I don't know, there are enough books out there that (at least to me) move very quickly. I hope I've managed to slow things down (I mean, my exposition, not the code...) and let new people in.

Thank you,
Dan
 
Lanny Gilbert
Ranch Hand
Posts: 158
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks for the reply, Daniel! Looks like this book is right up my alley. "Throwing fancy stuff around" seems to be the mantra of many computing books these days. Nice to see someone starting slow and building up, using
time-tested computer science techniques, to the best solution. NICE!
 
Campbell Ritchie
Marshal
Posts: 72059
312
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
You also don't want to move too fast for readers to keep up with you. I presume your exercises have that effect. Once you have got the exercise to work, you have taken the time to work through the theory.
 
Daniel Zingaro
Author
Posts: 34
3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Lanny Gilbert wrote:Thanks for the reply, Daniel! Looks like this book is right up my alley. "Throwing fancy stuff around" seems to be the mantra of many computing books these days. Nice to see someone starting slow and building up, using
time-tested computer science techniques, to the best solution. NICE!



Thank you! This is one of the reasons I used programming judges in the book. If the judge tells you that the code is too slow, well, we have to do better.

There are more topics that I teach in my algorithms courses, like maximum flows, that I'd love to cover in a similar way, but I haven't figured out exactly how yet. Maybe one day...

Dan


 
Daniel Zingaro
Author
Posts: 34
3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Campbell Ritchie wrote:You also don't want to move too fast for readers to keep up with you. I presume your exercises have that effect. Once you have got the exercise to work, you have taken the time to work through the theory.



That's the goal exactly. The reader gets hit with a problem that they can't quite solve yet -- they need a new technique. Now we can learn that new technique in the context of solving that problem.

At some point we need to generalize from solving a single problem to understanding the technique at large, so I do that after solving the first problem in each chapter. It's like, "OK, we just solved a problem, now let's zoom out and understand exactly what we did".

Then we solve more problems for the remainder of the chapter.

One thing I wasn't able to fit in here is a final chapter that poses problems that could use any approach that was taught in the book. Currently, the reader knows that the second and third problems in each chapter are going to be solved using the same technique as the first problem. That's great for practice and solidifying things. But this new final chapter idea would force readers to confront all of the material all over again in order to discover which of it to use. Ehhh, well, at least I'm not lacking for future writing ideas?

Thank you,
Dan
 
reply
    Bookmark Topic Watch Topic
  • New Topic