CS103a - Discrete Mathematics
CS103 is the first of a two-quarter sequence (CS103B is next quarter.) Both courses together constitute an in-depth course in discrete mathematics. This is the area of mathematics that deals with the study of discrete objects, where "discrete" means distinct or unconnected. Discrete math is used, for example, whenever objects are counted, when relationships between finite sets are studied, and when processes involving a finite number of steps are analyzed. This area of math has become increasingly important because information is stored and manipulated in a computer in a discrete fashion.
Discrete math provides the mathematical foundations for many computer science courses including data structures and algorithms, compilers, automata theory and formal languages, operating systems, database theory, to name a few. You will find these courses much more difficult if you attempt them without the foundations of discrete math.
Our goal in this course is to build skills and give you experience in the following areas:
- Mathematical Reasoning: The ability to construct a sound logical argument is essential for computer scientists, not only because proofs are important in certain areas of computer science, but also because the same basic thought process is used in constructing a proof and in writing a program.
- Combinatorial Analysis: An important problem solving skill is the ability to count or enumerate objects. It pops up surprisingly often in computer science applications.
- Discrete Structures: These are the abstract mathematical structures used to represent discrete objects and relationships between those objects. Discrete structures include sets, permutations, relations, trees, graphs and finite-state machines. These structures form the conceptual basis for many of the data structures that we use as programmers.
- Algorithmic Thinking: Certain classes of problems are solved by the specification of an algorithm which can be implemented in a program. The mathematical portions of this activity (which will interest us most) include the specification of the algorithm, the verification that it works properly, and the analysis of the computer memory and time required to perform it.
- Applications and Modeling: Discrete math has applications to almost every conceivable area of study including (of course) computer science, chemistry, botany, zoology, linguistics, geography, business, etc. Modeling with discrete math is an extremely important problem-solving skill.
Pre-Requisites
There are no pre-requisite for this course, but the student is assumed to have some experience with programming.Lectures
Monday, Wednesday, Friday at 10:00 in 420-040 (the psych building).Sections
There will be a weekly section where you can meet with a TA for an hour in small groups. The primary purposes are to review material from the lectures and/or to work problems that exercise your understanding. Participation in sections is not required, but can be very helpful especially if the material is new to you. Section time and location will be announced the first week of the quarter."Working" Office Hours
Each week, two of our TA's will hold office hours in a classroom where you can come and work on problems from a problem set or the textbook. The TA will be available to answer questions when needed. The purpose of this is to provide students with additional options for obtaining assistance besides section, and one-on-one office hours.Problem Sets & Exams
There will be weekly problem sets that will not be graded. We will provide solutions to these problems sets so you may check your own work. It is essential that you work through all the problems on the problem sets - you will not pass the exams without doing so. We prefer that you do your own work on problem sets since you will be on your own when you take the exams. The reason for this class structure is we want you to obtain feedback on your solutions as soon as possible after you have done the problem. It's been our experience that this feedback is essential to building strong skills. If your solutions differs from our solution, we are providing many opportunities (section, office hours, help line) for you to contact us with your questions. It is your responsibility to stay on track. It will simply not be possible to do all the problems on the problem sets right before the exam. The skills that are developed in doing the problem sets are built up gradually. It cannot be done in one night. There are four exams in CS103a. The first three are 24-hour take home exams, and the last is an in-class final. Exams must be taken during the 24-hour period specified in the syllabus, so please plan your time accordingly.Grading
Final grades will be based on the following:15% Exam1
25% Exam2
25% Exam3
35% Final
To receive a passing grade, you must complete passing work in both the exam and problem set area.
Textbook
There are two required textbooks that you can purchase in the bookstore. Additional materials will be provided in class. If you miss picking these things up in class, you can obtain them from the handout bin in Gates (if any are left over), or from our web page.There will be regular reading assignments and most of our problem sets will come from the text book. Lecture materials will sometimes cover material in the textbook, but will more often present supplementary materials and additional examples.
Rosen, K., Discrete Math and Its Applications, New York: McGraw-Hill,1999, and the Student Solutions Guide. Barwise, J. & Etchemendy, J. Language, Proof and Logic, New York: Seven Bridges Press, 1999.
This book and the solutions guide are excellent resources. You will find many examples that can
serve as models for the problems on the problem sets.
How to Succeed
The best way to obtain the skills required to succeed in this course is to practice solving problems
- lots and lots of problems. The textbook (and the associated web site) provide many practice
problems with detailed solutions given in the Solutions Guide.
The Solutions Guide also has a guide to writing proofs, a list of common mistakes,
sample exams, etc. So the way to succeed in CS103a: come to class where you will see especially
important examples and applications, stay on schedule by doing a part of
the current problem set each day after class, study the textbook and solutions guide carefully and thoroughly,
and come and see us if you need help (or write to the help line). Most
importantly, if you are feeling confused, frustrated or worried about anything pertaining to the
course, let us know.
Honor Code
You may do problem sets anyway that works best for you. It's best if you
work on the problems yourself since this is the best preparation for the
exams. You may discuss problem set questions with a partner or study
group. Just remember, you have to be able to do the problems yourself.
Exams are to be done individually and must represent original work -
It is a violation of the honor code to copy or derive exam question
solutions from anyone, from textbooks, or from previous instances of this
course.
