Fall 2017 CS40 Foundations of Computer Science

Instructor and Venue

• Instructor: William Wang
• TAs: Yi Ding (yding@cs.ucsb.edu), Yijun Xiao (yijunxiao@cs.ucsb.edu), and Yanju Chen (yanju@cs.ucsb.edu).
• Grader: Chani Jindal (chanijindal@cs.ucsb.edu)
• Time: M W 2:00am - 3:15pm
• Location: CHEM 1171
• Discussions:
  • Yi, M 4:00pm - 4:50pm, GIRV 1112.
  • Yanju, M 5:00pm - 5:50pm GIRV 1115,
  • Yijun M 6:00pm - 6:50pm PHELP3519.
• TA Office Hours (TA lab at Trailer 935, next to Phelps):
  • Yi, Tu 2:00pm - 3:00pm.
  • Yanju, Tu 3:00pm - 4:00pm.
  • Yijun Tu 4:00pm - 5:00pm.
• 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.
• Acknowledgement:
  • Matthew Turk.

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

Syllabus

• 10/2: Logic and Proofs: Propositional Logic
• 10/4: Propositional equivalences. Required reading: 1.1-1.3.
• 10/9: Predicate logic. Required Reading: 1.4-1.5. HW1 Out.
• 10/11: Predicate logic, rules of inference. Required Reading: 1.6-1.7.
• 10/16: Proof methods and strategy. Required Reading: 1.8. HW1 Due, HW2 Out.
• 10/18: Sets and set operations. Required Reading: 2.1-2.2.
• 10/23: Guest Lecture: Vivek Kulkarni on Sets (cont.) Required Reading: 2.3. HW2 Due, HW3 Out.
• 10/25: Set functions, sequences and summations, cardinality of sets. Required Reading: 2.4-2.5 (excluding Special Integer Sequences and Recurrence Relations in 2.4).
• 10/30: Sets and functions (cont.) HW3 Due, HW4 Out.
• 11/1: Sets and functions (cont.)
• 11/6: Algorithms, The Growth of Functions, Complexity of Algorithms. Required Reading: 3.1-3.3. HW4 Due, HW5 Out.
• 11/8: Midterm Exam
• 11/13: Algorithms, etc. (cont.) HW5 Due, HW6 Out.
• 11/15: Algorithms, etc. (cont.)
• 11/20: Complexity of algorithms; number theory. Required Reading: 4.1-4.3. HW6 Due, HW7 Out.
• 11/22: Induction and Recursion: Mathematical Induction, Strong Induction, Recursive Definitions and Structural Induction, Recursive Algorithms, Program Correctness. Required Reading: 5.1-5.4.
• 11/27: Counting: Basics, Pigeonhole principle, Permutations and combinations, Binomial coefficients and identities. Required Reading: 6.1-6.4 (optional) HW7 Due, HW8 Out.
• 11/29: Probabilistic Logics.
• 12/4: Review session (1). HW8 Due.
• 12/6: Review session (2).
• TBD: Final exam

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

Grades will be based on homework assignments, a midterm exam, and a final exam, as follows:

• 40% Homework assignments
• 30% Midterm exam
• 30% Final exam

All written work should be done professionally - i.e., written legibly, communicated clearly and precisely, done according to the instructions, and submitted on time.

Unless otherwise instructed, all homework assignments must be submitted to GauchoSpace in PDF format before class on the due date (unless specified otherwise). Late assignments will not be accepted - turn in what you have by the due date and time.

There are eight scheduled homework assignments. In order to avoid 1-2 rough weeks from negatively affecting your grade too much, and to help ameliorate the busyness of the two exams, here is the homework grading policy: your lowest two homework scores will be dropped.

You are encouraged to discuss homework assignments with classmates at a general level. However, you may not share answers/code or collaborate on solutions unless otherwise directed to do so. All work turned in must be completely your own. (See the Policy on Academic Integrity, below.)

Make-up exams will not be given except under very exceptional circumstances, which must be first approved by the dean's office.

Questioning a grade: You have a maximum of two weeks after an assignment has been graded and made available to question the grading. To do this, first contact the TA or Reader who graded the problem(s) in question. If a disagreement over grading cannot be resolved, come to the instructor next available office hour.

Please keep your graded materials throughout the quarter. If there is a discrepancy between your grade and the recorded grade, bring this to the attention of the TAs or instructor ASAP.

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.