| NEWS | INFO | HOMEWORK | DESCRIPTION | TOPICS | TEXT |
C241 - Discrete Structures for Computer Science - Fall 2006
| What's New -- Look here regularly for postings | |||||
| 28 aug |
| ||||
| 31 jul |
| ||||
| Course information | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Meetings: | Lecture: TBA Discussion (optional): TBA | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Instructor: |
Steve Johnson
( ): Wednesdays, 1:30-2:30PM &
Thursdays, 11:15AM-12:15PM, LH330F;
or by appointment.
Students welcome any time my door is open | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Assoc. Instr.: | TBA
| Text:
| Electronically distributed Lecture Notes [PDF],
hypertext version: [HPDF]
| NOTE: Corrections/additions/revisions are posted here.
| Homework:
|
Assignments (about 10, equally weighted)
are due in class on the specified date.
|
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
§ Catalog description
C241 Discrete Structures for Computer Science (3 cr.) P: C211. Induction and recursive programs, running time, asymptotic notations, combinatorics and discrete probability, trees and lists, the relational data model, graph algorithms, propositional and predicate logic.
§ General Description.
This course introduces fundamental mathematical concepts and techniques used throughout the computer science curriculum. It defines mathematical structures used to model digital computation from the level of discrete ``logic'' and finite-state machines to that of programing languages and concurrent systems.
A one-semester course at this level has the choice of aspects to emphasize, including
- Program correctness. How can you determine with mathematical certainty, whether or not a program does what it is supposed to do? To answer this kind of question, one needs to define a mathematical model of program meaning and develop ways to reason about these models. Further courses in this line include C311, P415 and B510.
- Program performance. When is one program ``better than'' another in the sense that it runs faster or uses fewer resources? To answer this kind of question one needs to define ways to measure program performance and estimate execution parameters over a range of inputs. Futher courses along this line include B343 and B403.
- Theory of computation. What is a ``computer?'' How do various theoretical models compare with one another? Are there problem classes that no computer can solve? (The answer is yes). Further courses along this line include B401 and B502.
In this version of C241 centers on program correctness, but not to the exclusion of the other aspects. Proving program correctness provides a thread, or ``story line,'' and a goal. Ultimately, the goal is to show, in a precise way, how to formulate a statement of program correctness as a mathematical theorem.
However, the object is not to learn how to prove a specific program but, rather, how understanding program proving guides us to better insight into what programs mean and better programming methods.
§ Background.
The mathematical basis of computer science is different from that of the Natural Sciences. Computing is discrete in character, whereas the physical world is regarded to be continuous. This means that much of the mathematical preparation in primary and secondary education does not directly apply to computer science. However, the general mathematical maturity that derives from that training does.
Participants are expected to be comfortable with algebra at a level expected in a first-semester Calculus class. Perhaps more important, they should be able to follow and perform mathematical arguments. Proficiency with mathematical reasoning varies among participants in this course, so do not be intimidated if you feel you lack experience. The goal is to get better.
One thing to bear in mind is that writing a program and proving a theorem involve essentially the same thought processes–as will be demonstrated by the end of the course. So if you're a good programmer, you have good mathematical aptitudes. Bringing the aptitudes to the surface, where you can use them, is a largely a matter of practice.
It is assumed that course participants have taken the course C211, Introduction to Computer Science. At IU, the programming language used in C211 is Scheme. Programming proficiency in Scheme is not crucial–there will be few, if any, programming assignments. Using recursive programming techniques is more important. If you have programmed in any "functional" language (Haskell, ML, etc.) you have the needed exposure.
If you have not been exposed to these programming languages and methods, but have taken courses in Logic or have generally good mathematical skills, you should be able to succeed in this course–but taking C211 concurrently is recommended.
§ Objectives.
An important goal of this course is to learn how to organize and present one's analysis of a problem. A standard way to show that a problem can be solved is to present an algorithm (program) for solving it. However, if the problem is hard or the solution is ingenious, it often requires additional explanation (i.e. a proof) to convince someone that the solution is indeed correct.
Concrete goals of this course include:
- Understanding the topics listed in the catalog description.
- Understanding how to define and reason about mathematical models used to specify programming languages, programs, and their properties.
- Exposure to basic terminoloty and results in countability, decidability, complexity,
- Familiarity with the numerous forms of inductive argument used throughout computer science.
- Understanding of the relationship between logic and programming, the difference between verification (proving that a program works correctly on all inputs) and testing (demonstrating that a program works correctly on some inputs), and insight into the nature of software desgin.
§ Topic Outline. This is a provisional outline of topics covered in this course.
- Preliminary Concepts [1 wk]
- Sets
- Words, Languages
- Relations [2 wks]
- Relations
- Functions
- Relations on a Single Set
- Trees
- DAGs
- Equivalence Relations
- Partial Orders
- Lattices
- Extended Operations
- Natural Induction
- Principle of Induction
- Variations
- Counting and Approximation [1-2 wks]
- Cardinality
- Permutations and Combinations
- Decision Trees
- Order and Countability
- Order Notation and Arithmetic
- Complexity Classes, Decidability
- Structural Induction [3 wks]
- Inductively Defined Sets
- Structural Induction
- Recursion
- Inductive Theories
- Recurrences
- Automata [1 wk]
- Automata as recognizers
- Relationship to Regular Languages
- Automata as translators
- Model checking
- Sequential hardware and finite state machines
- Languages and Meanings [2 wks]
- Language Definitions
- Specifying Precedence
- Language Interpretations
- Languages over a Data Type
- Terms
- Expressions
- An Experession Based Programming Language
- Application to Formal Logic [2 wks]
- Formal Proofs and Provability
- Inference System G
- Proving Programs [3 wks.]
- A Sequential Language of Statements
- Program Correctness Assertions
- Inference System H
- Program Synthesis
Suggested Reading: These references are not required, but may be of interest to students seeking more or broader information about topics in this course. Feel free to ask the Instructor for additional reading suggestions.
- Steven D. Johnson. Induction, Recursion and Programming, 2005 draft [PDF]. For those who want to read ahead, this is a prior draft of the textbook I am developing for this course. Be advised that the material posted for this course will be a revised draft and may differ in content from this version. However, the topic outline, and much of the material will be the same.
- Daniel Solow. How To Read And Do Proofs: An Introduction to Mathematical Thought Processes. (2nd ed.) John Wiley & Sons. A good introduction to proofs and proving in mathematics.
- Alfred V. Aho and Jeffrey D. Ullman. Foundations of Computer Science. W. H. Freeman & Co., 1995. Textbook covering many common topics in this course, with emphasis on performance analysis and concrete applications in programming.
- Kenneth H. Rosen. Discrete Mathematics and its Applications, McGraw Hill, 1999. A popular ``standard'' textbook on discrete mathematics.
- Ralph P. Grimaldi. Discrete and Combinatorial Mathmatics: An Applied Introduction. Addison Wesely, 1985. A popular ``standard'' textbook on discrete mathematics
- William J. Edgar. The Elements of Logic: For Use in Computer Science, Mathematics and Philosopy. Science Research Associates, 1989. An inexpensive introduction to formal logic, for students interested in that subject.
- Roger B. Nelson. Proofs Without Words: Exercised in Visual Thinking. Mathematical Association of America, 1993. A book devoted to the power of diagrams and pictures for mathematical reasoning.
- Carl B. Boyer. The History of the Calculus and its Conceptual Development. Dover, 1949. An classic, authoritative history of how The Calculus developed over two millenia. Highly recommended reading for computer scientists, providing some perspective on this young discipline.
- Mitchell Wand, Induction, Recursion and Programming. North Holland, 1976. Much of the material in this course's lecture notes derive from this textbook.
§ Evaluation.
Your grade is based on performance on approximately 12 homework assignments, two one-hour in-class tests and a two-hour final examination, according to the following percentages:
- 20% Homework
- 25% Test One, Date to be announced, two or three weeks before midterm evaluations are due.
- 25% Test Two, Date to be announced
- 30% Final Exam
Homework. Homework assignments are due at the beginning of class on the assigned date. Assignments turned in late are penalized 15% per day beyond the due date. If you are unable to attend class to turn in a homework assignment or find someone to turn it in for you, you may place it in the mail box labled "C. Task" (i.e. the AI's mail box, not Instructor's box nor the large drop box) The mail boxes in the Computer Science Main Office, LH215. You must also notify the AI by email that it is there. Late penalties are assessed at the time this notification message was sent.
Tests. Generally, tests focus on topics covered in lecture but not on the previous test; so they are not ``cumulative'' in that sense. At the same time, the topics a cumulative in the sense that they build on previous terminology, definitions and theorems in the course; so some degree of cumulative knowledge is required. It is also assumed that, throughout the course, participants are gaining proficiency in both reading and writing mathematical arguments.
Grade levels are generally based on demonstration of acquired skills:
D Ability to define and reason about inductive structures. Understanding the basic concepts and terminology of graphs, trees and languages. Understanding of logical operations and ideas of equivalence and normal forms. [ Your performance is insufficient for a successful computer science major and needs to be addressed. ] C In addition, understanding concepts underlying order estimation, how to assign meaning to a language, basic concepts relating to automata, greater facility using induction and recursion. Higher ability to conduct proofs. [ You may have a deficiency in mathematics that puts completion of a CS degree at risk. ] B In addition, insight into formal aspects of proofs. Understanding scoping issues in predicate logic and their relationship to programing languages. Understanding Hoare style program logics. Proving both sequential and functional programs. [ You are making good progress toward the successful completion of a BS or BA degree in computer science. If you are considering graduate study, consider building more strength in mathematics. ] A In addition, the ability to apply these concepts problems beyond those explicity encountered in class examples and homework. A level of "fluency" in mathematical comprehension and reasoning. [ You are "on track" toward completing an undergraduate computer science major and the prospect of advancing to professional (MS) or graduate (PhD) levels of study. ] It is not assumed that performance measures (tests, homeworks, etc.) are precise. Grading is neither strictly on a scale nor stictly on a "curve" (statistical cut-offs). In other words, I make judgements, subject to these considerations:
- Students whose cumlative performance exceeds 1.1 standard deviations above the class average are awarded no less than an A-, and usually an A.
- Students whose cumlative performance exceeds the class average for the class are awarded no less than a C.
- Students whose performance is substantially the same are awarded the same grade.
- Students with excellent performance on all exams have demonstrated to my satisfaction that they did not need to do the homework.
- Students who would have received higher grades had they turned in more homework assignments have demonstrated that they should have done more homework.
General Advice
As in any mathematics class, it is vital to do the homework, especially early on. The beginning concepts may be easy to grasp, but the ideas and methods build on one another as the semester progresses.
Academic Integrity Please review: The Computer Science Department Statement on Academic Integrity and consult with the Instructor if you have any questions about the policy.
It is important for many students to understand that learning mathematics is a social process of interaction. Students are encouraged to work together on the homework. Engage with both the Instructor and the Associate Instructor for individual guidance.
Of course, the down side of collaboration is that is can, in some instances, enable cheating. If you work with another student on homework, it is extremely important to acknowledge the collaboration with a written statement on the work turned in, for example, ``Judy Smith and I worked together on this assignment.'' Presenting someone else's work as your own is plagiarism, for which the penalties are severe: failure in the course and possibly expulsion.
If the Associate Instructor–or another student in the class–has been particularly helpful to you throughout the semester, please send a note of acknowledgment to the Instructor. People who show skill in teaching for education should be recognized.
Incompletes: Please review The Computer Science Department Incomplete Policy. A grade of I is intended for circumstances in which a student is inhibited from course involvement for a few days, up to a very few weeks. Incompletes are not awarded for students who fall behind in the course work and can't catch up, or who suffer circumstances that preclude long-term course participation. As a general rule for this class, if an incomplete is to be considered, it must be possible to make up the missed work within 2-4 weeks. In no case, will an incomplete be allowed when a student needs to re-take the course to learn the material.
Withdrawal: According to the Official Calendar the last day for automatic withdrawal is _______________. Prior to this date, students will receive sufficient performance feedback (at least one test and several homework assignments) to make a judgment about continuing in the course. Beyond that date, withdrawing students need authorization from the Instructor, Program Chair and Dean. And the Instructor is required to specify a ``passing'' or ``failing'' status for the student.
rev. Fri Sep 8 13:07:19 EDT 2006 [SDJ]