CS211 Data
Structures , Fall 2007
|
|
|||
|
Instructor: |
Professor Xiaoyan Li |
|
|
This course teaches the basic techniques to orgranize data in a running program You will know about well-known data structures as listed in the Quick Syllabus . You will be able to
(1) implement these structures as classes in C++;
(2) determine which structures are appropriate in various situations;
(3) confidently learn new structures beyond what's presented in this
class.
You will also learn part of object-oriented programming and
software development methodology.
|
Quick Syllabus |
|
To
become a Data Structures Expert · Precondition/Postcondition specifications · Time analysis techniques · Container classes · Pointers and dynamic arrays · Linked lists · Templates and iterators · Stacks · Queues · Recursive thinking · Trees · Sorting and searching techniques |
Textbook: Data Structures and Other Objects Using C++, Third Edition, by Michael Main and Walter Savitch ,ISBN 0-321-19716-X, Addison Wesley, softcover.
Supplements: The Code for the Book and the Corrections for the Text will be useful and can be found by clicking here .
References: Lots of good sample codes are found in C++ How to Program by Dietel & Dietel, 3rd Ed., Prentice Hall 2001, QA76.73.C153D45, ISBN 0-13-089571-7.
CS101 (Problem Solving and Structured Programming) and CS102 ( Object Oriented Programming). You should feel confident in your ability to design and implement simple programs using arrays and functions. As a rough guideline, all the materials before Chapter 5 (Pointers and Strings) of C++ How to Program by Dietel & Dietel are assumed to be understood. You should be familiar with some programming environment--either a PC or a Unix system.
The following schedule is based on Fall 2007 academic calendar :
|
|
||
|
Date |
Planned Lecture Topics |
Read/Assign/Exam |
|
|
|
|
|
Sep 10 (M) |
Lecture 2. ADT & C++
Classes ( code ) |
Ch 2.1-2.3; Assignment 1 |
|
Sep 17 (M) |
Lecture 4. Container
Classes |
Ch 3 (code ) |
|
Sep 24 (M) |
Lecture 6. Pointers
and Dynamic Arrays (I) ( point
code with pointers ) |
Ch 4.1 - 4.2 |
|
Oct 01 (M) |
Lecture 8. Dynamic
Classes and the Big Three ( code ) |
|
|
Oct 08 (M) |
Mid-semester break; no class! |
|
|
Oct 15 (M) |
Lecture 9. Linked
Lists ( code ) |
|
|
Oct 22 (M) |
Lecture 11. Software Development using Templates and
Iterators |
|
|
Oct 29 (M) |
Lecture 13. Introduction to Recursion |
|
|
Nov 05 (M) |
Exam Review 2 ; Assignment Discussions |
|
|
Nov 12 (M) |
Lecture 15. Trees and Traversals ( code ) |
|
|
Nov 19 (M) |
Lecture 17. B-Trees and Set Class (code
) |
|
|
Nov 26 (M) |
Lecture 18. Heaps and Priority Queues; Time Anaysis of
Trees |
|
|
Dec 03 (M) |
Lecture 20. Hashing |
|
|
Dec 10 (M) |
Lecture 22. Recusive Sorting , Heapsort & the STL
Quicksort (code ) |
|
|
Dec 15-19 |
Final exam (mainly Ch 10-13, some from Ch 1-9) |
|
See syllabus above for the tentative timetable for a schedule. There will be six to seven programming assignments distributed roughly every two weeks (counted roughly 30% of your final grade). Several in-class small quizzes will add up to 10 % of your final grade. There will be three in-class exams (60% of your final grade). Dates of these exams will be announced beforehand.
Policies: Students may discuss ideas together. But since each student get credits for his or her submissions, all actual program code and written answers must be done separately by each student, and must not be shared.
Communications: I would like the course to run smoothly and enjoyably. Feel free to let me know what you find good and interesting about the course. Let me know as soon as possible about the reverse. You may see me in my office during my office hours or send me messages by e-mail.
The language used for this class is C++ as supported by today's available compilers. You may use either Windows or Unix/Linux machines to work on your projects. GNU or Borland compilers work better with the sample code provided with the book for both examples and projects.
Copyright @ Xiaoyan Li ,