CIS Logo SVC Logo

   Computing & Information Systems
   Department

 

Schoology Facebook        Search CIS Site      Tutorials

CS 170 Syllabus



Discrete Structures I



Fall 2018



CIS Department



Saint Vincent College



General Information

  • 3 credits
  • Prerequisite:
    • CS 109, CS 110, MA 109, or MA 111 (any one of these four)
    • The student should have a solid background in high school algebra and precalculus.
  • Instructor: Brother David Carlson
  • Office: Dupre Science Pavilion, Tenley Hall W217
  • Office hours:
    • Mon, Wed 9:30 am - 11:20 am
    • Mon 12:30 pm - 1:50 pm
    • Tue, Thurs 8:30 am - 9:50 am
    • Tue, Thurs 2:30 pm - 4:00 pm
    • and by appointment
  • Phone: 724-805-2416
  • Email: david.carlson@stvincent.edu
  • Text: Discrete Mathematics and Its Applications, 8th ed., Rosen, K., McGraw-Hill (2019), loose leaf version, ISBN 978-1-259731280 or the textbook rental of the same text, ISBN 978-1-259676512.
    • Do not get the e-book version. Our exams are open book, open notes, but e-books are not allowed on the exams.
    • Do not get a different edition or an international edition as there are typically considerable differences in the exercises and sometimes in the chapter material as well. One international edition left out an entire chapter.
  • The CIS lab in W214 of the Dupre science complex will be available according to this schedule that will also be posted on the bulletin board outside our lab.

Description

This course is an introduction to the topics in discrete mathematics that are of particular use in computing. Discrete mathematics is especially concerned with counting techniques and finite or infinite sets of integers (discrete numbers), instead of a continuous range of numbers (such as the real numbers used in calculus). Topics to be covered include logic, sets, functions, simple proof techniques, algorithms, counting techniques, basics of graphs and trees, finite state machines, parsing, and grammars.

Why Take This Course?

The major purpose is to help the student to obtain some fluency in specific areas of discrete mathematics and to encourage the use of the associated techniques in other computing courses (such as CS 310). This course is also a prerequisite for CS 171, Discrete Structures II.

The Prerequisite

The prerequisite gives various possible routes into this course. Any one of those should give reasonable assurance that the student has the background and ability to handle CS 170. Although it helps to have some background in computer programming, it is not strictly necessary for this course.

The Text

This course will cover the essentials of the topics listed above and will usually follow the text fairly closely. The text assumes good abilities in high school algebra and many precalculus topics. Knowledge of calculus is not needed for this course, though the "mathematical maturity" obtained by completing calculus would help one to do better in this course. Thus it is usually best to take introductory calculus before taking this course.

Relevant CIS Department Student Learning Outcomes

By the time of graduation

  1. The CS, IT, or Cybersecurity major will have an ability to design, implement, and evaluate a computer-based solution to meet a given set of computing requirements in the context of the discipline.
  2. The CS major will have an ability to apply theory in the design and implementation of computer-based solutions.
  3. The CS major will have an ability to reason about and explain computer-based solutions at multiple levels of abstraction.

Course Learning Objectives

By the end of the course, students will be able to:

  1. Create new grammar rules to add new features to an existing computer grammar.
    This supports student learning outcomes 1 and 2 above.
  2. Determine the O() running time estimate for various algorithms.
    This supports student learning outcomes 2 and 3 above.
  3. Use propositional logic and first order predicate logic to construct and analyze arguments.
    This supports student learning outcome 3 above.
  4. Prove theorems (of the type covered in the text) using direct proof, indirect proof, and proof by induction.
    This supports student learning outcome 3 above.

Course Policies


Note on Flu

Because of the possibility of the flu affecting us on campus, please practice good hand washing, etc. If you get the flu, please notify me by phone or e-mail and stay home for 24 hours after the fever has gone. Check with me about what you miss. You will not be penalized for missing class in this situtation. It is better to stay away from class and not spread the flu when you are ill.

Grading, Exams, Quizzes, and Homework

  • 25% First Exam
  • 25% Second Exam
  • 25% Final Exam: Wed, Dec 12, 8:30 am - 10:30 am
  • 25% Homework (including WeBWorK) and Class Participation

