2012S004
From CDS 130
WELCOME TO THE HOMEPAGE FOR CDS-130/004 (SPRING 2012)! THIS CLASS MET MONDAYS AND WEDNESDAYS DURING THE SPRING 2012 SEMESTER, FROM 10:30AM--11:45AM IN INNOVATION HALL, ROOM 223. THIS PAGE WAS USED TO PROVIDE STUDENTS WITH A RUNNING COMMENTARY OF EACH CLASS MEETING: WHAT WE COVERED AND SOME OF THE FINER POINTS THAT EMERGED FROM CLASS DISCUSSION. THE DETAILED, DAY-TO-DAY TOPICAL SYLLABUS WAS FOUND IN THE CLASS ONE FOLDER ON BLACKBOARD. THAT SYLLABUS WAS UPDATED CONSTANTLY AND THUS ALWAYS REFLECTED WHAT WAS COVERED AND WHAT WAS COMING NEXT.
THANK YOU ALL FOR A WONDERFUL SEMESTER!
1. CDS-130/04 (SPRING 2012): ANNOUNCEMENTS
1.1. 11 MAY 2012: CDS-130/04 FINAL COURSE GRADE DISTRIBUTION
- Here's the OFFICIAL, final course grade distribution for CDS-130/04 Spring 2012:
- A+, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, B, B, B, B, B, B, B, B, B, C+, C+, C, C, C, C, C, F, F, F, F, F, F
- (see graphic on right)
1.2. 2 MAY 2012 (Class 28)
- Well, this was it, the last CDS-130/04 class of the Spring 2012 semester! Today we heard a lecture from Professor Juan Cebral from the School of Physics, Astronomy and Computational Sciences. That presentation addressed a highly relevant and timely topic, Computational Medicine -- the numerical modeling and simulation of patient-specific physiologies, for the dual purposes of improved diagnoses and treatments. It's a particularly timely topic because computational medicine has direct relevance to today's ongoing healthcare debate: complementing traditional medical practice with computational medicine enables doctors can offer improved care at lower costs. Doing so leads directly to enhanced outcomes for their patients.
- Professor Cebral's specific area of study is hemodynamics -- the simulation of blood flows in the human body -- and even more specifically, the hemodynamics associated with the growth, detection and treatment of brain aneurysms. He's a widely recognized expert in this field and has many scholarly publications to his credit. His presentation is available on Blackboard.
- Following the presentation, we spent the final minutes of the semester readying homework #10 for submission. Both hard copies and soft copies were due at the end of class today.
- I want to thank everyone for a wonderful semester! You've been a superb class, and I wish all of you much success in your respective futures!
- Our final exam will occur on 9 May 2012, in the same room as our classroom (Innovation Hall, room 223). It will begin at 10:30am and conclude at 1:15pm. Detailed study advice for the final exam will be distributed shortly.
1.3. 30 APRIL 2012 (Class 27)
- At long last we come to the summit: Numerical integration, as discussed in the Numerical Integration presentation found on Blackboard!
- I've advertised numerical integration as the "mathematical jack hammer", and it is that. Numerical integration (also called quadrature) enables us to power through some pretty complex and analytically mystifying integrations. We can get good, precise, convergent results. That said, it's not a panacea and must be handled with care. So we will.
- The particular quadrature technique we discussed was the trapezoid method. It's relatively simple, and just requires us to know how to compute the area of a trapezoid (luckily, I had that formula available!) Then, it's a matter of decreasing the size of a trapezoid and "tiling" a bunch of them under the curve of interest, to compute the area under that curve. That computation was the specific application we considered for numerical integration (although there are many, many others). It's not a difficult computation, but it requires bookkeeping. That said, the Matlab code to do the computation was short! Very concise. Very understandable. Furthermore, the method is GENERAL, meaning that it can be applied to compute the area under other curves, too!
- We won't use numerical integration specifically in any of our programming projects. But it is certainly useful to know -- and, because it will make an appearance on the final exam! Numerical integration is just one example of a vast number of numerical methods. These methods, the product of a branch of applied mathematics called numerical analysis, are tools (algorithms) used daily by computational scientists everywhere. Many of these algorithms are highly accurate and very stable. Using them, computational mathematicians and scientists can produce simulations of highly complex physical phenomena. Some of these phenomena will be discussed in the next lecture -- the last of the semester -- that will be delivered by Professor Juan Cebral.
1.4. 25 APRIL 2012 (Class 26)
- Bugs, bugs, bugs! As programmers, we hate 'em! But they're a fact of programming life. So today we considered some debugging techniques (some of which may come in handy as you complete homework #10).
- There are generally two types of bugs: syntax bugs and logic bugs. Of these two, syntax bugs are by far the easier to catch and to remedy. That's because our programming environment (be it Matlab, another integrated development environment, or perhaps just a good compiler) usually does a lot of work for us by identifying the syntax bug in the first place -- or at least identifying the general vicinity where it occurs. Then it's up to us to fix the bug. For syntax bugs this is usually a routine correction. Aggravating, but routine.
- Logic bugs, on the other hand, are insidious creatures. Often times they escape initial detection: These bugs are usually always embedded inside PERFECT SYNTAX! That means that Matlab usually won't catch them up front, nor will your favorite compiler. All will seem well...all will seem calm...and then...
- POW!!
- The first, normal reaction is, "What???" The second, normal reaction is, "The computer messed up..."
- Let me assure you: IT'S NOT THE COMPUTER -- IT'S YOUR CODE! Yep! That unexpected, incorrect output you're experiencing results from a LOGIC BUG in your code. Somehow, the logic you used to write a statement or series of statements in your program, is now going haywire and producing that unexpected and incorrect output [1].
- What to do? First remain calm. There's no sense in getting worked up because "the computer won't do what it's supposed to do..." The computer is doing EXACTLY what you told it to do! The thing is, you didn't tell it to do the correct thing!
- Now comes the hard part: Tracing the logic that produced the incorrect result. There's no formula for this. Rather, eliminating logic bugs is an art that requires you to understand WHAT you are trying to compute. If you do not (for example, if you're using someone else's code...Hmmm...) then you have almost no chance to swat that logic bug. Precisely because you didn't write the code. So you therefore have little (if any) understanding of how it works, or how it produced its output.
- On the other hand, if you did write your own code, then you have a pretty thorough understanding of how it works. So now it's time to WORK BACKWARDS from the output: Work through the steps that led to that result, tracing all output (internal and external) backward to the function or functions that produced it. Then, trace the internals of the function -- how does it operate? How does it handle the input it receives, to compute the (incorrect) output it produces? By working backward in this way, you have a fighting chance to discover and eliminate the logic bug. It's hard work!
- Logic bugs are evil and insidious because sometimes they lay dormant -- sometimes for years -- and do not manifest immediately. Rather, they "wait" until the right combination of inputs appears. That's when they rear their ugly head. And when they do, it's always at the most inopportune time.
- Logic bugs usually creep into lengthy programs (i.e., pages and pages of source code). Since we're not writing particularly long programs, logic bugs will probably not appear regularly in what we do (syntax bugs, on the other hand, will probably make daily appearances!). That said...we did discuss some "programming pearls", one of which contained a phenomenally destructive logic bug in a rather short program. So please be careful!
- Finally, the last exam extra credit quiz was delivered in class today, during the final 25 minutes of class.
- [1] Hmmmm...how do I know if my program's output is unexpected and/or incorrect? Well, that takes just a bit of intuition on your part. For example, if you're computing an ending bank account balance after a series of modestly sized deposits and withdrawals over, say, 25 years, and, if the computed ending account balance is equal to 2x10^30 dollars...well then...it's time to take a look at what your code is doing. Why? Because 2x10^30 dollars is more than 2x10^19 times richer than the richest person on planet Earth! In fact, if you had a dollar for every kilogram of mass of the Sun, you'd have about 2x10^30 dollars. So an ending balance of 2x10^30 dollars just isn't reasonable. Not by a long shot. A logic bug must therefore be at work somewhere in your code...
1.5. 23 APRIL 2012 (Class 25)
- The presentation entitled, Introduction to Modeling, IV (Systems of Equations -- version 2), was our focus today.
- Previously, in all our population equation modeling, we considered only non-interacting populations: dogs and cats living peacefully together, rabbits and foxes co-existing side-by-side, etc. There were no interactions between them -- of any kind.
- That changed today. For the first time we considered what happens when one population's emigrants (those exiting) become another population's immigrants (those entering). These exchanges provided us with new dynamics to consider, precisely because the populations are now coupled: What occurs in one population affects directly what occurs in another population.
- The mathematics aren't difficult: Our good 'ole population equation remains the same. We just simply apply the standard emigrant/immigrant corrections, being careful to apply the same correction to two different populations, but with different signs (negative for emigrants, positive for immigrants).
- Do these situations occur in real life? You bet! Examples include radioactive decay, and unimolecular chemical reactions, and we looked at both. The cool thing here is that your modeling capability just EXPANDED: Think of all the new situations you can cope with now. Let's say you work at the EPA, and want to model the environmental persistence of chemicals from a particular, historical spill accident that occurred 10 years ago. Now you can do that! All you need to know is the degradation chain for that chemical (which species decay into which other ones), and the associated decay constants, and you're good to go. Same with unimolecular chemical reaction networks: Once you know the chemical kinetic pathway and estimates of the kinetic parameters, you can generate an estimate of the time dependent chemistry.
- Actually, it's time to reassess what we've studied and the new modeling capabilities we have as a result. We've now simulated numerically all sorts of interesting situations: bank accounts and other financial instruments with variable interest rates, deposits, withdrawals and parallel accounts; economic valuations for financial business planning; growth and death of populations in the wild featuring unusual events (like wars, diseases and other afflictions endured by populations everywhere); periodic events; immigrants and emigrants. Hmmmmm...I'd say you've built up quite a nice portfolio of modeling capability there! Some of these problems are very complex to solve analytically. But now YOU have some cool tools, and as a result, can engage these problem types with confidence!
1.6. 18 APRIL 2012 (Class 24)
- Today was all about functions in Matlab and so, we worked with the Introduction to Matlab presentation found in the Matlab folder on Blackboard.
- Functions are useful constructs, and promote modular programming. Functions are also necessary constructs for us, since homework #9 uses a specially written function called "stats.m". Homework #9 is comprised of a single exercise found in Problem Set 9.6 (Parametric Study of Wheatfield Annual Harvest Yields -- version 2), which is found in the Homework Assignments folder on Blackboard. This problem requires you to run the Matlab code "wheatfield4.m", which in turn depends upon "stats.m" . PLEASE ENSURE THAT BOTH "wheatfield4.m" and "stats.m" are located in the SAME directory when you run "wheatfield4.m"!
- Using functions, programmers can encapsulate program components and isolate them from one another. That's modular programming. This programming style is useful for a number of reasons, among them: (1) Code re-use; and (2) Debugging.
- Code reuse is another way of saying, "Don't reinvent the wheel." In scientific programming, for example, heavy use is made of the venerable BLAS and LAPACK software libraries. These are collections of linear algebra programs (functions) that enable programmers to access efficient, well-tested, very accurate and highly stable linear algorithms -- for use in their own programs. That is, programmers don't have to spend time and energy re-inventing the wheel by writing and then debugging algorithms that duplicate the functionality already contained in BLAS and LAPACK. The modules are already available.
- Code debugging is supported by modular programming precisely because modular programming isolates program functionality into discrete units. So, if your program isn't producing a correct result, tracing the source of the difficulty is (usually) easier in these types of programs: You (usually) can discover at least the module where the error occurs, and thus focus your detective work in it.
- Finally, modular programming promotes teamwork. Modern software development is a highly complex activity. Large software projects are always decomposed into smaller pieces. Each piece is usually handled by one programmer, and the collective efforts of several programmers are "integrated" together into a working whole. Modular programming supports this "problem decomposition" because each programming "piece" usually represents a separate component of overall program functionality (i.e., a module).
- So modular programming is a good thing! That said, none of the Matlab programs we'll write will be large enough to exploit the benefits of modular programming style. But it's important that you become aware of it, simply because this is how modern software development is actually done.
1.7. 16 APRIL 2012 (Class 23)
- In the front part of today's class I returned the graded homework extra credit quiz we took on last Thursday, and we worked out some of the problems it contained.
- We also reviewed again that (occasionally) dangerous Matlab construction called a WHILE loop. Remember WHILE loops, from 2 April? These constructions contain features of both FOR loops and IF statements. The tricky thing, though, is that a WHILE loop's action is controlled by a conditional statement. If that conditional statement never "hits" (that is, never evaluates FALSE), then the WHILE loop continues iterating forever...an infinite loop situation! Sometimes infinite loops are desirable but most of the time they aren't. If you happen to find yourself trapped in infinite loop limbo -- which you'll recognize because the computer will become very sluggish, and you'll see a perpetual "BUSY" notification in the lower left corner of the Matlab screen -- the way out is to hit CRTL-C ("control-C") a couple of times. When you do, make sure that your cursor is positioned in Matlab's command window and not in the editor. Matlab should respond in a few seconds by unwinding itself from the infinite loop. Then you'll be ready to go again. My recommendation: Go back to your code and figure out what caused the infinite loop. Remember: A WHILE statement continues on forever if its conditional statement never evaluates to FALSE. So, an infinite loop happens when the conditional is prevented from evaluating to FALSE. What, in your code, prevented that from happening? Take a good look at your conditional statement, and at its dependencies. That's a good place to begin looking for the trouble.
- The rest of the class was reserved for in-class work and questions on homework #8 and continued our discussion of homeworks #10 and #11.
1.8. 11 APRIL 2012 (Class 22)
- Today was spent studying for the third and final homework extra credit quiz, which was delivered at the end of class. We also discussed homework #10...
- Homework #10 is rather comprehensive. It brings together most of the Matlab syntax that we've learned to date (FOR loops, DNFLs, IF statements, nested IF statements, pattern detectors, etc.) and deploys that knowledge against a real-world problem: Detecting isolated black pixels inside a binary black-and-white image.
- This sort of detection is very important. One application might be "denoising" images, whereby random background fluctuations (which could manifest as isolated pixels of a different color) are removed prior to additional, downstream image processing. Another application could be finding "dead pixels" in flat panel displays.
- Homework #10 and #11 really come together as a package: In homework #10 we'll evaluate whether or not your program is concise, well written and appears to represent correct problem solution logic. In homework #11, however, we will know for sure because homework #11 is a performance test of your homework #10 algorithm. That performance test will consist of running your homework #10 program inside a test framework. The framework will present your program with a series of randomly generated binary images. Your program must count the exact number of isolated black pixels that it finds in each of these images. For each image that your program processes correctly -- that is, for each image that your program counts correctly the number of isolated black pixels in it -- you'll receive credit for one image.
- Your score on homework #11 is computed as follows: the percent of total images computed correctly multiplied by 20, to arrive at a score out of 20 possible points. Scores will be rounded to the nearest tenth point.
- Homework #11 is considered submitted when you submit homework #10; homework #10 is due at the end of class -- in BOTH hard and soft copies -- on 2 May 2012. Soft copies will be emailed to me, and your email must be time stamped no later than the end of class on 2 May.
- Now, some students naturally ask: "Is it possible to get a perfect score on homework #10 and yet get a not-so-perfect score on homework #11?" The answer is yes: It is entirely possible that what LOOKS good to me may not in fact RUN properly. Homework #11 is therefore a performance test, and, ensures that what looks good actually is good. My recommendation is therefore to TEST your homework #10 program as much as you can, prior to handing it in. That's why I wrote the Matlab script "testshell.m" for you to use. This is a small test framework that generates random binary matrices of the type I'll use when testing your program. So . . . test, test test!
- It's a particularly good idea to retest your program AFTER making changes to it. In the software industry this is called "regression testing": ensuring that your program still operates as advertised, following the most recent changes.
- During the last 25 minutes of today's class I delivered the third and final homework extra credit quiz. Remember: These quiz points are added directly to your earned homework points. Today's quiz was worth 8 points, or, 40% of an entire homework grade -- more than enough to offset a past homework "hiccup".
1.9. 9 APRIL 2012 (Class 21)
- Here we are, on the threshold of randomness! We covered the presentation entitled, Introduction to Modeling, III: Stochastic Models and Monte Carlo Methods.
- Monte Carlo Methods ... hmmmm. The very words conjure up images of glitz and gambling. In fact, the name and the method originated with mathematician Stan Ulam, and he was apparently thinking about the real Monte Carlo when he named them! Stochastic Models ... hmmmm. No equivalently exciting images jump to mind when I say "stochastic models". But in fact, Monte Carlo methods are types of stochastic models. The unifying thread is randomness.
- So we reviewed random numbers -- how to generate them and how they're distributed. That was an important sidebar because the quality of stochastic simulations is directly tied to the quality of the random numbers fed into them ("quality of random numbers", as used here, refers to whether or not the random numbers consumed by a stochastic model are really random. For our purposes, we will assume that Matlab generates pretty good random numbers).
- One modeling example that we took some time to understand, was how to calculate an estimate for the number Pi, by "throwing darts" randomly at a board that consisted of a circle inscribed inside a square. That computational experiment demonstrated convincingly (I think!) how powerful stochastic simulations can be. The specific method we used, the Monte Carlo method called "hit or miss", is a relatively inefficient computational procedure. But it's very easy to understand and thus, doesn't produce confusion. That's exactly why we studied it and not some other method.
- Extending further, we also learned how to incorporate randomness inside what appeared at first blush to be a straight deterministic simulation. In our specific case, we looked at the growth of wheat in a wheat field over time. By using random numbers, we were able to simulate the effect of variable sunshine on the wheat's growth rate and thus, on the size of the final harvest yield from that field. At first it looked like there was no insight available to us at all: After all, most of the simulations resulted in different harvest yields!
- Aha! The insight came when we ran MANY computational experiments, and then, computed descriptive statistics of the set of simulation outcomes. When we did that, what we found was that we characterized very well the average yield and standard deviation. Armed with that information, a Kansas wheat farmer or a Washington policymaker could predict the likely yield from a wheat field field (or from many wheat fields) and thus, predict the likely range of harvest yields! This is very useful information to have for planning purposes. And also if you're a commodities trader: Traders who work at the Chicago Board of Trade and the New York Mercantile Exchange pay particular attention to the vagaries of global weather -- precisely because of weather's direct impact on future commodity prices. Fortunes are won and lost on these exchanges! And weather often plays a direct role.
- We also took some time to discuss Homeworks #10 and #11. These homeworks, which were released today (but not yet assigned), are an extension of the Homework #7 pattern recognition exercise. Specifically, Homework #10 requires you to write and test "detector logic" designed to count the instances of isolated black pixels in black-and-white images. This will be a substantial Matlab program, and as such, it's due on 2 May. Students only need to complete the program to satisfy the requirements of both homeworks: Homework #10 consists of whether or not you give me an well written, operable program, and homework #11 is that program's performance test. We'll talk more about these assignments in the coming days.
- Finally, we talked about the structure of the upcoming homework extra credit quiz. This will be the third and final homework extra credit quiz of the semester. It's worth 8 points, which is 40% of one homework! So it's worth your while to study for it. On 25 April we will have our second and final exam extra credit quiz.
1.10. 4 APRIL 2012 (Class 20)
- We continued our introduction to modeling and simulation by studying a canonical example: Exponential growth and decay (aka, the "Population Equation" model), which we integrate ahead in time using Euler forward integration. We'll deal exclusively with the discrete form of the model (although we briefly reviewed the continuous form of the model, to get an idea of our equations' origin). the presentation entitled, Modeling II: Population Equation Models (version 2), contains all the details covered in this lecture.
- There's a wide variety of interesting phenomena that can be modeled with exponential growth and decay -- particularly when we include "special effects" such as immigrants, emigrants, periodic events, and special one-time events. Examples of some of these phenomena include: cyclic variation of a wolf population, economic value depreciation of a newly installed machine, growth of rabbits on an island (subject to strange diseases), dollars in a bank account, heating and cooling, and many more. The list is endless. A key feature shared by all of them, however, is a common mathematical structure. When we identify that structure, symbolize it, and reduce it to practice inside a computational framework, the result is a tool from which we hopefully can gain some insights; we "ask" the computational model some questions. This is the essence of modeling and simulation.
- One final comment: The exponential growth and decay model, as presented today, is an example of what's called a deterministic model. Roughly, this means "no random component." Output is very well defined (very well determined) for a given input. Now, you may be thinking, "If there's such a thing as a deterministic model, then is there such as thing as a 'non-deterministic' model?" The answer is a resounding yes. Non-deterministic models contain an element of randomness. Often times, that randomness is the key that enables forward progress against otherwise insoluble problems. Models that contain one or more elements of randomness are called stochastic models. We'll examine a few stochastic model specimens up close, during our next class meeting.
1.11. 2 APRIL 2012 (Class 19)
- The focus of our attention today was the presentation entitled, Introduction to Modeling, I (version 2). We have now completed our transition away from binary, arithmetic and architectural considerations. From this point forward we will focus almost exclusively on modeling and simulation, and, Matlab software development. The software we write will be aimed directly at problem solving. In other words, algorithmic thinking.
- Modeling and simulation is the result of an intellectual journey that starts with Scientific Models, reduces those to Mathematical Models, and finally, encodes these models inside a computational framework. The end result is a computational model.
- Computational models have much in common with scientific instruments: They enhance our observational and deductive capabilities, and (we hope) lead to insight. That's it -- that's what we're after. For when we gain insight, we can say that we have "solved the problem", in some sense: We learn additional information, explore new parametric territory, and form new conjectures and hypotheses. In some cases, computational modeling reveals the existence of undiscovered (or unrecognized) phenomena (c.f.: Lorenz and chaotic system dynamics). Computational modeling enables us to go where few have gone -- or cannot go -- theoretically or experimentally.
- We also learned some new (and potentially dangerous!) Matlab syntax: the WHILE loop. WHILE loops are very powerful constructions that endow the Matlab programmer with significant new capability. That said, WHILE loops require care in handling. That power comes at a price, since the result could be an infinite loop. It's important to recognize that unlike a FOR loop, which has automatic, built-in iteration control because it uses indexes, a WHILE loop instead uses a test condition -- just like an IF statement. When viewed from that optic, a WHILE loop can be seen as a cross between a FOR loop and an IF statement. The required care arises because of that test condition: If it never becomes false, well then, the WHILE loop continues forever, and you're in for some excitement! Should that happen to you, simply hit CRTL-C a couple of times, and you should be OK.
- Finally, we talked about plots and plotting inside Matlab. This was an essential discussion because plots are how we usually present the result of computational simulations. It's what's called "visualization", and it's how humans can best interpret the masses of numbers produced by computational studies. I showed you how to construct simple plots, and gave you some shell code for doing so.
1.12. 28 MARCH 2012 (Class 18)
- Algorithms are the cornerstones of modern computational science. Cormen et al. recommend that we consider algorithms to be a class of technologies: ". . . we should consider algorithms, like computer hardware, as a technology. Total system performance depends on choosing efficient algorithms as much as on choosing fast hardware . . . Algorithms are at the core of most technologies used in contemporary computers." [1] How true! Very often, the difference between computational success (getting an insightful answer using a "reasonable" amount of resources) or failure (not getting an insightful answer -- or getting the wrong answer -- after expenditure of an inordinate amount of computational resources) boils down to the underlying algorithms.
- As it turns out, algorithms can be defined in various ways. We'll adopt Cormen's informal definition: "... an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output... An algorithm is said to be correct if, for every input instance, it halts with the correct output." [2]
- Algorithms can generally be classified into two categories: "good" and "bad". Good algorithms generally solve problems correctly in a reasonable amount of time. These algorithms execute in what's called polynomial time -- that is, the algorithm's execution time is proportional to some polynomial function of the input problem size. Bad algorithms, on the other hand, usually execute in other than polynomial time -- exponential time, for example -- meaning execution time proportional to some non-polynomial function of the input problem size. We examined both situations, using back-of-the-envelope calculations, and discovered tremendous differences in algorithm execution times for input problems of moderate size.
- Good algorithm design is an art as well as a science. Usually, good algorithms exploit some structure inherent in the problem itself. Or, sometimes they create structures that can be used to solve problems efficiently (sorting is an example of this). You might conclude that perhaps all problems can be solved by algorithms: all we have to do is come up with that good algorithm, apply it to the problem at hand, and, presto!
- But that's not necessarily true! We also examined a few examples of problems that just seem to be inherently "difficult", no matter which way we slice 'em: no matter how hard we try, these problem types resist efficient, exact solution by good algorithms (approximate solutions are a different matter, though, and as long as you're willing to accept some margin of error, exact solutions to these difficult problems can sometimes be closely approximated). These notoriously difficult problems populate a category called NP (both NP Hard and NP Complete). It's still an open research question whether any good, efficient algorithms exist that can solve NP problems. The consensus answer seems to be "no", but, that's also not yet proven to be the case. But if YOU can prove that fact, well then, fame and fortune await you, courtesy of the Clay Mathematics Institute: the P vs. NP Problem has a million dollar prize ready for you to claim!
- [1]: Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald L. and Clifford Stein, Introduction to Algorithms, 3rd Edition, MIT Press, 2009, p. 13.
- [2]: Ibid, p. 5.
1.13. 26 MARCH 2012 (Class 17)
- If you take a look in the Class 1 folder on Blackboard, you’ll see that the Course Policies presentation was updated to version 7.
- The principal changes were corrections to the homework calendar that precedes the detailed, class-by-class syllabus (it’s now up-to-date with respect to homework assign and due dates), and, the repositioning of homework #10.
- I plan to assign homework #10 on 11 April, concurrent with homework #8. Homework #10 will require you to write a larger Matlab program (more than just a few lines) to accomplish an image processing task. It will be due three weeks later, on 2 May, our last class meeting. So you’ll have three weeks to complete it instead of the normal one week.
- Associated with homework #10, but not shown explicitly on the calendar, is “homework #11”. This workproduct consists solely of a performance test of your homework #10 program. Your homework #11 score therefore depends upon how well your program performs: The idea is to insert your program into a well-defined “test harness” and present it with a large number of image processing tasks (in the software industry this is called “unit testing”). The number of tasks your program “gets right”, divided by the total number of tasks, is your program’s percent grade. Multiply that by 20, round to the nearest 0.1 point, and we have your homework #11 score out of 20 points.
- Random numbers! There's a whole class of computational simulations called stochastic simulations that depend upon randomness. So today we explored the basics of random numbers: sampling with replacement (SWR) and sampling without replacement (SWOR). There's a big difference between the two sampling methods. We also discovered that, given certain constraints on the generation of a sequence of random numbers, we should EXPECT to see certain "patterns": These "patterns" aren't really patterns at all -- just the result of normal expectation. For example, we saw that if we draw a billion integers randomly from a uniform distribution of the integers 0--9, and line them up, then we should expect to see any nine digit sequence once. Any nine digit sequence might show up more than once, or maybe not at all. But the expectation is to see it appear once. The first nine digits of pi are a good example of this phenomenon: 314159265 . Those nine digits showed up, in that exact sequence, in a string of one billion random digits. But that's expected, not magical. In fact, pick your favorite nine digit sequence. It should show up once! And yet . . . hmmmm . . . it perhaps seems a bit odd that such a well known number as pi would appear in a random sequence of integers.
- But it's not odd at all!
- We'll use randomness in an upcoming lecture when we simulate the growth of wheat in a wheatfield under conditions of varying sunshine. Although exact outcomes will very likely differ from one simulation to the next, we can draw some very interesting conclusions if we consider all simulation outcomes in the aggregate. Meaning: We can define, very well, the expected average outcome. We can also gather other useful statistical descriptions, such as the standard deviation and the variance. All this is made possible by stochastic simulations. And these simulations are defined by an element of randomness.
- We also finished our discussion of IF/ELSE/END and IF/ELSEIF/.../ELSE/END constructions today. At the end of next class we'll talk about plotting in Matlab. Producing informative graphs is essential for communicating the result of computational simulations -- it's the essence of INSIGHT. And that's the endpoint, the reason why we do computational simulations.
1.14. 21 MARCH 2012 (Class 16)
- Continuing our transition away from discussions of binary and other architectural considerations, and toward modeling . . . today we discussed the contents of the Image Processing and Pattern Recognition presentation.
- Applications of image processing abound, from digital photo retouching to medical X-ray interpretation. They very importance of image processing derives from the old adage, "A picture is worth a thousand words". Images usually contain a ton of information. Pixel patterns represent some of that information, and so pattern detection is one of the key goals of modern image processing algorithms. To detect and classify patterns correctly and without excessive error, is a holy grail requirement. That's the case precisely because often times, images come in sets and those sets contain thousands, hundreds of thousands or perhaps even millions of individual images. That's way too many to process via manual inspection. So automating some image processing tasks can be a very useful thing to do.
- We'll focus on black and white images, represented as matrices containing the values 0 or 1. To "get inside" these images, we'll use double nested FOR loops to "walk down the rows and across the columns", and test each pixel's value using a combination of IF statements. In fact, IF statements embedded inside double nested FOR loops is a programming pattern that we'll employ frequently.
- Following our excursion into image processing, we'll begin to focus on aspects of computational modeling. First up will be random numbers -- their generation and use inside Matlab. We'll follow that with in-depth examinations of several model types. Ultimately, the goal is to gain scientific insights by writing and then executing computational models of selected, real-world physical systems.
1.15. 19 MARCH 2012 (Class 15)
- Welcome back from Spring Break everyone!
- IT security, ethics and the Dark Side of Binary filled the hour today.
- IT security and ethics are essential topics that underpin many of our computer system interactions. Understanding good security practice is a fundamental IT skill, and one that helps you protect your accounts and those of others from unauthorized access.
- It all begins with strong password selection. We took a look at the consequences of strong and weak password selection, from the point of view of someone trying to guess ("crack") your password and gain access to your account. Clearly, selecting password characters from as large a subset as possible of the available ASCII characters is essential, and can lead to strong passwords if the characters are chosen randomly. Practices to avoid were also discussed, and specifically with respect to passwords, we learned that choosing a password that's found in the dictionary is definitely not a good idea.
- We also explored the more insidious insider threat to IT system security, and took a look at the practice of "social engineering". Rounding out the hour, we learned one specific way that binary concepts can be used against us: when they're used to implement a highly focused email spam campaign. The fictional campaign we studied used "spear phishing" techniques to great effect, and had a good chance of appearing legitimate to email recipients. The mechanics of how these scams work are not hard to understand and thus, they're easy to perpetrate against the unsuspecting. But, forearmed with some knowledge of how they work, and, of how victims' internal thought processes operate, we're much better positioned to recognize these email scams when we see them, and thus, not become victims ourselves.
1.16. 9 MARCH 2012
- As per GMU’s policy for lower division classes, I’ve created feedback to let you know your current status in CDS-130. In other words, I’m answering your question, "How am I doing in CDS-130 right now, at the middle of the semester, following the midterm exam?" The idea is to give you some indication of your overall performance thus far, that is, the grade you would receive IF I was issuing course grades today.
- That grade appears on Blackboard in a column entitled Current Course Grade. This column appears directly to the right of the Total Exam Grade column. The computation, according to our Class 1 Course Policies presentation, is simply this: (0.4 x Total HW Grade) + (0.6 x Total Exam Grade) = Current Course Grade.
- For example: Let’s assume you currently have an 87% for your Total Homework Grade, and a 93% for your Total Exam Grade, then your Current Course Grade is computed as follows: (0.4 x 87%) + (0.6 x 93%) = 90.6% which is an A.
- Fairly straightforward.
- Here’s the CDS-130/04 Current Course Grade distribution, following Wednesday’s midterm exam:
Current Course Grade | Number of Students |
---|---|
A+ | 1 |
A | 24 |
B+ | 1 |
B | 9 |
C+ | 2 |
C | 5 |
D | 4 |
F | 3 |
- Now, keep in mind that these current course grades can be volatile: We’ve only had four homeworks so far (eleven are planned through the end of the semester, from which I will select your ten best) and we still have the final exam to complete. So there are quite a few more workproducts waiting in the wings. That said, this "snapshot" of your current situation should prove informative.
- I’ll keep the Current Course Grade column active on Blackboard through approximately 5pm on Friday 23 March 2012, after which it will disappear. It will reappear again after your final exam.
1.17. 7 MARCH 2012 (Class 14)
- IN-CLASS MIDTERM EXAM.
1.18. 5 MARCH 2012 (Class 13)
- As advertised previously, we continued to explore Matlab syntax today. Specifically, we focused on double nested FOR loops (DNFLs) and worked through several examples in detail.
- It's essential to understand the operation of DNFLs since they are fundamental programming constructs. A well known heuristic (see here, for example) is the 90/10 rule: 90% of a program's execution time is spent in 10% of the code. Typically, that 10% involves very heavy use of loops. This is certainly the case for large computational simulations.
- We also spent some time on IF statements. We'll review these again, after everyone returns from Spring Break. Like loops, IF statements are absolutely essential programming constructs. With them, programs are endowed with decision-making capability. Our next topic, image processing, will demonstrate convincingly why a decision-making capability is crucial to the operation of a program.
- Finally: Good luck on tomorrow's midterm exam! If you require any last minute assistance to clear up lingering conceptual doubts or misunderstandings, please be sure to reach out to us. We're ready to help.
1.19. 4 MARCH 2012 (Midterm Exam Preliminary Information)
- By now everyone should have the midterm exam study advice in their possession (it was emailed and simultaneously posted to Blackboard). If that's not the case, then please let me know so I can get you a copy.
- The midterm exam will be delivered on 7 March 2012, from 10:30am through 11:45am, in room 223 of Innovation Hall. The exam will begin PROMPTLY at 10:30am. There's no waiting for late-comers. If you should find yourself arriving late, please see the assistants in the back of the room. They will give you an exam booklet and a scratch paper booklet. Then please find an open seat and begin working. You will need to finish the exam by 11:45am.
- My recommendation is to arrive early on Wednesday. Doing so will enable you to gather yourself together, collect your thoughts, and begin to focus. The room is ours at 10:20am but please feel free to enter it a bit early if the preceding class is finished.
- Focus is important on this exam. By arriving early you begin to establish your focus. To ensure that everything goes as smoothly as possible, I'll distribute the exams early. They will remain face down on your desk. At 10:30am we'll all turn them over together and begin working. I will also distribute a scratch paper booklet for your use during the exam. You must turn in BOTH your exam booklet and your scratch paper booklet to me at or before 11:45am. If you finish the exam before that time, simply come to the front and place your exam face down inside the box that will be available for that purpose. Place your scratch paper booklet face down on top of your exam.
- PLEASE, PLEASE, PLEASE: Sign your exam and your exam booklet! I would like this to be the very first thing that you do when you begin.
- You may ask questions during the exam. To initiate a question, simply remain seated and raise your hand. Either I or one of the assistants will get to you, and we'll try to do that as rapidly as we can. So don't be surprised by quick movements on our part: we're simply trying to save your exam time and keep you focused on the exam itself.
- We will hold a formal midterm review session tomorrow from 4pm - 8pm. It will be led by Feredun (other assistants may make appearances, and I may make a guest appearance). The idea here is to clear up any lingering confusions or doubts about the material that we've covered since Class 1. Please consider attending. I do not have any location information yet, but I should have that available by tomorrow's class. Also, we will hold the regularly scheduled "drop-in" help session as well. Finally, it may be the case that I'll be able to secure either room 301 or room 302 in Research Hall, for tomorrow afternoon. That is my intention. If I do, then I will be available in that classroom. I will notify everyone by email if this situation obtains. But if it does not, you will still have the regularly scheduled "drop-in" session available to you, as well as Feredun's session from 4-8pm.
1.20. 29 FEBRUARY 2012 (Class 12)
- HAPPY LEAP YEAR!! Enjoy it! The next chance you'll get is four years from now!
- We took time out today to consider several problems from Homework #4 (which was due at the end of class). This was important since by doing so, we cleared up some lingering doubt about matrices, arrays and vectors (or at least I hope we did!) Furthermore, since matrices, arrays and vectors -- and the Matlab code associated with them -- will be featured on the upcoming midterm exam (7 Match 2012, 10:30am -- 11:45am, Innovation Hall room 223), it was essential to finally get a good grip on these constructs.
- At the end of class we opened the door a bit more on double nested FOR loops (DNFLs) but did not launch straight into them. We'll do that during Monday's class (4 March).
- By the end of the day today I also had the answer keys for homeworks #1-#4, homework extra credit quiz #2, and exam extra credit quiz #1 posted to Blackboard. These answer keys will support your studying for the midterm exam.
- I also distributed the midterm exam study advice. That was emailed to all CDS-130 students. It also appears on Blackboard, just in case (For example: what do you do if your email server goes down? Are you locked out of the midterm exam study advice? Answer: No, just head over to our class space on Blackboard!).
- My strong recommendation is to study this advice carefully. It directs you toward the topics that you need to know about. Problems appearing on the midterm exam will address these topics, and will usually be close variants to those you may see appearing in the advice.
- There are, however, a few pieces of information that I'll expect you to "just know" on the midterm: The logic tables for AND, OR, NOT, NAND, NOR; and how many bits and bytes comprise one ASCII character. You will be given a table of powers of two on the exam, as well as a table of unit conversions (example: you will be shown how many kilobytes comprise a megabyte, how many megabytes comprise a gigabyte, etc.). Focus, study efficiently and effectively, and you should be well-prepared for Wednesday's exam.
1.21. 27 FEBRUARY 2012 (Class 11)
- We took a brief timeout from Matlab to finish the presentation Introduction to Images and Colormaps. But then, it was back to the Introduction to Matlab presentation. FOR loops were in our sights, and we stayed with them througout the remainder of the class and arrived at the doorstep of double-nested FOR loops (aka, DNFLs)
- FOR loops are not only essential, we can't live without them. It's impossible to do programming of any sort without the capability to iterate, and that's exactly what FOR loops give us. Using them, our programs can execute sequences of instructions again and again. You may ask youself why that's important. The answer is that many physical and mathematical structures are amenable to analysis by iterative means. So time spent learning FOR loops is time very well spent.
- DNFLs are natural extensions of FOR loops, and themselves represent fundamental computational constructs. They're composed of two FOR loops -- one nested inside the other (hence the name, DNFL). DNFLs will become the basic tools that we'll use to process two dimensional images. Using them, we will be able to "walk through" an image, row by row, column by column.
1.22. 22 FEBRUARY 2012 (Class 10)
- Exam extra credit quiz #1 was delivered in-class today, from 11:15am to 11:35am. Prior to that, we initiated our move away from the purely architectural considerations we've been studying (binary, bit patterns, computing limits, etc.) and began taking a look at images.
- Images are nothing more than arrays of numbers. The software you're using (in this case, Matlab) translates those numbers into the appealing, colorful images displayed on-screen. It's important to understand that images are nothing more than a set of numbers with some interpretation (colormap) attached to them. It's that set, plus the interpretation, that results in the image. We made it about 2/3 of the way through the Introduction to Images and Colormaps presentation.
- Although we didn't finish it, we will on 27 February. We'll also explore double nested FOR loops (DNFLs) and Matlab's IF statement syntax. The combination of DNFLs and IF statements will enable us to "walk" through images, looking for specific patterns in them, and taking actions when we detect these patterns. We'll also find out how to selectively edit images. These operations (and others) are collectively referred to as "image processing". We'll be doing a lot of image processing in the coming weeks.
1.23. 20 FEBRUARY 2012 (Class 9)
- 100% Matlab! We finished vector and matrices, and began investigating the operation of FOR loops. FOR loops are absolutely fundamental computer programming constructs. They instruct the computer to perform many, many repetitions of a set of commands, and (usually!) operate with well defined stopping conditions (there are exceptions). There are so many things you can do with FOR loops -- and that can only be done with FOR loops -- that your imagination is the limit. And computing resources, of course! All of the material covered in today's lecture is found in the Introduction to Matlab presentation.
- Just prior to the end of class today, we also resolved the following issue: Should the homework assign/due day remain Monday, or, should it be moved to Wednesday? The move to Wednesday won overwhelmingly in the class vote. And so, Wednesdays are our new homework due/assign days. The midterm exam was also moved from Monday, 5 March to Wednesday, 7 March. I did that to accommodate those seeking assistant help: It does little good to have the help session AFTER the midterm exam!
1.24. 15 FEBRUARY 2012 (Class 8)
- More Matlab! Today we covered additional Matlab syntax from the Introduction to Matlab presentation. In particular, vectors. Vectors are one dimensional, contiguous arrangements of data. Elements of vectors can be manipulated all at once or individually. We saw how to do both operations. Arithmetic on vectors works pretty much as we would expect (that is, follows closely the rules for pure numbers, or, scalars). The exception to the rule is exponentiation, which requires the addition of a dot before the exponentiation operator: " .^ " and not just " ^ " This is the case because Matlab interprets " ^ " differently. We also began looking at matrices, or, arrays (for us they'll be synonymous) and we'll pick up with this topic again next Monday.
- I also announced that homework #3 is due on Wednesday, 22 February and not Monday, 20 February. The idea is to give all of you a chance to visit our assistants, as needed, who will be available on Monday from 1-4pm in Student Union II Meeting Room VIP 3. These "drop in help sessions" will occur on Monday afternoons for the rest of the Spring 2012 semester. The schedule can be found here: http://cds130.org/Main_Page. BTW, we will vote again on Monday. Issue: Whether to move the homework assign/due day from Mondays to Wednesdays for the remainder of the semester. Today's voting outcome was 12-12, and so this issue has not yet been resolved.
1.25. 13 FEBRUARY 2012 (Class 7)
- What's a logic gate? A logic circuit? Today we found out in the Memory, Logic and Logic Gates presentation. We first looked at the three common logic gates, AND, OR and NOT. Then we strung them together to form logic circuits (also called digital logic circuits), and discovered that these circuits COMPUTE. That is, they transform input bit patterns into output bit patterns. Most, if not all computations done by a computer are done with logic circuits. They're the fundamental building blocks of computational hardware. Logic gates are DEFINED by their associated logic tables.
- It's not hard to compute the output of logic circuits, given the inputs. Those computations follow a few simple rules. The thing to remember, is to organize the computation by beginning at the inputs and then working through the circuit one logic gate at a time: Transform one gate's input into output. Then distribute that output to wherever it needs to go (often, one gate's output becomes another gate's input). Repeat the process, moving systematically through all logic gates in the circuit. Doing so enables us to compute the entire circuit's output, given any of its permissible inputs.
- We also talked briefly about the extra credit quiz, and I worked through the first two problems on it. I'll finish up that discussion on Wednesday. PLEASE: If anyone has any lingering questions about the quiz problems, don't hesitate to ask!
- Today also marked the beginning of our regular Monday afternoon help sessions. Either Soo or Nicole will be available each Monday from 1-3pm in a reserved room at the Johnson Center. The reserved locations will be posted soon, for everyone’s reference.
- Now, since Monday help sessions are currently scheduled to begin at 1pm, which is AFTER 11:45am, the time your homework is due on Monday, one can logically ask, "What the heck!!! How helpful is that?"
- A very good question!
- As a result, I may now assign and collect homework on Wednesdays, not Mondays. Doing so will enable everyone to have access to our assistants in one convenient location -- BEFORE homework is due. This format is more useful, I think, than having assistants available to you only after your homework is handed in.
- The catch (if you want to consider it a catch) is that I’m unavailable Tuesday evenings. In other words, I’m unavailable the night before your homework would be due under this new schedule. I therefore can’t respond to texts on Tuesday evening. I mention this precisely because I got several texts yesterday evening and also the Sunday before -- i.e., on the days right before your homework was due.
- We’ll discuss this issue on Wednesday and vote on it (I’ll wait for the vote until near the end of class, so that everyone’s present, and if I should forget, PLEASE, someone remind me! :) ). We’re voting on whether to move the homework assign/due days to Wednesday, from the current assign/due day, which is Monday.
- Finally: Homework #3 is posted on Blackboard. It was actually posted before class today. You’ll see a variety of exercises assigned, from problem sets 2-5. Exercises from problem set 5 require you to fill out logic tables for logic circuits, just like we did today in class. We worked through two examples in today’s presentation, and there are other examples there for your reference. Please use these references when completing the assigned exercises from problem set 5.
1.26. 12 FEBRUARY 2012
- We've been getting some questions today on the following homework #2 exercise:
- Exercise 23: If I have 32 bits available to represent positive integers, what is the binary representation of the LARGEST POSITIVE INTEGER?
- OK, let's take a look. Remember BIT RULE #2: The largest positive integer that can be written with N bits, is equal to 2^N - 1. So for example the largest positive integer that can be written with 3 bits is equal to 2^3 - 1, or, 7.
- Now, how do we write 7 in binary? It's written like this: 1 1 1 . In other words, given three bits, to generate the largest positive integer using only these three bits, I "take one of everything" in the binary template: 1 unit of 2^0, 1 unit of 2^1 and 1 unit of 2^2. That's why I'll write 1 1 1 for the binary representation of the largest positive integer I can represent with 3 bits.
- We've also received a couple of questions about Problem Set 4, exercise #15. This exercise asks you to evaluate the following claim:
- "A quadword can represent positive integers that are at most four times larger than those represented by a word."
- OK, here we go: A word is comprised of four bytes, and, each byte is 8 bits. So a word is comprised of 32 bits. Now using BIT RULE #2 again, we see that the largest positive integer that can be represented by 32 bits, is equal to 2^32 - 1.
- Since a word is 32 bits, and since a quadword contains four words, then a quadword is comprised of 32 x 4 = 128 bits, correct? Using BIT RULE #2, we discover that in the case of a quadword, the largest positive integer that can be represented by 128 bits is equal to 2^128 - 1.
- So it seems to me that the claim is essentially this: "2^128 - 1 is at most four times larger than 2^32 - 1".
- Do you agree with that claim? Why or why not?
1.27. 8 FEBRUARY 2012 (Class 6)
- Homework extra credit quiz #2 was delivered at the end of class today; grades are posted on Blackboard.
- VERY GOOD JOB on almost everyone's part! I'll hand back the graded quizzes on Monday and we will discuss the problems then. You should also see homework #1 grades appearing on or before next Monday's class.
- Today also marked our transition away from a purely binary number approach to understanding 1s and 0s. Instead, we'll adopt a more general approach from now on, referring to 1s and 0s as bit patterns. That's the approach taken in the Binary Data, Encoding and Computing Limits presentation. In addition, we'll also learn about fundamental computing limits associated with bit pattern representations. These limitations will motivate questions such as, "Is there a largest integer that a computer can represent? If so, why, and what is it?". We'll also explore a concept called the machine epsilon and why that's important.
1.28. 6 FEBRUARY 2012 (Class 5)
- The presentation Binary Number Operations II (Multiplication & Division) rounded out our binary number mathematical repertoire. Multiplying binary numbers isn't so difficult. There are just two simple rules to remember. And, if we're multiplying a binary number by a power of two (i.e., conducting a LEFT SHIFT operation), well then, things simply even further: just add the appropriate number of zeros onto the right end of the binary number! Integer division (i.e., a RIGHT SHIFT) is also very easy: Just cross out binary digits, starting with the binary digit furthest to the right.
- Binary addition, multiplication and simple division are fundamental binary number processing operations that occur on-chip. Now that we've got them under control we can move onward. In the next lecture we'll broaden our perspective. No longer will we refer to strings of 1s and 0s exclusively as binary numbers. Instead, we'll begin calling them bit patterns. We'll learn that strings of bits (1s and 0s) can represent almost anything. The interpretation is up to us. That said, standard interpretations do exist. ASCII code, for example, assigns alphanumeric character interpretations to bit patterns consisting of 8 bits (standard ASCII). We'll learn all about this on Wednesday. Consider the above comments to be a preview.
- In today's Matlab session we reviewed the MOD function and were introduced to vectors. Please review the MOD function examples found in the presentation, to ensure that you know how MOD works. The green star has moved further along, and can now be found on slide 113. That's where we'll pick up our Matlab discussion next time.
- On Wednesday we’ll have our second homework extra credit quiz. It’s worth 7 points, distributed across four problems, as follows: Problem 1 (1 pt), Problem 2 (2 pts), Problem 3 (2 pts) and Problem 4 (2 pts).
- To prepare for this quiz, I strongly recommend that you review the exercises identified in the below study advice, from the indicated problem sets. These exercises are closest in design to the actual quiz problems. Therefore, if you’re fluent with these exercises, you should find the quiz to be straightforward. It will cover material discussed in today’s lecture as well as material from the last two lectures, and, material found in the problem sets (such as the discussion on the extended binary template method). Please focus laser-like on the below study advice: It’s designed to be helpful, and, to direct you at what matters for this quiz.
- The second homework extra credit quiz will occur during the final 30 minutes of class: I’ll begin distributing the quiz at about 11:15am and it will begin promptly at 11:20am. It will conclude promptly at 11:40am. For those of you who arrive late, you must finish the quiz in the time remaining between your arrival and 11:40am. Calculators are not permitted on the quiz. Also, there’s no make-up if you miss it. Remember: Extra credit quizzes are offers of extra credit. As such, they’ll never work against you or hurt you. They can only help you.
- Quiz study advice follows:
- Quiz Problem #1 is most similar to: Problem Set #3, exercises 20 and 21
- Quiz Problem #2 is most similar to: Problem Set #1.1, exercises 16, 17, 18 and 22
- Quiz Problem #3 is most similar to: Problem Set #3, exercises 14, 15 and 16
- Quiz Problem #4 is most similar to: Problem Set #3, exercises 6, 7, 8 and 9, as well as binary to base ten conversions using the binary template method
1.29. 4 FEBRUARY 2012
- This morning I received a report from a student unable to access CDS-130/04 content posted to Blackboard. In response, I packaged together everything that students need to complete homework assignment #1 (including the Introduction to Matlab presentation and the Matlab access presentations). I emailed that package to all CDS-130/04 students earlier today, as two separate zipped files. Let's hope Blackboard resolves its access problems soon.
1.30. 1 FEBRUARY 2012 (Class 4)
- I just updated the Introduction to Matlab presentation: I moved the green star to Example #2 of Chapter 3.
- Now the next example, Example 3, is really an extension of Example 2. So there's not much to Example 3. But following Example 3 you'll find a detailed explanation of the MOD function. My recommendation is that everyone read to the end of Chapter 3 in Introduction to Matlab, to get familiar with how the MOD function works. MOD is really nothing more than integer division and integer remainder -- we're already familiar with those operations. What isn't familiar is the syntax. We'll use mod frequently in upcoming lectures; MOD will also appear in other places. So understanding it now will be quite useful later. As always, if you have questions, please don't hesitate to ask.
- Also (repeating from today's lecture, for Mac users): If you're using a Mac and having trouble getting a remote connection to Matlab, let us know. Trevor is available during class to help you. Please bring in your Mac, and Trevor can walk you through the connection steps. These are also found in the presentation entitled, Mac Remote Access Presentation, which is in the MATLAB folder on Blackboard. Or, you can connect up through the VCL, as discussed in last class. Use the method that works best for you: that choice is entirely up to you.
- On Monday we'll learn about binary number multiplication (two different methods) and simple division. Next Wednesday's homework extra credit quiz will cover all material from Class 2 through Class 5. As I've done in the past, I intend to send out quiz study advice in advance of the quiz.
1.31. 30 JANUARY 2012 (Class 3)
- For the first half of class today we covered Binary Number Operations I (Addition). We've been interpreting binary strings as positive integers thus far and so a natural thing to do is learn how to add together two binary numbers. Furthermore, binary addition is a fundamental operation at the chip level and so it's good to know a little bit about what's going on there. Following binary addition, we moved ahead into our "Introduction to Matlab" presentation and worked our way up to Chapter 3. Along the way we learned about Matlab's desktop environment and also how to access Matlab remotely using GMU's Virtual Computing Laboratory (VCL). VCL is a great tool, and will enable you to access Matlab wherever you have a wireless connection!
- After class today a student asked me a very good question: How do I want to receive homework #1?
- Here’s the answer: Please submit homework #1 to me in hard copy. The Matlab code that you write (if I still go with these problems – and I’ll know that after Wednesday’s lecture, when we cover some more Matlab) should also be submitted in hard copy, along with its output.
- Now in the past students have hand-written their homeworks and also written them in Microsoft Word. Either works fine for me. Later in the term, we’ll all get Wiki accounts on the class Wiki, and begin posting homeworks there. We’ll do that to introduce you to the Wiki as a useful collaboration tool.
- But now, for homework #1 and those that follow, please submit them to me in hard copy. Please remember: homework #1 is due at the end of next Monday’s class, 6 February 2012. My assistants and I will collect homework #1 from you before class ends. When I depart our classroom, the homework “window” closes.
- PLEASE: If anything seems confusing or uncertain, at any time, don’t hesitate to ask questions. You all have my contact information and contact information for our assistants. We welcome your outreach! You also have our email addresses, for the same purpose. We can also accommodate requests for individual help sessions: We do a lot of those (more as the semester progresses), both singly and in groups. So . . . never hesitate to ask for help, as needed. It’s available!
- Finally, I’ve updated the Introduction to Matlab presentation: I moved the green star and it’s now awaiting our return to Chapter 3 on Wednesday, 1 February. Wednesday’s class will be devoted entirely to Matlab.
- For those of you who wish to access Matlab from off-campus locations using a Mac, please refer to the VCL on Mac presentation, found in the MATLAB folder on Blackboard. It contains detailed, step-by-step, graphical instructions about how to use your Mac to connect up to GMU’s Virtual Computer Laboratory (VCL) and thus access Matlab remotely – similar to the instructions we reviewed today for accessing the VCL using a Windows computer. If you encounter trouble with these instructions, or, cannot connect up to VCL using your Mac, fear not: Trevor is a Mac power-user and will be able to assist you and answer your questions on Wednesday.
1.32. 28 JANUARY 2012
- Earlier today I posted the presentation Introduction to Matlab in the "MATLAB" folder on our class Blackboard account. I also posted Problem Set 1.1 and Problem Set 2.0 into the "Problem Sets" folder.
- I’ll reference these problem sets (and others that will be posted later) when I create your homework assignments. For example, homework assignment #1, which will appear on Blackboard before tomorrow’s class, will ask you to complete selected exercises from both of these problem sets. NOTE: There’s NO NEED to complete all the exercises in these problem sets! Certainly, all the exercises won’t be assigned for homework. But I’m providing you with more than you need because I’ll reference selected exercises for other purposes, such as pointing out those that bear interesting resemblances (perhaps even very strong resemblances) to problems that will appear on upcoming extra credit quizzes and exams. So it’s worth your while to have these problem sets handy for reference. Furthermore, the unassigned problems make great practice!
1.33. 27 JANUARY 2012
- Wanna get a head-start on binary, perhaps practice a bit? But, you have no paper and pencil handy to draw out a binary template? Well, not to worry: Cisco Systems has you covered! Check out this binary game, similar in spirit to Tetris: http://forums.cisco.com/CertCom/game/binary_game_page.htm I don't know where they got their music choices from, though (and there are only three available)!
1.34. 25 JANUARY 2012 (Class 2)
- Today's focus was on binary numbers: How to interpret them and convert back-and-forth between base two and base ten. We also delved (briefly) into other bases, for illustration purposes only! The tool supporting all these excursions is the binary template. Using it, and the template method, we found that conversions between base two and base ten are handled almost automatically. It's a great tool and wonderful method!
- In coming lectures we'll expand our capabilities by learning how to add, multiply and divide binary numbers. Furthermore (and perhaps more importantly), we'll begin focusing on a binary string as a bit pattern, that is, as a pattern of 1s and 0s to which we may assign other interpretations (other than numerical). Our current focus -- interpreting a binary string as a positive integer -- is entirely appropriate as a means of introducing this new and important concept.
- Watch for new material to appear on Blackboard in the coming days. In particular, I'll post the Matlab presentation we'll use as a "textbook" for the rest of the class. Again, if you feel more comfortable having a printed text, please see the comments from 28 December, below, for a specific purchase recommendation.
1.35. 23 JANUARY 2012 (Class 1)
- I had today's extra credit quiz scores posted to Blackboard by lunchtime, but could not send out a notification because my email was down. Since coming back online I've sent an email announcement that the grades are posted.
- Great job on the quiz! Forty six students out of fifty took the quiz and almost everyone who took it got a 4 or 5. Please remember: This was a homework extra credit quiz. That is, the points you earned today are homework extra credit points -- missing a point or two (or all five) can't work against you. These points only help you. So, almost everyone starts with some "money in the bank".
- I'll take a few moments on Wednesday to hand back the graded quizzes (another way I get to learn your names!) If you should happen to arrive late to Wednesday's class, you'll find your quiz residing comfortably with our assistants, in the back row, and so you may retrieve it from them upon your arrival.
1.36. 22 JANUARY 2012
- For those of you who may be interested in getting a head-start, I've posted new content to Blackboard: Remote Access to Matlab at Mason, and VCL on Mac. Both of these presentations can be found under "Course Content" in the "MATLAB" folder.
- "Remote Access to Matlab at Mason" shows Windows users how to access Matlab via Mason's Virtual Computing Laboratory (VCL). It also contains instructions for accessing Matlab using CygWin on Windows (if you prefer running a Unix shell on Windows), and also, how to log directly into the Mason cluster from a Linux environment and use Matlab that way.
- If you prefer using a Mac, then "VCL on Mac" will be of interest to you. It shows you the step-by-step special procedures for accessing the VCL from a Mac (there are a few different steps involved).
- Following class on 23 January, I'll also post a presentation entitled, Introduction to Matlab. This will serve as our Matlab "textbook" throughout the semester.
1.37. 17 JANUARY 2012
- In CDS-130 we study the binary number system first, and follow that with a detailed excursion into bits, bytes, data representation and data storage. Well . . . check this out: Atomic-sized bytes! Researchers have managed to fit a byte of information (8 bits) into a stable, 96 atom configuration. Read a news announcement here, and IEEE commentary here. The original paper is published here.
- CDS-130/04 is now available on Blackboard to all registered students. You'll find the CDS-130/04 Spring 2012 syllabus posted there. I'll use Blackboard throughout the semester to post class presentations, homework assignments, grades, etc. Presentations will generally be available on Blackboard no later than one day following the class during which they were originally discussed.
1.38. 13 JANUARY 2012
- Early next week I'll open up the Blackboard account for CDS-130/004. I'll post the syllabus there; we'll also go over it on the first day of class, 23 January 2012.
- Class meets Monday and Wednesday, from 10:30am -- 11:45am, in Innovation Hall, room 223. Each seat in this room is equipped with a computer workstation, thus facilitating access to electronic course materials, and, to Matlab. We'll work with Matlab in-class, but it will also be worth your while to learn how to access Matlab through GMU's Virtual Computing Lab (VCL). When class starts, I'll post detailed instructions on our Blackboard account that demonstrate how to access the VCL using Windows, Linux or the Mac. Those instructions will also show how to access Matlab via VCL. But for those of you who'd like to get a headstart, consider visiting the VCL before class begins, just to familiarize yourself with how it works.
1.39. 3 JANUARY 2012: Medical School, Anyone?
- For those of you who are interested in applying to medical school, you may be very interested in the information that appears here.
- Electing to study computational science (either as a major or as a minor) is excellent preparation for medical school -- precisely because computational science combines mathematics with physical sciences. And having a background in these areas is beneficial when it comes to applying to medical school! Furthermore, GMU's department of Computational & Data Sciences features research in computational medicine. You might want to think about becoming involved. Professors Kirk Borne (kborne@gmu.edu) and Bob Weigel (rweigel@gmu.edu) can show you how.
- Your gateway into computational & data sciences is right here, in CDS-130; you're in the right place! We prepare our students by developing their abilities to think algorithmically and to solve scientific problems computationally. These are two very important skills that are in high demand in today's marketplace!
1.40. 1 JANUARY 2012
- HAPPY NEW YEAR EVERYONE!!!
1.41. 28 DECEMBER 2011
- Some students have already emailed me, asking about the text for this course. Well, lucky for you: THERE'S NO REQUIRED TEXTBOOK!
- Instead, I use a combination of PowerPoint presentations, handouts, Matlab code, posts to this Wiki page and other materials. Collectively these constitute the "text" for CDS-130. This format has worked wonderfully in the past and so I'll continue to follow it.
- However, for those of you who feel more comfortable with a written reference work . . . I can suggest one, for Matlab: "Getting Started with MATLAB: A Quick Introduction for Scientists and Engineers", by Rudra Pratap. We don't actually use this book in CDS-130 (I have a very comprehensive Matlab presentation that we'll use instead -- it's really a textbook all by itself!), but, I've found Pratap's book to be an appropriate level reference for the MATLAB material and techniques that I teach.
1.42. Miscellaneous
- My office is Research 1, room 345. During our first class meeting I'll distribute my email contact information as well as a telephone number at which CDS-130 students may text me for assistance. My office hours are usually by appointment, but please feel free to drop by anytime for a chat or assistance, as needed: I maintain an open-door policy.
- We have two teaching assistants for this course: Ms. Soo Choi and Mr. Harendra Puviharen. Their contact information will also be distributed during our first class meeting. Please feel free to contact them at any time with questions you may have, or, to schedule individual help sessions, as required.
- We are also fortunate enough to have two in-class technical assistants: Mr. Feredun Azari and Ms. Nicole Gordon. They will be available during class to help you with Matlab in case difficulties arise and to answer other questions that you may have. Their contact information will also be distributed during our first class meeting.
- Information about the last runnings of my class: CDS-130/03 (Fall 2011) and CDS-130/C02 (Summer 2011).
- Also visit the CDS-130 support page, which includes some instructor background info as well.