Syllabus V22.0102: Computer Science II

Spring 2009

Instructor: Samuel Marateck, Room 423, Warren Weaver Hall. Phone number: (212) 998--3146, and e-mail address: Office hours are Mondays and Wednesdays 12:20 to 1:00 and 3:20 to 4:10

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

Lectures: Our lectures for both honors and non-honors sections take place on MW 2:00-3:15 in rm 102 Warren Weaver Hall.

Recitations: There is one recitation section for this course. It meets at 9:30 to 10:45 am in room 102 Warren Weaver Hall on Thursday.

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 two 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, try not to submit homeworks to me via email to ask for help; first go to the etutor and then the TA; if for some unknown reason they don't respond, contact me. If you don't do all the projects, you cannot pass the course. You must do the homework assignments by yourself. Collaborating with someone else will be considered cheating!

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

Textbook: The textbook is : Data Structures & Algorithms Analysis in JAVA 2nd Ed. by Weiss

Work: Your grade will be based on three (possibly four) programming assignments, one or two midterm examinations, and a final examination. The first midterm will probably be WED, MAR 4 The programming assignments will count for 10% of your grade; the two midterm exams will count for 25% each, for a total of 50%; 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%; then again, if you do well on the final, it will also 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