Syllabus V22.0102: Computer Science II

Spring 2003

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 1:55 to 3:25 and Wednesday 12:25pm to 1:55pm

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 MW 9:30-10:45 sec 03 in rm 102 Warren Weaver Hall and MW 3:30 to 4:45 rm 109 Warren Weaver Hall

Recitations: There are two recitation sections for this course. One meets at 11:00 to 12:15 pm in room 109 Warren Weaver Hall on Mondays and the other at 2:00 to 3:15 am in room 109 Warren Weaver Hall on Wednesdays. 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 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/spring03/V22.0102-002/homepage.html

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 you must see Prof. Michael Overton in order to take a placement exam.

Textbook: The textbook is Textbook: Data Structures & Algorithm Analysis in JAVA by Weiss

Work: Your grade will be based on three (possibly four) programming assignments, one or 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. Asymptotic Notation
  2. Stacks
    1. Stack Operations
    2. Array Implementation
    3. Linked List Implementation (introduction to pointers)
    4. Hybrid Implementation
    5. Application: Arithmetic Expressions
  3. Recursion
    1. Simple Examples
    2. Designing Correct Recursive Programs
    3. More Complicated Examples
  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