CSC 230

last class: mon mar 13, 2006

Final Exam starts at 6:30 pm... the details are below.

I will be in my office on Sunday afternoon from 5:00 to 7:00, if you need help. Of course, you can also email me questions or to setup a different meeting time.

run forrest run... yow, bill

wed mar 8, 2006

Alan Turing (to the right there) was a serviceable amateur marathoner in his day, evidently. Turing has a nice three-fer: 1) he helped break the Enigma Code during the war, 2) he developed the notion of the Turing Machine, and 3) he described the Turing test for artificial intelligence programs. This level of success and genius inevitably leads to a gnarly ending, right? In this case, it's suicide by poison apple. Excellent wiki page on him, and our textbook's blurb on page 774 is good as well.

Last class. We'll chat about homework #16 and then preview the Final Exam. Ah, the Final Exam:

• Monday March 13, 6:30 pm
• It's worth 40% of your grade
• You can bring one side of one page of notes. Also, you can bring your first sheet that you used for the midterm. Please note, you can't bring two sheets covering the 2nd half material.
• Same style as the midterm, I reckon... 2 hours or so of homework-ish problems.
• The Final Exam will be comprehensive with a strong emphasis on the second half material, including:
  • Section 5.1 - discrete probability
  • Sections 6.1, 6.2, 6.5 and 6.6 - recurrence relations and inclusion-exclusion principle
  • Sections 2.4-2.6 - number theory and RSA
  • Chapter 7 - relations and closure
  • Section 8.1-8.6 - graphs
  • Chapter 9 - trees
  • Section 10.4 - K-maps, Quine-McCluskey
  • Chapter 11 - grammar, FSM's, regular expressions, Turing Machines

Gulp.

be there... yow, bill

mon mar 6, 2006

We'll wrap-up Chapter 11 today. Homework returned, due and posted... for the last time.

Three super-fun nerd stories for you:

First... Quote of the Day:

"a bug-eyed, hexagonal smurf with a head of electrified hair"

- description of the new Mimivirus, the largest virus scientists have found thus far, from http://www.discover.com/issues/mar-06/cover/

Second... A wonderfully nerd exposition on quantum computing from down there at the U of I:

http://www.newscientist.com/channel/info-tech/mg18925405.700.html

Third... I always knew this was true... "sleeping on it" to solve a technical problem. Always study your exam notes before falling asleep the night before the test.

http://www.kurzweilai.net/news/frame.html?main=/news/news_single.html?id%3D5323

These stories are from one of my favorite sources of latest, greatest research... Ray Kurzweil's "Singularity" site:

http://www.singularity.com/kain.php

smurf... yow, bill

PS - Oh yeah, the Final Exam is in one week, Monday March 13 at 6:30.

  

wed mar 1, 2006

We'll optimize logic most of lecture using 2 algorithms: K-maps and Quine-McCluskey.

Homework due, homework returned, and homework posted (soon)... blah blah blah.

he he... yow, bill

PS - Submitted for your approval...

• Don Knotts, died Feb 24th at age 81
• Darren McGavin, died Feb 25th at age 83
• Dennis Weaver, died Feb 24th at age 81

The best death trinity of all time? Sign of the coming apocalypse? Too much time on my hands? You be the judge.

  

mon feb 27, 2006

Last week, we played with Dijkstra's Algorithm for determining the shortest path in a graph. There's a picture of Lenny Dykstra over there to the right. In addition to his computer science heroics, Lenny spent 12 seasons in the big leagues. A leadoff man, Lenny compiled a .285 batting average and, more importantly, a .375 OBP for his career. Lenny played for the Mets and the Phillies. If that weren't bad enough, Dykstra has been implicated in both steroids and gambling since his retirement 10 years ago. Sigh.

We had a chat a couple weeks back about preschoolers taking discrete math or some such thing. It did get me wondering... what are the big boys doing in discrete math. Well, they don't get much bigger than my old haunt in Champaign. For grins, here's the Illini flavor of discrete math course: http://www.cs.uiuc.edu/class/sp06/cs173/

They use the same Rosen text that we do. The selection of topics may be somewhat different because other courses at North Central will cover some of the topics that we are skipping. Also, I would expect that their exams and homework assignments to be a bit tougher, but they're posted so you can evaluate that yourself.

We're in a groove... homework's due... reading... lecture.

be there... yow, bill

PS - Um, a little instructor errata there. It appears that Lenny Dykstra, the ballplayer, did not work on shortest path algorithms. I guess that would be Edsger Dijkstra, actually. And no, I won't attempt to pronounce it.

PPS - BTW, if you're into baseball, www.baseballreference.com is absolutely outstanding. Check it out.

PPPS - February 27th... what a fine day of the year!

  

wed feb 22, 2006

IMPORTANT! READ ME! Hey, I just noticed that the homework #12 posting had a mistake. You only have to do parts a) and b) of section 7.4, exercises 25 and 26. Dop.

