CSS 343 – Data Structures and Algorithms – Fall 2009

University of Washington, Bothell - Computing & Software Systems

http://courses.washington.edu/css343/cfolson

 

 

Professor:                   Dr. Clark F. Olson                   Class:                 TTh 3:30-5:35pm, UW1-030

                                    Office: UW1 – 347                   Office Hours:    TTh 2:30-3:30pm, UW1-347

                                    Phone: (425) 352-5288                                       or by appointment

                                    E-mail: cfolson@u.washington.edu                      

 

Course content

This is the second course in a two-part sequence that integrates mathematical principles with programming concepts.  Topics to be covered include:

• Abstract data types – trees, priority queues, graphs, heaps, and tables
• Object-oriented programming and design, including inheritance and polymorphism
• Modeling computation – regular expressions, finite state machines, context-free grammars, and Turing machines
• Algorithm development and analysis – Huffman’s algorithm, Dijkstra’s algorithm, etc.

 

 

Textbooks

Required:

• Mark Allen Weiss, Data Structures and Problem Solving Using C++, Second edition, Addison-Wesley, 2000.
• Kenneth H. Rosen, Discrete Mathematics and Its Applications, Sixth edition, Addison-Wesley, 2007.

You may also want to have a C++ reference book.

 

Grading

Labs:                35%                

Midterm:          30%

Final exam:       35%

 

I typically use a linear grading scale such that: 75% = 2.0, 85% = 3.0, 95% = 4.0.  This may be adjusted to the difficulty level of the exams given in this class.  To be successful you should expect to spend 10-20 hours per week working outside of the classroom.

 

Class policies

Assignments will turned in using Catalyst at the following web page:

https://catalysttools.washington.edu/collectit/dropbox/cfolson/7014/  

 

Assignments are due prior to class on the due date.  The submission site will close promptly at the start of class.  There will be no individual extensions.  Assignments can be turned in up to 5 days late (including weekends) with a 10% grade reduction per day.  All assignments are to be completed independently.  Please be very careful to adhere to the student code of conduct:

http://www.washington.edu/students/handbook/conduct.html

 

There is also a message board on Catalyst that will be used for questions and discussion at:

https://catalysttools.washington.edu/gopost/board/cfolson/12782/

 

Make-up exams will not be given except under extraordinary circumstances.  These should be discussed with the instructor in advance, except in the case of an emergency, which should be well documented.

 

The University of Washington is committed to providing equal opportunity and reasonable accommodation in its services, programs, activities, education and employment for individuals with disabilities.  If you believe that you have a disability and would like academic accommodations, please contact Disability Support Services at 425.352.5307, 425.352.5303 TDD, 425.352.3581 FAX, or at dss@uwb.edu.  You will need to provide documentation of your disability as part of the review process.

 

Class courtesy

Please turn off all cell phones and beepers prior to class.  Talking and other noise during lecture should be kept to a minimum as a courtesy to other students who are trying to learn.

 

Tentative Schedule (subject to change)

Date	Topic	Reading	Assignments
Oct  1	Introduction, review
Oct  6	Trees	Weiss 18, Rosen 10.1
Oct  8	Trees, Binary search trees	Weiss 19.1-19.3, Rosen 10.3	Lab 1 due
Oct 13	Binary search trees	Weiss 11.2, 13.1, Rosen 10.2
Oct 15	Priority queues, binary heaps	Weiss 7.9, 21.1-21.6
Oct 20	Graphs	Weiss 15.1-15.3, Rosen 9	Lab 2 due
Oct 22	Graphs	Rosen 10.4-10.5
Oct 27	Balanced binary search trees	Weiss 19.4
Oct 29	Balanced binary search trees	Weiss 19.8
Nov  3	Inheritance, polymorphism	Weiss 4	Lab 3 due
Nov  5	Midterm
Nov 10	Object-oriented design
Nov 12	Hash tables	Weiss 20.1-20.3
Nov 15	Last day to drop	Weiss 20.4-20.7
Nov 17	Hash tables
Nov 19	Design reviews		Lab 4 design due
Nov 24	Finite state machines	Rosen 12.2-12.3
Nov 26	Thanksgiving holiday
Dec  1	Languages and grammars	Rosen 12.1, 12.4
Dec  3	No class (project work day)
Dec  8	Turing Machines	Rosen 12.5	Lab 4 due
Dec 10	Review / catch-up
Dec 15	Final (in class)

 

 

H1N1 ACTION STEPS IN THIS COURSE: As part of the campus community’s shared responsibility for minimizing the possible spread of H1N1 virus this year, it is critical that all students are familiar with the symptoms of H1N1 Flu described on the UW Bothell website at http://www.uwb.edu/flu.  Any student or instructor with flu-like symptoms is encouraged to stay at home until at least 24 hours after they no longer have a fever without the use of fever-reducing medications (ibuprofen or acetaminophen).  If you are sick and have an extended absence, please speak with your instructor regarding alternative ways to maintain your progress in your courses.  If your instructor is sick and needs to cancel class, you will be notified.