BOSTON UNIVERSITY
Metropolitan College
MET CS342 Data Structures with Java

Dr. V.Shtern (Fall 2012)

Course Syllabus



1. Course Objectives

Welcome to MET CS342 Data Structures with Java. The intent of this course is to familiarize the student with the state-of-the-art concepts of data structures, data abstraction, evaluation of algorithms, implementation of data structures and algorithms by Java libraries, and their use for modular software design with Java.

Today, the object-oriented approach to software design and programming makes the appropriate choice and implementation of data structures crucial for program performance and for its future maintainability. A good understanding of standard data structures and associated algorithms becomes an indispensable component of designer's knowledge.

In this course, we will briefly review the basic Java facilities for software modularization (classes, their components, inheritance, interfaces). We will use them to implement standard data structures: stacks, queues, lists, trees, hash tables, sets and maps. We will also consider algorithms for sorting and searching along with basic topics on performance evaluation and recursion and the use of Java generics and its Collections classes.

Upon the completion of this course, you will further develop your skills of modular approach to producing maintainable, documented and adequately tested software of realistic size using Java as the implementation language.

2. Course Prerequisites

As it is common for any training or college course, you have to make sure that you are sufficiently prepared to learn the course material, handle the course homework and participate in course interactions.

For this course, a working knowledge of Java is required (MET CS232 or equivalent is sufficient). Some degree of mathematical maturity beyond high-school (e.g., MET CS248) would be useful for understanding course materials, but it is not mandatory.

3. Course Policies

This course is a "learn by doing" course. You will have to do programming homework assignments to help you master the course material.

