MA 210: Introduction to Mathematics of Computer Science — Spring 2014

Course Syllabus

Instructor

Joel Ross
email: jross@pugetsound.edu
office: Thompson 405
phone: x3558

Class Meetings

Mon/Wed/Thu/Fri 10:00am to 10:50am (MWF Thompson 399, Th Thompson 310)

Website: http://cs.pugetsound.edu/~jross/courses/ma210/
Moodle: https://moodle.pugetsound.edu/moodle/course/view.php?id=7405
WeBWorK (Homeworks): http://webwork.pugetsound.edu/webwork2/SP14_MA210
Note that you must be on campus to connect to the WeBWorK server; if you are not on campus, you can connect using a Virtual Private Network (VPN)

Office Hours

Mon through Fri 11:30am to 12:30pm, whenever my office door is open (which is often), or by appointment.

Course Description

An introduction to the mathematics underlying computer science. Topics include a review of basic set theory, logic (propositional and predicate), theorem proving techniques, logic as a method for representing information, equivalence relations, induction, combinatorics, graph theory, formal languages, and automata.

Prerequisites: None, though CS 261 will provide context for examples.

Course Goals

After completing this course, a student will be able to:

Textbook

Doerr and Levasseur. Applied Discrete Structures. Online. This is a free textbook (CC license) that covers most of the topics of the course, though we will be jummbling the order a bit.

For the second half of the course, we'll be trying out a separate (better?) textbook:

  • Rosen. Discrete Mathematics and Its Applications, 7th Edition. McGraw-Hill 2011. Chapters 10-14.

The relevant chapters (10-14) and problems from this textbook are available as a course reader from the bookstore. Note that the goal is to start working out of this text on Fri, 03/28.

There are a couple of other texts that I will be drawing examples from; you may find one to be a helpful resource:

If you find another useful texts or resources, please let me know so I can share them with the class!

Resources

Course Components

Homeworks

