12-174 (4 credits)

Study Guide

Spring 2000

This study guide provides the objectives, requirements, and timetable for this course. It also provides some guidelines for designing and creating programs.

Introduction

Computer Science is a discipline concerned with building large abstractions out of smaller abstractions. Every system used on a computer is constructed from smaller components. Unfortunately, the number of components and the complexity of their interactions grows exponentially with the size of the system. As a result, one theme that computer science is constantly pursuing is to find methods of increasing abstraction and constraining the number of connections between components. One of the more recent developments in creating and managing abstractions is object oriented programming.

Many different programming languages have been created that implement object oriented methodologies. One of the most popular languages (though not the purest) is C++. Many industries have adopted, or are in the process of adopting, C++ as their primary lanugage. Unfortunately, C++ is build on top of the C language and inherits many of its complexities and arcane idiocinricies. In addition, the designers of C++ wanted to ensure that there would be as few inefficiencies in the language as possible. The result is a flexible, powerful, fast language that has a very involved syntax and plenty of pitfalls. As the old adage says ``C allows you to shoot yourself in the foot, C++ lets you reuse the bullet''.

A second theme that flows throughout computer science is the need for basic structures. Data structures are basic abstractions for organizing and storing data so that specific information can be accessed quickly. Object orientation is one mechanism to organize solutions that use data structures, though data structures can be used with a wide variety of organizational methods.

Finally, there is a classic tradeoff in computer science between time and space. Often solutions can be accelarated if more space is allocated and space can be minimized at the expense of additional time. Thus a final theme covered in this course is the evaluation of solutions using various data structures. Various data structures will be examined to determine how fast operations can be performed and how much space the solution requires and numerous alogrithms will be studied to see how fast they operate.

Homework and exams will emphasize the theoretical issues discussed in class while laboratories and lab exams will require you to explore implementation issues by using concepts learned in lecture to develop programs in C++.

Warning. This is a difficult course. There are a myrid of intricate details that must be mastered. Though each detail is in itself easily grasped, the sum of details can be staggering and you will spend a lot of time on the computer completing assignments.

Lecture Goal: To understand, use, and evaluate the basic building blocks of computer science (data structures), to develop problem solving and design skills using object-oriented programming, and to understand how to evaluate solutions in terms of both time and space.

Laboratory Goal: To develop programming skills and understand how to implement data structures and solutions that use data structures.

Required Textbooks.

C++ Plus Data Structures, Nell Dale, Jones and Bartlett, New York, 1999. This book will be used for the theoretical material given in the lectures.

Data Structures in C++, A Laboratory Course, James Roberge, Jones and Bartlett. This book contains all the laboratories (except the first one) that we will be using in the course.

Communication

• Class lectures will not exactly follow the texts. You are expected to attend all classes and attendence will be taken.

• You are accountable for all material covered, all announcements made, and all handouts given out during class.

• Ways to reach me:

  • . Come during office hours!!!

  • Send electronic mail to barr@ithaca.edu
    

  • . Leave a note (including your name, schedule, phone number and userid) either under my door or in my mailbox in the Math/Computer Science Department Office (212 Williams).

Grading

Grading will be based on the following events:

Exams (2 exams, 1 final; each 100pts) 33%. Exams will take place at night on 24 Feb and 30 March. The final will be at 7:30 AM on Friday May 5th in 310 Williams.

Lab Exams (2 exams; each 50 pts) 11%. Exams will take place in lab during the weeks of 21 Feb and 20 Mar. These exams will test your knowledge of implementation principles in C++ and will occupy the lab period.

Laboratories (weekly; about 10 total; 20pts each) 22%.

Homework (periodic; about 5 total; 20pts each ) 11%.

Projects (2; 50pts/100pts each) 17%.

Class Participation 6%.

Assignments

1. Exams will take place at night on the scheduled date. You must let me know by the end of the first week of classes if you have a conflict with these times.

2. All class material, except exams, will be posted on the class home page. You are responsible for checking the class home page daily to view announcements.

3. Class attendance is mandatory. You are responsible for all material and announcements given in class. If you miss a class you are responsible for obtaining the missed material/announcements.

4. PreLabs and projects will be done in teams.

5. Labs and PostLabs must be done independently unless otherwise indicated.

6. You must complete all prelabs and labs to pass the course. If you fail to turn in two or more prelabs or labs without talking to me, you will be dropped from the course.

7. All assignments other than prelabs and projects are expected to be INDIVIDUAL work. Thus homework, exams, labs, and postlabs must be completed individually. All work handed in must be original. Duplicate or very similar assignments receive negative grades. Flagrant cheating (on an exam or project, or on repeated homeworks) will result in (at minimum) a FAILING GRADE for the course. General discussion is allowed, but not sharing of answers, algorithms, or code.

8. SAVE your intermediate work until an assignment has been graded, returned, and recorded. KEEP backup copies of the final versions of your homeworks. Also, keep the source code of your programs on your disk, without editing them. NEVER leave program listings lying around or throw them away in public areas.

9. Assignments are to be turned in either before or after class or put under my office door. Some programs will be placed in the class directory and I will run them on my data. You should always keep copies of your runs for yourself.

10. Graded assignments will be returned in class. Work unclaimed in class may be picked up later from outside my office. If you have a question on a grade, bring it to my attention within one week of the assignment's return.

11. Periodically, I will electronically post grades as we have them recorded. It is your responsibility to check these listings to ensure their correctness, within one week of the posting.

12. Handwritten assignments should be neat and easy to read (Or else type them!). Include your name and section number on every page.

13. It is more productive to use the computer for entering, editing, and running programs, and then spend time AWAY from the machine debugging from a listing.

14. Good programming style at all levels includes using efficient algorithms (not tricky ones), structured programming techniques and good documentation. I.e., your grade is not solely determined by whether or not a program "works".

15. Style. Programming assignments must start with a block of comments (typed) giving your name, section and the assignment number. This introductory block should briefly describe the purpose of the program and provide and major data structures. Functions must begin with a block of coments that include the name of the fuction, inputs expected and outputs produced, and a general algorithm (if the function is not trivial). More specific details are given in the style guide.

16. Approach your programs by first writing an algorithm and/or a solution in an algorithm. Second, code and test a portion of the solution (preferably the easiest). Continue to expand on this working portion by making small, modular changes and testing each change. Do lots of hand and machine tracing and run small amounts of data. Include your comments as you go.

17. A late assignment will have 33% of the points deducted from the grade if it is turned in within 24 hours after the due time, 67% deducted if within 48 hours. After 48 hours an assignment will be marked but no credit will be given. Always turn in whatever work is done at the due time. You should have something FINISHED (i.e., functioning and commented), even if the entire assignment isn't completed. Individual exceptions should be discussed with me in advance.

18. Don't get behind in this class! Start each assignment as soon as it is handed out, so that you have time to ask questions and can use your time wisely.

Last Modified: 11 January 2000

THIS PAGE MAINTAINED BY:
John Barr, Ithaca College