You are also expected to read the textbook and lecture handouts in advance to prepare for each lecture. Advance preparation is essential for your understanding of the course concepts. Before each class, the instructor will post class notes, homework assignments and additional announcements on the course Blackboard 8 Web site (http://blackboard.bu.edu/). Make sure that you print and read them before the class.

Be active in course interactions, express your opinions, display your knowledge, and ask your questions. If your understanding is incorrect, the instructor will provide you with additional explanations and references. If you do not speak up, your understanding will remain incorrect. This will negatively affect both effectiveness of the course for you and your grade.

Class attendance and doing programming homework on time are mandatory. If you have to skip a class or miss a deadline, do not worry - this course is designed for busy adults with many responsibilities, and it is more flexible than a regular day time college course. Still, it is your job to notify the professor that a professional or personal emergency has occurred: you should ask for an extension and set the recovery timetable and priorities mutually agreeable with the professor.

Homework submitted late without prior permission will not be accepted.

4. Textbook

J. Lewis, J. Chase. Java Software Structures: Designing and Using Data Structures. Third Edition, 2010, Addison-Wesley, ISBN 978-0136078586.

5. Grading Criteria

There will be two exams (midterm and final) that will include analysis and coding problems, definitions of terms and concepts, and brief discussions of course concepts and their relationships. The exams are closed book, but you are allowed to prepare and bring a "cheat sheet."

Grades will be based on your participation in class discussions and attendance (10%) and your grades for homework exercises (35%), the midterm exam (25%) and the final examination (30%).

Grading criteria for homework include:
(a) correctness and clarity of your code and comments,
(b) correct use of Java programming idioms for implementing required data structures, and, last but not least,
(c) your ability to follow the homework specification and to explain your design decisions (please take this very seriously).

Grading criteria for the exams include your ability to understand and explain course concepts and their relationships and your skills in using Java for implementing these concepts.

6. Academic Honesty

The course is governed by the Boston University Academic Conduct Committee policies regarding plagiarism (any attempt to represent the work of another person as one's own). This includes copying (even with modifications) of a program or a segment of code or documentation or letting your work to be copied. Your participation in interactions with the instructor and your classmates is encouraged, but the work you submit must be your own. Collaboration is not permitted (for more details, see http://www.bu.edu/met/for-students/met-policies-procedures-resources/academic-conduct-code/).

7. Computing Facilities

As a Boston University student, you have the right to use the bookstore, libraries, sport facilities, and parking. The same is true of Boston University computing facilities. If you wish to use a Boston University Academic Computer Center account, one will be created for you, and you will be able to use its Unix operating system and its Java compiler. The Center office and the terminal room are located at 111 Cummington Street. To open an account, you have to show a valid BU ID card and choose your user name and a Kerberos password. System help and information is available at 617-353-2784.

You can also use the MET College computing labs that include PCs running Windows, Linux, or Unix (808 Commonwealth Avenue, 2nd floor). To enter the lab, you should register your BU ID card with an operator. To use a PC, you log in using your BU user name and your Kerberos password.

You will also need your Kerberos password to access the course materials on the Blackboard 8 system.

This course, however, is not environment-specific. Those students who have access to other computer systems that support Java should feel free to use them. Make sure, however, that these systems run the Java (tm) 2 Platform Standard Edition 6.

If you want to download the latest version of Java to your personal computer, go to the Sun Microsystems web site. There is no need to go after the Enterprise Edition (J2EE), Java SE with its JDK is sufficient. Download the latest update for Java SE Development Kit and its Documentation from http://www.oracle.com/technetwork/java/javase/downloads/index.html.

Notice that you do not need to learn how to use a debugger or an IDE (Integrated Development Environment) for this course. Learning these tools will significantly increase the number of problems you will have to deal with in this course. Meanwhile, the programming assignments in this course are simple enough and could be written using a simple text editor. They should be debugged and tested using your intelligence, not sophisticated and complex software tools.

The recommended development environment is TextPad from http://www.textpad.com. Its trial version is free, its user interface is very simple and intuitive, and it is sufficient for the course work. Make sure that you install Java JDK first and Textpad next to enable Textpad to find your version of Java.

8. Course Instructor

Your primary contact for the course during this semester will be the course instructor, Prof. Victor Shtern. Prof. Shtern came to the USA from Russia. He has many years of experience developing process control systems, database systems, operating systems, and systems for computer-aided instruction. Currently, he is Associate Professor at the MET Computer Science department of Boston University, where he designs and teaches courses on object-oriented technology. He designed and taught computer-aided and distance education courses for several high technology companies, Boston University, and National Technological University.

Prof. Shtern is very enthusiastic about teaching this course and will make every possible effort to help you understand and master the course material in the most effective way. All course materials will be posted on the course Web site ( http://blackboard.bu.edu/).

Learning is more enjoyable and productive when it is interactive. This course provides you with many opportunities to interact with the course instructor and with your classmates. Feel free to ask questions and make comments and suggestions.

Contact Prof. Shtern either in class or send a Blackboard email (a "message" in Blackboard terminology) or telephone (617-358-0003, leave a message if necessary) or regular mail (Boston University, MET Computer Science Department, 808 Commonwealth Avenue, Room 250, Boston, MA 02215). Use regular e-mail (vshtern@bu.edu) only in case of emergency

9. Office Hours

Regular office hours will be held on Tuesdays from 5 to 5:50 P.M. at 808 Commonwealth Avenue, Room 250, Boston, MA 02215. Other times could be arranged by appointment.

10. Establishing Feedback

To be sure that your Blackboard account is indeed activated and you are able to communicate with the professor, log in to Blackboard (using your BU user name and password) and send Prof. Shtern a "message" (not e-mail).

In the message, specify your name, BU ID and the phone numbers to be used for emergencies. Describe your professional background, your current place of work, position and duties. List operating systems and programming languages you are comfortable with, computer science courses you have taken at BU and elsewhere, your goals in taking this course.

Send this message within two days from the start of the course and login into your Blackboard account regularly.



                            BOSTON  UNIVERSITY
                           Metropolitan College
                   MET CS342 Data Structures with Java
                               Dr. V.Shtern


MET CS342       CLASS SCHEDULE                           Fall 2012


Num Date            Topic                                 Chapter

 1 Sep 04  Course introduction.  Discussion of software
           quality and algorithm analysis                    1,2

 2 Sep 11  Overview of object-oriented design and its
           support in Java                                  App.A,B

 3 Sep 18  Introduction to collections. Stacks and their
           array implementations                               3

 4 Sep 25  Implementing collections using linked lists         4

 5 Oct 02  Queues, their implementations and applications      5

   Oct 09  No class: Monday schedule of classes

 6 Oct 16  General lists, their ordered and unordered
           implementations and applications                    6

 7 Oct 23  Recursion; properties of recursive definitions
           and algorithms. Recursive view on data structures.  7

 8 Oct 30  Midterm exam.

 9 Nov 06  Searching and sorting.  Simple algorithms,
           efficient algorithms, their implementations         8

10 Nov 13  Trees, their implementations. Tree traversals.
           Expession trees.                                    9

11 Nov 20  Binary search trees. Balanced binary search
           trees, their implementations                        10

12 Nov 27  Heaps, priority queues.                             11

13 Dec 04  B-trees.                                            12

14 Dec 11  Hashing, sets and maps                             14,15

15 Dec 18  Final examination

Dr. Victor Shtern vshtern@bu.edu
Last modified: August 1, 2012