Homework will be conducted through WeBWorK, an online homework system (it's similar to the Moodle Quizzes, but intended for math and sciences). The homework site can be found at http://webwork.pugetsound.edu/webwork2/SP14_MA210 (you must be connected to the campus network to access). You can log in using your Puget Sound login as a username, and your student id as the password.

Note that you can work on problems individually, and in any order. You can submit and find out the answers to one problem before answering another. This is not like an exam. You will often be allowed unlimited "attempts" for each problem, so you can see if you got the answer right (and if not, you can fix it!) However, multiple-choice questions will only have 2 or 3 attempts available--be sure and check your work before you submit each answer!

Homeworks will be divided into problem sets of around 8-12 problems each, with one set due each week--on Sunday at 11:59pm, unless otherwise noted. Homework deadlines are strictly enforced by the system, so try to do a couple problems every day. Homework sets will be completed entirely on your own--you should not consult with classmates (you are of course welcome to use the text, notes, and other provided resources).

Homeworks are worth 20% of the course grade in total.

REVISION (03/04):

Due to a less-than-optimal-connection between homeworks and exams, the homework component of this course will be adjusted as follows:

Homeworks will be assigned from the problems in the textbook (problems are listed on the schedule below). Problems will include a mix of problems with and without provided answers. There will still be around 8-12 problems a week, so try to do a couple each day.

Homeworks will be submitted (on paper) each Monday at the start of class. Homeworks will be graded on "completion" credit--I'll check that you have in fact worked through and answered the problem, though won't necessarily check the answer is correct. Each student must submit their own answers, though you are welcome to ask for help and/or work through a problem with other students if that helps clarify the course material.

Note that for the time being, webwork problems will still be made

Exams

There will be five (5) one-hour section exams held in class--exam days are indicated on the calendar. Each exam covers 2-3 "topics" or chapters. The lowest exam score will be dropped. All together, Section exams are worth 50% of the course grade.

There will also be a comprehensive final exam. Our final exam time is Wednesday, May 14 at 8am. Note that I will likely allow you to work on the exam for longer than the scheduled two hour exam time. The final exam is worth 25% of the course grade. Note that improvement on the final exam can also "bump up" borderline grades.

Participation

You are expected to be an active participant in this class, and this course component reflects that. The best way to earn participation points is to be both physically and mentally present! Show up to class, ask and answer revelant questions, share an opinion, and otherwise contribute to a conducive learning environment. Participation is worth 5% of the course grade.

A note about grades: final grades are determine neither on a formal curve (with equal numbers of As and Fs, Bs and Ds, and so on) nor necessarily on a fixed, straight scale. The following scale provides upper bounds--that is, your grade will not be lower than indicated, but may very well be higher: A >= 95, A- >= 90, B+ >= 87, B >= 83, B- >= 80, C+ >= 77, C >= 73, C- >= 70, D+ >= 67, D >= 63, D- >= 60, F

REVISION (03/04): I have added an extra credit assignment option for this course.

Course Policies

Respect

This class may involve in-class discussion of topics on which you and your classmates may have differences in opinion. Please be respectful of others (students or otherwise) at all times.

Correspondence

I will send out course announcements and information by email, so you should check your email daily. Note that this email will go to your pugetsound.edu address. If you prefer to read your email on another account, you should set your Pugetsound account to forward your email to your preferred account (see http://www.pugetsound.edu/files/resources/6291_ForwardWebmail.pdf).

When emailing me, please make sure to sign your emails! This will let me know who is writing, and will help me to better answer any questions.

My office hours are listed above. I am more than happy to talk about any questions or concerns you may have about the course or its material. I highly recommend you take advantage of professor's office hours; it's one of the greatest benefits of attending a school like UPS.

Attendance

Make every effort to attend each class meeting; while the textbook will act as a resource, things will make a lot more sense when we discuss them in class. We will also cover some material that isn't directly in the textbook and so can't be found anywhere else. Classes will begin and (usually) end on time. Please do your best to get to class before the start of the hour. Students are expected to attend all lectures, with exceptions permitted in case of illness and family emergencies. I reserve the right to drop from the course any student that misses 5 or more classes.

Technology in Class

The use of cell phones and laptops will not be permitted in class unless specific permission is given. Please silence all cell phones/pagers/etc. before the beginning of each lecture.

Late Work

In this class, late assignments will not be accepted. If it looks like you will miss a due date, let me know ASAP.

Academic Honesty

Please review the Academic Honesty Policy in the Student Handbook and ask me if you have any questions regarding its application to this course. All graded work (including homework) should be entirely your own. The consequences of academic dishonesty are not worth the risks. The simple rule is: do not claim anyone else's work, code, words, or ideas as your own. If you're in doubt, come talk to me in advance.

Special Accommodations

Academic accommodations are available for students with disabilities who are registered with the Office of the Office of Accessibility and Accommodations. If you have a physical, psychological, medical or learning disability that may impact your course work, please contact Peggy Perno, Director of the Office of Accessibility and Accommodations, 105 Howarth, 253.879.3395. She will determine with you what accommodations are necessary and appropriate. All information and documentation is confidential.

I also encourage all students having difficulty, whatever the reason, to consult privately with me at any time.

Emergency Procedures

Please review university emergency preparedness and response procedures posted at http:www.pugetsound.edu/emergency/. There is a link on the university home page. Familiarize yourself with hall exit doors and the designated gathering area for your class and laboratory buildings.

If building evacuation becomes necessary (e.g. earthquake), meet your instructor at the designated gathering area so she/he can account for your presence. Then wait for further instructions. Do not return to the building or classroom until advised by a university emergency response representative.

If confronted by an act of violence, be prepared to make quick decisions to protect your safety. Flee the area by running away from the source of danger if you can safely do so. If this is not possible, shelter in place by securing classroom or lab doors and windows, closing blinds, and turning off room lights. Lie on the floor out of sight and away from windows and doors. Place cell phones or pagers on vibrate so that you can receive messages quietly. Wait for further instructions.

Course Calendar

Below is a very approximate schedule for the course. It includes a list of topics to help students plan their work in this course, as well as assignments and relevant book chapters. Note that this schedule is tentative and subject to change; all changes will be announced in class, and I will do my best to keep this schedule updated. Any changes to due dates or exam dates will be announced.

Week Date Topic Textbook Homework
1 01/20 Introduction; Set Notation 1.1-1.3, 1.5 Hwk Set 0 due Thu
Hwk Set 1 due Sun
2 01/27 Logic 3.1-3.4, 3.6, 3.8 Hwk Set 2 due Sun
3 02/03 Proofs
Exam 1 Friday 		3.5, 3.7, 3.9 Hwk Set 3 due Sun
4 02/10 Set Theory; Combinatorics 4.1-4.4; 2.1, 2.3 Hwk Set 4 due Sun
5 02/17 Combinatorics; Vectors 2.2, 2.4; wikibook Hwk Set 5 due Sun
6 02/24 Matrices
Exam 2 Friday 		5.1-5.6, 12.1-12.3 Hwk Set 6 due Sun
7 03/03 Relationships 6.1-6.5 6.1: 1a, 2a, 6;
6.2: 4a;
6.3: 4b, 5abc, 7abc;
6.4: 4a, 7;
6.5: 5ad;
Sup: 8, 10bc, 16, 17bc;
8 03/10 Functions
Exam 3 Friday 		7.1-7.3 7.1: 3, 5, 6 (challenge!)
7.2: 3, 4, 8ab, 12
7.3: 1
Sup: 1, 5, 14, 15,
Spring Break
9 03/24 Recurrence Relations D&L 8.1-8.4


Fri: Rosen 10.1 - 10.2 (p655) 		D&L 8.1: 5
D&L 8.2: 1, 4
D&L 8.3: 2-7, 11, 15
Rosen 10.1: 1, 12, 13
Rosen 10.2: 5, 13, 20
10 03/31 Graphs Mon: Rosen 10.2 (p656) - 10.3
Wed: Rosen 10.4
Thur: Rosen 10.5 (10.6 optional)
Fri: Rosen 10.7 - 10.8 		10.2: 26abc, 33, 51, 59abc
10.3: 11, 29, 41, 57ab, 66
10.4: 16, 29, 56, 57, 59
10.5: 16, 26abc, 58, 59, 60
10.7: 7, 13, 15, 18, 23, 28[extra credit!]
10.8: 3, 12, 19, 23
turn in even problems!
11 04/07 Trees Mon: Rosen 11.1, 11.2 (skim okay)
Wed: Rosen 11.3 (skim okay), 11.4
Thur: Rosen 11.5 		11.1: 11a, 15, 16, 21, 37, 39, 42
11.4: 1, 19, 25, 26(#8), 44, 47
11.5: 5, 10 (Kruskal only), 12, 13, 21, 35
turn in even problems!
12 04/14 Boolean Algebra
Exam 4 Monday 		Wed: Rosen 12.1
Thu: Rosen 12.2
Fri: Rosen 12.3 		12.1: 7, 25, 27, 31, 39
12.2: 1, 3, 5, 9, 15
12.3: 3, 6b, 9, 13, 15, 17 (optional)
turn in all problems!
13 04/21 Formal Languages & Finite State Machines Mon: Rosen 12.4
Wed: Rosen 13.1
Thu: Rosen 13.2
Fri: Rosen 13.3 		12.4: 23c, 25c, 9 [optional]
13.1: 5, 13, 19a-d, 29, 33
13.2: 1b, 2a, 3b, 11
13.3: 5c, 19, 25, 33, 37, 49
14 04/28 Regular Languages & Turing Machines Mon: Rosen 13.4
Wed: Rosen 13.5 		13.4: 1, 3, 13b, 5cde, 15
13.5: 1, 5, 7, 31 [optional]
15 05/05 Conclusions
Exam 5 Monday
Finals Final Exam: Wednesday 05/14, 8:00am