Letter grades will be assigned according to the scheme found in the current College Bulletin. Exams will be announced in advance. Due to the technical nature of the course, exams will be of the open-book, open-notes variety. Calculators may be used (and are expected to be used) on exams. Cell phones and pagers should be turned off and put away during exams. On a test, students may only use the test itself, books, notes, handouts, calculators, pens, pencils, and erasers. Calculators may not be passed between students. No laptops or other computers may be used on an exam. Calculators and Mathematica are of use in the graphing of functions and in certain other parts of this course. These can also be used to aid in doing homework.

We will be using the WeBWorK online homework system for some of the homework this semester. This will provide you with more feedback and assistance in doing homework than what is typically available with written homework. The system will usually allow you more than one attempt at a problem, and may even give a hint. It will also show you the answers after the due date, which is useful in learning how to solve problems that you did not get and in studying for exams. However, there will be written homework for some of the topics in the course. On occasion a written homework assignment might be collected and graded. Homework and test answers are expected to be written using good English and good mathematics. These items will be graded on the correctness of the steps used to get the answers, as well as the answers themselves, and (with a lesser weight) the clarity of their presentation. That last category is intended to help the student to develop good written communications skills. If time allows, students may sometimes be asked to present at the board solutions to homework problems and be graded on these presentations. The purpose is both to help others with the problems and to assist the students doing the presentations in developing good communications skills.

Homework (including WeBWorK) and exams will ask critical thinking questions that require careful analysis, mathematical explanation and/or proof, and meaningful conclusions. For example, given some algorithm, you might be asked to estimate its running time by determining the most important instructions that get repeated, counting them, and then generalizing from this to a formula for the number of these instructions done in the general case. You might also be asked to summarize the running time with a tight big-O estimate and to compare this running time to that of other algorithms for the same problem in order to conclude which is best in various situations. The details should be written in good mathematical notation, with good English descriptions where needed, especially in the introduction and conclusion. In some cases the solution to a question requires some interpretation, some explanation of the meaning and/or correctness of the solution. Other problems might ask for mathematical proof of some proposition.

Classroom Etiquette

Both the instructor and students are expected to do their best to produce a good class and to treat each other with respect. This includes many factors, such as listening when someone else is speaking, trying to understand what others are saying, being of assistance to others, etc. It definitely does NOT include making fun of others. On a practical level, do your best to improve your grade: read the text, attend class, do the work, ask questions, and try to answer questions in class! Mathematics and computer science are not spectator sports! They requires active participation and repeated practice. If you begin to feel lost, consult one of the tutors, see the instructor, or work through the difficulties with the help of another student in the course. Do not let yourself get behind. In fact, one key to academic success is to start early on homework and other tasks. Last-minute miracles seldom work! Note in particular that attendance is expected. Student performance is bound to deteriorate when classes are missed. In order to emphasize the importance of attendance, the policies outlined after this paragraph will be used.

Grading and Attendance Policies

  • If the student does not attain a passing average in the test category, a failing grade will be received for the course.
  • Each unexcused absence after the first 4 results in 1 percentage point being deducted from the final course grade.
  • Arriving late for class or leaving early (without a proper excuse) is counted as 1/2 of an absence.
  • An unexcused absence from an exam results in the failure of the course.
  • Unexcused absence from more than one-third of the semester's classes results in the failure of the course.
  • Attendance is used to decide borderline grades at the end of the semester.
  • Unexcused absence from class also means a grade of zero on any homework collected in that class.
  • Late work is not accepted unless resulting from an excused absence, but partial credit is given for incomplete homework that is submitted on time.
  • Email me if you must miss class for any reason, whether it is due to an illness or some other issue. It is always best to let me know instead of leaving me to wonder why you are not in class.
  • Written documentation (such as a note from a doctor's office or coach of one's sports team) is normally required for an absence to be excused. Always bring a copy of such a note to give to your instructor when you can do so. In special circumstances, check with your instructor, as it is not always possible to get documentation.
  • Exam and quiz questions normally require you to show all major steps for producing the answer to each question. Failure to do so will likely result in losing a significant number of points on the problem. It is more important to know how to solve a problem and explain it well than to simply have the correct answer. Exceptions where you can simply write the answer will be marked.

