| • • Computer Science Department , Indiana University | rev. Wed Nov 14 16:09:59 EST 2012 [SDJ] |
| NEWS | INFO | HOMEWORK | DESCRIPTION | TOPICS | TEXT |
| What's New -- Look here regularly for postings | |||||
| dec 18 |
| ||||
| dec 10 |
| ||||
| dec 7 |
| ||||
| nov 28 |
| ||||
| nov 14 |
| ||||
| nov 7 |
| ||||
| oct 18 |
| ||||
| oct 15 |
| ||||
| |||||
| 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 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Text: |
§ 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. § 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
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:
§ Topic Outline. This is a provisional outline of topics covered in this course. The numbers indicate the expected number of lectures on each topic.
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.
§ 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:
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:
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:
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. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
