Data Structures and Algorithm Analysis I

Professor:

David Casperson, Office: Lib 471, Phone: 960-6672, Newsgroup  unbc.cpsc200

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 e-mail:  David.Casperson@unbc.ca, 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 /.

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 week1=2s	$$	Algorithm analysis and asymptotic complexity.
1 week1=1s	$$	Loop variants, loop invariants, and recursive programming.
2 week1=2s	$$	Templates, the Standard Template Library, containers, iterators, and generic programming in /.
2 week1=2s	$$	Sorting algorithms.
1 week1=1s	$$	Error handling and exceptions.
1 week1=1s	$$	List classes.
1 week1=1s	$$	List based classes: stacks, queues, and deques.
1 week1=1s	$$	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 / Programmers., by Leen Ammeraal. (Wiley, 1997)

/ 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 / Programming Language 3 thstndrdththth 3 edition, by Bjarne Stroustrup.