Computer Science Department , Indiana University rev. Wed Nov 14 16:09:59 EST 2012 [SDJ]

C241/H241 - Discrete Structures for Computer Science – Fall 2012

What's New -- Look here regularly for postings
dec 18
•  Scores with grades [PDF] and a chart [PDF] have been posted.
dec 10
•  Score check. Please check the current score sheet [PDF] to confirm your scores to date.
dec 7
•  Solutions to Homework 10 have been posted [PDF]
nov 28
•  Draft lecture/presentation notes on automata [PDF]. This is work in progress so note the timestamp.
nov 14
•  A ninth problem and a supplementary problem have been added to Homework Assignment 10. If you have downloaded this assignment you should refresh your copy.
nov 7
nov 6
•  The links below have been fixed.
•  Homework & test scores [PDF] and a chart [PDF] have been posted. Please verify your scores and let me know of any discrepancies. NOTE: Grade ranges shown on the chart are estimates based on past classes and do not reflect the analyses done when final grades are determined.
oct 18
•  Peer tutoring positions are available for the Spring semester in A201, C211, C212, and C241. The time committment is at most three hours a week. Tutors are paid $10/hr. Qualified applicants must have completed (or are about to complete) the received (or expect to receive) an A or A+. To apply follow this [LINK].
oct 15
•  Examples from today's lecture [PDF]
•  Old What's New postings [HTM].

Course Information
Meetings: Lecture: MW 2:30-3:45 SB150 (Student Building)
Discussion: F 11:15-1:10 or F 1:25-3:20 I2 130 (Info East)
Honors Discussion: F 9:05-11:00 I2 122 (Info East)
Help Session: T 6:30-8:30 LH125
Instructor: Steve Johnson (sjohnson)
Office hours: Times TBA Lindley 330F
Students welcome any time my door is open
Assoc. Instr.: Josh Hieronymus
Mark Jenne
Andrew Kaizer
The electronically distributed lecture notes are under revision. Chapters to be released as content is updated. Solutions to selected exercises are posted to the right.
[PDF] Posted August 18
1. Sets  
2. Relations, Functions  
3. Proposition Logic and Boolean Algebra  
4. Counting  
5. Numerical Induction  
>[PDF] Posted October 3. Added Ch. 5; minor revisions to Chs. 1–4
6. Countability and Order  
7. Structural Induction  
8. Language Specification  
[PDF] Posted October 3. Added Chs. 5–8; minor revisions to Chs. 1–4
9. Automata & Regular Grammars  
10. Formal Logic  
11. Proving Programs  

HomeworkAssignments—about 10, equally weighted—are due at the beginning of class on Wednesday of the specified week.
# Posted Due Assignment Solutions
1 W, 8/22 W, 8/29 [PDF] [PDF]
2 W, 8/29 W, 9/5 [PDF] [PDF]
3 W, 9/5 W, 9/12 [PDF] [PDF]
F, 9/21 In-class Test One. This 75-minute test will be held in your regular discussion session starting promptly at the beginning of the session. [PDF]
4 W, 9/13 W, 9/26 [PDF] [PDF]
5 W, 9/26 W, 10/4 [PDF] [PDF]
6 W, 10/3 W, 10/10 [PDF] [PDF]
7 W, 10/10 W, 10/17 [PDF] [PDF]
F, 10/19
F, 10/26
In-class Test Two covering Chapters 3 (Propositional Logic and Boolean Algebra), 4 (Counting) and 5 (Numerical Induction). This 75-minute test will be held in your regular discussion session starting promptly at the beginning of the session. [PDF]
8 R, 10/18 W, 10/31 [PDF] [PDF]
9 R, 11/1 W, 11/14 [PDF] [PDF]
10 W, 11/14 W, 11/28 [PDF] [PDF]
  Additional assignments as time permits.  
    Complete departmental course & instructor evaluations  
December 14
In-class Test Three covering Chapters 6 (Program Analysis, Order and Countability), 7 (Structural Induction) and 8 (Languages and Meanings). According to the university-wide Final Exam Schedule, this exam will take place in our usual classroom on Friday, December 14 at 2:45pm-4:45pm. [PDF]

§ Catalog description

C241 Discrete Structures for Computer Science (3 cr.) P: C211. MATH M211 recommended. 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.
H241 Discrete Structures for Computer Science, Honors (3 cr.) P: CSCI-C 211, MATH-M 211 recommended. Honors version of CSCI-C 241. 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. Credit given for only one of CSCI-C 241 or H 241.

H241 participants have an "honors discussion section," topics are explored at greater depth. There may also be supplementary problem assignments.

§ 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

  1. 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.
  2. 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. Further courses along this line include B343 and B403.
  3. 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 whether you realize it or not. 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:

  1. Understanding the topics listed in the catalog description.
  2. Understanding how to define and reason about mathematical models used to specify programming languages, programs, and their properties.
  3. Exposure to basic terminology and results in countability, decidability, complexity,
  4. Familiarity with the numerous forms of inductive argument used throughout computer science.
  5. 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 design.

§ Topic Outline. This is a provisional outline of topics covered in this course. The numbers indicate the expected number of lectures on each topic.

  1. [1] Sets, Languages
  2. [2] Relations
    1. Functions
    2. Relations on a Single Set
    3. Trees
    4. DAGs
    5. Applications*
  3. [2] Logic and Boolean Algebra
    1. Logical Connectives
    2. Truth Tables
    3. Boolean Algebra
    4. Normal Forms
    5. Applications*
  4. [1] Numerical Induction
  5. [1] Counting
    1. Cardinality
    2. Permutations and Combinations
    3. Decision Trees
  6. [2] Order
    1. Countability
    2. Order Notation
    3. Decidability, Complexity
  7. [3] Structural Induction
    1. Inductively Defined Sets
    2. Principle of Structural Induction
    3. Defining Functions by Recursion
    4. Applications*
  8. [2] Automata
    1. Automata as recognizers
    2. Relationship to Regular Languages
    3. Applications*
  9. [2] Languages and Meanings
    1. Language Definitions
    2. Specifying Precedence
    3. Language Interpretations
    4. Languages over a Data Type
    5. Language of Expressions
    6. Language of Statements

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.

  • Daniel Solow. How To Read And Do Proofs: An Introduction to Mathematical Thought Processes. (2nd ed.) John Wiley & Sons. An excellent introduction to mathematical reasoning.
  • Alfred V. Aho and Jeffrey D. Ullman. Foundations of Computer Science. W. H. Freeman & Co., 1995. Textbook covering many topics in common with this course, with greater 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 Mathematics: 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 Philosophy. 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, 75 minutes, given in the 5th or 6th week.
25% Test Two, 75 minutes, given in the 12th or 13th week.
30% Final Exam, 120 minutes, as scheduled by the Registrar during finals week.
5% Participation, attendance, bonus problems, etc. Generally, participation credit is considered only in borderline cases.

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, notify one of the AIs and arrange to turn your work in to them.

Tests. Each test will include two homework problems assigned since the previous test—but details such as wording, variable names or constant parameters may be changed.

Generally, tests focus on topics covered in lecture but not on the previous test; so they are not "cumulative" in that sense. However, the topics themselves are 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. ]
  • [2] Numerical Induction
  • 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 explicit 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 strictly on a "curve" (statistical cut-offs). In other words, I make judgments, subject to these considerations:

    • Students whose cumulative performance exceeds 1.1 standard deviations above the class average are awarded no less than an A-, and usually an A.
    • Students whose cumulative 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: If you are considering withdrawing, please consult with the instructor for a detailed analysis of your performance in the course. Prior to the "Automatic W Deadline," 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.