CSE 30331 - Data Structures - Fall 2011

Syllabus   |   Forum at Piazza   |   Tech Basics   |   Project Home Page

Phase III demos Schedule   |   Poster guidelines PPT PDF   |   Poster Presentation Schedule

Overview

Data structures, such as lists, trees or graphs, are the ways in which data is represented and organized in memory. Along with the corresponding algorithms that access and update the data, data structures are the building blocks of software. Well designed and well implemented data structures are crucial for constructing software systems of non-trivial size that are efficient, reliable, understandable, testable, and maintainable. Appropriate data structures also facilitate the division of work and communication within teams of developers and the successful adoption of components and services by third parties.

Goals

1. A variety of abstract data types, including vectors, lists, sets, bitsets, stacks, queues, deques, priority queues, tables, trees, and graphs.
2. Recursive and divide-and-conquer strategies for designing algorithms.
3. Specific algorithms for searching, sorting, and hashing.
4. Techniques and criteria for determining the asymptotic efficiency of algorithms and which algorithm is best for a given application.
5. Principles of good program design, coding and testing using an object oriented approach.
6. The C++ Standard Template Library (STL) as a means to implement and use data structures.

Books and Resources

Required

• Data Structures with C++ Using STL (Second Edition) by William Ford and William Topp. Online resources (code)
• Technical Basics Compendium for assignments in this class

Recommended

• Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein. 2nd or 3rd edition.
• Dictionary of Algorithms and Data Structures (by NIST)

Some C++ Resources

• Book: C++ How to Program, by Deitel & Deitel
• Book: The C++ Programming Language by Stroustrup
• C++ FAQ Lite
• C++ Tutorial
• STL Library

Other resources

• Book ``Design Patterns: Elements of Reusable Object-Oriented Software'' by Gamma, Helm, Johnson, Vlissides. 1994. Seminal book!
• Design Patterns notes (Scott Emrich)
• Animated algorithms and data structures based on ``Algorithms in Action'' by Linda Stern and colleagues (Australia)

Announcements

• 12/13/11: Ryan Turner pointed out problems with the solutions for Quiz 5 and Quiz 6, which are now corrected (v2 of each document).
• 12/11/11: Posted solutions for Homework 3 1-6 and problem 7.
• 12/9/11: Posted solution for PA3. A neat solution from a student (Patrick Collard), despite two smaller problems (see INSTRUCTOR-NOTES.txt inside).
• 12/7/11: Posted practice problems for the Final Exam
• 12/2/11: Started posting solutions for post-midtern quizzes: Quiz 8 (fixed, v2), Quiz 7, Quiz 6 (v2), Quiz 5 (v2). (Quiz 8's fix was for one number in table in Problem 1)
• 11/30/11: Improved correctness proof for strong-components algorithm in lecture 19 slides.
• 11/30/11: Updated in lecture 19 slides the definitions of graph types based on connectivity (strongly connected, connected, and weakly connected)
• 11/29/11: Updated lecture 21 slides with some impovements/clarifications.
• 11/22/11: Posted Homework 3, due 12/7. This is the last assignment.
• 11/22/11: Today we had Quiz 8 in class. If you attended class today and turned it in, you will have a specially lenient grading. If you attended but decide to turn it in on 11/29, you WON'T have a penalty. If you didn't attend, you can turn it in 11/29 for up to 75% of the score.
• 11/22/11: One more correction to lecture 20 slides: the weight of a cut does not depend on edges going from right to left partition.
• 11/21/11: Posted poster guidelines. PPT, PDF.
• 11/20/11: Poster presentation schedule has been completed. Check your slot here.
• 11/16/11: New PA3 submission rules. 5% bonus if you submit on time. No bonus or penalty if submitted by midnight. 5% penalty for each day late, up to Sunday 11/20.
• 11/13/11: Relaxed a rule in PA3 (now v3) to allow for an interesting twist to the simulation. It's optional (you can adopt only if you want).
• 11/12/11: Posted Homework 2 Solution..
• 11/4/11: Updated Programming Assignment 3 to v2 with a small fix.
• 11/4/11: Please set up ASAP a meeting with one of us during office hours to demo your Phase-II submission. At least one person per group. Must occur within 1 week from the due date.
• 11/3/11: Published Programming Assignment 3, due on Nov. 16th

      ... Older Announcements

Quizzes

Today (11/22) we had Quiz 8 in class. If you attended class today (11/22) and turned it in, you will have a specially lenient grading. If you attended but decide to turn it in on 11/29, you WON'T have a penalty. If you didn't attend, you can turn it in 11/29 for up to 75% of the score.

This is Quiz 7. If you didn't attend class or didn't turn it in in class or you prefer to re-answer it, bring your answers to class on Thu 11/17 for up to 50% of the score.

These are solutions for the post-midterm Quizzes:

• Quiz 8 solution (fixed, v2: one number missing in table in Problem 1)
• Quiz 7 solution
• Quiz 6 solution (v2)
• Quiz 5 solution (v2)

Assignments

Next assignments:

Past assignments:

Schedule