CS61b: General Information for Fall 95

Data Structures and Advanced Programming

Introduction

CS61B is the second course in the CS61 series. In this course we will study advanced programming techniques including data structures and basic algorithms for manipulating them, and a taste of ``software engineering''---the development of large programs.

Read this document carefully. It contains most of the answers to questions that students ask during the first few weeks of class. The subjects include: how to contact the staff, prerequisites, textbooks, labs, grading, late penalties, policy on academic misconduct. For a list of discussion sections and labs and the TAs who run them, see the section schedule. A tentative syllabus is also available, which includes due dates, exam dates, and reading assignments.

To print this document, use this postscript copy. If you have a general question about something that is NOT covered here, the best option is to post a message in the cs61b news group. This is read by the course staff and other students, all of whom may be able to answer your question. To contact all of the TAs and me, send mail to cs1b@po.eecs.berkeley.edu. If you wish to talk with one of us, the easiest way is to come during the office hours posted on our doors and listed in the file $master/adm/hours. Otherwise, please make an appointment by sending electronic mail.

Staff

Instructor Prof. Kathy Yelick
Office: 777 Soda Hall
Office Hours: TBA
Phone: 642-8900
Email: yelick@po.eecs

Course Secretary
Crystal Williams
385 Soda Hall
642-0930

Teaching Assistants
Roy Chua, cs61b-ta@po.eecs
Ken Johnson, cs61b-tb@po.eecs
Kim Liu, cs61b-tc@po.eecs
Jeff Sidell, cs61b-td@po.eecs
Jonathan Walden, cs61b-te@po.eecs

Lectures are MWF 3:00-4:00pm in 100 Lewis. Office hours for teaching assistants are held in 283 Soda, although you may find the TAs in the lab (271 or 273) during their office hours, if many students have questions that are easier to answer in front of a computer.

Prerequisites

The prerequisite for CS61B is CS61A. CS61A is an introductory course taught in Scheme, which covers topics like recursion, higher order functions, object-oriented programming style, simple data structures (lists and tables), as well as the basics of using the computers in our labs. If you wish to take the course without the prerequisite, but are familiar with some programming language and with most of these topics, you should have adequate background for CS61B. Otherwise, I strongly encourage you to take CS61A before taking this course. We will be using the C++ programming language in this course; C++ is an extension of C with support for object-oriented programming. You need not be familiar with C or C++, but should feel comfortable programming in some language (preferably Scheme) before taking this course.

If you are already familiar with C or C++ and have taken a data structures course in any programming language (e.g., Pascal), you probably do not need to take this course. If you feel this course may be repeating prior experience, please see me.

If you are not familiar with the Unix operating system and basic tools, it is important that you learn. The ``EECS Instructional Users's Guide to UNIX'' (described in the section on textbooks) contains some introductory material on UNIX. IS&T will be running UNIX short courses on September 11, 13, and 15 from 10am to noon in 262 Evans. These are free, but you need to register in 241 Evans.

Textbooks

The textbooks for Fall '95 61B are the same as the texts used this summer '95, but different from those used in previous years. The required texts are: These as well as the recommended texts should be available at the ASUC bookstore or across Bancroft at either Ned's or the Campus Textbook Exchange. The Deitel and Deitel book (abbreviated D&D in the remainder of this handout) gives a thorough introduction to programming in C++. We will be using this book starting the first week of classes so it is important that you purchase this book as soon as possible.

We will not be using the second required text (Carrano) until the third week of the semester, so you may postpone buying this book if you're not sure you will be taking this course. The Carrano book is on data structures and uses C++ in the code examples.

The first recommended text is: ``The C++ Programming Language'' by Bjarne Stroustrup (Addison Wesley, second edition, 1991, printed with corrections, 1993), the canonical C++ reference by the designer of C++. The book is hard to read unless you know C, and even then it is a bit dry. However, it may be a good book to have on your shelf if you plan to do more C++ programming after this semester. CS162 and CS169 both use C++, and this semester CS164 is also being taught using C++. The Deitel and Deitel book has been used as a reference for CS169 (Software Engineering), so it is fairly complete. Most likely you will not need a copy of Stroustrup, but if you have a question about some fine point in C++ syntax or semantics, it is a good place to look. Copies of Stroustrup and the other texts are on reserve in the Engineering library.

The final recommended text is the ``The GDB Reference Manual'' by the Free Software Foundation. This is a manual for the GNU Debugger that goes with the compiler.

