Date: Wed, 20 Nov 1996 22:32:42 GMT Server: Apache/1.0.3 Content-type: text/html Content-length: 11725 Last-modified: Wed, 20 Nov 1996 20:41:28 GMT C241 Course Description

C241 - Discrete Structures for Computer Science
Fall 1996 (3 cr)

Computer Science Department, Indiana University.

Course description Textbook Announcements
Exam 2--Wed, Nov 13
Honors stuff
H241 only
General information Communication Homework Assignments
and Solutions
Grading Policies Handouts

General Information

Instructors

Michael Jahn mjahn@cs.indiana.edu

Kata Bimbó kbimbo@ophelia.ucs.indiana.edu

Office Hours

Michael Jahn:
LH 301-G
MW 3:00-4:00

Kata Bimbó:
LH 301-I
Wednesday 2:45-3:45 and Thursday 4:45-5:45

Meeting times

Lectures: MW 4:00-5:15 in LH 102
Discussion: Section 1136 6:00-8:00 W BH 331
Section 8455 6:00-8:00 R WH 004

Prerequisites

C211, M215, and as a prerequisite or corequisite C212.

Textbook

Alfred V. Aho and Jeffrey D. Ullman, Foundations of Computer Science, C Edition, Computer Science Press, New York, 1994.

Course Description

Almost every course in computer science uses concepts from mathematics. It is the aim of this course to present many of the mathematical topics that are frequently encountered while learning computer science. Those who have taken C201 using Scheme know the importance of recursion in programming. We start by examining in more detail the concept of recursion in Chapter 2 entitled "Iteration, Induction, and Recursion." In preparation for study in the analysis of algorithms, we shall look at the big-Oh notation in Chapter 3. Throughout mathematics we find that graphical representation of ideas make them easier to comprehend. The same is true in computer science, and we next go to Chapter 5 to discuss special graphs, called trees, as they are used as a data model in computing. Sets are another important mathematical concept underlying much of computer science, and these are treated in Chapter 7. Those who work in database theory know the importance of the relational databases. We next study functions and relations from a set theoretic point of view. Chapter 9 presents a more general discussion of graph theory than the previous discussion of trees. Logic underlies all of computer science. We next cover propositional logic, which makes up Chapters 12 and 14 of Aho and Ullman. If time permits, in the last part of the course we shall investigate finite state automata, a way of modeling computation. This material is is contained in Chapter 10. If time permits, we shall also discuss Turing machines and the halting problem.

Note that we have skipped many of the chapters in our text. We shall also skip over many of the sections within chapters. This text is designed for a year-long course which introduces students not only to the fundamental ideas underlying computer science but also to the important data structures used in computing. It would be nice to have enough time during the semester to cover the whole text, but since this is not the case, and since the material that we skip is so interesting, you might consider reading some of the sections or chapters we skip to get a head start for some of the future courses.

Homework assignments will be posted to the class web page regularly, usually due the next discussion section. Late assignments will not be accepted. Please write your solutions to the problems in a way that will be easy for the graders to read and understand. Presentation of the answers is a significant factor in grading homework.

In this course, you may discuss assignments with other students. (Do not assume this is true in all your courses!) We expect you to actually think through and fully understand assignment solutions. We have found that students who copy someone else's work and turn in something they do not fully understand usually do poorly on the examinations, which carry much more weight in grading.

Teamwork in doing assignments is good as long as each member of the team contributes, and fully understands the assignment. If you are working with a group, please indicate it on your homework papers. If someone has given you a lot of help, acknowledge them; you will not be penalized and they will get the thanks they deserve.


Announcements

Exam 2--Wed, Nov 13

Oct. 23

Oct. 3

Sept. 30

Sept. 17

Sept. 16

Sept. 13

Form of HW

Sept. 5


Handouts

Template for strong mathematical induction.

Template for (regular) mathematical induction.


Assignments

No late assignments will be accepted.

Due Mon/Wed 25/27.

Due Fri 22.

Due Mon 18.

Due Mon 11. Solutions

Due Fri 8. Solutions

Due Fri 1. Solutions

Due Mon 28. Solutions

Due Fri 25. Solutions

Due Fri 18. Solutions

Due Fri 4. Solutions

Due Fri 27. Solutions

Due Mon 16. Solutions

Due Mon 9 at the beginning of class. Solutions

Due Wed 4 by the end of the day. Solutions


Communication

E-mail / Office Hours

Michael Jahn mjahn@cs.indiana.edu
MW 3:00-4:00, LH 301-G

Kata Bimbó kbimbo@ophelia.ucs.indiana.edu
Wednesday 2:45-3:45 and Thursday 4:45-5:45, LH 301-I

The course newsgroup, ac.csci.c241, will be used to post more urgent announcements (such as changes to assignments, exams, and any exceptions to our usual office hours) to ensure that people can get that info even if they don't have a web browser at home, but can read the newsgroup. You are also encouraged to use it to post questions related to the course or share related information with the rest of the class. On individual matters, please feel free to contact us in person or via email.

This web page will be the primary means of out-of-class information dispersal for c241 this semester.

This course description is accessible as an HTML (hypertext markup language) file on the WWW (World Wide Web) with the URL (Universal Resource Locator) http://www.cs.indiana.edu/classes/c241/home.html. It will be updated with additional information, such as homework assignments, as the course progresses.

To view a resource given its URL, use the netscape or mosaic program on a networked PC or Mac. These programs underline HTML hypertext links; to follow a link, click on it. The URL for the computer science department's home page is http://www.cs.indiana.edu/, from which all sorts of information can be obtained, including a thread to this home page.


Grading

No special assignments or projects will be given to help students raise their grades.

Policies

Academic Integrity

Read the Computer Science Department's Statement on Academic Integrity to be sure you understand the rules under which computer science courses operate. Cases of academic dishonesty will be reported to the Office of Student Ethics, a branch of the Office of the Dean of Students.

Withdrawal

??? is the last day (until 4:00pm) to drop a course or withdraw from all courses with an automatic W. After that date, a student may withdraw only with the permission of his or her dean. This approval is normally only for urgent reasons related to extended illness or equivalent distress.

??? is the last day for deans to approve a course drop.

Incomplete grade

An incomplete (I) final grade will be given only by prior arrangement in exceptional circumstances conforming to university and departmental policy which requires, among other things, that the student must have completed the bulk of the work required for the course with a passing grade, and that the remaining work can be made up within 30 days after the end of the semester. If these conditions cannot be met withdrawal is the appropriate course of action.

Special accomodation

Students who need any special accommodation must contact the the professor during the first week of class to discuss arrangements.

Questions

If you have questions about any of these policies, please ask the instructor.

Honors stuff


Extra Problem--Honors HW due Fri 10/25
Honors HW due Fri 10/25
Announcement about Monday, 16th homework.
Announcement about Honors Homework Policies.
Honors HW due Mon 9/16
Announcement about Friday Sept.13 discussion.

This page was posted on Sept ?, 1996.