Instructor: John E. Howland

Text: Lecture notes distributed by instructor

Exams: Weekly quizes and a final examination.

Course Objectives: The objectives of this course include:

a) learning the important ideas of computer science

b) learning the use of notation to express the abstractions of computer science

c) learning experimental aspects of computer science

EXAMINATION SCHEDULE

Quizes on each topic will be given (approximately weekly) at the end of a lecture or at the beginning of the laboratory class.

A comprehensive final examination will be given on Friday, December 11, 2009 at 12:00 p.m.

HONOR CODE

All students are covered by a policy that prohibits dishonesty in academic work. The Academic Integrity Policy (AIP) covers all students who entered Trinity before the Fall of 2004. The Academic Honor Code covers all those who entered the Fall of 2004 or later.

The Integrity Policy and the Code share many features: each asserts that the academic community is based on honesty and trust; each contains the similar violations; each provides for a procedure to determine if a violation has occurred and what the punishment will be; each provides for an appeal process.

The main difference is that the faculty implements the AIP while the Code is implemented by the Academic Honor Council. Under the Integrity Policy, the faculty member determines whether a violation has occurred as well as the punishment for the violation (if any) within certain guidelines. Under the Code, a faculty member will (or a student may) report an alleged violation to the Academic Honor Council. It is the task of the Council to investigate, adjudicate, and assign a punishment within certain guidelines if a violation has been verified.

Students who are under the Honor Code are required to pledge all written work that is submitted for a grade: On my honor, I have neither given nor received any unauthorized assistance on this work and their signature. The pledge may be abbreviated pledged with a signature.

Information on the Honor Code and Academic Integrity Policy.

GRADING

Read biology professor Blystone's words on grades.

The approximate breakdown on grading will be as follows. Quizes will be used to determine 35% of the final semester grade. The lowest quiz grade will be dropped. Laboratory problems are assigned on a weekly basis and their grades will determine 30% of the final semester grade. The final examination will be used to determine 25% of the final semester grade. Class participation will determine the remaining 10% of each student's grade. Class participation is a subjective measure and will include such things as class attendance, in-class discussion and out-of-class discussion which is conducted on a course mailing list, cs1311@mail.cs.trinity.edu . Each student should attempt to contribute to the discussion regularly. The instructor will be reading the course mailing list and may contribute to the discussion from time to time. Discussion topics should be limited to the course but may cover any aspect of the course. The course mailing list will be archived but not moderated. This means that all of the discussion will be saved so that it can be accessed at any time, but what you post to the list will be seen by all readers without any editing. It is up to you to engage in friendly conversation and debate. Personal attacks are sure to cause you to be flamed by others and are not encouraged. Each student should go to http://www.cs.trinity.edu/mailman/listinfo/cs1311/ and follow the instructions for subscribing to the CS1311 mail list. The mailing list archives may be accessed at http://www.cs.trinity.edu/pipermail/cs1311/.

Topics:

0 Programming Notation
Describing Programs
Syntax
Semantics
Evaluation Rules
Describing Data

1 Computer Organization
Processor
Memory Hierarchy
Input/Output Systems
computer architecture

2 Computer Arithmetic
Primitive Numeric Types
Fixed Point Arithmetic
Floating Point Arithmetic
Rational Numbers
Complex Numbers
Big Numbers

3 Computer Circuits
How Do Computers Work
Circuits for Primitive Functions
Memory Circuits
Switches
Integrated Circuits
Designing a Computer

4 Algorithms
What is an Algorithm?
Instances of an Algorithm
Analysis of Algorithms
Measures of Efficiency

5 Data Structures
Records
Arrays
Lists
Stacks
Queues
Trees
Grahs
Memory Management

6 Programming Methodology
Top-Down Programming
Decomposition of Programs
Iteration
Recursion
Object Oriented Programming

7 Software Engineering
Engineering Methodology
Prototypes
Large-Scale Programming Projects
The Program Life Cycle
CASE Tools

8 Language Translation
Machine Languages
Syntax Rules
Production Rules
Semantics
Interpreters
Compilers
Programming Languages

9 Program Execution Time
The Limitations of Computer Science
Tractable Computations
Intractable Computations
Some Practical Computations with Very Expensive Solutions

10 Computer Networks
Data Communications
Networking
Internetworking
Global Networks

11 Parallel Computation
Multiple Processes
Communicating Processes
Parallel Computation on a Single Processor
Parallel Computer Architectures

12 Computability
Speed is Not Enough
The Existence of Noncomputable Functions
Programs that Read Programs
The Halting Problem
Examples of Noncomputable Problems
Proving Noncomputability

13 Artificial Intelligence
Knowledge Representations
Understanding
Learning
Game Playing
Expert Systems