Search


CS 171 Syllabus



Discrete Structures II



Spring 2008



CIS Department



Saint Vincent College



General Information

  • 3 credits
  • Prerequisite:
    • CS 170, Discrete Structures I
    • or permission of the instructor
  • Instructor: Brother David Carlson
  • Office: Physics 201
  • Office hours:
    • Mon Wed Fri 9:00 - 10:15 am
    • Mon 2:00 - 4:00 pm
    • Thurs 12:30 - 2:30 pm
    • and by appointment
  • Phone: 724-805-2416
  • Email: carlsond@stvincent.edu
  • Schedule for the CIS lab (available soon after the start of the semester).
  • Text: Discrete Mathematics and Its Applications, 6th ed., by Kenneth H. Rosen, WCB/McGraw-Hill (2007).

Description


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 anaylsis, computability theory (using Turing machines and the like), complexity theory, grammars & parsers, and counting techniques (especially recurrence relations and generating functions). 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, practical applications are also brought out (such as the use of this theory in creating parsers).

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 CIS majors who are doing the computer science concentration. 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). Mathematics majors also sometimes take discrete mathematics in order to broaden their knowledge of mathematics.

The Prerequisite


CS 170 is the normal prerequisite, which itself has a prerequisite of CS 111. Thus students should have some knowledge of discrete mathematics and programming before taking this course. Occasional exceptions are granted for strong students with a particular need for or interest in this course.

The Text


The course will mostly use those portions of the text not covered in CS 170, although some CS 170 topics will be briefly reviewed. 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. The instructor will also supply his own software to illustrate a few of the topics covered (such as the traveling salesperson problem and parsers).

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

CIS Department Goals


This course contributes to the following departmental goals, listed in order of emphasis. Note that software engineering is not emphasized in this course, as this is not a software development course. Problem-solving, however, is key to this course.
  1. The CIS graduate should demonstrate the ability to manage the complexity of a technical problem through the use of good problem solving skills and software engineering skills, as well as ethical and decision-making skills.
  2. The CIS graduate should have a broad knowledge of the field of computing.

Course Goals and Means of Assessment


Specific course goals include the following. These goals will be assessed by means of homework assignments, quizes, class participation, and tests. 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, explain the importance of the existence of unsolvable problems.)

Grading and Course Policies

  • 25% First Exam
  • 25% Second Exam
  • 25% Final Exam: Wed, May 7, 11:00 am - 1:00 pm
  • 25% Homework and Quizzes
On occasion a homework assignment may be collected, graded, and counted as a quiz. Homework, quiz, and test answers are expected to be written using good English and 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. A student may at times be asked to present at the board, the solution to a homework problem and graded on this solution and its presentation. The purpose is both to help others with the solution of the problem and to assist the student in developing good communications skills.

Letter grades will be assigned according to the scheme found in the current College Bulletin. Exams will be announced in advance, but quizzes could be given at any time. Due to the technical nature of the course, exams and quizzes will be of the open-book, open-notes variety. However, you must still be well-prepared as it is not possible to look up how to solve every problem in the time given. Calculators may be used on the exams and quizzes. 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 or quiz. 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.

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 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. In order to emphasize the importance of attendance, the policies outlined right after this paragraph will be used.

  • 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.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 or quiz given in that class.
  • Late work is not accepted unless resulting from an excused absence.
  • 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 class must be missed. In special circumstances, check with your instructor.
  • The lowest 2 grades in the homework/quiz category will be dropped at the end of the semester. This is intended to cover absences due to minor illnesses, sports, and the like.
Make-up quizzes will not normally be given. For an excused absence, the student will simply be excused from the quiz. Make-up exams are strongly discouraged. If possible, take the regularly scheduled exam. For an excused absence for a 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.). Students participating in sports teams are required to provide the instructor at the start of the semester with a schedule of games that might conflict with class. 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, as it is understood that illnesses and other complications do happen.

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 are referred to the college administration. In this course, students are expected especially to do entirely their own work on the exams and quizzes. Other work 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 test questions on your own.

Be sure to read and follow the CIS Department Policies, available under the CIS Department Web Page. (This statement covers especially the proper use of departmental computing facilities, policies concerning your Web pages, etc.) In addition, read the Regulations section of the College Bulletin (which covers such things as grading, academic honesty, etc.) and the Student Handbook (especially the section on academic honesty and the section on the misuse of computers or computer networks).

Students with disabilities who may be eligible for academic accomodations and support services should please consult Mrs. Sandy Quinlivan by phone (724-805-2371), email (sandy.quinlivan@email.stvincent.edu) or by appointment (Academic Affairs - directly above the post office). Reasonable accomodations do not alter the essential elements of any course, program, or activity.

If the instructor needs to cancel class, every effort will be made to post a note to this effect on the course web page and on the door to the classroom. If this cannot be done, as a last resort the instructor's phone greeting will be changed to indicate that class is cancelled.



Maintained by: Br. David Carlson
Last updated: January 11, 2008
Disclaimer