4.1, due on October 9

Something that confused me was the difference between an optimal value and an optimizer. Remark 4.1.2 discusses that difference, but I'm at a loss for what those actually are.

The example about Fibonacci numbers was really interesting, because I've build Fibonacci number generators in Python and Java but they always take forever for large inputs. But implementing the algorithm with memoization makes it work very quickly! It's a neat idea. In regards to the issue with spatial complexity, I feel like the high memory cost can be mitigated by working iteratively and deleting previous results. Of course, this wouldn't be effective if the program needed to run multiple times and wanted temporal savings after running multiple times. But this way the spatial complexity is constant because it only needs a variable to store the current n-value and two variables for the current Fibonacci number values. Also, the program could store just the results and the previous values (n and n-1) each time, which would act as a bookmark so the program could skip to it and then move backward or forward in Fibonacci values. I feel like a program like this would have spatial complexity of O(1) and temporal complexity of at most O(n) but very often lower than that.

OK, so I just read the subsection on bottom-up approaches. This algorithm is equivalent to that one, plus the bookmarking idea to reduce temporal complexity after running several times.

Comments

Post a Comment

Popular posts from this blog

8.7, due on December 11

I see the graphs of the Daubechies db2 scaling function, but I really don't understand how to use it since there's no definition that I can easily look at. We'll need to talk about that in class in order for me to understand it. Also, the proof for 8.7.5(iv) was long and I couldn't follow the algebra very well. The idea that you can use any version of the wavelets you want to reproduce the function you're looking at is very powerful. It's interesting to see such a complicated function like the Daubechies function be used. I'd like to know more about how to choose a function that works well for different types of data.
Read more

Finals preparation, due on December 13

The most important things I learned in this course were big-Oh notation, the Master Theorem, the various algorithm styles available, and probability theory. To review for the test I'll make a list of important theorems and definitions to memorize, and practice proving simple facts about each of them. I'll also go over past tests and make sure I could get 100% on them. In class tomorrow I'd like to go over an example of Monte Carlo integration. I feel like in this class I've learned how to apply the mathematics I've learned to real-world problems, more than in any other class I've taken. I feel that way because I'm most interested in using computers to solve problems, and the principles we've talked about this semester have been foundational to my understanding of how to do that.
Read more

8.4, due on December 4

Now I know what antialiasing is in computer graphics! It makes so much sense now. It's cool to see how something as simple as the Nyquist value can tell you so much about the parameters of a given problem. The methods for antialiasing are intuitive as well, kind of in the same way as least-square solutions were in Volume 1. It would be nice to get some intuition for why the Nyquist rate is twice the Nyquist value, and why the function becomes uniquely determined at that point and not before. Also, I'd like to run through a full example in class of how we can sample from a function, find the DFS, and perform ant-aliasing. That would help me understand the process a little better than before.
Read more