Com1201

Algorithms and Data Structures 2

Spring 2003

 

Instructor

 

            Jeff Raab (jmr@ccs.neu.edu)

            239 Cullinane Hall (inside lab in 229 Cullinane Hall)

 

            617-373-5876 (office)

            617-792-3410 (mobile)

            617-254-9962 (home)

 

Meeting times

 

Lectures:          Monday, Wednesday, Thursdays in Shillman (SH).

Lab times:         1 hour on Tuesdays or Wednesdays in 229 Cullinane (CN)

 

Required text

 

Riley, The Object of Data Abstraction and Structures Using Java,

Addison Wesley, 2003.

 

Office hours

 

            Monday from 1 to 4pm in my office.  (or by appointment)

 

Online course information

 

Up to date information about the course, including this document, notes, homework, due dates, review materials, solutions, and more, can be found at the course web site:

 

http://www.ccs.neu.edu/course/com1201/

 

News and discussion of course materials will occur on the Blackboard system:

 

            http://blackboard.neu.edu/

 

Questions and comments regarding lectures, homework, examination review, and more should be posted to the discussion boards on the Blackboard site.  Questions and comments of a personal matter involving grades, misconduct, &c. must be delivered via private email.  If you send me something via email that should have been posted to the discussion board, I will send it for you, with your name included.

 

Important information will be delivered via email as well as posted to the Blackboard site.  If you do not have an email account, please get one as soon as you can and check your email regularly.  If you do not have a Blackboard account, please get one as soon as you can and sign up for our course.

 

Rules of conduct

 

Although most of our class time will consist of lecture, discussion is always welcome.  Participation in discussions is not mandatory, but you will learn more if you participate regularly.  If you have a question or a comment, you may interrupt my lecture.  During a discussion involving other students, however, you must be respectful to your fellow students and raise your hand to participate.

 

If your mobile phone or pager rings in class, I will reduce your grade one step.  For example, if your final grade was to be A-, it will be reduced to B+.  These effects accumulate every time it rings.

 

Grading

 

Your overall grade for the course will be based on this outline:

 

Final examination                                                                           40%

Homework                                                                                    35%

Midterm examination                                                                     20%

Miscellaneous items                                                                         5%

 

If you receive a failing grade on the final examination you will receive a failing grade for this course, no matter what your average is.  Your grade will be reduced upon each missed homework assignment.  If you miss 3 or more homework assignments, you will receive a failing grade for the course, no matter what your average is.

 

You must take a short test on the Blackboard system each week of the quarter.  Your peer tutor will grade these tests, and if you do poorly, schedule meetings to get you up to speed.  Although your grades on the weekly tests will not figure into your final grade, they are mandatory, as well as the follow up meetings with your peer tutor as necessary.
Course outline

 

This outline does not list topics in the order we cover them, but rather by general theme.

 

A.  Java Programming

            1.  Using Java on a computer

            2.  Primitive types and simple algorithmics

            3.  Classes, objects, and references

            4.  Arrays

            5.  Classes with self-referential data

B.  Analysis of programs

            1.  Counting statements in execution

            2.  Asymptotic analysis

            3.  Simple verification of correctness

C.  Abstract data types

            1.  Stack ADT

            2.  Queue ADT

            3.  Vector ADT

            4.  List ADT

            5.  Priority Queue ADT

            6.  Map ADT

D.  Implementation techniques

            1.  Array

            2.  Circular array

            3.  Growing array

            4.  Dynamic array

            5.  Linked list

            6.  Doubly linked list

            7.  Tree stored in array

            8.  Doubly linked tree

            9.  Binary search tree

            10.  Open addressing hashtable

            11.  Separate chaining hashtable

E.  Algorithms

            1.  Insertion-Sort

            2.  Selection-Sort

            3.  Merge-Sort

            4.  Binary-Search           
Schedule (tentative, of course)

 

        Date        Description                                                                                                      Chapter(s)               Due

______________________________________________________________________________________________________________________________________________________

    26 Mar        Lecture:     Introduction, Extreme Java basics                                                  O1

    27 Mar        Lecture:     Primitive types, arithmetic, logic, loops, exceptions                    O4                        

______________________________________________________________________________________________________________________________________________________

    31 Mar        Lecture:     Abstraction in Java                                                                     1, O2, O3         Homework 1

      2 Apr        Lecture:     Abstraction in Java, Containers                                                       2                          

      3 Apr        Lecture:     Containers                                                                                                                        

______________________________________________________________________________________________________________________________________________________

      7 Apr        Lecture:     Analyzing programs                                                                           3                Homework 2

      9 Apr        Lecture:     Analyzing programs                                                                                                       

    10 Apr        Lecture:     Analyzing programs                                                                                                       

______________________________________________________________________________________________________________________________________________________

    14 Apr        Lecture:     Arrays                                                                                                   4                Homework 3

    16 Apr        Lecture:     Vector ADT and array implementations                                                                      

    17 Apr        Lecture:     Vector ADT and array implementations

______________________________________________________________________________________________________________________________________________________

    21 Apr        Lecture:     Linked lists                                                                                           5                Homework 4

    23 Apr        Lecture:     List ADT and linked list implementations                                                                   

    24 Apr        Lecture:     List ADT and linked list implementations                                       

______________________________________________________________________________________________________________________________________________________

    28 Apr        Lecture:     Applying lists                                                                                      6                          

    30 Apr        Test:            Midterm examination                                                        1 to 5                      

     1 May        Lecture:     Stack ADT, Queue ADT and implementations                       7.1 to 7.8                   

______________________________________________________________________________________________________________________________________________________

     5 May        Lecture:     Priority Queue ADT                                                                          7.9              Homework 5

     7 May        Lecture:     Priority Queue ADT and linear implementations                                                       

     8 May        Lecture:     Trees and binary trees                                                                 9.1 to 9.6                   

______________________________________________________________________________________________________________________________________________________

   12 May        Lecture:     Trees and binary trees                                                                                         Homework 6

   14 May        Lecture:     Priority Queue ADT and heap implementation                             9.7                        

   15 May        Lecture:     Map ADT                                                                                             8                          

______________________________________________________________________________________________________________________________________________________

   19 May        Lecture:     Map ADT and linear implementations                                                                        

   21 May        Lecture:     Map ADT and binary search tree implementation                  9.8 to 9.9                   

   22 May        Lecture:     Map ADT and binary search tree implementation                                          Homework 7

______________________________________________________________________________________________________________________________________________________

   26 May        *** Memorial Day ***                                                                                                              

   28 May        Lecture:     Map ADT and hash table implementation                                                                  

   29 May        Lecture:     Map ADT and hash table implementation                                                                  

______________________________________________________________________________________________________________________________________________________

       TBA        Test:            Final examination                                                                                     Homework 8