In addition to the textbooks, there is an optional reader describing the machines and basic UNIX utilities called the ``EECS Instructional Users's Guide to UNIX.'' It tells you how to read mail, post and read news groups, print, and do other useful things. It is available at Copy Central on Euclid for about $9. If you took CS61A or another CS course recently you should already have a copy of this (only minor changes have been made since last year) and do not need to purchase another one.

There will be other handouts during the semester, of course, and you need to give your TA $5 to cover the copying charges for these. A check to U.C. Regents is preferred, but we will also accept cash. This money will be collected in discussion section this week.

We will keep electronic copies of all handouts on the course machines in the directory $master/handouts, and lecture notes will be in $master/lectures. There may be two types files in these directories: raw ASCII text (filenames ending in .txt) should should be printed using the enscript -2r command; postscript files (filenames ending in .ps) must be printed using the lpr command. Most of these documents will be available through the class home page.

Finally, we will post various announcements, hints, and so forth electronically. Your accounts will be set up to show the current set of class messages when you login. In addition, you should start reading the 61B newsgroup regularly, as we will be posting homework clarifications and other material of general interest there. To read the news group, type rn ucb.class.cs61b -q. For a GUI (Graphical User Interface) version, try xrn or simply use your HTML reader. You should send questions or information of general class-related interest to the news group using the post command. Additional information on the use of newsgroups can be found in the UNIX guide.

Enrollment---Laboratory and Discussion Sections

In addition to the lectures, the course consists of a discussion section one hour per week and a scheduled lab two hours per week. The discussion sections meet between Monday and Wednesday lectures, whereas scheduled labs meet between Wednesday and Friday lectures. All labs meet in 271 Soda. You should have the same TA and student colleagues in the lab and discussion section. (Two exceptions are sections 116/16 and 120/20, which have different instructors for lab and discussion.) Your Lab TA will be your ``primary'' TA--he or she will check off your lab assignments, will return your graded homeworks and projects, and can help with grading corrections. You should feel free to attend any of the staff office hours or ask any of us for help.

Students sometimes ask whether section and lab attendance is required or optional. Some of the TAs may use ``mini-quizzes'' in discussion section to give them feedback on how much the class understands and to help focus the discussion, but nothing done in section will directly affect your grade. On the other hand, discussion sections are your best opportunity to ask questions and learn interactively, and there may be examples worked out in section that will be helpful on the graded assignments. Scheduled labs, which are two-hour slots in the second half of the week, are required. Each week there will be a assignment for the lab, and points to be checked off by your TA.

Account forms will be given out in lab this week, so it is important that you attend. You must fill our a computer account during the first week of class. After reading and signing your account form, give the top portion to your Lab TA. If you miss your first lab, account forms, like all handouts, will be available from Crystal Williams (in 385 Soda). It is important that you login to your account and choose a password the first week; your accounts are set up to gather certain information we need and we use this information to determine who is really in the class.

If you are not yet enrolled through Telebears, or if you are something other than a regular Berkeley undergraduate, then you probably need a signature on a form admitting you to the course. Past experience indicates that enough students will drop the course to allow me to admit all qualified applicants. However, I won't be sure about this until after the computer accounts are assigned. Therefore, I will not sign your add form until the second week of classes. Meanwhile, you should get your computer account and begin doing the course work on the assumption that you will be admitted.

In addition to the scheduled labs, there will be some periods in which the lab assistants will be available to answer questions in 271 Soda. A list of these times is posted outside the lab. The Soda labs are open from 7:30am-6:00pm Monday through Friday. Outside of these hours it is usually running, but the doors to the building and lab are locked. You will need to obtain a card key from 395 Cory for after hours access; these will not be available immediately, because we need an accurate list of who is in the class first. An announcement will be made in lecture when they are ready.

Watching Taped Lectures

For those of you who miss lectures, a taped version will be shown. Monday and Wednesday lectures will be shown Tuesday and Thursday at 4pm in 225 Wheeler. Friday lectures will be shown on Mondays at 4pm in 222 Wheeler. In addition, aa tape for each lecture will be available for approximately one week in 205 McLaughlin. 205 McLaughlin is open MTRF 9:30 to 5:00 and W 9:30-2:00 (may be subject to change).

Course Work and Grading

There are a total of 200 points you can earn toward your final grade in the course. There will be two midterm exams, each worth 25 points, and a final exam worth 50 points. The tests concentrate on the material that has been covered up to and including the week before the test. The tests coverage is cumulative, so material from the beginning of the course may be tested in either midterm or on the final. All exams will be graded by the TAs and myself.

