 # Syllabus

DISCRETE COMPUTATIONAL STRUCTURES

Com S 330

Syllabus

Introduction and Objective

This course should teach you how to think mathematically. We will stress mathematical reasoning and study different techniques for solving problems and proving mathematical results.We will study combinatorial analysis and discrete structures.

Mathematical Reasoning is the skill to read, comprehend and construct mathematical arguments. We will study mathematical logic, which is a foundation for developing proof methods. An important proof technique, the principle of mathematical induction, will be studied.

Combinatorial Analysis involves different techniques for counting or enumerating objects, an important skill for problem solving.

Discrete Structures are the abstract mathematical structures used to represent discrete objects and the relationships between these objects. The discrete structures we will be studying include sets, permutations, relations, graphs, and trees.

Prerequisites

(i) Math 166, (ii) English 250, (iii) Com S 228.

All undergraduates will need to have these three pre-requisites before they can take Com S 330. In addition, Computer Science undergraduates will need to have at least a C- in these courses. Graduate students may have some or all of these courses waived at the discretion of the instructor, if they can show proof of having taken the equivalent courses elsewhere.

Topics

• Logic and Proofs: Rosen 1.1-1.7
• Sets, Functions, Sequences, and Sums: Rosen 2.1-2.4
• Relations: Rosen 8.1, 8.5
• Induction and Recursion: Rosen 4.1-4.5
• Counting: Rosen 5.1-5.5
• Discrete Probability: Rosen 6.1-6.2
• Graphs: Rosen 9.1, 9.2, 9.4, CLRS B.4
• Trees: Rosen 10.1, CLRS B.5

Grading will be based on 12 homeworks and 3 one-hour exams. There will be no final exam.

 Homeworks 25% 3 Midterms (25% each)

 Score Grade at least 90 A at least 85 but less than 90 A- at least 80 but less than 85 B+ at least 75 but less than 80 B at least 70 but less than 75 B- at least 65 but less than 70 C+ at least 60 but less than 65 C at least 55 but less than 60 C- at least 50 but less than 55 D less than 50 F

Assignments

Homework will be due every week except in the weeks following exams. There will be a total of 12 homework assignments, two of which will be extra credit. All assignments will be posted on the Assignments page, about seven days before the due date. Please go over (and attempt) the homework problems before you come to recitation so that you are prepared with questions.

The homework must be submitted at the beginning of the lecture on the due date. Please do not submit homework once class has started since this is disruptive! Late homework will not be accepted.

Exams

There will be three one-hour exams. Roughly speaking, the breakdown of the topics will be as follows. The first exam will focus on Sets and Logic. The second exam will focus on Functions and Relations, the Principle of Mathematical Induction and Recursion. The third exam will focus on Counting Techniques and Graph Theory. Since the material is cumulative, you may be tested on topics covered in earlier exams as well.

The first exam has been tentatively scheduled for Friday, February 25, the second for Friday, April 8, and the third for Wednesday, May 4. The first two will be held during the regular class time while the third will be held during the scheduled final exam time. Further information on the exams, including dates and specific topics, will be posted on the Exams page.

Office Hours

Office hours are provided to answer any questions that you have regarding lecture material, exams or homework. Please take advantage of this opportunity.

In this course, you are encouraged to discuss assignments with other students since this helps in understanding. (Do not assume this is true in all your courses!) However, the solutions you turn in must be written individually, based on your own understanding. Acts of academic dishonesty will result in zero points awarded for the homework/exam and a formal charge of Academic Dishonesty through the Dean of Students' Office (see the University's Academic Dishonesty Policy for details).

Iowa State University - Computer Science Department - Top of this page