Computer Science 243
Discrete Structures of Computer Science
Fall 1997
- Instructor:
Gianfranco Ciardo
- Class meetings:
Mon/Wed/Fri 2:00 p.m. - 2:50 p.m., Room: Tercentenary 20
- Textbook:
Discrete Algorithmic Mathematics,
Stephen B. Maurer and Anthony Ralston, Addison Wesley
- Office hours:
Mon/Wed 3:00 p.m. - 5:00 p.m., or by appointment,
Room: Tercentenary Hall 117
This course will teach you what it means to prove
(or disprove!) a mathematical statement and how to express your
mathematical reasoning in a clear and formal way.
Proof by (mathematical) induction will be often used for this purpose.
At the same time, the topics covered, such as relations and functions,
recursion, are at the core of computer science.
We will devote a good portion of the course to the study of graphs,
perhaps the most useful and ubiquitous concept in computer science.
Another important topic which we will study is combinatorics,
which will allow us both to ``count things'' and tackle discrete
probabilistic problems.
The discrete mathematics covered by this course are fundamental
to Computer Science.
Indeed, CSci 243 is a prerequisite for any course numbered above 300.
Prerequisites
Undergraduate students enrolled in CSci 243 must have taken and
successfully passed CSci 141, Introduction to Computer Science,
or the equivalent.
Topics outline
The main topics covered are:
- Background and introduction
- Sets and operations on sets:
Naturals, Integers, Rationals, Reals, the empty set;
defining a set by giving the properties its elements must satisfy;
cardinality of a set;
subset, strict subset, superset, strict superset;
the powerset;
union, intersection, concept of universe, complement, difference;
Cartesian product.
- Summation and product over an index set:
notation and their properties.
- Definition and notation of:
absolute value; floor and ceiling; factorial; mod and div;
k-th power, exponential, and logarithm; polynomials.
- Definition of algorithm:
finiteness; correctness; invariants.
- Relations
- Reflexive, symmetric, transitive relations.
Transitive closure of a relation.
- Equivalence relations and equivalence classes.
- Partial and total order relations.
- Functions; domain, range, image;
inverse of a function; surjections, injections, and bijections.
- Logic
- Propositional calculus; logical conjunction, disjunction, negation,
implication, biimplication.
- Truth tables. Well-formed formulas. Tautologies.
- Boolean algebra.
- Predicate calculus; universal and existential quantifiers.
- Bound and free variables.
- Recursion and induction
- Recursive definitions and implementations: factorials,
k-th power, exponential.
- The Towers of Hanoi problem.
- Weak and strong induction.
- Important orders of growth for sequences and how to recognize them:
linear, polynomial, exponential.
- Common errors in proofs by induction.
- Using induction to prove correctness and complexity of algorithms.
- Graphs
- Definitions: directed vs. undirected graph; null graph; isomorphic
graphs; simple graph; multigraph; subgraph; degree, indegree,
and outdegree of a vertex; isolated vertices; clique and
clique number; path; length of a path; cycle; elementary path;
simple path; connected graph; strongly and weakly connected digraph;
connected component.
- Adjacency matrix: meaning of its powers; Warshall's algorithm.
- Breadth-first and depth-first search.
- Graph algorithms.
- Combinatorics and probability
- Basics: sum, product, and division rule.
- Permutations and combinations.
- Properties of the combinatorial numbers; Pascal's Triangle;
binomial theorem; multinomial theorem.
- The principle of inclusion-exclusion.
- Algorithmic issues: generating permutations.
- The pigeonhole principle.
- Probability concepts: event;
sample space; probability measure; atomic vs. compound events.
- Interpretation of probability as a frequency or ratio.
- Conditional probability; independent events; Bayes' theorem.
Homeworks
I will assign homeworks on a periodic basis, but I will not collect them.
You are strongly encouraged to work on them individually or in groups.
The weekly quizzes will reflect the knowledge and experience you should
have accumulated by working on the homeworks.
Quizzes
Weekly 10-minute in-class tests will account for 40% of the grade.
There is no make-up quizzes, so you should not miss any of them.
Quizzes will be normally on Wednesdays, unless otherwise announced
at least one class ahead of time.
Programming projects
Two take-home projects will account for 10% of the grade each.
The programming environment is C++.
Details will be provided with each project, but the first rule you
must remember is the following:
To receive partial credit, your program must compile correctly
using the specified compiler options and must run correctly on
the test case(s) I provide.
I make no exception to this rule!
Exams
In-class midterm and final exams account for 10% and 30% of the grade,
respectively.
The final exam covers the entire course material and it is scheduled for
Tuesday, December 9, 1997, 1:30 p.m. - 4:30 p.m.
Absences and missed deadlines
If you are absent without justification the day of a quiz or exam,
your grade for it is zero.
Projects will be accepted after the due date only for
justifiable reasons, such as a documented illness.
Note that, if you have two or three weeks to complete a project,
having been sick the night of the due date is not
automatically an acceptable reason for lateness.
In other words, PLAN AHEAD
Notes
You are allowed to bring with you and use one 8.5'' by 11'' sheet
of notes for all quizzes and exams.
No other material (notes, books, etc.) is allowed.
Final grade policy
An overall grade of at least 90% results in a final grade
A.
An overall grade of at least 80% but less than 90% results in a final grade
B.
An overall grade of at least 70% but less than 80% results in a final grade
C.
An overall grade of at least 60% but less than 70% results in a final grade
D.
An overall grade of less than 60% results in a final grade
F.
I reserve the right to raise the final grade, but not to lower it:
if your overall grade is 89%,
I might decide to give you an A- or a B+, but if it is 80% you
are guaranteed at least a B.
Students with disabilities
If you have a disability that may affect your participation in this
course and wish to discuss academic accommodations, please contact
me as soon as possible.
Last updated: August 18, 1997. Report suggestions and problems to:
ciardo@cs.wm.edu
URL: http://www.cs.wm.edu/~ciardo/teaching/CSci243/CSci243Syllabus.html