" /> CS 171 Syllabus
CIS Logo SVC Logo

   Computing & Information Systems


Schoology Facebook        Search CIS Site      Tutorials

CS 171 Syllabus

Discrete Structures II

Spring 2018

CIS Department

Saint Vincent College

General Information

  • 3 credits
  • Prerequisite: CS 170 or MA 110 or MA 112
  • Instructor: Brother David Carlson
  • Office: Dupre Science Pavilion, Tenley Hall W217
  • Office hours:
    • Mon, Fri 8:30 am - 9:20 am
    • Tue, Thurs 8:30 am - 9:50 am
    • Mon, Fri 10:30 am - 11:20 am
    • Mon 2:00 pm - 2:50 pm
    • Tue 2:00 pm - 4:30 pm
    • Thurs 3:00 pm - 4:30 pm
    • and by appointment
  • Phone: 724-805-2416
  • Email: david.carlson@stvincent.edu
  • 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. This schedule also shows you which tutor is staffing the lab at what times.
  • Text: Discrete Mathematics and Its Applications, 7th ed., Rosen, K., McGraw-Hill (2012), ISBN 978-0-07-338309-5 (or the custom book with ISBN 978-1-121-73373-2 if it is still available). Do not get an international edition of the book, as they often leave out entire chapters. An electronic book is not recommended as you will not be able to use it during the exams. Only paper materials, including the printed textbook, can be used on the exams.


This course continues the study of discrete mathematics which was begun in CS 170. The mathematical and theoretical foundations of computer science are emphasized. Topics to be covered include proofs of program correctness, running time analysis, computability theory (and Turing machines), complexity theory (including the classes P, NP, etc.), more on grammars & parsing, push-down automata, number theory & encryption, and counting techniques (especially recurrence relations and generating functions). Important fundamental questions will be answered, such as whether all functions are computable. Optional topics might be added as time allows, such as the connection between Prolog and predicate logic (e.g. the resolution principle). In spite of the emphasis on theory, the goal is to show how this theory is used in practical applications in computer science. The practical applications that are emphasized include aspects of the design of parsers and compilers, solving the traveling salesperson problem, finding and comparing the computational complexity of various algorithms, and how to show that critical software is correct. The implications for practical computing of unsolvable problems (such as the general halting problem) and problems with bad computational complexity are also considered.

Why Take This Course?

As with CS 170, 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. This course is required for those students in the computer science major. Computer scientists often use and develop the rich theory of discrete mathematics which is introduced in this course. Students who plan to go to graduate school in computer science will see a number of discrete mathematics questions on the GRE computer science examination (if they take that exam). In addition, many of the practical applications of discrete mathematics outlined above are important for all students of computing. Mathematics majors also sometimes take discrete mathematics in order to broaden their knowledge of mathematics.

The Text

The course will mostly use those topics from the Rosen text not covered in CS 170 (primarily modular arithmetic, RSA encryption, proofs of program correctness, solving recurrence relations, generating functions, and Turing machines), although some CS 170 topics (such as grammars and finite state machines) will be covered again, but in greater depth. In addition, the instructor will supply other material not found in the text, so as to be able to incorporate a wide range of topics from a number of sources. These topics include computability and complexity theory, Turing's thesis, Church's thesis, Godel's Incompleteness Theorem, infinite sets, and push-down automata. The instructor will also supply software to illustrate a few of the topics covered (such as solving the traveling salesperson problem and using a table-driven parser).

Core Goals

This course contributes especially toward the following core curriculum goals, listed in order of emphasis. Writing good mathematics in the solution of problems is the key communication skill for this course.

  1. To develop mathematical skills and quantitative literacy
  2. To form habits of ordered inquiry, logical thinking, and critical analysis
  3. To develop effective communication skills
  4. To foster historical awareness (of the field of discrete mathematics and the foundations of computer science, in this case)

CIS Department Learning Goals

This course contributes mainly to the following desired departmental learning goals, listed in order of emphasis.

  1. An ability to analyze a problem, and identify and define the computing requirements appropriate to its solution
  2. 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
  3. An ability to apply theory in the design and implementation of computer-based solutions
  4. An ability to reason about and explain computer-based solutions at multiple levels of abstraction
  5. An ability to communicate effectively with a range of audiences about technical information

Course Goals and Means of Assessment