Make-up exams are strongly discouraged. If possible, take the regularly scheduled exam. For an excused absence or other significant reason, the instructor may agree to give a make-up exam. Whenever possible, see your instructor ahead of time if you know you must miss an exam (e.g. due to sports). Normally some type of written documentation is required (such as a note from the coach, doctor, etc.). If the documentation or reason for missing an exam is poor, the student can count on receiving a significantly more difficult exam, if one is given at all! Do ask about a makeup exam if you have a good reason to miss an exam, even if documentation is not readily available, as it is understood that illnesses and other complications do happen. Students participating in sports teams are required to notify the instructor in advance of games that might conflict with class.

Academic Integrity

Intellectual honesty is important at Saint Vincent College. Attempts to pass off the work of another as one's own, or group work as one's individual work, will result in action appropriate to the seriousness of the situation. All cases of apparent intellectual dishonesty will be referred to the college administration. If the administration does not say what to do about the grades in a case where plagiarism occurred, the first offense will involve a significant grade penalty (such as a grade of zero) on the item in question, while a second offense may result in failure of the course. In this course, students are expected to do entirely their own work on the exams and WeBWorK problems. Written homework can be done together unless explicitly stated otherwise. Some students learn better when working mostly alone. Others do better when working together. However, never simply copy someone else's work as that does little to help you to learn the material. Remember that you are responsible for knowing how to solve the homework problems and that you will have to face the exam questions on your own.

Be sure to read and follow the CIS Department Policies, available under the CIS Department web site. (This statement covers especially the proper use of departmental computing facilities, policies concerning your web pages, etc.) Be sure to read the regulations found under the Academic Programs and Regulations section of the College Bulletin (which covers such things as grading, academic honesty, academic warning and dismissal, etc.) and the Student Handbook (which covers academic honesty, classroom etiquette, etc.).

Title IX: Sexual Misconduct and Harassment

Saint Vincent faculty are committed to helping create a safe learning environment for all students and for the college as a whole. If you have experienced any form of gender or sex-based discrimination or harassment, including sexual assault, sexual harassment, intimate partner (dating or domestic) violence, sexual exploitation, or stalking, know that help and support are available. Saint Vincent College has staff members trained to support students in navigating campus life, accessing health and counseling services, providing academic and housing accommodations, and more. The College strongly encourages all students to report any such incidents.

Please be aware that all Saint Vincent employees (other than those designated as confidential employees such as counselors, clergy and healthcare providers) are required to report information about such discrimination and harassment. This means that I have a mandatory duty to report to the Title IX Coordinator any information I receive about possible sexual misconduct. This includes information shared in class discussions or assignments, as well as information shared in conversations outside class. The Title IX Coordinator will contact you to inform you of your rights and options and connect you with support resources, including possibilities for holding accountable the person who harmed you. Know that you will not be forced to share information and your level of involvement will be your choice. The purpose of reporting is to allow Saint Vincent to take steps to ensure that you are provided with any necessary resources needed and to provide a safe learning environment for all.

The College's Title IX Coordinator is:
Eileen K. Flinn, Esq.
Saint Vincent College
Second Floor, Alfred Hall
724-805-2897

The College also has confidential resources available, who can provide assistance to those who have experienced sexual misconduct without triggering a mandatory reporting duty. More information about confidential resources is available at https://www.stvincent.edu/student-life/title-ix.

If you wish to speak to a confidential employee who does not have this reporting responsibility, you can contact Campus Ministry at 724-805-2350 or the Wellness Center in the Carey Student Center at 724-805-2115. For more information regarding your rights and options, please see the Sexual Misconduct and Harassment policy which can be found on MySVC portal under Quick Links or on the web at https://www.stvincent.edu/student-life/title-ix.

Disability Statement

Students with disabilities who may be eligible for academic accommodations and support services should contact Ms. Marisa Carlson, Director of Academic Accommodations and Academic Advisor, by phone (724-805-2828), email (marisa.carlson@stvincent.edu) or by appointment (Academic Affairs-Headmasters Hall). Reasonable accommodations do not alter the essential elements of any course, program or activity. The Notification of Approved Academic Accommodations form indicates the effective date of all approved academic accommodations and is not retroactive.

Class Cancellation

If the instructor needs to cancel class, every effort will be made to send an email message to students' Saint Vincent email accounts.

Maintained by: Br. David Carlson
Last updated: August 19, 2018
Disclaimer