MATH/CS 11

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

My office hours will be in Surge 263, on Mondays through Thursdays from 11:30 to 1: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 to look up 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 for three things:

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 here. (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. This traditional 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) will be special material required only 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 would have to stretch pretty hard 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.

Textbooks and handouts

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 don't have to buy the other one. Both of these books 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).

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 the Lipschutz & Lipson textbook mentioned above. 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.

You can buy books online usually cheaper than at the bookstore (but then there are shipping delays):

There have also been two supplementary handouts on rules of inference. The first one covers material that's not (completely) in either book but which you are still responsible for knowing:

The second one gives templates (in diagrammatic form) for the various rules of inference; this material is pretty idiosyncratic (although I've based it on the teaching of Paul Taylor, a theoretical computer scientist in England), so you won't be required to know it. Nevertheless, it may help you to use the rules of inference to find proofs:

Syllabus

The topics to be covered include: I will post a more complete syllabus online.

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 on the back of the assignment sheet; 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. 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 before it is due.

Each week (except the last), I will also assign a 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.

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. Do not turn in anything that you copied from another person (except for properly cited quotations), and do not let other students copy from what you plan to turn in.

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.

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

Final exam

The final exam will be July 22 Friday from 10:30 to 12:30. To help you prepare, here is a mock final: The mock final is longer than the actual final, but the questions are very similar.

Resources

Some good places to learn about mathematics on the World Wide Web include:
This web page and the handouts linked from it were written between 2003 and 2005 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/2005/.

HTML 5