MATH/CS 11

Welcome to the home page for MATH/CS 11 at the University of California, Riverside, in the first Summer Session of 2006. I am Toby Bartels, the instructor. You can email me at toby+s6w@math.ucr.edu. The class meets in Sproul 2365 on Monday through Thursday mornings from 9:40 to 11:10.

My office hours will be in Surge 263, on Mondays through Thursdays from 12:30 to 2:00. You can also meet with me by appointment; you can make an appointment by email or whenever you see me. In fact, you should feel free to drop by my office at any time; I might not be there, and I might not have time when you come even if I am there, but your odds are good, so give it a shot!

This web site will be updated from time to time, so if you want up-to-date information, then check online. Any important changes will be in the announcements, so at least check there. Of course, I'll also announce things in class.

The course also appears on UCR's Blackboard site. I will use that site to send any important announcements to you by email and to record your grades where you can read them (under Student Tools). If your email address on Blackboard (which is also listed under Student Tools) is missing or wrong, then you won't get announcements by email, but they'll still show up on the main course website. (If you haven't received an email from me yet, then probably either you aren't registered or your email address on Blackboard is wrong.) Note that the Blackboard site requires Javascript to work.

Introduction

Discrete mathematics, as the name suggests, is mathematics that is unconcerned with the continuity properties of the real line. I like to think of it as that branch of mathematics that has nothing at all to do with calculus (although that is an exaggeration). As such, it covers very different material from what you may be used to from other math classes. In the past half century, discrete mathematics has had a great deal of application to computer science, and this course is intended to prepare for those applications. Nevertheless, the material is math, not CS.

There is a myth, which I've found prevalent among undergraduates, that mathematics study is a linear progression: arithmetic, algebra, geometry, trigonometry, calculus, and so on. This is almost entirely false; mathematics is a web of ideas, all related but in different ways, and the traditional high school curriculum in the United States is simply one way to organise it. That curriculum is geared towards calculus; it focuses on the ideas needed for calculus, which in turn is needed for the engineering that was central to the American economy (and the Cold War) half a century ago.

The curriculum could equally well pass from algebra to logic (including proofs), modular arithmetic, algorithms, graph theory, and (instead of calculus) abstract algebra. This is a curriculum of discrete mathematics, which is needed for computer science, systems engineering, logistics and management engineering, and similar endeavours. In another 50 years, MATH 11 may simply be the remedial class for students that didn't learn what they should have in high school; while MATH 9 (calculus) should be special material primarily for biology and economics majors.

Prerequisites

The formal prerequisites for this course are either two terms of calculus or one term of calculus and one term of C++. These are entirely unnecessary! Discrete mathematics is neither more nor less advanced than calculus, and I have to stretch to even use examples from it. On the other hand, the methods of C++ (or any other specific language) are irrelevant to the general mathematical ideas that are covered here. That said, a term of calculus has, hopefully, given your algebra a review; and familiarity with any programming will be useful.

Books

The official book for this course is Discrete Mathematics and its Applications, by Kenneth H. Rosen, 5th edition (2003), published by McGraw-Hill. I also recommend Schaum's Outline of Discrete Mathematics, by Seymour Lipschutz and Marc Lipson, 2nd edition (1997), also published by McGraw-Hill. If you have either of these books, then as far as I'm concerned, you have a textbook for this course; you don't have to get the other one.

However, if you take MATH/CS 111, the sequel to this course, then you'll probably need to get Rosen (for homework assignments if nothing else); the instructor is not likely to know or care about Lipschutz & Lipson. That may be just as well; in my opinion, Rosen is a very good book that covers a lot of useful material. Lipschutz & Lipson is less well written and less thorough; it doesn't even cover all of MATH/CS 111, let alone all of the extra material in Rosen. However, Lipschutz & Lipson does have one great superiority: it's about $100 cheaper than Rosen.

Another useful book is 2000 Solved Problems in Discrete Mathematics, by Seymour Lipschutz alone (1991), again published by McGraw-Hill. This book is a companion to Lipschutz & Lipson; as its title says, it contains 2000 solved problems, so you can use it for practice or extra study. I should also warn you not to get Schaum's Easy Outline of Discrete Mathematics. This is an abbreviation of Lipschutz & Lipson, and it doesn't cover enough material to be a textbook for this course.

