What is this course about?
This course is the second programming course in Computer Science required of all Computer Science majors. The unofficial purpose of the course is to elevate the student into a solid programmer familiar with the basic organizational principles of Computer Science. Under one point of view, this course is about acquiring the programming "tricks" which as a body form the foundation of stable, predictable and efficient programs. Under another point of view, the course introduces the student to the "Science" part of "Computer Science": the ideas exposed in this course are arguably what historically set Computer Science apart from its conceptual ancestors of Electrical Engineering and Mathematics. Thus the official purpose of the course is to foster an intuitive understanding of both points of view: the practical programming "tricks" viewpoint, and the theoretical foundational Computer Science viewpoint. In line with its dual-purposes, homework sets will be split into two kinds:
CS 3139 constitutes the most important lower-level gateway course taught at the Computer Science department, in the sense that it is the most widely required course by upper-level courses. For example, courses which require CS 3139 (or CS 3137) are CS 3156 (Software Engineering), CS 3261 (Computability), CS 4121 (Multimedia), CS 4180 (Network Security), CS 4231 (Analysis of Algorithms), CS 4236 (Introduction to Computational Complexity), CS 4701 (Artificial Intelligence), CS 4705 (Natural Language Processing), CS 4733 (Robotics), CS 4861 (Computer-Aided Design of Digital Systems), and CS 6181 (Advanced Internet Services),
What's the difference between 3139 and 3137? This course covers the same basic material as 3137. The differences lie in the approach for teaching data structures as well as on the expectations put on the students. Students are assumed to be familiar with basic GUI programming in addition to the material covered in 1007. Furthermore, students should not be "afraid of proofs" as a more rigorous approach to theory will be used than in 3137. The viewpoint of the course differs from many versions of 3137 in that the Data Structures concepts are covered in less detail and students are assumed to be reading and understanding the material by the time that it is discussed in class. This allows for a more high-level approach which emphasizes how the Data Structures are used to solve algorithmic problems interesting in their own right, rather than focusing on the nitty-gritty behavior of the particular Data Structure. Of course, students are still assumed to be able to reproduce the nitty gritty behavior of the Data Structure if asked to do so on an exam or homework, but this will be the easiest kind of exercise encountered, rather than a typical question, as might be the case in 3137.
Who is eligible to take 3139? Anyone who took 1009 is eligible, as well as anyone who took 1007, received a solid A or above, and is willing to study the GUI-related material necessary for doing Homework number 4 of CS 1009, Fall 2000 (www.columbia.edu/~cs1009/hw4.html). Exceptions can be made, and you should see the instructor for approval to be let in the class if you feel that you deserve that an exception be made. If you're not sure about whether or not you should take the course, please have a look at the first two homework sets at: www.cs.columbia.edu/~zeph/3139/hw.html The last day to add a course is 1/26. However, students in 3139/3137 will be allowed to switch between the two courses up to one week after the midterm which occurs 2/28 and homework and exam credit will be transfered. It is not recommended that you do this, however, unless you absolutely have to as the courses will diverge fairly soon.
Course web site:
www.cs.columbia.edu/~zeph/3139/
Times and places:
Instructor Office Hours: 4:15 - 7:00pm on Wednesdays in 626 CEPSR
Required Text : Data Structures and Algorithm Analysis in Java by Weiss (Addison-Wesley-Longman, ISBN: 0201357542). You can buy it at Papyrus (114th & Broadway).
It is the traditional book used both in CS 3139 and CS 3137. It is also the traditional text in Prof. Okasaki's Advanced Data Structures Course. The book is in-depth and definitive. On the other hand, the book is very dense and the theoretical arguments can be hard to follow; furthermore, the author's Java code can be bizarre at times, so students should read Weiss's code with a grain of salt. Overall, no other available book covers as many data-structures as well, with as modern an approach, and with the least number of pages as this text.Recommended References:
Java Books:
Internet Java resources:
Homeworks: Please consult the syllabus for a list of homework due-dates. There are 10 homeworks. Homeworks alternate between theory and programming. Theory homeworks are each worth 20 pts., while all the programming homeworks are worth 30 pts., except for the final project which will be worth 45 pts. Homeworks are due at 2:40 pm in the class room. For theory homeworks, this means that you bring in a hand written (or typed) copy to hand in. For programming homeworks, this means that you bring in a hard copy of your code to hand in, AND have submitted your code electronically from your CUNIX account, using the submit program. Again we must reiterate the following:
If you haven't given the collecting TA your homework before the TA leaves class, your homework is considered late. Late homeworks will be accepted until the solutions appear, but be aware that solutions are slated to appear on the afternoon on which they are due. 10% is taken off for each day late, starting with 10% off the first day. It is the student's responsibility to find a TA or the Professor to hand in a late homework. Homework should constitute your own work. You are encouraged to discuss homeworks with other students, but in such a case you should list all the people that you collaborated with on the top of the homework submitted. You should not copy solutions from other students. There is a more stringent cheating policy on programming assignments: Don't even look at another student's code in this class, or let another student view your code, before the the code has been submitted and the official solutions have appeared. Here are typical examples of what does and does not constitute cheating:
For convenience, all programming can be developed on any machine in any version of JAVA. However, only programs that are submitted electronically by the submit program on Columbia machines and that compile using the JAVA compiler on those machines, and can be read legibly via EMACS on the CUNIX machines will be graded. In addition, a hard copy of the program source code and its execution on test data must be turned in, so that both the programming homework can receive TA grades, feedback, and comments.
It is critically important that all submitted program listings and executions be thoroughly documented. Further, all documentation must be internal; annotations made to hard copy listings will be ignored. Good programming style will account for a substantial portion of the grade assigned to the programming part of the assignments.
All programs must compile; programs that do not compile will receive a grade of zero. Usually the homework assignments will only state the major objectives of the program to be written; it will be often up to you to make design decisions regarding I/O, efficiency, error handling, and so on. Make sure you provide adequate test cases to indicate the correctness and robustness of your approaches. In general, the failure of a grader to understand your work or to appreciate the thoroughness of its testing will be considered to be your error. Unfortunately, there is neither time nor facilities to allow live demos of homeworks.
Final project: The final programming homework will be worth 50% more than each of the other programming assignments. Students with interesting ideas for projects related to the topics of the course can come talk to the instructor. Depending on the proposal, extra credit may be assigned to the final project.
Extra credit: Extra credit will be available on some homework assignments and due with the homework, except for cases noted otherwise. Exams may also have an extra credit component.
Grading: There will be a curve on both the total homework score and exams. The theory homework is worth 20%, the programming homework is worth 35%, the midterm is worth 15% and the final is worth 30%. Time allowing, an announced quiz or two may be added. In such a case the quiz's weight will be announced and taken from the final (under one scenario, a single quiz would be given with weight 5% and then the Final's weight would be reduced to 25%). Extra credit is assigned with points weighted relative to the homework. For example, correctly doing an extra credit problem worth 6 pts. ends up giving you an extra 0.6% on your final grade. Total homework score, midterm, quiz and final scores will be curved separately. Extra credit is not curved.
After curving the raw exam and homework scores in percentages, the grade weighting above is summarized (assuming no quiz) by:
finalGrade = 0.35*ProgrammingHW + 0.20*TheoryHW + 0.15*midterm + 0.30*final + ExtraCredit
Readings: The schedule contains a list of readings for each lecture. You should do the readings before the lecture.
Cheating: Cheating consists of falsely representing work as your own, whether on homeworks or exams. You are strongly encouraged to discuss homeworks with friends, but you may not copy solutions, either from the friend you worked with, from the internet, or any other source. See above for examples of what does and doesn't constitute instances of cheating. Penalties for cheating include but are not limited to getting a 0 on the work which contained cheating, and disciplinary action. For more information about the department's cheating policy see Columbia Computer Science Department's cheating policy.
Regrades: If you feel that a problem on a homework or on the midterm was graded incorrectly, the grading TA can give you a regrade. Be aware that the TA will regrade the whole assignment and that your score may go down if mistakes which were previously ignored are discovered. All regrades must be requested within 2 weeks of when the assignment or exam was returned. Grade changes are subject to instructor approval.
Uncollected work: A designated collecting TA will hold on to any homework or midterm that you didn't pick up.
Special circumstances: If there are reasons beyond your control which make it impossible to follow one of the above policies, you should inform us as soon as possible. You will need to properly document your special situation.