UW CSE 373: Syllabus (Spring 2005)

CSE 373: Syllabus (Spring 2005)

Course Goals and Contents

The objective of this class is to study the fundamental data structures and algorithms used in computer science. Students will study advanced programming techniques and will learn to analyze the algorithms to determine their time and space requirements. By the end of the course, students should have the skills necessary for selecting between existing data structures and algorithms, and for designing their own.

Major topics will include: mathematical tools for describing algorithmic complexity; lists, stacks, and queues; general trees; binary trees; binary search trees; balanced binary trees; heaps and priority queues; hashing; graphs; B-trees (time permitting); union-find algorithms (time permitting). The implementation of these data structures and algorithms in Java will be studied and practiced.

In addition to the listed topics, a goal of the course is to improve your ability to solve interesting problems through programming, by recognizing when and how standard data structures can be used, and how new data structures can be created for novel situations.

Activities

The course activities include lectures, tests, quizzes, homework assignments of various types, and programming projects. Note that there are no quiz sections. However, there are TAs assigned to the course. You are encouraged to visit the professor and TAs frequently to discuss course material and assignments.

Grading

Tentative weights: the following is an approximation to the formula that will be used to determine overall scores at the end of the quarter.

Assignments (not including designated projects): 15 percent. These are primarily book exercises, but may include some relatively small programming assignments. Note: if there are too few such assignments to constitute a reasonable grading category, Assignments and Projects will be grouped together into a single category.
Projects (major programming plus intermediate steps, accompanying documentation, demonstration, etc.): 20 percent.
Service and Participation: 3 percent. This may include peer reviews, selected in-class exercises, assistance to course staff, and other class-related activities.
Quizzes: 10 percent
Two Midterms: 30 percent total.
Final Exam: 21 percent.

Each graded assignment, quiz or exam is reduced to a percentage before being used in calculating the course grading. In particular, each quiz is equally weighted, regardless of the number of points on particular quizzes; e.g., a 15-point quiz counts as heavily as a 1-point quiz.

Exams

Exams will be give only on the date stated. Please check the exam schedule, and your own schedule, now to make sure there are no conflicts.

Quizzes

Quizzes will generally cover very recently introduced material. Occasionally there may be questions based on assigned reading which has not yet been discussed in class.

There are no make-up quizzes, regardless of reason. There are no make-up quizzes, regardless of reason. One or two quizzes will be dropped at the end of the quarter.

Late policy

Except in very unusual circumstances, late work will not be accepted.

Academic misconduct

Please review the Computer Science and Engineering Academic Conduct Policy.

Some brief notes:
In each assignment, each student shall make an accurate and complete attribution of credit for the material presented. Any quotations must be marked as quotations. Complete references must be given for each source of information used, whether the information came from the web, a printed book, or personal verbal communication. Any direct help on an assignment must be mentioned and attributed to the helper. Any apparent deliberate misrepresentation will be treated as a case of academic misconduct and will be handled according to standard procedures of the College of Arts and Sciences, College of Engineering, or other university division.

Computing Resources

Campus computing resources are available to CSE373 students through two facilities:

the UW uniform access computing resources, esp. for posting web pages. Most of the open labs, such as Odegaard, have a Java programming environment installed.
the MSCC computing resources. The computer lab is in the Communications Building, B022.

To use campus labs you will need a UWNetID. If you have been enrolled at UW before, you know what this is about. If you are new to UW or are a non-matriculated student, please check immediately to make sure you have access; if you don't, take steps to make sure you do!

If you plan to use your own computer, you will need access to a Java development kit at least.

personal computers and publicly available Java compilers. The recommended compiler for this course is the one in Sun Microsystems' Java Development Kit J2SE 1.4.2 for Windows or Linux. You can download it free of charge. The size of the download file is is about 49 MB.
the Eclipse integrated development environment. To run this, you will need a reasonably powerful computer -- roughly a 1 GH processor and 512 MB of RAM. If you do not have a machine at this level, you can either use the JDK tools from the command line, or you can go to the MSCC lab and use Eclipse there. The Eclipse software is available free from the eclipse.org web site. To get started with Eclipse, take a look at their FAQ page. For me, the most useful entry on the FAQ page was how to write a Hello World program in Eclipse.

If you have not programmed before in Java, you must take steps immediately to get caught up, not just on the language but on the tools such as those mentioned above.

Other Resources

Students are encouraged to take advantage of the following categories of resources for this course:

books, including the assigned textbook by Goodrich and Tamassia, Data Structures and Algorithms in Java, 3d ed published by Wiley. If you join the IEEE Computer Society ($52 for student membership for one year) you will get free access to an electronic version of this book. News flash 4/11/2005 [thanks to J.K.]: It appears that only the 2nd edition of the textbook is available electronically via the IEEE. The 2nd edition is sufficiently different from the third that it should be avoided.
the World Wide Web and its resources related to data structures, algorithms, and programming.

Particular topic-oriented resources which have been useful in past quarters. Possibly some of these won't be as relevant this quarter.

For those of you new to Java applets, there is an online tutorial at the Java website. There is also a version for Java Swing applets here .
The Visual Stack Applet. This Java programs can be used to produce demonstrations of other data structures.
An illustration of mathematical functions in descriptions of abstract data types.
Here is a very simple applet that shows how "AWT buttons" work. OnOffApplet and its source code.
Here is a simple applet that shows how a textarea works. TextTestApplet.
Here is an applet that demonstrates very simple graphics in Java. You have to feed it commands such as LINE 0 0 200 300 LineApplet.
The next applet builds on the previous one by incorporating timing, so that multiple lines can be drawn with a controlled time delay between each successive pair. TimedLineApplet.

Class Email List

Each student should subscribe to the course email list. Instructions for subscribing will be given later. This list will serve both as a means of announcement from the instructor and TAs and as a forum for discussing course-related issues. An archive will be available on the web.