CS 61B General Information

Introduction

Welcome to CS 61B, "Data Structures and Programming Methodology".

What's CS 61B all about?

CS 61A covered high-level approaches to problem solving, providing you with a variety of ways to view programming problems (in terms of functions, objects, or rules). In CS 61B, we move to a somewhat more detailed level of programming. As in 61A, the correctness of a program is important; in addition, however, we're concerned with a program's efficient use of time and memory resources. Much of 61B will be devoted to the tradeoffs in time and memory that arise from a variety of methods for structuring data. (The third course in the sequence, CS 61C, continues the journey from high-level programming to the details of the machine level, covering the basics of computer architecture and revealing aspects of the computer that programming environments hide from you.)

The 61ABC sequence arose from a desire to enhance the connection between CS 61A and the data structures material. In this course we will make frequent reference to material covered in CS 61A: recursion, linked data structures, and object-oriented programming.

What's new about CS 61B?

Instead of running the class with loosely coordinated lecture, discussion, and lab sections as in previous versions of CS 61B, we have only one hour of lecture plus a six-hour lab section. (We have run CS 3 in a similar format for the past three years, and ran a successful pilot section of the new format in CS 61B last fall.) In the lab section, we expect to get to know you better. We also hope to integrate the various parts of the course more closely and thereby help you to learn better. We will be using software that structures the various course activities, increases opportunities for collaboration, and gives you better feedback on your work. It should be a fun semester.

Staff

The instructor is Mike Clancy (clancy@cs.berkeley.edu, 779 Soda, 642-7017). His administrative assistants are Cindy Palwick and Sue DeVries in 385 Soda. The teaching assistants are still being assigned as this is written. There will also be lab assistants working with us during the lab sections, and readers to grade your homework. Detailed information on contacting staff will be available later this week.

Books and other course material

There are four required texts for the course. Three are available at the campus bookstores:

The first edition of Head First Java should suffice for this class. It and Data Structures and Algorithms in Java were used in CS 61B last semester, so used copies should be available.

The fourth text is named "CS 61B Readings", available at Copy Central, 2483 Hearst. We will be using the Readings, Head First Java, and Pragmatic Unit Testing the first month or so of the semester, and Data Structures and Algorithms in Java later on.

Should you need a guide to the UNIX operating system, we suggest either the EECS Instructional User's Guide to UNIX, available online through the URL http://inst.eecs.berkeley.edu/labs.html, or A Practical Guide to Solaris, by Mark Sobell (Addison-Wesley, 1999), available at a bookstore. Also, we expect the Computer Science Undergraduate Association soon to be running UNIX help sessions. Access the URL http://www.csua.berkeley.edu/help-sessions for up-to-date information.

Class activities and scheduling

