Instructor: Phill Conrad
Course Meetings:
LEC MWF 200- 250 CONRAD P T PHELP 1425
Discussion Sections:
07690 W 1100-1150 PHELP 1401
07708 F 900- 950 GIRV 2119
Contact Email: pconrad at cs.ucsb.edu,
Office Hours: Monday and Wednesday, 3:30-4:30, or by appointment, Harold Frank Hall Room 1113
What this course is about
Computer Science is more than just programming. It is also a way of thinking about computation and problem solving—a certain way of looking at problems. In a sense, you could say that this course lays the foundation of everything you'll study in Computer Science that goes beyond just programming.
As it turns out, that foundation is a mathematical foundation. So, this is going to feel more like a math class than any programming class you've taken so far. But, even that may be misleading, for it won't probably feel like any math class you've ever taken—except perhaps for High School Geometry. Why Geometry? Because in the course, we emphasize starting from definitions and axioms, and then proving theorems.
Most of the problems you'll solve, therefore, are very unlike algebra, trig, or calculus, where you slog through pages of problems where the techniques are all laid out—you just apply the technique and derive the answer. That math can get sort of tedious, but is has the advantage that if you just learn the technique, the answer is straightforward.
In this class, it isn't always clear how to get the answer. As Euclid reportedly said to King Ptolemy, "there is no royal road to mathematics". Therefore, this kind of math requires creativity and problem solving.
But I just want to be a programmer or an engineer. Why do I need to learn this stuff?
You might be majoring in computer science (or computer engineering, or some related field) because you enjoy writing code, or thinking about designing systems. It can be difficult, at first, to see the value of what we are learning in this course. It can seem very abstract, or theoretical, and you might question the value. You might ask:
Doesn't the real world involve actually writing code? When will I ever need this stuff?
It turns out that many of the most interesting programs you will ever write—for example, programs to calculate the shortest path through a network, to compile code for a new programming language, or to find the best molecule from a database of chemicals to test as a new life-saving drug—these programs all rely heavily on material you will learn in this course. Graph theory, sets, functions, relations, predicate logic, probability—these all come up in later courses, including networks, compilers, AI, databases, architecture, and more. In the course, we lay the foundations of computer science (hence the course title).
But what about the theorem proving? Will I ever need to prove a theorem in the real world?
This is the most challenging question to answer, and rather than answer it directly, I'm going to offer what in the practice of Zen is called a Koan—a puzzling dialogue that at first seems absurd, but when you penetrate the meaning of the answer, you will understand in a way that goes deeper than conventional language.
Koan:
The student asks: "Why do I need to prove theorems to be a programmer?"
The teacher responds: "Wax on, wax off."
The solution to the koan is left as an exercise to the student. I'll offer some hints on the first day of class.
Catalog Description:
Propositional predicate logic, set theory, functions and relations, counting, mathematical induction and recursion (generating functions)
Prerequisites: Computer Science 10 or 12 and Mathematics 3C
Textbook(s): Kenneth Rosen, Discrete Mathematics and Its Applications, (6th edition) McGraw Hill. 2007
Grading:
50% Homework/Quizzes + 20% Midterm + 30% Final Examination
Quizzes may occur at anytime, announced or unannounced. Missed quizzes may not be made up.
Thus attendance is required, and reading the assigned readings is required.
A conventional 10 point scale will be used to map your numeric average into a letter grade, with the lower three and upper three points of each range representing plus/minus.
| grade >= 93 | A | 73<= grade < 77 | C | |
| 90 <= grade < 93 | A- | 70<= grade < 73 | C- | |
| 87 <= grade < 90 | B+ | 67 <= grade < 70 | D+ | |
| 83<= grade < 87 | B | 63<= grade < 67 | D | |
| 80<= grade < 83 | B- | 60<= grade < 63 | D- | |
| 77 <= grade < 80 | C+ | grade < 60 | F |
This 10 point scale represents the minimum letter grade you will be assigned—at the instructor's discretion, the letter grade scale may be altered in the students' favor if this will be better reflect the students' mastery of the material. Thus, if there is a "curve", it will be applied at the end, not to individual assignments.
Academic Honesty:
You should read and understand the UCSB policy on academic honesty listed below. You should also understand that I take academic honesty and personal integrity very seriously, and will do my best to uphold and enforce this UCSB policy.
It is expected that students attending the University of California understand and subscribe to the ideal of academic integrity, and are willing to bear individual responsibility for their work. Any work (written or otherwise) submitted to fulfill an academic requirement must represent a student’s original work. Any act of academic dishonesty, such as cheating or plagiarism, will subject a person to University disciplinary action. Using or attempting to use materials, information, study aids, or commercial “research” services not authorized by the instructor of the course constitutes cheating. Representing the words, ideas, or concepts of another person without appropriate attribution is plagiarism. Whenever another person’s written work is utilized, whether it be a single phrase or longer, quotation marks must be used and sources cited. Paraphrasing another’s work, i.e., borrowing the ideas or concepts and putting them into one’s “own” words, must also be acknowledged. Although a person’s state of mind and intention will be considered in determining the University response to an act of academic dishonesty, this in no way lessens the responsibility of the student.
(Section A.2 from: http://www.sa.ucsb.edu/regulations, Student Conduct, General Standards of Conduct)
Course Goals:
To explain the basic concepts of discrete mathematics as they arise in computer science and, whenever practical, show how they are applied. Learn mathematical induction and proof techniques. Learn mathematical reasoning.
Prerequisites by Topic: Programming experience, Calculus with applications
Major Topics Covered in the Course
(Note: hours listed in square brackets represent the approximate amount of class time spent on each topic.)
Propositions; logical connectives; contradictions & contingencies; truth tables; well-formed formulae; the laws of logic; rules of inference; methods of proof
Open statements; quantifiers and their negation; inference rules; applications of logic
What is a set? Notations for sets; Russell's paradox; Kurt Godel; complements; operations on sets; laws of set theory; proofs in set theory; the Venn diagram
Cartesian products; functions and operations on them; sequences; growth of functions; languages; relations; equivalence relations, partial orders and posets
The sum and product rules; binomial coefficients; permutations and combinations; the principle of inclusion-exclusion; occupancy problems; the pigeonhole principle
Sample spaces and events; random variables and moments; the birthday paradox
Generating functions; recursion; the Fibonacci numbers; solving 2nd order constant-coefficient; homogeneous linear recurrences; convolution
Divisibility; modular arithmetic; prime numbers; the Mersenne primes; theorems of Euler and Fermat
Basic concepts; bipartite graphs; Hall's Theorem
This syllabus is as accurate as possible, but is subject to change as the instructors discretion, within the bounds of UC policy.