Data Structures and Algorithm Analysis I

Prerequisites:

A grade of C⁻ or better in CPSC 100, CPSC 101, CPSC 141, and CPSC 142; or permission of instructor.

Lecture times:

MWF 9:30–10:20. Room 7-125. There are no assigned lab or tutorial times.

Text Book:

Data Structures and Algorithm Analysis ( $\mathsurround=0pt 2^{\hbox{nd}}$ edition), by Mark Allen Weiss. The second edition is vastly improved with respect to its use of C++.

Syllabus:

Much of the material is from Weiss, in particular Chapters 2-4 and 7, with other material as time permits. I shall also cover material from Chapters 12, 13, 19, and 20 of Deitel and Deitel.

Topics include:

2 weeks	Algorithm analysis and asymptotic complexity.
1 week	Loop variants, loop invariants, and recursive programming.
2 weeks	Templates, the Standard Template Library, containers, iterators, and generic programming in /.
2 weeks	Sorting algorithms.
1 week	Error handling and exceptions.
1 week	List classes.
1 week	List based classes: stacks, queues, and deques.
1 week	Tree classes.

Times are approximate.

Grading Scheme:

I reserve the right to change the weight of any portion of this marking scheme. If changes are made, your grade will be calculated using the original weighting and the new weighting, and you will be given the higher of the two.

References:

STL for C++ Programmers., by Leen Ammeraal. (Wiley, 1997)

C++ How to Program, by Deitel and Deitel.

The Art of Computer Programming by Donald E. Knuth. Difficult reading, but these three volumes contain a wealth of information on list data-structures, algorithmic analysis and sorting algorithms.

The C++ Programming Language 3rd 3 edition, by Bjarne Stroustrup.