CSS 343 — Data Structures and Algorithms (Autumn 2013)

Syllabus
Assignments
Study Questions
Lecture Notes
Code Snippets
Resources

New

Sun Dec 1 07:45:29 2013: added notes for lecture #18
Wed Nov 27 18:43:34 2013: added instructor's solution for assignment #3
Fri Nov 22 15:35:26 2013: added notes for lecture #17
Wed Nov 20 23:19:45 2013: added notes for lecture #16
Mon Nov 18 10:52:40 2013: added notes for lecture #15
Fri Nov 15 13:13:22 2013: added instructor's solution to assignment #2
Wed Nov 13 21:21:59 2013: added notes for lecture #14
Mon Nov 11 12:07:34 2013: assignment 4 published
Fri Nov 8 09:24:11 2013: added notes for lecture #13
Wed Nov 6 07:50:51 2013: added notes for lecture #12
Sun Nov 3 08:39:46 2013: added notes for lecture #11
Mon Oct 28 11:02:07 2013:
- added instructor's solution to assignment #1
- added notes for lecture #8
Mon Oct 21 13:54:08 2013: added notes for lectures #6 & #7
Mon Oct 14 12:45:39 2013: added notes for lectures #4 & #5
Wed Oct 9 18:58:08 2013: added annotated source code for 2-3 tree (Lecture #4)
Tue Oct 8 13:55:41 2013: added notes for lectures #3 & #3
Mon Sep 30 22:30:27 2013: added notes for lecture #1
Mon Sep 23 18:51:27 2013:
- Minor tweaks to syllabus
- Added link to Winter 2013 site
- Additional updates to assignment #3
Wed Sep 11 22:32:53 2013: updated assignment #3
Fri Aug 16 16:02:34 2013: initial version for Autumn 2013

Syllabus

This core computer science course is about how algorithms and data structures work from mathematical principles to implementation in C++. Topics include trees and graphs, hashing, greedy algorithms, dynamic programming, abstract data types & object-oriented design, regular expressions, context-free grammars, and theoretical (mathematical) models of computation.

http://courses.washington.edu/css343/bernstein/current/syllabus.html

Assignments

Please submit assignments to the course dropbox (zip or compressed tarball, please): https://catalyst.uw.edu/collectit/dropbox/morrisb9/28568

Assignment 1: BTree
Due date: October 10, 2013
Revised due date: October 22, 2013
Instructor's solution: word_counter.zip
Alternate instructor's solution: word_counter_modular.zip
Assignment 2: Huffman Coding
Due date: October 29, 2013
Revised due date: November 11
Instructor's solution: huffpuff.zip
Assignment 3: Shortest Path
Due date: November 14, 2013
Revised due date: November 25
Instructor's solution: shortest-path.zip
Alternate instructor's solution (template-based): shortest-path-generic.zip
Alternate alternate instructor's solution (inheritance-based): shortest-path-inheritance.zip
Assignment 4: Project Scheduling
Due date: December 3, 2013
Revised due date: December 5, 2013

Hackathons

To be announced.

Study Questions

final exam study questions: study-questions.pdf

Lecture Notes

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

Lecture #1 Introduction & Review Complexity Theory (Performance) Complexity (Cognitive Load)	Lecture #6 Priority Queues	Lecture #11 Network Flow Problems Shortest-Path Problem (unweighted & weighted) Breadth-First Search Dijkstra's Algorithm	Lecture #16 Iterators Finite-State Automata
Lecture #2 The Tool Chain Nasal Demons (Undefined Behavior) Pointers & Memory Management	Lecture #7 Huffman Coding	Lecture #12 Dijkstra's Algorithm Hashing	Lecture #17 Pointers & Virtual Functions Finite-State Automata (cont.) Regular Expressions
Lecture #3 Type Casting Sequential Processing Random Access Dictionaries Binary Search Binary Search Tree	Lecture #8 Graphs & Graph Algorithms: Intro	Lecture #13 Bit Twiddling Hashing (cont.) Delving Deeper into C++	Lecture #18 Context-Free Grammars
Lecture #4 2-3 Tree B Tree	Lecture #9 Midterm Review: no notes	Lecture #14 virtual functions	Lecture #19
Lecture #5 Tree Rotations AVL Tree BST Deletion Red-Black Tree	Lecture #10 Midterm: no notes	Lecture #15 Resource Management: RAII Object-Oriented Design Principles	Lecture #20 Final review: no notes

Code Snippets

Often, the best way to understand some feature of a programming language is to write a small program that exercises the feature:

voyeur.cc: using a cast to access and modify private const member
ptr_math.cc: pointer arithmetic
inverted_array.cc: pointer-array equivalence
sizes.cc: sizes of different things
args.cc: command-line argument processing
destructor.cc: constructor & destructors with inheritance
func_ptr.cc: function pointer example (call with command-line arguments)
compile with or without -DUSE_TYPEDEFS
inheritance.cc: calling virtual/nonvirtual functions via base pointers
constructor.cc: constructor/initializer syntax & semantics
single_dispatch.cc: single dispatch A->func(B) (function chosen based on dynamic type of A but static type of B)
dispatch.cc: simulating double dispatch (A, B)->func() (function chosen based on dynamic type of A and B)