So, dang it:

• Homework #12 is due.
• We'll chat about Chapter 8

thanks... yow, bill

  

mon feb 20, 2006

Homework #11 is due.

We'll finish Chapter 7 in lecture.

New York City!

yow, bill

  

wed feb 15, 2006

Homework #10 is really due today. Also, please read chapter 7 before lecture; I'll peek at your notes.

Lecture, you ask? I'll wrap Chapter 6 in 10-15 minutes and then onto Chapter 7.

Mathematician Paul Erdos is featured on page 533 of our text. Erdos' claim to fame (well, mostly) is his prolific publishing history of over 1,500 published technical articles.

This amazing output spawned the notion of the Erdos number amongst mathematicians as a tribute to Erdos. A mathematician's Erdos number is... well here's how Wikipedia describes it:

An author's Erdos number is defined inductively as follows:

• Paul Erdos has an Erdos number of zero.
• The Erdos number of author M is one plus the minimum among the Erdos numbers of all the authors with whom M coauthored a mathematical paper.

OK, so Erdos' own number is zero, and his direct collaborators number is one, their collaborators are two and so on. Get it? Sort of like 6 degrees of Kevin Bacon or something.

thanks... yow, bill

  

mon feb 13, 2006

Homework #10 is due.

We'll wrap-up RSA security, Chapter 2, and maybe tidy up Chapter 6's loose ends as well.

Donald Knuth is a computer science brother and is featured on page 135, near all complexity stuff that we are skipping because you'll get that in 210. It's a good read.

Knuth's most famous work is as author of "The Art of Computer Programming", a task he continues to this day. The detail and density of these volumes is amazing. I'll try to remember to bring one of mine.

In the books, Knuth describes his algorithms in an assembly language of his own design because to use a higher-level language would make his efforts less pure. Bill Gates once said that he would never hire a CS guy who hadn't read some of Knuth and would never hire one who had read all of it. Knuth promises any reader a check for $2.56 (like the one to the right) for any new errata found in TAOCP because 256 pennies is one hexadecimal dollar. Nerd out! I've heard that Knuth checks have been put up for sale on ebay, but I've never seen one myself.
Knuth is also a deeply religious man and wrote an excellent book called "3:16 Bible Texts Illuminated"... which I happen to own, if you'd like to borrow it.
Finally, Knuth's Wikipedia page is an excellent root for other exploration.

race... yow, bill

PS - Please read Chapter 7 for next time.

  

wed feb 8, 2006

Homework #9 is due.

In lecture, we'll sprint through sections 2.4 - 2.6 in search of better encryption. Here's a nice wiki-primer on RSA encryption.

Gauss to the right, "the prince of mathematics"... good one. He's on everyone's top ten mathematician's list, and I have his rookie baseball card.

The wiki-link is a very good read and so is the mini-bio in our text on page 162.

thanks... yow, bill

   

mon feb 6, 2006

I'll return the midterm exams, and we'll chat about it.

Lecture will cover Chapter 6. I'll focus on Sections 6.1 "Recurrence relations", 6.5 "Uber Inclusion-Exclusion Principle", and 6.6 "Some fun I-E Algorithms".

Homework #8 is due.

thanks... yow, bill

PS - BTW, you should be able to "see" your midterm grades on Merlin.

PPS - BTW #2, I must apologize profusely for my lag in reporting the discovery of the 43rd Mersenne prime number, the largest known prime number to date, around Christmas time. More on this story at New Largest Known Prime Number. It's actual number is 2^(30,402,457)-1 or in its non-exponential state: 2^(30,402,457)-1 ... all 9,152,052 digits of it. Another step closer to the $100,000 prize for the first 10 million digit prime number to be discovered.

PPPS - I might use this page in lecture:

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

  

wed feb 1, 2006

We'll take the Midterm. Duh.

The material in section 5.1 is attributed to Pierre-Simon LaPlace, picture to the right. He's a Frenchie, and his LaPlace transform is his most renowned work.

There's a tiny section 5.1 homework assignment posted; it's due next Monday.

race you in... yow, bill

PS - I promised a little detail on Eric's question from lecture last night. We were selecting committees from page 326, exercise 30, part a, with at least one woman, and three different approaches were presented:

• Mine: I took all possible ways the committee could be organized and subtracted those that were only men.

C(16,5) - C(9,5) = 4,242

• Tony's or the Christi Cases approach: Sum the number of ways a 1-woman committee plus a 2-woman committee and a 3-woman committee, and so on...

C(7,1)*C(9,4) + C(7,2)*C(9,3) +

C(7,3)*C(9,2) + C(7,4)*C(9,1) +

   C(7,5) = 4,242

• Eric's: If you select one woman, then you can select the rest of the committee from all the remaining people, regardless of gender.

C(7,1)*C(15,4) = 9,555

