Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Dynamic Progamming: First Principles

flawlessrhetoric.com

Post reply on HN
Print view View original

91–100 of 102 posts

Re: Dynamic Progamming: First Principles

#91

Post by megaman22 »

Bromskloss wrote: post #39
megaman22 wrote: post #34

Earlier quoted context omitted.

Same. Probably the worst class I ever took was my algorithms and data structures class. I swear the professor transcribed most of CLRS onto the blackboard over 10 weeks verbatim, and we never so much as touched a keyboard.

Is paper programming in pseudocode bad, though? I mean, computing science is not about computers, and all that.

I'm not sure it is an awful format for some people, but it sure didn't work for me.

I mean, I ended up implementing most of the problem sets in Python anyway - then had to transpile them into the bizarre undocumented form of pseudocode that was apparently the only thing the instructor and TAs could understand.

Combined with the complete lack of value added by the in-class lectures, compared to just reading the textbook, and the draconian attendance policy, it was far and away the worst class I endured in college. Particularly galling for a subject so central to the course of study and one that had material that could be so interesting if handled differently.

Re: Dynamic Progamming: First Principles

#92

Post by smitherfield »

cdax wrote: post #62
misja111 wrote: post #58

> Tail recursion [3], a variant of traditional recursion implements memoisation, which uses memoisation very economically. I don't understand this part, can anybody explain?

