CS 114, Sect. A: INTRODUCTION TO COMPUTER SCIENCE II Fall 1985 William J. Rapaport MWF 10-10:50 Bell 214 Cooke 127 636-3193 Office Hours: to be announced or by appointment THE INFORMATION IN THIS SYLLABUS PERTAINS TO SECTION A ONLY. TEXTS: Required: (1) Dale & Orshalick, Introduction to Pascal and Structured Design (Lexington: Heath, 1983); fifth (or later) printing. (2) Dale & Lilly, Pascal Plus Data Structures, Algorithms, and Advanced Programming (Lexington: Heath, 1985). Recommended: (1) Cooper, Standard Pascal (New York: Norton, 1983). TOPICS: This course is the sequel to CS 113. We shall begin with a study of Pascal data structures: arrays, records, files, and sets, and then turn to issues of software design, which will concern us for the rest of the semester. Good software requires good modular design; this is accomplished by top-down design of actions (procedures and functions) and of objects (data struc- tures). The notion of an abstract data type that can be imple- mented by different data structures will be the central theme of the course. We will study: stacks, queues, linked lists, pointers, and trees; their implementation in Pascal by recursive procedures and functions; and mathematical analyses of efficient algorithms using them. PREREQUISITES: The prerequisite for CS 114 is CS 113 or its equivalent (roughly, the material in Dale & Orshalick, Chaps. 1-11), including knowledge of Pascal and use of the Cyber. NO INSTRUCTION IN USE OF THE CYBER WILL BE GIVEN IN CS 114. All students in all sections of CS 114 who do not know how to use the Cyber (or who have forgotten how!) are required to attend the series of videotapes that teach you how to use the Cyber, the NOS operating system, and the BED editor. Each showing lasts 2 hours, including 1 1/2 hours for viewing the tapes and 1/2 hour for questions and answers. You will receive a free copy of "Viewer Guide to Timesharing Primer". The showings are as fol- lows: Sep. 5, 6, 9, 10, 11 at 1, 3, 5, 7 P.M. in Capen 10. COURSE REQUIREMENTS AND GRADING: You will be expected to attend all classes, and to complete all readings and assignments on time. There will be regular homework assignments at the end of each chapter, regular programming projects, a midterm exam, and a final exam (during exam week). You will receive two grades: a 3-credit grade from the lecture and a 1-credit grade from the recitation. The 1-credit recita- tion grade will be entirely determined by your grades on the pro- gramming projects, which will each be of equal weight. (There may be as few as 4 long projects or as many as 8 shorter ones.) The 3-credit lecture grade will be determined on the basis of the following requirements, with weights as indicated: Recitation Assignments: 1/3 (including attendance, homeworks, quizzes, etc.) Midterm Exam: 1/3 Final Exam: 1/3 NOTES: (1) Homework assignments should be turned in at your recitation section the week following the assignment. NO LATE HOME- WORKS WILL BE ACCEPTED; you will receive a zero grade for them--that is, no homeworks will be accepted at any other time or place. (2) Although the homework assignments will be primarily from the D&L Pre-Tests, there may be some short programming homeworks (which won't count as programming projects), and it is expected that you will work the Exercises for each chapter as well, checking your work against the answers at the back of the book. (3) Programming projects will be assigned and must be turned in during lecture. No projects will be accepted at any other time or place. Every program handed in must be complete from banner through page count, as produced by the job con- trol you will be given in class. The pages must not be separated. You will be notified how project grades will be determined when the projects are assigned. (4) LATE POLICY FOR PROGRAMMING PROJECTS: All projects are due at the START of each class. If you turn in a project AFTER the start of the class, your grade will be discounted by one full letter grade (e.g., B+ becomes C+). If you turn in a project after the start of the next class, your grade will be discounted by two full letter grades (B+ becomes D+). If you turn in a project after the start of the class after that, your grade will be discounted by three full letter grades (B+ becomes F+). NO PROJECTS WILL BE ACCEPTED AFTER THAT. The final project, however, may NOT be late. (5) If the Cyber is down for 3 or more days at ALL sites, the due date for a project will be extended. Otherwise, no excuses (other than for illness documented by a physician, or other serious personal problems discussed with me in advance) will be allowed, including: you took too many courses, you have projects due at the same time in other courses, your vacation time didn't match the University's vacations, you had trouble getting a listing at the last minute (PLAN AHEAD--THE CYBER IS SLOW !), the printer at the site where you usually work was down (PLAN AHEAD--PRINTERS GO DOWN WHEN YOU LEAST EXPECT IT). Your grade will generally be much higher if you turn in an incomplete project on time (with a list of bugs in the user's manual) than if you turn in a complete project late. (6) It is important that you keep a record of all work that you do for programming projects. That is, you should keep all first drafts of programs, all listings that you get before the final one, etc. This is for your own protection in case someone else copies or otherwise steals your work-you can prove that you did the work; the other person cannot. (7) YOU ARE RESPONSIBLE ON EXAMINATIONS FOR ALL ASSIGNED READ- ING, FOR CONTENT TAUGHT IN BOTH LECTURES AND RECITATIONS, AND FOR CONCEPTS LEARNED AT COMPUTER TERMINALS. For exam- ple, exams will not merely be a subset of assigned written work. (8) SPECIFIC HOMEWORK ASSIGNMENTS AND PROGRAMMING PROJECTS WILL BE ANNOUNCED IN CLASS. Be sure to get a classmate's phone number, so that you will not miss assignments in the unlikely event that you miss a class. TENTATIVE SCHEDULE & TOPICS: Aug 26 - Aug 30: Records (D&O, Ch. 12) Sep 4 - Sep 11: Files and sets (D&O, Ch. 13) Sep 13 - Sep 18: Software design (D&L, pp. 474-480 and Ch. 1) Sep 20 - Sep 30: Pascal data structures (D&L, Ch. 2) Oct 2 - Oct 7: Stacks (D&L, Ch. 3) Oct 9: Review ________________________________________________________________ FRIDAY, OCTOBER 11: MID-TERM EXAM ________________________________________________________________ Oct 14 - Oct 18: Queues (D&L, Ch. 4) Oct 18: LAST R DAY Oct 21 - Oct 30: Linked lists (D&L, Ch. 5) Nov 1 - Nov 4: Pointer variables (D&L, Ch. 6) Nov 6 - Nov 11: Recursion (D&L, Ch. 7) Nov 13 - Dec 2: Trees and variant records (D&L, Chs. 8-9, App. G) Dec 4 - Dec 9: Efficiency of algorithms for searching and sorting(D&L, Chs. 11-12) Dec 11: Review (D&L, Ch. 13)