There will be a one-hour lecture each week on Mondays from 5 to 6pm. (The lectures from CS 61B were webcast last semester and will be again this semester. The webcasts, available at http://webcast.berkeley.edu, may be a useful resource.) In-class exams on Monday, September 26 and Monday, November 7 will extend into the 6-7pm hour.

You are each assigned a lab section that you are to attend each week. Available sections are TuTh 11-2pm, TuTh 2-5pm, WF 11-2pm, and WF 2-5pm. (A section formerly listed for TuTh 5-8pm has been cancelled.) You may attend a section to which you're not assigned only with the permission of both the relevant lab t.a.s.

For most of the semester, the typical lab period will involve a variety of activities, all provided online. It will start with a short quiz based on topics covered on the homework or in the preceding lab; each start-of-period quiz will count toward your course grade. It may conclude with another quiz covering the material you just worked with; each end-of-period quiz will function as a diagnostic to give you feedback on what you don't fully understand. In between, you'll be reading, experimenting, brainstorming, evaluating each other's ideas, and sometimes working with partners.

A short set of homework exercises will be typically be assigned at the end of each lab. The exercises will involve writing or analyzing programs and contributing to online discussions about typical programming misconceptions. Solutions to the programming exercises and contributions to the discussions will be submitted online. There will be three larger project assignments during the semester, to which some of the lab meetings will be devoted. (The first two projects will be individual efforts; for the third, you'll be allowed to work in partnership.) You should expect to put in at least four or five hours of work per week outside of class. If you finish the online exercises early, you may leave early or work on your homework.

There will also be three exams. Two will be in class, on September 26 and November 7, from 5 to 7pm. (Note the extra hour.) The other will be the final exam, Saturday, December 17 from 12:30 to 3:30pm (exam group 14).

The programming tools and course material used in CS 61B were devised by a research group of computer science and education researchers. To determine the effectiveness of these tools and material, we will gather data on your background and performance, via questionnaires, interviews, and analysis of your work. You will be expected to take part in an hour-long interview with a staff member, and to complete several surveys through the course of the semester.

Computing

Most of your work for this course will be done in class in 275 Soda. Outside of class, you may work in any EECS lab room in which a lab section is not meeting.

To access the CS 61B Course Portal, http://fall05.ucwise.org, you should use a recent version of the Mozilla browser, with a plugin that supports Java 1.3, or (on Macintosh OS X) a recent version of the Safari browser. Earlier versions of Netscape and any version of Internet Explorer will not work well. There are a variety of free Java programming environments available, e.g. JBuilder, Jipe, DrJava, NetBeans, and Eclipse. We will use Eclipse in lab.

You will each be given an account on the EECS instructional computers. Account forms will be handed out in your first lab section. You should change your password during your first lab section; password changes need a half hour or so to take effect, so do this right before you log off. Initial access to the CS 61B Portal also requires an enrollment code, which t.a.s will provide in your lab section.

The Soda labs are open from 7:30am to 6pm Monday through Friday. Outside of these hours the doors to the building and lab are locked, and you will need to obtain a card key for after hours access. Card keys will not be available immediately, because we need an accurate list of who is in the class first; an announcement will be made in class when they are ready. If you have a new student ID card that can double as a card key, access to Soda on weekends or late at night is free; otherwise you can obtain a card key from 390 Soda for a $25 fee ($15 is refundable at the end of the semester).

Grading

The various course activities will contribute points to your grade as follows.

activity course points percent of total grade
projects 36 18%
all other homework scaled to 24 12%
all quizzes scaled to 14 7%
selections from other monitored activity 6 3%
both midterm exams 60 (30 each) 30% (15% each)
final exam 60 30%

Your quiz score will be capped at 70% of the maximum total points, then scaled to 14. Similarly, your homework score will be capped at 90% of the maximum total points, then scaled to 24.

You are expected to keep up with the classwork. There will occasionally be time devoted in lab to helping you catch up or solidify your understanding of the material. Homeworks assigned in one lab section are due at the start of the next section unless otherwise specified. You will be expected to submit homework on time, and to take quizzes on the day they are assigned. Quizzes are online, and thus may be taken outside of the lab room. You will receive credit for at most four quizzes taken outside of your lab section. Any quiz assigned in one lab section must be completed by the start of the next lab section to earn any credit.

Each week one of the steps in the online materials will count towards your grade. (This grading component is referred to as "selections from other monitored activity" in the table above.) Which step this is won't be known to you (or to us, beforehand). It will generally be a step for which you are asked to answer a question or create a file. This serves as an incentive for you to keep up with the lab materials. The grades for these steps will be for your honest attempts rather than for perfect solutions.

Your letter grade will be determined by total course points, as shown in the following table:

points 185-200 165-185 155-165 145-155 135-145 125-135
grade A+ A A– B+ B B–
points 115-125 105-115 95-105 75-97 <75
grade C+ C C– D F

In other words, there is no curve; your grade will depend only on how well you do, not on how well everyone else does.

Incomplete grades will be granted only for dire medical or personal emergencies that cause you to miss the final exam, and only if your work up to that point is satisfactory.

Copying and presenting another person's work as your own constitutes cheating. It will be penalized at least by a 0 on the work in question and notification of the incident to the Office of Student Conduct.

Approximate topic/activity schedule

Here is a very tentative schedule of topics to be covered, project due dates, and exams. Titles of the four course texts are abbreviated as follows:

week of ... activities topics reading
August 29 introduction to Java; flow-of-control; testing HFJ chapters 1-2; 61BR, "CS 61A Scheme to CS 61B Java"; DSAJ sections 2.5 and 4.1
September 5 Labor Day holiday (Monday) variables; objects; references; arrays; test-driven development; JUnit HFJ chapters 3, 4, and 9 except material on inheritance in pages 250-255; PUT chapters 1 and 2; 61BR, "Boxes and arrows"
September 12 for loops; more on arrays and testing; java.util HFJ chapters 5, 6, and 10, and Appendix B #7 and #2; PUT sections 3.1-3.3 and chapters 4 and 5; DSAJ sections 5.1-5.3
September 19 inheritance, polymorphism, and interfaces HFJ chapters 7 and 8, pages 250-255 in chapter 9, and Appendix B #4; DSAJ sections 2.1, 2.2, and 2.4
September 26 exam 1 (Monday) sorting; big-Oh notation; linked lists; comparative implementations 61BR, "Notes on linked data structures"; DSAJ chapters 3 and 5
October 3 project 1 due (Monday) exceptions; stacks and queues; trees and tree iterators HFJ chapter 11; DSAJ section 2.3 and chapters 4 and 6
October 10 more on trees
October 17 hashing DSAJ chapter 8 except section 8.4
October 24 more on hashing; search trees; project work DSAJ section 9.1
October 31 project 2 due (Monday) priority queues DSAJ chapter 7
November 7 exam 2 (Monday); Veterans Day holiday (Friday) graphs DSAJ chapter 12
November 14 more on graphs; more on sorting
November 21 Thanksgiving holiday (Thursday, Friday) project work DSAJ chapter 10
November 28 balanced trees, tries; project work DSAJ chapter 9 and section 11.3
December 5 project 3 due (Friday) project work; review

Policy on collaboration and cheating

Copying and presenting another person's work as your own constitutes cheating. Cheating directly affects the reputation of the Department and University and lowers the morale of other students. Consistent with departmental policy, each incident of cheating on a homework or lab activity will result in a negative grade on that activity, while cheating on a project or exam 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.

Sometimes it's hard to draw the line between cheating and appropriate collaboration. Obviously wrong is getting a "homework service" to write your program for you, or finding a solution on the Internet and submitting it as your own. On the other hand, providing suggestions to a classmate about the meaning of a question and offering advice about the likely meaning of a compiler error message are examples of interaction that we encourage. The various collaboration activities in CS 61B may complicate matters further. Some useful rules of thumb, however, are the following:

Fortunately, we have found in the past that the close interaction between lab instructor and students in a lab-based class serves to support student learning (reducing the need to cheat) and to convince students both that the instructor cares what they learn and that solutions that differ significantly from students' earlier work will be detected.

Other courses

If you're interested only in learning Java, the self-paced course CS 9G ("Java for Programmers") may be more appropriate for you. CS 9G is not a prerequisite for CS 61B, nor does it satisfy any requirements that CS 61B does.

CS 9E ("Personal UNIX") is another self-paced course of interest. It covers UNIX use in more depth than does any other course currently offered in the Computer Science Division.

Both courses (and the other CS 9 courses) are 1 unit, and must be taken P/NP. There are no lectures other than the identical orientation meetings Monday, August 29 and Tuesday, August 30, both 6-7pm in 306 Soda.

Those of you who have had a data structures course that covered most but not all of CS 61B are eligible to take CS 47B, a one-unit course that completes the material of CS 61B and satisfies all requirements for CS 61B. CS 47B is also self-paced, graded. Programming is done in Java.