Specific course goals include the following. These goals will be assessed by means of homework assignments, tests, and class participation. Informal student comments are also considered.

  1. By the end of the course, the student should be able to prove the correctness of short programs that use IF and WHILE loop constructs.
  2. By the end of the course, the student should be able to solve discrete mathematics problems of average difficulty of the types covered in the course. (For example, analyze the running time of an algorithm by constructing and solving a recurrence.)
  3. By the end of the course, the student should be able to explain the basic significance of the various theoretical items covered. (For example, the student should be able to explain the importance of the existence of unsolvable problems or the implications of the time complexity of the traveling salesperson problem.)

Grading and Course Policies

  • 25% First Exam
  • 25% Second Exam
  • 25% Final Exam
  • 25% Homework

Homework and Exams

Letter grades will be given using the scale found in the College Bulletin. Due to the technical nature of the course, exams will be open book, open notes and will be announced in advance. Be sure to bring to each exam notes from class, handouts, homework solutions, and examples. However, you must still be well-prepared as it is not possible to look up how to solve every problem in the time given. Homework and test answers are expected to be written using good English and good mathematics. These items will be graded not just on the correctness of their answers, but also on the clarity of their presentation. This is intended to help the student to develop good written communications skills. On exams, cell phones, tablets, laptops, and similar devices should be turned off and put away. The use of calculators is encouraged (and, in fact, necessary to answer some exam questions), but calculators are not to be shared among students during an exam. Calculators and Mathematica are of use in the graphing of functions and in certain other parts of this course. These can be used to aid you with homework. Not all of the homework will be collected, but some of it will be.

Producing a Good Class

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 course materials, attend class, review what was done in each class before the next class, do the homework, ask questions, and try to answer questions in class! Mathematics is not a spectator sport! It requires active participation and repeated practice. Do lots of homework problems! 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. Partly in order to emphasize the importance of attendance, the policies outlined right after this paragraph will be used.

Course 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 3 results in 1.5 percentage points 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 collected homework due in that class.
  • Late work is not accepted unless resulting from an excused absence or other significant complication, but partial credit is given for incomplete homework that is submitted on time.
  • 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.

Make-up Exams

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.

Exam Questions

Exams will ask critical thinking questions that require careful analysis, mathematical explanation and/or proof, and meaningful conclusions. For example, you might be asked to write a mathematical proof that a small section of a program is correct. You might also be asked to take a small integer m to a large integer power e, modulo some prime p. You would have to decide whether finding m to the e on a calculator would work reasonably, whether the "square and multiply" modular exponentiation algorithm would be best to use, or perhaps whether Fermat's Little Theorem would lead more quickly to a solution. You would then need to state your solution method, apply it to the given problem, write the details in good mathematical notation, and present the solution. In some cases the solution requires some interpretation, some explanation of the meaning and/or correctness of the solution.

Homework Questions

Homework will be very mathematical and similar to the questions just mentioned. Although the problems are usually short, they can be very detailed. As such, they require careful work and sometimes cannot be completed in one sitting. Since there are different types of assignments in this class (paper assignments, online homework, etc.) the way in which they are collected will vary. Pay attention to the instructions for each assignment in regard to how the assignment is to be turned in and when it is due.

Intellectual Honesty and Plagiarism

Some of the homeworks for this course will not be individual ones. Thus, you will be able to consult with other students in the class about how to solve them and even to look at some of each other's work. However, many of the homework assignments will be individual ones where you may not consult other students in the class, look for online answers, etc. There are typically the homeworks that are graded. If it is not clear whether homework is to be done individually or whether it will be graded, please ask.

Intellectual honesty is important at Saint Vincent College. On individual assignments as well as exams, attempts to pass off the work of another as one's own, or group work as one's individual work, etc. will result in action appropriate to the seriousness of the situation. If there is some doubt as to whether you solved a homework or test question yourself, you may be asked to explain the solution. If you can do so, that provides good evidence that you did do the work yourself. All cases of apparent intellectual dishonesty will be referred to the administration. If the administration does not say what to do about the grades in such a case, the first offense will involve a significant grade penalty (such as a grade of zero on the assignment or exam), while a second offense may result in failure of the course. In this course, students are expected to do entirely their own work on tests and any homework designated as individual homework. Note, too, that copying someone else's work 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 test questions on your own.

Policy Documents

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, academic honesty, etc.) Be sure to read the Regulations section of the College Bulletin (which covers such things as grading, academic honesty, 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

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 http://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 http://www.stvincent.edu/student-life/title-ix.

Students with Disabilities

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: January 12, 2018