Columbia University, Computer Science Department


CS W3137 Data Structures and Algorithms,Spring 2011, General Information


Instructor

Prerequisites

Textbook

Java Language References - any Java book is fine, here are some choices:

Course Structure

The course consists of 29 lectures. Four or five will be released immediately, thereafter there will be three new lectures aavailable a week. There will be about 5 homework assignments with the possibility of an optional sixth due on a regular basis, a midterm (closed book and notes) and a 3 hour final exam (closed book and notes). The language used for this class is JAVA version 1.6 as implemented on the CUIT Cunix machines. You may use another machine if you wish with the caveat that it must have a standard Java compiler and that you do not use any extensions on the machine beyond those available here at Columbia. Your programs eventually must be run on our system when you hand them in, so make sure the code you write is portable and compatible with our systems. The only acceptable running programs are those on our machines here at Columbia. Programs will be submitted electronically.

Get help when you need it! We would like the course to run smoothly and enjoyably. Feel free to let us know what you find good, interesting, or problematic about the course. If you have any concerns about your level of preparation for this course, or if you begin to have difficulty with the material, please see me or the TAs to get extra help. Likewise, if a situation that affects your class work arises during the term (e.g. medical or family emergency), please contact me as soon as possible so that we can arrange for you to catch up with missed work. The I am very happy to work with individual students in office hours over the course of the term -- please get help when you need it. Unfortunately, there is very little I can do for students who only come to see me at the end of the term and have not completed enough work to pass the course. I will be available by email or during my regular office hours and by appointment. If you are unable to see me for any reason, send me mail at bms2156@columbia.edu . Students sometimes have problems in the beginning of this course, and that is exactly the time to communicate with me before things get out of hand.

Course Grade

The final grade for the course will be determined as follows: Homework assignments 40%, Midterm 25%, Final 35%

Main Topics to be Covered

  • Recursion
  • Algorithm Analysis
  • Linked Lists
  • Stacks, Queues
  • Trees
  • Heaps
  • Graphs
  • Hashing
  • Sorting

    Cheating and Academic Dishonesty

    First, read the CS Department Policies and Procedures Regarding Acadmeic Honesty. Unfortunately, it is necessary to mention the subject of cheating. I have taught this class over many semesters, and I HAVE ALWAYS HAD A CHEATING INCIDENT, usually multiple incidents. While I sincerely hope that this does not happen this semester, I must make everyone aware of the policies in place to prevent cheating.

    Why does cheating occur? It usually occurs because students run out of time to do an assignment, and feel they have no other way of completing the assignment. How can you prevent this urge to cheat from overcoming you?

  • Do not wait to start the assignment until a few days before it is due. This is guaranteed to cause you problems
  • Do not hesitate to get help from the TA's or myself if you find yourself stumped or unable to begin an assignment
  • Realize that this course is 4 credits, and as such, requires a hefty time commitment. You can't successfully do the work in this course if you are holding down a part-time job, and taking 18-20 credits of classes.

    The assignments and all extra credit exercises assigned for this course are NOT team projects. There is to be no collaboration with anyone else, other than the TA's or myself. These are individual asignments.

    A major goal of this course is to learn the concepts required in the construction of programs. Each student must actually engage in the creative process of constructing these programs - simply producing a working program is not enough. Each exercise, if carried out by the student, will give the student understanding, or will reinforce the student's understanding, of an important computer science concept. Hence, the student is permitted to inspect related problems and ask questions of the TA and others in the class about the problem and related problems, but the student is not permitted to copy the work of ANYONE. The ONLY exception to this is code in the textbook or in my class notes. Likewise, students allowing others to copy their own work are guilty of cheating. Furthermore, it is the responsibility of every student to make sure their work is not available to others. One way to determine if cheating or collaboration has occurred is to analyze the level of understanding each student has in their own work. Since this understanding is at the center of the course goals, each student must strive to have a complete understanding of every exercise. If you have not collaborated or cheated,, then you should know exactly what you produced and handed in.

    Of particular concern is using resources that include other textbooks and written materials, and web content of others. Note, you may not use code written by others (other than in your own textbook or class notes), including anything you find on the web. The TA's are particulalry adept at finding web-based cheating. Note that the same site a cheater may find through Google, our TA's can also find that site! Also note that we have electronic means to detect collaboration (MOSS), which is even better than our own expertise, that we will use to check for cheating on every assignment.

    back to CS 3137 Home page