Both textbooks (Rosen and Lipschutz & Lipson) are available at the UCR bookstore, but only Rosen is downstairs in the textbook section; Lipschutz & Lipson is upstairs with the general mathematics books (specifically with the educational aids among a bunch of other Schaum's Outlines). You can buy books online usually cheaper than at the bookstore (but then there are shipping delays):

The textbooks are also on reserve at the library.

There is also be a supplementary handout on Rules of Inference, which is material that's not (completely) in either textbook, but which you are still responsible for knowing:

Syllabus

The topics to be covered include: Note that this is a different order from the official department syllabus (which follows Chapters 1 through 5 of Rosen), although it's the same material. Keep in mind that any schedule is tentative and subject to change.

This Summer Session course covers in 5 weeks material that is normally covered in 10 (or 11 if you count finals week). Each day of lecture here corresponds to half a week of the normal class. There's no discussion section either, which means that in total there's less class time. Be prepared to work hard, and don't expect to get away with skipping lecture.

Assignments

Each day, I will lecture on the material for that day. At the beginning of the next day, I'll assign some homework problems. (I always write out all of the homework problems that I assign, so you never need to look them up in a particular textbook. The homework will also be posted online.) Some of the homework will be Practice problems, fairly straightforward and with answers at the end of the assignment handout; do as much of these as you need until they become easy. The rest of the homework will be Due two class days after it was handed out; to avoid giving you an incentive to come late to lecture, Due homework is not officially due until the end of the office hour on the appropriate day. The beginning of each class (about 15 minutes) will be devoted to answering questions; please participate in the discussion! You should look at homework each day so that you can ask questions about it on the day before it is due (that's why I give you two days to complete it). I will not answer questions about homework on the due date itself!

Each week (except the last), I will also assign a research project that is due one week later. These projects ask you to write an essay (of a few pages) about a topic related to the class material. You'll have a choice of topics, and you'll probably need to do research outside of the class lecture. The projects will also be posted online.

The final exam will be July 28 Friday from 10:30 to 12:30 (there is no finals week in Summer Session). Here is a mock final, which is longer than the actual final will be; if you study for the mock final, then you should do well on the exam:

Grading

Strictly speaking, there is no curve, so you are not competing against your fellow students. I encourage you to study together and learn from each other! However, if grades don't turn out as I expect, then I'll consider whether an assignment was more difficult than I intended and adjust the grades accordingly (usually by making a hard problem extra credit).

Numerically, I will grade harshly —it's hard to get 100% on any single assignment. On the other hand, the correspondence between numerical grades and letter grades is nicer than most math courses (especially at the low end):

Here, ‘[x%, y%[’ means ‹at least x% but less than y%›. There is no rounding here; an average of 49.99% is not enough for a C. Note that you can get an A+ without being perfect, because many homework assignments will include extra credit problems.

There will be 4 projects worth 40% in total (10% each), about 16 homework assignments worth 20% in total (about 1.25% each), and 1 examination worth 40%.

Collaboration and plagiarism

For both homework and projects, I encourage you to talk with your fellow students. In my class, this is not cheating! However, the final result that you turn in to me must be your own work, written by you in your own words; you should understand (at least more or less) what you've written. Don't turn in anything that you copied from another person (except for properly cited quotations in your project essays), and don't have other students copy from what you plan to turn in. Other than that, collaboration is good.

In the past, I've had problems with plagiarism on the projects. In this class, whenever you turn something in, the default assumption is that it consists of either your own ideas and words or else material from the class lectures or the textbooks. Whenever this is not true (and it usually won't be true in the projects), then you must say so, or else you're cheating. So if you get an idea from somewhere else (a web site, another book, or even talking with another person), then say where you got the idea from. And if you want to copy the words that somebody else wrote (or said), then go ahead; but put quotation marks around them and say exactly who wrote what and where you read it. You should give as complete citations for the sources as possible; for example, give the complete URL of a web page, or include the page number and edition of a book.

Resources

Some good places to learn about mathematics on the World Wide Web include: You should keep in mind that all of these contain some errors (although in my experience, PlanetMath contains the fewest, and Wikipedia corrects them the fastest). That said, I've been known to make a few mistakes myself from time to time; so think carefully and please let me know if something seems wrong!
This web page and the handouts linked from it were written between 2003 and 2006 by Toby Bartels. Toby reserves no legal rights to them.

Although the page has been preserved in its original form, the handouts linked from it have been converted to DjVu using Any2DjVu; they can be viewed on almost any operating system using DjVuLibre.

The permanent URI of this web page is http://tobybartels.name/MATH11/2006/.

HTML 5