Syllabus
Spring 2004
I. Instructors Information
Name: Prof. Charles R. Hardnett
Office: Room 219 Science Bldg (Tapley)
Phone: 404-270-5880 (please leave a message)
Email: hardnett@spelman.edu (best way to communicate)
Office Hours: M 11a-12noon, 2p-4p,
W 1p-3p, and by appt
II. Course Description
4-3-0. Prerequisite: CIS 122.
An introduction to the theoretical foundations of computer science with emphasis on topics such as finite state machines, formal languages, Boolean logic and combinatorics. Also a study of the vision of the field of computer science with exposure to the breadth of the basic areas of study.
This course provides the theoretical foundation for understanding subsequent courses in computer science: the calculations, abstractions, and proof techniques that are important in understanding how algorithms work and how fast or efficient they are. It provides a transition from the simple data structures of your first programming courses to the sophisticated data structures of an advanced algorithms course. Finally, it provides a breadth of vision as to what computer science is all about Ð what topics and research issues it comprises Ð thereby preparing the student fro advanced courses.
Course materials such as lectures, links to significant web pages, and grades will be available on the web page: www.spelman.edu/~compsci/cis213. You will need access to WebCT for grades and other supplemental information.
III. A 4-hour course?
This course is accompanied by a 0-credit mandatory lab. The lab will take place for one hour each week. The content of the lab is designed to provide empirical study of lecture material as well as provide additional information needed to complete programming assignments. A portion of your final grade will be derived from your participation in lab and completion of lab assignments (see section VI).
IV. Course Objectives
The primary objectives of this course are for you to develop the abilities to:
a. Solve programming problems involving sets, trees, and graphs,
b. Prove facts over infinite sets of discrete objects,
c. Determine and prove the time and space complexity of algorithms based on sets, trees, and graphs,
d. Describe, analyze, and implement algorithms using finite state machine theory and formal language theory, and
e. Explain the fundamental goals and issues of selected topics in advanced computer science.
V. Learning Activities
This course will involve several learning activities including:
a. Attending class lectures/discussions
b. Performing laboratory exercises
c. Completing homework assignments which may be worked on collaboratively
d. Implementing algorithms using advanced data structures and discrete mathematical techniques as programming assignments
e. Write an essay on an advanced computer science topic
Letter grades will be assigned
based on the following scale:
|
Numeric |
Letter |
|
94 - 100 |
A |
|
90 - 93 |
A- |
|
87 - 89 |
B+ |
|
84 - 86 |
B |
|
80 - 83 |
B- |
|
77 - 79 |
C+ |
|
70 - 76 |
C |
|
60 - 69 |
D |
|
< 60 |
F |
The final grade for the course will be computed based on the following
categories and weights:
Exams (3) 30%
Lab 10%
Quizzes (approx 10) 10%
Programming Assignments 25%
Essay 05%
Final Exam (2nd half of Sem) 20%
Labs will take on two roles in this course. The first role is to serve as a means to reinforce lecture material through empirical study. The second role is to provide background and setup for programming assignments. The 10% lab grade is based on your participation and completing lab assignments, while the 25% programming grade is based on completing the programming assignments that are introduced in lab classes. All labs are mandatory.
VII. Textbooks
Required: Foundations of Computer Science, by Alfred V. Aho and Jeffery D. Ullman, third Edition (2003), W.H. Freeman and Co. Publishers, 1994. ISBN 0-7167-8284-7.
VIII. Major Assignments
These dates are not meant to be flexible. They will only be changed in extreme circumstances and with plenty of notice.
a. February 2nd Prog Assignment #1 (lists)
b. March 3rd Prog Assignment #2 (trees/lists)
c. April 2nd Prog Assignment #3 (trees)
d. April 19th Prog Assignment #4 (graphs/hashing)
IX. Late Assignments
It is not a good idea to submit late work because it may compromise the completion of later assignments. However, I realize that things happen that can affect you in completing assignments. For this reason, I allow each student four late days. You may use your four late days anyway you see fit. You may use them all at once, and submit one assignment 4 days late without penalty; or you may scatter the use throughout the semester. These late days only apply to programming assignments and homework assignments.
X. Course Outline
This is meant to serve as an approximate schedule. The amount of time devoted to each topic is partially dependent on how many questions are asked and other factors. Significant modifications to the schedule will be made as early as possible.
a. Chapter 1 Introduction (3)
b. Chapter 2.1-2.3 Induction (3)
c. Chapter 2.4-2.7 Recursion (3)
d. Chapter 2.8-end Merge Sort (3)
e. Chapter 3.1-3.6 Time Complexity (2)
Exam #1 Chapters 1-3.6 (target date is Wednesday, Feb. 18th)
f. Chapter 3.7-3.10 Time Complexity (1)
g. Chapter 5.1-5.4 Trees (3)
h. Chapter 5.5-5.6 Binary Trees (3)
i. Chapter 7.1-7.4 Sets (3)
j. Chapter 7.5-7.6 Sets and Hashing (2)
Exam #2 Chapters 3.7-7.6 (target date is Monday, Mar. 29th)
k. Chapter 9.1-9.4, 9.6-9.7 Graphs (3)
l. Chapter 10.1-10.4 Finite State Machines (3)
m. Chapter 10.5-end Regular languages and automata (2)
Exam #3 Chapters 9.1-end of 10 (target date is Friday, Apr. 23rd)
n. Chapters 11.1-11.6 Context-Free Grammars (2)
Final Chapters 1-11.6 (Wed May 5th 10:30am Ð 12:30pm)
XI. Reading Assignments and Bibliography
Most reading assignments are based on the textbook. However, you will be encouraged and/or required to read other sources including other textbooks, research papers, web pages, etc.
XII. Attendance Policy
Students are required to be present and on time for each class and are responsible for all material covered in class whether they are present or absent. The instructor may withdraw students with excessive unexcused absences.
XIII. Academic Honesty
At the heart of Spelman CollegeÕs mission is academic excellence, along with the development of intellectual, ethical and leadership qualities. These goals can only flourish in an institutional environment where every member of the College affirms honesty, trust, and mutual respect. All members of the academic community of Spelman College are expected to understand and follow the basic standards. Students are expected to read and abide by the Spelman College Code of Conduct (see the Spelman College Student Handbook 2003-2004) and are expected to behave as mature and responsible members of the Spelman College academic community. Students are expected to follow ethical standards in their personal conduct and in their behavior towards other members of the community. They are expected to observe basic honesty in their work, words, ideas, and actions. Failure to do so is a violation of the Spelman College Academic Integrity Policy. Violators will be subject to the sanctions outlined in the Spelman College Bulletin.
XIV. Disability
Spelman College is sensitive to the special needs of students with disabilities. Any student who feels she may need an accommodation based on the impact of a disability should contact the Office of Disability Services privately to discuss her specific needs. Please contact the Office of Disability Service at 404-270-5289 in MacVicar Hall to coordinate reasonable accommodations.