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.

Here are the solutions to the Friday final exam. (corrected 12-17 because I got problems 14 and 16 wrong in the first posting)

Here are the solutions to the Monday final exam. (corrected 12-18 because I got problems 15 and 16 wrong in the first posting)

Here are the final exam grades. The mean (and average) in the first section was higher than in the second section. Of course it's hard to tell whether the second exam was harder or the students in the first section are better; but anyway I assumed that the exam was probably harder, and so I added 15 points to the score of each student who took the second-section exam (including those actually enrolled in the first section), before assigning letter grades. That explains the column in the table called "weighted score".

Here are the course grades with supporting calculations. There were 9 A's, 28 B's, 10 C's, and 7 F's. All seven F's went to people who failed on at least three of the seven programming assignments to submit a serious effort (let alone to pass).

Wondering how it can be that some students who have passed the Google assignment cannot answer simple questions on the final about that assignment, I ran a "plagiarism detection" tool developed at Stanford on the Google submissions.

I have now run this tool on all the programming assignments and in all discovered eight students who cut-and-pasted code from the Internet (or possibly from each other) and turned it in as their own. That is about one-seventh of all students, and explains why those students could not answer simple exam questions about their homework. Those caught in plagiarism will be treated as specified on the green sheet. In particular grade change forms will be filed to convert passing grades to F, in cases where plagiarism is discovered after passing grades have been turned in. So if you are one of those students, it means nothing that you see a passing grade in MySJSU--that will be changed, after I have completed the required personal interviews next semester.

My advice to these students: find a different career, at which you can succeed without compromising your personal integrity.

The grades shown in the above table (except with three grades changed to incomplete) were turned in to the University Friday afternoon.

Here are the overall homework grades, including the two handwritten assignments and the overall average.

Here are the solutions to the second midterm.

The links about genetic engineering have been moved to the bottom of the page.

Here are the grades on both the first and second midterms.

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.

Here are the solutions to the first midterm.

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.

In class there was a brief discussion of the ethics of a career in bionformatics. A student made the point that genetically modified organisms are bad; that's a point with which I disagree, but just below are the two links the student sent to support his opinion. I say "the student" because I'm not sure if he wants to be identified by name or not.

http://www.hulu.com/watch/67878/the-future-of-food

http://topdocumentaryfilms.com/the-disappearing-male/

Here are some links I'm posting.

Golden rice is a genetically modified rice that will help prevent many cases of blindness. The article tells how Greenpeace recognizes this fact and promises not to interfere with this GMO crop.

Genetically modified wheat may be very helpful in feeding 9 billion people by 2050.