MACS358: Algebraic Structures and Discrete Mathematics
Homework assignments
Document also available in PDF, Postscript, DVI, pure text and LaTeX.
This course is an introductory course in discrete mathematics and
algebraic structures.

Teacher:
 Nicolas M. Thiéry
 Office:
 Stratton Hall 222, extension: 3462
 Email:
 nthiery@mines.edu
 Web Page:
 http://www.mines.edu/~nthiery/
 Where and when:
 TuesdayThursday 9:30am10:45am, Green Center 210 S
 Course web page:
 http://www.mines.edu/Academic/courses/math_cs/macs358/
 Reserve:
 In the library
 Textbook:
 Mathematical Structures for Computer Science, Judith
L. Gersting, 4th edition[Gersting.MSCS]
Tentative syllabus for Spring 2000

08/24: Introduction
 08/2908/31: I. Formal Logic: 1.1, 1.2 (propositional logic)
 09/0509/07: 1.3, 1.4 (predicate logic)
 09/1209/14: II. Proofs: 2.1 (proof techniques)
 09/1909/21: 2.2 (induction); 2.4 (recursion)
 09/2609/28: 2.3, 2.5 (Proofs and analysis of Algorithms)
 10/0310/05: Test1; III. Sets and Combinatorics
 10/1010/12:
 10/1710/19:
 10/2410/26: IV. Relations, Functions and Matrices
 10/3111/02:
 11/0711/09: Test 2; VIII. Modeling Arithmetic, Computations and Languages
 11/1411/16:
 11/2111/23:
 11/2811/30: V. Graphs and Trees / VI. Graph algorithms
 12/05:
 12/07: Optional review session
 12/14: Final Exam ?
Course objectives
Learn mathematical techniques and tools for solving problems arising
in computer science. More precisely, learn counting techniques and
basic algebraic and discrete structures; learn how to write proofs and
abstraction (how to identify the very structure of a problem and use
it for implementing a solution).
Prerequisites
Calculus III (MACS 213 or MACS 223). If possible being familiar with a
computer language (C++, Pascal, Java, Mathematica, Maple, MuPAD,
Matlab, Scilab or whatever).
Web page
Most information about this course is available from it's
web
page. This includes the syllabus, homework assignments, computer
projects, class notes, dates of the exams, review sheets, etc.
Office hours
If you have any question, if you need help or extra explanations, if
you have some problem or comment about the class, feel free to come to
my office anytime. However, if you want to be sure I am there, either
come during my office hours (see my
web page), or ask for an
appointment by email.
Grading policy

Exams: 70%
Test 1: 20%, Test 2: 20%, Final: 30%
 Homeworks & quizzes: 30%
 Computer projects: extra credit
Homeworks and Quizzes
There is one homework assignment each and every week. It consists of a
list of exercises, most of the time taken from the text book. The list
is posted on the web page on monday, and the assignment is due for the
following monday. The exercises are about the material seen in class
during the previous and current weeks. Some of the exercises may be
difficult, and require work over several days, so start doing them
early! If you wish (and I strongly suggest it), you can work in
group, as long as you write down the final solution on your own. I
also suggest that you ask for clues during the week for the exercises
that you find difficult. The best is to ask at the beginning of the
class, but you can also ask by email or whatever. I expect everybody
to be able to do all of the exercises (possibly after some help).
The correction of the homework will be available on Tuesday in the
reserve in the library. If one of the exercises seems particularily
difficult, you can ask for a correction in class.
Every two week, the homework will be collected on Tuesday and graded.
Every other week, there will be a 10 minute quizz on Thursday, which
will consists of one randomly choosen exercise of the homework. The
quizz may also ask extra questions about the material of the previous
week.
In addition, there will often be a small homework given at the end of
a class to be done for the following class. Even if it's non graded,
it is mandatory, and will help a lot understanding the material in the
following class.
Computer Projects
From time to time, there will be a computer project which will be
graded for extra credit.
Hints and suggestions

Don't work a lot, work hard!
 Be efficient, don't waste your time in class!
 Be active! If you get bored during the class because you already
know the material, start doing the homeworks
 If you have a problem, don't stay stuck on it. Ask for help!
References
 [Gersting.MSCS]

Judith L. Gersting.
Mathematical Structures for Computer Science.
W. H. Freeman and Company, 4 edition, 1998.
 [Hofstadter.GEB]

Douglas R. Hofstadter.
Gödel, Escher, Bach: an eternal golden braid.
Basic Books Inc. Publishers, New York, 1979.
 [Knuth.ACP1]

Donald E. Knuth.
The art of computer programming. Vol. 1: Fundamental
algorithms.
AddisonWesley Publishing Co., Reading, Mass.LondonDon Mills, Ont,
1969.
Second printing.
 [Polya.HSI]

G. Pólya.
How to solve it.
Princeton University Press, Princeton, NJ, second edition, 1988.
A new aspect of mathematical method.
MACS358: Algebraic Structures and Discrete Mathematics
Homework assignments
Syllabus /
CSM MACS358 /
Nicolas M. Thiéry
Last modified: Tue Dec 2 13:40:18 2003