In addition to exams, there are three types of assignments: homeworks, labs, and projects. Homeworks (roughly one per week) will involve written assignments and programming to be done individually. These will typically be due before lecture on Wednesdays and will be graded by one of the class readers. Homeworks are worth a total of 20 points out of the 200.

Labs are short programming assignments that must be done during the scheduled lab period in the latter part of the week. Labs will be done in teams of two assigned by your Lab TA. Grading of labs will be done by having certain steps checked off by your TA--most of the credit for these will come from demonstrating a certain amount of progress on the assignment. Labs are worth 10 points of your final grade, and we will ignore your two lowest lab grades during the semester.

The remaining 70 points of your final grade will come from the programming projects. There will be two of these during the semester, both worth 35 points. (Project 2 was mistakenly listed as being worth 40 points in the original version of this handout.) Both projects will be done with in teams of two. Your project partner should be someone in your lab and discussion section.

Your final letter grade will be determined by the following formula: 185 or above is an A+, 175-184 is an A, and down by ten points each to the lowest passing grade (D-). In other words, there is no curve; your grade will depend only on how you do and not on how well everyone else does. If everyone does exceptionally badly on one exam, I may decide the exam was at fault rather than the students, in which case the grades may be raised from these guidelines. I will not adjust grades in the other direction; if everyone gets an A, that's great.

We will return graded course work in labs. Everything you turn in for grading must show your name, your computer account, and your lab section number. You will receive no credit for assignments that are turned in without this information. If you believe we have misgraded a midterm exam question or project, return it to your Lab TA with a note explaining the problem. The entire exam or project will be regraded, so be sure to check the solutions to confirm that your final grade will go up after regrading. Your grades will be recorded online and can be viewed using the glookup program. All requests for regrades and recording corrections must be made before the final exam. By University policy, final exams may not be regraded.

Grades of Incomplete will be granted only for dire medical or personal emergencies that cause you to miss the final, and only if your work up to that point has been satisfactory.

Lateness

We will give no credit for written homework or labs turned in after the deadline, so that we can make online solutions available promptly and so that you can discuss those solutions in your discussion sections. Please do not ask for exceptions; an individual assignment is worth too few points to justify the effort. You can miss a couple of assignments or labs and still get your A+. If some personal crisis disrupts your schedule one week, don't waste your time and ours by trying to fake it; just be sure you do the next week's work on time.

On programming projects, we are slightly more lenient. If an assignment is N hours late, we'll penalize it ceiling(N/3) percent. While this gives you some leeway for putting the final touches on a project, do not stretch the deadlines too far. A project that is one day late will loose 8% and after a few days even a perfect solution may not earn a passing grade.

Policy on Collaboration and Cheating

Cheating directly affects the reputation of the Department and University and lowers the morale of other students. As is consistent with departmental policy, incidents of cheating on homeworks or labs will result in a grade of zero on that assignment, while cheating on projects or exams will result in a failing grade in the course. All incidents of cheating will be reported to the Office of Student Conduct where records of academic misconduct are kept throughout your undergraduate career.

We encourage you to help each other learn the material by discussing the work before you do the assignments. I believe that most students can distinguish between helping other students, for example, explaining the meaning of question, and cheating. If you are not sure whether a particular interaction is appropriate, talk to your TA or to me before you turn in the assignment. If you receive a significant idea from someone in the class, clearly acknowledge them in your solution. Not only is this a good scholarly conduct, it also protects you from accusation of theft of your colleagues' ideas.

Presenting another person's work as your own constitutes cheating. Everything you turn in must be your own doing, and it is your responsibility to make it clear to the graders that it really is your own work. The following activities are specifically forbidden on all graded course work:

Some of the assignments in this course will be done in teams. This will be clearly marked on the assignment, along with rules for choosing a partner. Any assignment that is not designated as a team assignment should be done individually. On team assignments, the above rules for individuals apply to teams: you may not increase the size of your team, exchange partners without our permission, work with another team, or share solutions across teams. Each individual in a team is responsible for the entire project, which means that you will be held responsible if your partner uses another group's solution to produce part of your team's solution.

In my experience, nobody begins the semester with the intention of cheating. Students who cheat do so because they fall behind gradually and then panic, or because they perceive that they have fallen behind when they have not. Some students get into this situation because they are afraid of an unpleasant conversation with a professor if they admit to not understanding something. I would much rather deal with your misunderstanding early than deal with its consequences later. Even if you are convinced that you are the only person in the class that doesn't understand the material, and that it is entirely your fault for having fallen behind, please overcome your feeling of guilt and ask for help as soon as you need it. Also remember that the other students in the class are working under similar constraints---they are taking multiple classes and are sometimes holding down outside employment.