Phone: X2704
Home Phone: 781-862-5107
Office Hours: MWF 7:30-8:00
Mon
Wed
Fri
Please give me a 'heads up' if you plan to come during lunch.
Note: There is no class on
at
Homework
Assignments
Unit 1: Logic, Set Theory and
Cirucit Design
Unit 2: Algorithms, Cardinality
and Complexity, with Appalications to Cryptography
Unit 3: Mathematical Induction
Unit 4: Combinatorics
Unit 5: Graphs and Trees
This course has two major goals: to learn certain material fundamental to mathematics and computer science, and to increase your sophistication and ability in handling abstract problems. In order to achieve these goals you will be very 'hands on' through out the course; you will spend a lot of time talking about and writing about mathematics. That is, this is a course with a lot of small group work and much less lecturing than most math courses. This means that the course is a lot of fun (especially since the material itself is a lot of fun) . It also means that it is critical that you do the assigned reading before class and are well prepared for class. Remember that your entire group is depending on you!
Reading mathematics is sometimes slow going, and a section will usually require two or three readings. It is a good idea to read the section first for the general flow of ideas, skipping over anything that doesn't seem obvious. On the second and third readings, now that you know where the book is heading, you should read the book closely, making note of anything that does not make sense, or any calculation you can't follow.
As you re-read, you may also choose to make a note to yourself to ask about something in class. For example, 'p. 37, line 4 doesn’t make sense' is a fine thing to ask about in the beginning of class (and a lot more helpful than 'I'm lost'.) I encourage you to ask questions in class; it is rarely the case that only one student finds something mysterious. If I do not ask for questions at the beginning of class, and you have some, please ask your questions.
All assignments are from your text. In each assignment you are expected to read carefully the section of the book from which the problems are assigned. Although we may not have time to discuss all the material in class, you are responsible for everything in those sections unless explicitly told otherwise. Indeed, because the aim of the course is to increase your sophistication, as the course progresses you will be asked to 'dig out' more of the material on your own.
Talking about mathematics: A lot of class time will be used to work on problems in small groups. These problems will be similar to those due for homework. In order to contribute to your group you must read the material and try some of these problems before coming to class. The purpose of the small group work is to get you to talk about mathematics as a way to master it and to help you develop strategies for problem solving.
Writing about mathematics: Understanding mathematics also means being able to write about it. This course is 'writing intensive.' There is a writing assistant (WA) for the course. I am very excited about the emphasis on writing in this course. Just as the small group work entails a lot of talking about math as a way to understand it, the assignments also require a lot of writing about math as a way to understand it. So you will find many small assignments - writing proofs and problem solutions. The writing assignments will be handed in.
Grading: There will be a test or other summative effort at the end of Units 1, 3, and 4, and a final. (Unit 2 is included in the Unit 3 test; Unit 5 is on the final) Each of the tests and the final count equally.
Accommodations for Special
Needs: Reasonable accommodations will be provided for students with
documented physical, sensory, systemic, cognitive, learning, and psychiatric
disabilities. If you have a disability and anticipate that you will need a
reasonable accommodation in this class, it is important that you contact the
Academic Support Center Director at 617-521-2471 early in the semester.
Students with disabilities receiving accommodations are also encouraged to
contact their instructors within the first 2 sessions of the semester to
discuss their individual needs for accommodations.
In the first part of the course we examine Aristotelian or truth table logic and its equivalences to set theory, Boolean algebra and design of logic circuits for computers.
Our study of logic gives us a chance to make precise what is meant by saying that two statements are equivalent, that one implies another, or that a statement is a tautology or fallacy. We also study some of the basic rules of reasoning, such as modus ponens, syllogism and De Morgan's laws.
Truth table logic is equivalent to naive set theory, which most of you have seen before (Venn diagrams for intersection and union) . They are also equivalent to certain simple circuits - series and parallel circuits to implement 'and' and 'or' gates in computers. We will examine the correspondences, see how to design circuits for functions such as addition in a computer, and how a logical or Boolean expression may be written in conjunctive or disjunctive normal form.
Quantified logic introduces the phrases 'for all' and 'there exists'. You will translate English, database, and mathematical statements into this format , and learn how to negate quantified statements. In this context we will discuss the difference between and an example and a proof. We will apply our knowledge to writing focused queries for Internet searches and for databases.
We will learn in Unit 2 what it means when we say that truth table logic is 'complete', 'consisten'” and 'decidable'.
Unit 2 - Algorithms, Cardinality and Complexity, with Applications to Cryptography
Mathematicians, in addition to worrying about what it means to prove something and how to prove things, also spend a lot of time thinking about measuring things. In this part of the course we will discuss what it means for two sets to have the same number of elements ( or cardinality ). For example, we will ask if all infinite sets are the same size. This material requires us to review certain concepts about functions dž one-to-one, onto and inverse functions.
In addition to measuring sets, we will also try to measure how hard a problem (such as factor an integer into primes) is, or the complexity of the algorithm to solve it.
Quantified logic does not have the neat characteristics (complete, decidable) of truth table logic. We revisit these notions and learn about Russell's paradox, Godel's Incompleteness Theorem (a fundamental result in the foundations of mathematics) and about the Halting Problem and 'P=NP?' (the fundamental outstanding problem in foundations of computer science).
We will see how hard problems are valuable to people trying to protect computer systems from hackers.
Unit
3 - Mathematical Induction
In this section of the course we use out knowledge of quantified logic to talk about valid and invalid arguments.
We then move on to one of the most important tools mathematicians have for proving theorems - Mathematical Induction. We will spend a significant amount of time mastering induction (both Strong and Weak forms). We will examine briefly Peano's Postulates for the integers, and, in computer science, recurrence relationships and recursion, and how these matters are related to mathematical induction.
Unit
4 – Combinatorics
Here we study basic ways of counting: the pigeon-hole principle, the law of inclusion-exclusion, the binomial theorem (and Pascal’s triangle), counting permutations and combinations, and some discrete probability. The relationships of probability to set theory and measurement tie this to Units 1 and 2 of the course. A substantial amount of effort is expended on leaning how to analyze these problems.
Unit
5 - Graph Theory and Trees
The basic notions of graph theory are introduced - vertices, edges, degree of a vertex, connected components, directed and undirected graphs, and acyclic graphs or trees. The notion of isomorphism (and its usefulness in mathematics) is discussed.
As time allow, a variety of graph theory problems and their solutions will be explored -Eulerian and Hamiltonian graphs, graph coloring, minimal spanning trees, etc. - as well as applications of graphs and trees to real world problems.
All assignments are from
your text.
Please reread the material
on “Approach to the Course”.
The “Problems” listed below are the ones you are to hand in. You may choose to check your understanding of the book by working odd-numbered problems (answers in the back of the book). In other words this list is a minimum, not a maximum assignment.
The “Lab Problems” are to be worked in class. Any lab problems your group doesn’t “get to” should be finished outside class, but not handed in.
The “Writing Assignments” are to be your individual work (with the help of the WA) and are to be handed in. Each test will include a writing assignment (to be done individually and without the help of the WA).