So, why is Eric's answer larger than the first two approaches... and incorrect? This approach is double-counting some committee choices. Consider that our two classmates Dori and Christi are 2 of the 7 women available to be chosen. In Eric's approach, if Dori is the first women chosen, then Christi is returned to the pool of possible committee members, so one committee choice is {Dori, Christi, A, B, C}, where A, B, C are any of the other potential members. Now, when Christi is selected as Eric's primary woman in the committee, then Dori returns to the pool, making {Christi, Dori, A, B, C} a valid choice. However, this choice has already been counted because order is not important. This is an example of how Eric's solution over-counts the possible committee choices. Make sense?

PPS - Study harder!

  

mon jan 30, 2006

OK, the Binomial Theorem is accredited to Blaise Pascal though it had its origins much earlier.

It seems Blaise had a number of medical problems throughout his life... not a good idea in the 17th century. Wikipedia says that "he wore stockings steeped in brandy to warm his feet." OK.

Anyway, homework #7 is due Monday. In class, we'll talk about that homework and any questions you may have. Then, I'll preview the Midterm. Ah, the Midterm:

• It's Wednesday Feb 1... same place, same time
• It's worth 30 points, or 30% of your grade
• We'll cover material i Chapter 1, Section 2.7, Chapter 3 & Chapter 4
• Bring 1 side of 1 page of notes with you... no books, no calculators
• It'll be a lot like the homework problems, I reckon

If we have any time leftover, then I'll chat you up on section 5.1... we'll see.

thanks... yow, bill

PS - BTW, there's a fun proof of the Binomial Theorem using induction on the Wikipedia page. Enjoy! Also, for you "enquiring minds"... yes, there is a Multinomial Theorem of which the Binomial Theorem is a special case.

  

wed jan 25, 2006

Tonight, we'll finish up lecture on Chapter 4. This will conclude the material that will be on the midterm. If you didn't by a scorecard, the midterm is next Wednesday, Feb 1, and will cover: Chapter 1, Section 2.7, Chapter 3, and Chapter 4.

Homework #6 is due, and homework #7 will be posted chop chop.

thanks... yow, bill

  

mon jan 23, 2006

GUYS, PLEASE READ THIS!
Jeez, I'm slumping. The assignments posted for homework #5, due next class, were wrong up until 10:30 Friday morning when I fixed them. I had listed Chapter 4 problems as due Monday, but we haven't talked about that stuff yet. I have fixed this, and the new, correct homework problems are from sections 3.3 and 3.4 as they should be.  I apologize if this jammed anyone up.

Anyway, on Monday we'll start talking about Chapter 4, Counting.
sigh... yow, bill

  

wed jan 18, 2006

Neil Sloane is cited on page 229 of our text and is, among other things, the creator and maintainer of the On-Line Encyclopedia of Integer Sequences. To the right there, Neil is toasting the 100,000th contribution to the OEIS (ack-ronym!) in 1994. The encyclopedia currently says that it has 114,381 entries. Check it out because you can enter your own integer sequence, and it will search its database for a match. It is... pause... cool. I also own the book version, which is less cool. Not to be redundant, but the Wikipedia page on the OEIS is also very cool.
On to b'ness, today we'll finish lecture on Chapter 3... mostly we'll do some proofs using induction. And surprise, homework is due today.

Hey guys, I just added a homework page... check it out for the homework expected for each class: homework.htm 
Homework #4 is due today. Homework #5 is posted and is due next Monday.
thanks... yow, bill
PS - Yes guys, I'm stepping on the gas a little bit. Vroom! Three things:

1. We're making up the lost Jan 2 ground,
2. I think we (well, you) can do 2.7 without much lecture help, and
3. I want the midterm to cover chapters 1-4.

PPS - Bill, note to self... the Unicode works on my Firefox in the part-timer office; it's version 1.5.

  

mon jan 16, 2006

GH Hardy is perhaps more known, today, for the peripheral work around his career rather than his actual mathematical exploits. He worked closely with Indian prodigy Srinivasa Ramanujan (see below). Hardy is also the author of the enigmatic "A Mathematician's Apology". There's a better picture on page 296 of our text.

Now, Srinivasa Ramanujan was more or less discovered by Hardy. Check this out:

• ஸ்ரீனிவாஸ ஐயங்கார் ராமானுஜன - Srini's name in his native tongue... gosh, you gotta love Unicode.
• And Charles, can you verify for us that Ramanujan's "other way" of calculating pi is correct?

 
We'll finish mopping up Chapter 1 by doing some proofs from section 5, and then onto Chapter 3.
That is all... yow, bill
PS - Almost forgot... Homework #4, due next class:

homework #4 due wed jan 18
section	pages	exercises
1.5	73-75	1, 2, 5-8, 11, 12, 23, 24, 33, 38, 39 (do the first half of the multi-parts) This section delayed till next class!
3.1	223-224	2, 3, 6, 7, 16, 28
3.2	236-237	1, 2, 13, 14, 15, 16, 27

PPS - And a big shout out to Charles' spell-checking roommate.