Fall 2017 CS40 Foundations of Computer Science

Instructor and Venue

• Instructor: William Wang
• TAs: TBD
• Grader: TBD
• Time: M W 2:00am - 3:15pm
• Location: CHEM 1171
• Discussions: M 4:00pm - 4:50pm GIRV 1112, M 5:00pm - 5:50pm GIRV 1115, M 6:00pm - 6:50pm PHELP3519
• TA Office Hours: TBD
• Instructor Office Hours: M 4:30-5:30 HFH 1115
• Prerequisites: Computer Science 16 with a grade of C or better and Mathematics 4A with a grade of C or better.

Course Objective

We follow the course goals set by Prof. Matthew Turk's previous offering of CS 40.

To learn and be able to apply basic knowledge of:

• Logic - propositional logic, predicate logic, rules of inference
• Proofs - proof methods and strategies
• Sets and functions - sets, set operations and functions, function types
• Algorithms and complexity
• Relations - representing relations and their properties; orderings
• Recursion and induction
• Counting - counting methods, permutations and combinations
• Number theory - divisibility and modular arithmetic

As an instructor, my goals are to help you to become more of a self-directed learner, i.e. to learn how to learn on your own. Self-directed learning, like any skill, takes practice.

What you will learn

By the end of the quarter, you should understand the basic concepts of logic, proofs, sets, functions, algorithms, proof techniques, counting, and relations - and have some insight into how these relate to more advanced topics in computer science. You will gain experience, both conceptually and practically, by homework assignments that involve solving problems and implementing learned concepts and techniques.

Piazza

Please enroll if you haven't: piazza.com/ucsb/fall2017/cs40

Course Description

The course provides an introduction to the theoretical underpinnings of computer science. Topics include propositional predicate logic, set theory, functions and relations, counting, mathematical induction and recursion (generating functions). It prepares students for concepts and material in upper-division CS courses and beyond. Overview

This course introduces you to the discrete mathematics that underlies much of computer science and is needed to understand a wide range of computing topics (and to successfully complete your computer science degree). Learning to produce and write mathematical proofs is a central theme of the course. CS 40 will prepare computer science students for the mathematical knowledge and maturity required by some upper division courses, such as the courses on algorithms, automata, formal languages, and artificial intelligence.

Text Book

There is a required textbook from which reading and homework will be assigned throughout the quarter:

• Required: Discrete Mathematics and Its Applications (7th edition), by Kenneth H. Rosen, McGraw Hill Press, 2012.
  • This is available at the UCSB bookstore and at Amazon.com. It is rentable at Amazon. There are used books to be bought at UCSB.
  • Online student resources for textbook
  • Two copies of the textbook for 2-hour checkout are available in Course Reserves at Davidson Library.
  • The 6th edition of the book can be useful, but there will be homework assignments from the 7th edition, and it is each student's responsibility to learn the material and have access to the homework problems in the 7th edition.

Grading

There will be four homework assignments (40%), one mid-term exam (20%), and a final exam (40%). Four late days are allowed with no penalty. After that 50% will be deducted if it is within 4 days after the due day, unless you have a note from the doctors' office. Homework assignment submissions that are five days late will receive zero credits. Your grade can be found on GauchoSpace.

Academic Integrity

We follow UCSB's academic integrity policy from UCSB Campus Regulations, Chapter VII:``Student Conduct and Discipline"):

• 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.

More specifically, we follow Stefano Tessaro and William Cohen's policy in this class:

You cannot copy the code or answers to homework questions or exams from your classmates or from other sources; You may discuss course materials and assignments with your classmate, but you cannot write anything down. You must write down the answers / code independently. The presence or absence of any form of help or collaboration, whether given or received, must be explicitly stated and disclosed in full by all involved, on the first page of their assignment. Specifically, each assignment solution must start by answering the following questions:

• (1) Did you receive any help whatsoever from anyone in solving this assignment? Yes / No.
  • If you answered 'yes', give full details: (e.g. ``Jane explained to me what is asked in Question 3.4")
• (2) Did you give any help whatsoever to anyone in solving this assignment? Yes / No.
  • If you answered 'yes', give full details: (e.g. ``I pointed Joe to section 2.3 to help him with Question 2".
• No electronics are allowed during exams, but you may prepare an A4-sized note and bring it the exam.
• If you have questions, often ask the teaching staff.

Academic dishonesty will be reported to the highest line of command at UCSB. Students who engage in such activities will receive an F grade automatically.

Accessibility

Students with documented disability are asked to contact the DSP office to arrange the necessary academic accommodations.

Discussions

All discussions and questions should be posted on our course Piazza site.

Attendance

Class attendance is required: you are responsible for everything that goes on in class. "I wasn't there" and "I didn't know" are not valid excuses for missing something important. Prepare in advance by studying the assigned reading before coming to class and by making sure you understand the previous lecture. If you feel lost during the quarter, read the assigned reading first; then talk to the TAs and/or the instructor.

Weekly one-hour discussion sections, led by TAs, will focus on (1) presenting supplementary material (such as practical examples) to the lectures and (2) answering questions (about lecture topics, homework problems, etc.). Come prepared to ask questions - the "no such thing as a stupid question" concept applies here! Students are required to attend these sessions; you are responsible for the material presented in the discussion sessions. Students are encouraged to give the TAs (and, if appropriate, the instructor) feedback regarding topics or issues they would like to have discussed during this time.