Syllabus V22.0102: Computer Science II

Spring 1998

Instructor: Samuel Marateck, Room 623, Warren Weaver Hall. Phone number: (212) 998--3146, and e-mail address: Office hours are Mondays and Wednesdays from 4:30 pm to 6:00 pm.

Whenever you have a question about the course material, Please feel free to drop by during my office hours.

Lectures: Our lectures take place on Mondays and Wednesdays from 9:55 am to 11:10 pm in Room 109, Warren Weaver Hall.

Recitations: There are two recitation sections for this course. One meets on Mondays from 11:55 am to 1:10 pm, and the other meets on Wednesdays also from 11:55 am to 1:10 pm; both meet in Room 109, Warren Weaver Hall. You are expected to attend the section that you registered for. I am the recitation instructor and will go over exercises in the textbook, discuss programming assignments, review for exams, and answer any questions that you have about the course material.

Email Protocol When ever you send email, your last name must appear in the FROM part of the heading. Any mail that is sent to the e-tutors or myself with an alias instead of your last name in the FROM part will not be answered. Also, please capitalize words where appropriate. For instance, don't write something like "i will not be able to come to class tomorrow". Instead please write "I will not ...".

Submitting homeworks: There will be three or four e-tutors for the class. All homeworks must be submitted by email to the e-tutor assigned to you. For instructions on how to so this, please see the instructions on the homepage for this course. The URL is given below. All homeworks will be submitted in two parts, the first draft and the final draft. The first draft is due on the date given in the handout sheet for the assignment. The second draft is due one week from the day you receive the response for the first draft from your e-tutor. The e-tutors will give you suggestions when they return your first draft. Please do not abuse the process of asking them for help, i.e., do not continually submit a program until you get it correct. Submit the second draft when its as close to the finished product as you can get. I will use the recitations to help you do the programs. You are also encouraged to see me during my office hours to get additional help; but, please never submit homeworks to me via email to ask for help (remember,there are approximatley 130 students in the class.)

The URL for this class is:

Course Description: (Four Credits) The design of data structures for representing information in computer memory. Topics include: Abstract data types and their implementations; Stacks; Queues; Priority queues; Dictionaries; Sorting; Recursion. For more details, please see the list of topics at the end of this syllabus.

Prerequisites: The prerequisite for this course is Introduction to Computer Science I (V22.0101). You must have gotten a C or better in this course. If you received a C-, D, or an F, you will not be allowed to continue. If you have not taken that course (or an equivalent course), please see me after class. You should be a proficient Pascal programmer.

Textbook: The primary textbook is the Turbo Pascal edition of Data Structures and Other Objects by Main and Savitch. Don't feel compelled to buy this text or the supplementary text if you do not care too; however, if you feel that you are going to find the course really hard, then get the texts.

The supplementary text is Turbo Pascal, John Wiley and Sons. Most of you have this text. The answers to all the exercises in this text are available on the server ACFSW, as is indicated on the homepage. Copies of both texts are available at the NYU Bookstore.

Work: Your grade will be based on three (possibly four) programming assignments, two midterm examinations, and a final examination. The programming assignments will count for 25% of your grade; the two midterm exams will count for 20% each, for a total of 40%; and the final exam will count for 35%. If you do poorly on the final exam, it will effect your final grade more than 35%,

Help: If you feel overloaded, desire help, or just want to talk, please contact me. Don't let yourself fall behind.

Topics: Below is a listing of the topics that we plan to cover.

  1. Introduction
    1. What are Data Structures?
    2. Abstract Data Types
    3. Pascal Units
    4. Asymptotic Notation
  2. Recursion
    1. Simple Examples
    2. Designing Correct Recursive Programs
    3. More Complicated Examples
  3. Stacks
    1. Stack Operations
    2. Array Implementation
    3. Linked List Implementation (introduction to pointers)
    4. Hybrid Implementation
    5. Time Analysis
    6. Application: Arithmetic Expressions
  4. Queues
    1. Queue Operations
    2. Array Implementations (linear versus circular array)
    3. Linked List Implementation
    4. Time Analysis
    5. Deques
  5. Dictionaries
    1. Dictionary Operations
    2. Array and Linked List Implementations (binary search)
    3. Search Tree Implementations
    4. Balanced Search Tree Implementations
    5. Hashing
    6. Time Analysis
  6. Priority Queues
    1. Priority Queue Operations
    2. Array and Linked List Implementations
    3. Search Tree Implementation
    4. Heap Implementation
    5. Time Analysis
    6. Application: Sorting
  7. Sorting
    1. Insertion Sort
    2. Merge Sort
    3. Heap Sort
    4. Quick Sort
    5. Time Analysis