Syllabus V22.0102: Computer Science II

Spring 1997

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 102, 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.

Submitting homeworks: There will be three 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 90 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). If you have not taken that course (or an equivalent course), please see me after class. You should know how to program in Pascal.

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 about 40% of your grade; the two midterm exams will count for about 15% each, for a total of 30%; and the final exam will count for about 30%.

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