CS 146 Fall 2009

Data Structures and Algorithms

Dr. Beeson

This is the main course web page. It will contain links to important course information, as well as a link to the homework submission system. Students in the course should check this page often. Recent important changes will be in red.

The Needleman-Wunsch assignment was posted Friday morning, Nov. 20.

Here are the solutions to the second midterm.

Here are the grades on both the first and second midterms. Most students did well on the middle six problems; no student correctly solved the first problem. About half the students knew what line of code was needed to help Bob get home; that probably earned them a B; and the A students could also say something sensible on the last problem. Of course these generalizations may not apply in individual cases.

The fact that no student could solve a recurrence relation on the midterm made nobody happy. Here is an email conversation I had with a student (whose name is deleted) about the subject.

Regarding the Google assignment. If you are having difficulty please be sure you understand the algorithm before programming. To do that, do TWO hand simulations of Example 0. The first one, as we did in class, writing the matrix in the usual human way. The second pencil-and-paper simulation of Example 0 should be done writing the matrix (on paper) as a BigMatrix, i.e. with a linked-list diagram for each row. Make sure you understand how the B-matrix is built.

Rules for what constitutes an acceptable submission on programming homework.

Questions students have asked about those rules, and my answers.

Here’s a copy of the green sheet. There you can find out what the textbook is and what the grading system will be.

Here are the Assignments.

If you are having trouble with ListBigNum timing out on large inputs, you could adjust your program so it gives up immediately on computing Fibonacci(n) when n >= 150,000. Then you'll fail the last test and still get a B (minus late penalty = D) if you pass all the other tests. But D is a passing grade.

Here are the solutions to the first midterm.

If you want your exam back, please pick it up during my office hours. If you think there has been a mistake in grading, this must be settled before you take the exam out of my office. In other words, you can't take it home and then come back and raise an issue.

Here are the review exercises. You will get an A for completing all the review exercises, and that A will count as one homework assignment in this course.

View the grades. It's a good idea to check, after submitting, if your grade shows up properly here.

Are you having problems submitting your homework? Check these possible problems and their solutions.

Photo Galleries: Section 1 and Section 2

Here's a sample first midterm exam. It is from a previous year and covers a topic we didn't cover, so ignore that topic.

Here's a sample second midterm exam.

Here's an old final exam for your use in preparing for your final exam.

What I expect from my students. These things ought to be of obvious benefit to the student, but this semester, as an experiment, you'll get a direct 5% of the grade for the first four of them. See the green sheet.

Lecture Plan and Readings This is the revised-on-November 5 schedule. (You can still find the original by altering the URL). The original plan reflects the course syllabus developed in Fall 2005 by the Undergraduate Curriculum Committee, and is designed to mesh with the prerequisite course CS46b and the course in Design and Analysis of Algorithms (CS155) that comes after CS146. All sections of CS146 should cover these same topics.

This semester's course is three lectures shorter than in previous semesters, thanks to the faculty furloughs, and another two shorter thanks to instructor illness. The topics not covered are: B-tree deletion algorithm (Chapter 18, section 3), greedy programming and Huffman codes (Chapter 16), and implementation of stacks and queues in a fixed array (Chapter 10, section 1), as well as the second lecture on dynamic programming and the Floyd-Warshall algorithm.

Here's a story about the failure of a space mission that illustrates why I have a minimum performance requirement: better that students should fail now than go out in the world and cause the failure of space missions. Note the list of reasons for the failure cited in that article.

There are a few elementary programming issues with which some students need help. For example, how to create an array of objects in Java. As a second example, some students did not know how to call Arrays.sort with a programmer-defined Comparator object. Practice this first by sorting an array of integers in descending order, instead of ascending as you get with the one-argument version of Arrays.sort.