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.
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
- 40% Homework assignments and quizzes.
- 20% Exam 1 In class. Day tba.
- 20% Exam 2 In class. Day tba.
- 20% Final Exam. 5:00-7:00pm Wed Dec 18.
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.