In "traditional" recursion, each recursive call is pushed onto the function call stack. This means that your recursive solution will eventually run out of memory when the number of recursive calls is more than what the function call stack can handle. e.g., consider the following recursive solution for calculating the sum of all positive integers up to a given `n`: fn sum(n): if n == 0: return 0 else: return n + sum(n…

NB: Although the ES6 spec requires TCO, it turned out to present significant implementation challenges, so it's only implemented in WebKit (Safari), and is, IIRC, marked WONTFIX in V8 (Chrome, Node), SpiderMonkey (Firefox) and Chakra (Edge). There's a good chance it'll get removed from a later edition of the standard.

Re: Dynamic Progamming: First Principles

#93

Post by jjaredsimpson »

TuringTest wrote: post #73
quotemstr wrote: post #69

Earlier quoted context omitted.

What precise meaning does "memorize" denote that "memorize" wouldn't? Sometimes jargon is just jargon.

"Memoization" is only used in the context of caching results of previous function calls. So if you see the word, you instantly know that this is the context. You wouldn't know that if you see "memorization".

Exactly. Memorization is the process of committing something to memory. Things like spaced repetition, flashcards, using mnemonics, etc. Memoization is the technique of caching expensive function calls and returning those cached values upon subsequent invocations.

Seeing the word memorize implies a process that an actor is undergoing and says nothing about the data being memorized. Seeing the word memoize implies the existence of an expensive function and implies a process of repeated calls to the function. It also implies the function is pure, i.e. you can't memoize calls to fread().

Re: Dynamic Progamming: First Principles

#94

Post by barrkel »

beardbandit wrote: post #26
baddox wrote: post #15

Earlier quoted context omitted.

It’s odd that there would be algorithms classes that don’t require some implementations.

When I took Algorithms II in college at a top 10 CS program, our entire class involved ZERO coding or programming of any sort.

I had to reproduce quicksort or binary search (I don't recall which) by hand, on pen and paper, in an exam :)

Re: Dynamic Progamming: First Principles

#95

Post by khedoros1 »

quotemstr wrote: post #69
Retra wrote: post #53

Earlier quoted context omitted.

Obscure words are very well suited to esoteric subject matter where precision is needed. A particular brand of function optimization is exactly that.

What precise meaning does "memorize" denote that "memorize" wouldn't? Sometimes jargon is just jargon.

I think of memoization in terms of memos. You're leaving memos behind to avoid recalculating, but you're going to throw them out when you have your result; it's scratch paper to refer back to your previous work. The word itself denotes the reason for storing the data.

Memorization makes me think of a repetitive process of committing something permanently to memory.

Re: Dynamic Progamming: First Principles

#96

Post by mlevental »

psykotic wrote: post #54

I'm fond of this old RAND report from Dreyfus, which is worth skimming if you're mathematically inclined: Dynamic Programming and the Calculus of Variations, https://www.rand.org/content/dam/rand/pubs/reports/2006/R441... One important takeaway is that dynamic programming in the Bellman formulation is a discrete analogue of Hamilton-Jacobi theory in how it writes down an equation for the optimal value as a function o…

understand basically all of you've said here except this:

>The relationship between Hamilton-Jacobi and Euler-Lagrange is the classical version of wave-particle duality.

in what sense are two formalisms (hamiltonian and lagrange) related to the relationship between time and freq space for fourier solutions to pdes?

also holy shit i would pay pretty good money for a service that typeset these old monographs using latex.

Re: Dynamic Progamming: First Principles

#97

Post by kbenson »

mlevental wrote: post #96
psykotic wrote: post #54

I'm fond of this old RAND report from Dreyfus, which is worth skimming if you're mathematically inclined: Dynamic Programming and the Calculus of Variations, https://www.rand.org/content/dam/rand/pubs/reports/2006/R441... One important takeaway is that dynamic programming in the Bellman formulation is a discrete analogue of Hamilton-Jacobi theory in how it writes down an equation for the optimal value as a function o…

understand basically all of you've said here except this: >The relationship between Hamilton-Jacobi and Euler-Lagrange is the classical version of wave-particle duality. in what sense are two formalisms (hamiltonian and lagrange) related to the relationship between time and freq space for fourier solutions to pdes? also holy shit i would pay pretty good money for a service that typeset these old monographs using late…

Seems like in a world where there's on-demand photoshop editing through a gig economy, something like this should be feasible, if not already exist. Maybe a separate cost per page for text, diagram or both, and a system to pay other people to review pages for correctness (mechanical turk style, or just actually use mechanical turk), and you have a nifty way to update old scanned documents while helping put food on some poor grad student's table.

Re: Dynamic Progamming: First Principles

#98

Post by kbenson »

jjaredsimpson wrote: post #93
TuringTest wrote: post #73

Earlier quoted context omitted.

"Memoization" is only used in the context of caching results of previous function calls. So if you see the word, you instantly know that this is the context. You wouldn't know that if you see "memorization".

Exactly. Memorization is the process of committing something to memory. Things like spaced repetition, flashcards, using mnemonics, etc. Memoization is the technique of caching expensive function calls and returning those cached values upon subsequent invocations. Seeing the word memorize implies a process that an actor is undergoing and says nothing about the data being memorized. Seeing the word memoize implies the…

Memoization implies caching specifically, which implies its own things, such as cache size and eviction methodology. Not something that's necessarily thought of when using the term "memory".

Memoization is close enough to "memorization" that you pretty much know what it is without having heard of it before and easily rememberable, while being specific enough to the actual concept as to be easily searchable and imply specific concerns of its own. That's a win-win in my book.

Re: Dynamic Progamming: First Principles

#99

Post by lemming »

kbenson wrote: post #98
jjaredsimpson wrote: post #93

Earlier quoted context omitted.

Exactly. Memorization is the process of committing something to memory. Things like spaced repetition, flashcards, using mnemonics, etc. Memoization is the technique of caching expensive function calls and returning those cached values upon subsequent invocations. Seeing the word memorize implies a process that an actor is undergoing and says nothing about the data being memorized. Seeing the word memoize implies the…

Memoization implies caching specifically, which implies its own things, such as cache size and eviction methodology. Not something that's necessarily thought of when using the term "memory". Memoization is close enough to "memorization" that you pretty much know what it is without having heard of it before and easily rememberable, while being specific enough to the actual concept as to be easily searchable and imply…

Sadly, the older I get the more I am aware of my memory's aggressive cache eviction policy.

Re: Dynamic Progamming: First Principles

#100

Post by kbenson »

lemming wrote: post #99
kbenson wrote: post #98

Earlier quoted context omitted.

Memoization implies caching specifically, which implies its own things, such as cache size and eviction methodology. Not something that's necessarily thought of when using the term "memory". Memoization is close enough to "memorization" that you pretty much know what it is without having heard of it before and easily rememberable, while being specific enough to the actual concept as to be easily searchable and imply…

Sadly, the older I get the more I am aware of my memory's aggressive cache eviction policy.

You and me both. :

But that's part of it, you generally don't really associate that with memory until you get older...

Post reply on HN