Syllabus V22.0102: Computer Science II

Spring 2000

Instructor: Samuel Marateck, Room 620, Warren Weaver Hall. Phone number: (212) 998--3146, and e-mail address: marateck@cs.nyu.edu. Office hours are Mondays 5:00pm to 6:00pm and Wednesdays from 1:30 pm to 3:30 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 11:00 am to 12:15 pm in Room 109, Warren Weaver Hall.

Recitations: There are two recitation sections for this course.One meets at 12:30 to 1:45 pm in room 109 Warren Weaver Hall on Monday and the other at 9:30 to 10:45 am in room 102 Warren Weaver Hall on Wednesday. You are expected to attend the one for which you registered. Thus you should attend either on Mondays or Wednesdays, but not both. 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 115 students in the class.) If you don't do all the projects, you cannot pass the course.

The URL for this class is:

http://cs.nyu.edu/courses/spring00/V22.0102-002/

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 Program Design, 3rd Edition by Kruse. 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 this page as well as 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 20% of your grade; the two midterm exams will count for 20% each, for a total of 40%; and the final exam will count for 40%. If you do poorly on the final exam, it will effect your final grade more than 40%,

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