CPSC 211 (Sec 201-203): Data Structures and Implementations, Honors
Spring 2004

Announcements

• 5/10: Just to clarify, you may bring one 8.5" by 11" sheet of paper with your notes on it to the final (as for Exam 2 - but it does not have to be the exact same sheet you used for Exam 2).

• 5/3: Honors Courses evaluations and peer teacher evaluations tomorrow (Tue, 5/4). Also, makeup quiz (for those with official excuses for previous quizzes).

• 5/3: Deadline for Program 8 is extended to 5:00 PM on Thursday, May 6. Turn in your paperwork to me (either my mailbox on 3rd floor Bright or to my office - you can slip it under the door if I'm not there). If you turn it in by the original deadline of 10:20 AM tomorrow, then you get 5 bonus points.

• 4/30: Final exam review is now available.

• 4/28: For those of you who had a valid University excuse for missing a quiz, the make-up quiz will be held in class on Tue, May 4 (probably at the end).

• 4/21: Average on Exam 2 is 84.

• 4/20: On the advice of Lidia, I'm postponing the due date for Program 7 again until this Friday (10:20 AM). If you turn it in by tomorrow at 10:20, you'll get 5 extra credit points on it. Focus on getting a clean Java implementation - it'll help you a lot in the C version.

• 4/20: Some updates about the hash function for Programs 7 and 8: Steven Houston pointed out (and many of you may have discovered this) that the hash function I specified works terribly. Here are some other options that you can use:
  • Steven's:

          for (int i=0; i < stringLength; i++) {
                 prod = (prod % (hashTableSize - 2))* (ASCII value of char at index i in string);
          }
          return Math.abs(prod % hashTableSize);
         

  • Lidia's: Here's a version that uses twice as many probes as Steven's:

          for (int i=0; i < stringLength; i++) {
              prod = (prod % (hashTableSize - 2))* (ASCII value of char at index i in string);
          }
          return Math.abs(prod % hashTableSize);
          

    A small variation of this with ( hashTableSize - i) instead of (hashTableSize - 2) does even better, reducing the number of probes by a factor of 2.
  • Daniel's: For an even better hash function, try converting the string to a key using a transformation from base 27 to base 10. This can be done through the following:

          private int hash (String key) {
            long hashed = 0;
            int currentCharNum; // Ranges 0-26, a=0, b=1,..., z=25, [space]=26
            for (int i = 0; i < key.length(); i++) {
              currentCharNum = (key.charAt(i) == ' ')? 26 : key.charAt(i)-'a';
              hashed += currentCharNum*Math.pow(27, i);
            }
            hashed %= hashTableSize; // hashTableSize needs to be an instance variable
            return (int)hashed;
          }
         

• 4/12: To give you more time to study for Exam 2, I'm postponing the due date for program 7 to Wed, April 21.

• 4/12: You may bring one 8.5 by 11 inch sheet of paper with your own notes on it to the exam on 4/14.

• 4/12: Yet another change to program 7, thanks to Bryan Boyd: run your experiments on window sizes of 3, 4, 5 and 6. Much larger window sizes will cause there to be too many different keys and thus cause memory problems.

• 4/11: Exam 2 review is now available.

• 4/9: Lecture notes on skip lists available here.

• 4/7: VERY IMPORTANT! Bryan Boyd pointed out to me that on program 7, the performance analysis section didn't make a lot of sense, since every execution for a fixed window size will be the same on the same input file. So I have changed it - now you'll execute the program once for 6 different window sizes. See the updated assignment.

• 4/7: Update to grading scheme: since we are not actually having any pencil and paper homework, I am shifting that 15% of your course grade to the programs category. As a result: exams 35%, quizzes 15%, programs 45%, culture reports 5%.

• 4/6: Jim Griffin will not be in lab on Thu, Apr 8. Instead, he'll have office hours from 1:45 to 4:45 PM Wed, Apr 7. His office hours will be in room 219 Bright.

• 3/31: Programming assignment 7 and Programming assignment 8 are now available, due Mon, April 19 and Tue, May 4 respectively.

• 3/29: I made an algebra error in class today: the formula should be h < 2 * log M(h) - 2.

• 3/26: Programming assignments 5 and 6 - DUE DATE POSTPONED to Wed, Mar 31.

• 3/24: Correction to Programming assignments 5 and 6: the code of the distributed leader election algorithm had a missing "else" - it's now been corrected.

• 3/23: Rough idea of "curve" on exam 1: 85-100 excellent, 70-85 good, 53-70 fair, below 53 poor. Remember that this grade will be averaged in with everything else - it is the overall course average that I use in deciding the curve for course grades.

• 3/23: My office hours today are changed to 4:00 - 5:00 PM.

• 3/11: Information on internship available here (followup to Nick Neumann's presentation in class last week).

• 3/9: Programming assignment 5 and Programming assignment 6 are now available, due Fri, March 26.

• 3/8: Quiz 7 will be on Wed, Mar 10!

• 3/3: The next programming assignment will not formally be available until early next week, but you can start on part of it now: implement a FIFO Queue abstract data type using a circular array that expands dynamically to avoid overflow. Do it in both Java and C. Be sure to code it so that you can easily change the specific data type to be stored in the queue.

• 3/1: Here are some sample specifications, in PDF, thanks to Aaron Bray.

• 3/1: My office hours on Tue, Mar 2 are changed to 4:00 - 5:30. I will be out of town Wedneday afternoon through Friday, so my office hours on Fri, Mar 5 are cancelled. Lidia will proctor the exam on Fri, Mar 5.

• 3/1: Exam 1 review is now available.

• 2/23: Hoffmann Distinguished Lecture scheduled for Feb 25 has been cancelled.

• 2/23: My office hours on Tue, Feb 24 are changed from 2-3:30 to 4-5:30.

• 2/20: Student Engineers' Council is having "Constituency Day" on March 3 and 4, 9 AM - 3 PM in the Zachry and Blocker lobbies. Please stop by and fill out their survey. "Constituency Day is an event put on by the Student Engineers' Council. Our goal is to solicit opinions from the engineering student body about different aspects of the Dwight Look College of Engineering. Through this information we hope to help improve the college in order to make it a better learning environment. The information gathered from our surveys will be presented to the Dean and Department Heads of our college."

• 2/17: Programming assignment 3 and Programming assignment 4 are now available, due Wed, March 3.

• 2/13: Exam 1 will be on Friday, March 5.

• 2/13: Undergraduate summer research grants program application deadline is Fri, Feb. 20! This is a great opportunity to spend the summer doing research and getting paid for it.

• 2/8: There is a fourth Department of Computer Science Distinguished Lecturer this month - tomorrow, Mon, Feb 9. The speaker is Prof. Devika Subramanian, Rice University. If you like, you may substitute attendance at her lecture and a report for one of your culture reports. More details here.

• 2/5: My office hours on Fri, 2/6, are cancelled. Please contact me by email if you need to see me on Fri.

• 2/4: Programming assignment 2 is now available, due Wed, Feb 18.

  Start reading in the C book.

• 2/2: New office hours for Lidia: Mondays and Wednesdays 1:00 - 2:30 PM.

• 1/28: Correction to due date for Culture 4: it is due Mon, Apr 12 (not Apr 13).

• 1/26: Here is a link to a good sample testing document from last year (warning: the assignment was somewhat different than yours); thanks to Blake Birkenfeld.

• 1/26: Instructions for using the turnin program are here.

• 1/26: Due dates for all culture reports are now available - see calendar.

  There are three (!) Department of Computer Science Distinguished Lecturers coming in February. If you like, you may substitute attendance at their lectures and a report for up to three of your culture reports. More details here.

• 1/26: See in the syllabus below for Daniel and Jim's office hours.

• 1/26: Programming assignment 1 is now available, due Wed, Feb 4. Start working on it in lab this week.

• 1/23: You can get copies of my lecture notes here in either postscript or PDF format. Don't forget to check the corrections!
  • Installment 1 (pp 1-94): postscript, PDF
  • Installment 2 (pp 95-220): postscript, PDF
  • Installment 3 (pp 221-312): postscript, PDF
  • Installment 4 (pp 313-348): postscript, PDF
  • Corrections

• 1/21: Labs this week are informal - meet Lidia, Daniel and Jim; make sure your account works, etc.

Back to beginning

Syllabus

Teaching Assistant: Lidia Onica
Office: 514E H.R. Bright Bldg
Office Hours: Mondays and Wednesdays 1:00 - 2:30 PM (*updated 2/2*); other times by appointment
Email: lonica@cs.tamu.edu
Office Phone: 862-3411

Peer Teacher: Daniel Delwood
Office Hours:

• Monday, 9:00 - 9:50 AM, HRBB 232 (sec 201 lab time)
• Monday, 9:50 - 10:15 AM, HRBB 214 (for those who wish to stay late)
• Monday, 8:30 - 11:00 PM, HRBB 214 (general "office" hours)
• Wednesday, 9:00 - 9:50 AM, HRBB 232 (sec 201 lab time)
• Wednesday, 9:50 - 10:15 AM, HRBB 214 (for those who wish to stay late)

Peer Teacher: Jim Griffin
Office Hours:

• Tuesday, 10:00 - 10:50 AM, HRBB 232 (sec 202 lab time)
• Tuesday, 11:00 - 11:50 AM, HRBB 232 (sec 203 lab time)
• Wednesday, 1:45 - 2:45 PM, HRBB 214 (general "office" hour)
• Thursday, 10:00 - 10:50 AM, HRBB 232 (sec 202 lab time)
• Thursday, 11:00 - 11:50 AM, HRBB 232 (sec 203 lab time)

Prerequisite: CPSC 111, Computer Science Concepts and Programming, and honors eligibility.

Lecture: Mondays, Wednesdays, Fridays, 10:20 - 11:10 AM, ZACH 105B.

Labs: All sections meet in HRBB 232.
Section 201: Mondays and Wednesdays 9:00 - 9:50 AM (Daniel)
Section 202: Tuesdays and Thursdays 10:00 - 10:50 PM (Jim)
Section 203: Tuesdays and Thursdays 11:00 - 11:50 PM (Jim)

Textbooks:

1. Data Structures in Java , Thomas A. Standish, Addison Wesley, 1998.
2. C By Dissection, Fourth Edition, Al Kelley and Ira Pohl, Addison Wesley, 2001.

Course URL: https://people.engr.tamu.edu/j-welch/teaching/211.s04

At the end of the semester you should:

• be fluent in the use of the basic data structures mentioned above;
• understand and apply the principles of abstraction, modularity, and information hiding;
• appreciate and adhere to good software development practices;
• be able to program competently in the subset of Java and the subset of C covered in the course;
• be familiar with many of the computer science problems and issues that will be studied later in the curriculum.

Tentative Schedule: The course will cover the following topics.

Your grade will be based on five components:

• exams 35% - There will be two exams during the semester, worth 10% each, and one final exam, worth 15%. The exams will be held in class.

• quizzes 15% - There will be twelve five-minute quizzes, consisting of a few simple questions (short answer, true-false, or multiple choice) concerning the reading and/or the material covered in the last class. The purpose of the quiz is to encourage you to do the reading in advance and to stay caught up in the class. Your lowest two quiz grades will be dropped.

• programs 30% - There will be several programming assignments in Java and C. More details are available here.

• homework 15% - Pencil and paper exercises, both take-home and in-class.

• culture reports 5% - This component is to round out your classwork. Find, read, and write short reports on five technical papers in computer science journals. More details are available here.

Some assignments may be done in groups. No more than 20% of your total course grade will be based on group work.

No late assignments will be accepted. There will be no make-up exams or quizzes. Discuss unusual circumstances in advance with the instructor. All excused absences must also be cleared with the instructor.

Course grades will be assigned according to this scale:

Collaboration: Discussion of concepts with others is encouraged, but all assignments must be done on your own, unless otherwise instructed. If you use any source other than the text, reference it/him/her, whether it be a person, a book, a solution set, a web page or whatever. You MUST write up the solutions in your own words. Copying is strictly forbidden. Every assignment must be turned in with this cover sheet, which lists all sources you used. More information on academic integrity, plagiarism, etc. is available at the TAMU Plagiarism web site.

University Regulations define scholastic dishonesty to include acquiring answers from any unauthorized source, working with another person when not specifically permitted, observing the work of other students during any exam, providing answers when not specifically authorized to do so, informing any person of the contents of an exam prior to the exam, and failing to credit sources used. Disciplinary actions range from grade penalty to expulsion.

Back to beginning

Calendar

• readings
• quizzes and exams
• programs and homeworks
• culture reports (and related seminars)

• details on the assignments
• exam reviews

Back to beginning

Programs

• design -- 25%. You will be learning about this topic all semester (and beyond). This refers to what kind of user interface your program has, how your program is broken into pieces, how the pieces communicate, what data structures and algorithms you decide to use for the pieces.

• readability/documentation -- 25%. Most software is written by many people and/or worked on over a long span of years. Communicating your ideas to other people is crucial. Here are the style guides that you must follow: Java and C . Every program's documentation must include an assessment that discusses
  • any assumptions made about the input
  • limitations of the program with regard to the requirements
  • known bugs

• testing -- 25%. For most programs, it is practically impossible to prove that the program is correct on all inputs. Instead, you must try to convince skeptics that it mostly works right, by testing the program on various inputs and documenting what you have done. Here is the program testing guide that you must follow.

• correctness -- 25%. This will be evaluated by inspection and running your program on our set of test cases.

Back to beginning

Culture Reports

You are to find, read, and write short reports on five technical papers in computer science journals. Articles in the following two journals are usually at about the right level:

• Communications of the ACM
• IEEE Computer

Each report is to be one to two pages long, typed, and must include

• correct bibliographic information for the paper (title of article; names of all authors; name of journal with volume, number, date and page numbers)
• a summary of the paper contents
• at least one comment about the paper or question that it raised in your mind, indicating that you have thought critically about the material.

DO NOT PLAGIARIZE! You must write up your summary in your own words. See collaboration policy in syllabus.

Report due dates are indicated in the calendar and are summarized here:

• Culture Report 1: due 10:20 AM, Mon, Feb 9, 2004
• Culture Report 2: due 10:20 AM, Fri, Feb 27, 2004
• Culture Report 3: due 10:20 AM, Wed, Mar 24, 2004
• Culture Report 4: due 10:20 AM, Mon, Apr 12, 2004
• Culture Report 5: due 10:20 AM, Fri, Apr 30, 2004

On occasion, a culture assignment may be substituted by attendance at and a report on a Distinguished Lecture. These opportunities are:

• Thu, Feb 5, 4:00pm (Rm 302 HRBB), Michi Henning, ZeroC, Inc., "A New Approach to Object-Oriented Middleware"
• Mon, Feb 9, 2:00pm (Rm 302 HRBB), Devika Subramanian, Rice University, "Statistical Machine Learning and its Applications in Science and Engineering"
• Wed, Feb 18, 4:10pm (Rm 124 HRBB), Gene H. Golub, Stanford University, "Shape from Moments"
• *** Hoffman lecture scheduled for Feb 25 is cancelled. ***

Each report is to be one to two pages long, typed, and must include

• name and professional affiliation of the speaker
• a summary of the seminar
• at least one comment about the seminar or question that it raised in your mind, indicating that you have thought critically about the material.

Back to beginning

Useful Links

• Texas A&M Computing Society (TACS) -- student organization for those interested in computing. Affiliated with the two main professional organizations, ACM and IEEE Computer Society.

• Computer Science Department, TAMU

• Student Computing and Information Page: central source of information about student computing at TAMU.

• Schedule of short courses offered by the CIS Computer Help and Training Group.

Careers and Mentoring

• Office of Honors Programs and Academic Scholarships

• Computer Science Department mentoring -- has lots of good info about research opportunities, including summer ones with money!

• TAMU Co-operative Education

Back to beginning