CSS 502B: Data Structures & Object-Oriented Programming II (Winter 2016)

• New
• Syllabus
• Discussion Board
• Assignments
• Lecture Notes
• Resources
• Additional Advice

New

• Wed Mar 23 17:31:44 2016
  • Assignment 5 rubric posted
• Tue Mar 22 10:14:00 PDT 2016
  • Final grades are posted. You learned a lot and the grades reflect that result. Take a moment to congratulate yourselves, then get back to work. We just scratched the surface and there's a lot more to learn.
  • Assignment 5 graded: The rubric will be posted in the next day or so. I've tried to mark down substantial, conceptual problems and not worry about petty stuff, but with the firehose-volume of material to cover, a few important things slipped through the cracks:
    • Adequate testing: your routing is run against my reference solution and my test data is run against your solution
    • Coding to the spec: if the spec says check for error conditions, assume my test data will have those error conditions
    • Coding to the spec: if you change an input file format (or rename the planets), it breaks my test cases. I spent far too much time altering my input data to fit strange input requirements.
    • Coding to the spec: if you hardcode the name of the input file, it makes it harder for me to test your programs
    • Reading the spec: there was specific information requested in the README file in addition to general notes.
    • No marks were deducted, but if you're compiling C++, always compile with -Wall -Werror flags (all warnings, warnings treated as errors)
    See me during office hours next quarter if you have questions.
  • In view of the complexity of assignment 4 vs. assignment 5, I decided to make assignment 4 worth 20 points instead of 10 (would you have done anything differently?).
• Mon Mar 14 06:40:13 PDT 2016
  • Ongoing power failure. Follow the saga on the UW Bothell Emergency Page, In case of extended power outage, go to the offsite backup page at http://www.uwbalert.com/. Don't sacrifice study time for the final exam. If grades have to be submitted late, so be it.
• Sun Mar 13 18:14:44 PDT 2016
  • Power failure at Bothell. Assignment 5 due date extended to Monday evening.
• Mon Mar 7 08:09:58 PST 2016
  • Found a defect in the Assignment 5 spec last night while debugging my solution: suppose an optimal solution has a ship Sj arriving at planet Pi at time Ti and departing at Ti + 4. If there is a locally-optimal route to Pi via Sk that arrives at Ti - 1, it cannot depart on Sj at (Ti - 1) + 5 because of the 6-hour minimum connection time. "Optimal choice" has been violated. There is an easy way and a hard way to repair this. We're going to take the easy way.
    • Solution: reset the minimum legal connection time to 4 hours. This should be a one-line change to a symbolic constant.
    • Sorry, my bad.
• Sun Mar 6 10:18:27 2016
  • Assignment 5 update: your program may assume that the input file has routes grouped by ship, in the order of their routes. Input that is out-of-order can be easily preprocessed by a simple shell script: sort by fields 1 (ship name) and 3 (depature time).
• Sun Mar 6 06:58:06 2016
  • Today's Broom Hilda
• Mon Feb 29 18:37:44 2016
  • Map of a galaxy far, far away (as rendered by fdp):
    
• Sun Feb 21 16:05:37 2016:
  • Sample text and Huffman coded file (note for a small file, the overhead of the coding table swamps any gains from bit compression).
  • Assignment 5: Dijkstra's Algorithm posted
• Mon Jan 25 17:32:11 2016: Assignment 4: Huffman Coding posted
• Sun Jan 10 15:23:28 2016: Introduction to Bash Scripting slides & "live" demo

Syllabus

Full syllabus: http://courses.washington.edu/css502/bernstein/syllabus.html

Tentative schedule: syllabus.html#schedule

Course Description

This core computer science course covers the internal workings of algorithms and data structures, from mathematical principles to implementation in C++. Topics include:

• trees & graphs
• hashing
• object-oriented design
• formal languages & automata theory

The objective of the course is to refine and extend the concepts and practical skills introduced in CSS 501.

The subject matter is highly technical so plan to put in considerable time and effort master the material. Expect to spend 10-15 hours or more outside of class per week.

Prerequisite: CSS 501 with a grade of 2.7 or better

Discussion Board

A discussion board has been created: https://catalyst.uw.edu/gopost/manage/morrisb9/41365

Assignments

Submit assignments to the course dropbox: https://catalyst.uw.edu/collectit/dropbox/morrisb9/37019

• Assignment 1: Binary Search Tree
  due: Jan 13
• Assignment 2: Red-Black Tree
  due: Jan 20
• Assignment 3: Binary Heap
  due: Feb 10
• Assignment 4: Huffman Coding
  due: Feb 17
• Design Project
  due: Mar 9

Lecture Notes

Lecture notes and supplemental materials will be posted as instructor time permits and may be incomplete.

Resources

resources

Additional Advice

Coming soon...