MACS 358, Algebraic Structures and Discrete Maths

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: Tuesday-Thursday 9:30am-10: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[?]

Tentative syllabus for Spring 2000

1. 08/24: Introduction

2. 08/29-08/31: I. Formal Logic: 1.1, 1.2 (propositional logic)

3. 09/05-09/07: 1.3, 1.4 (predicate logic)

4. 09/12-09/14: II. Proofs: 2.1 (proof techniques)

5. 09/19-09/21: 2.2 (induction); 2.4 (recursion)

6. 09/26-09/28: 2.3, 2.5 (Proofs and analysis of Algorithms)

7. 10/03-10/05: Test1; III. Sets and Combinatorics

8. 10/10-10/12:

9. 10/17-10/19:

10. 10/24-10/26: IV. Relations, Functions and Matrices

11. 10/31-11/02:

12. 11/07-11/09: Test 2; VIII. Modeling Arithmetic, Computations and Languages

13. 11/14-11/16:

14. 11/21-11/23:

15. 11/28-11/30: V. Graphs and Trees / VI. Graph algorithms 16. 12/05:

17. 12/07: Optional review session

18. 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

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

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

[Knu69] Donald E. Knuth. The art of computer programming. Vol. 1: Fundamental algorithms. Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont, 1969. Second printing.

[Pól88] G. Pólya. How to solve it. Princeton University Press, Princeton, NJ, second edition, 1988. A new aspect of mathematical method.