University of Maryland/Asian Division

CMIS 240 - Data Structures and Abstraction

DE Term 4 : Apr 04, 2005 - Jul 24, 2005

David Wills
http:///sensei.ad.umuc.edu/dwills/
dwills@ad.umuc.edu

PREREQUISITES:CMIS 140. Taking CMIS 140 and 240 in consecutive semesters is recommended.

GENERAL INFORMATION: Presentation of and practice in additional features of C++. Concepts and techniques of data abstraction and data structures are studied. Topics include structuring, storing, and accessing data; using sort/merge methods; and updating, deleting, and inserting records in data structures such as linked lists and trees. Students may receive credit for only one of the following courses: CMIS 240 or CMIS 315.

This course continues with the study of computer and information science started in CMIS 140 using the C++ language. It is the prerequisite for most upper-level CMIS courses. The theory and techniques of this class are fundamental to the computer science, programming, and software engineering disciplines. The classic, most useful, and most commonly needed data structures of computer software are learned. Topics covered include pointers and dynamic memory allocation, linked lists, recursion, sorting, searching, stacks, queues, and binary search trees. Programming projects ensure that students have the opportunity to learn the material. An introduction is made to object-oriented programming (OOP) that will be expanded upon in CMIS 345. OOP topics include: encapsulation, data hiding, classes and objects, constructors, destructors, member functions, overloaded operators, templates.

COURSE OBJECTIVES: On successful completion of this course, you will be able to:

1. Build reusable software objects using C++ classes
2. Use operator overloading and function overloading to make your classes act
like the built-in C++ data types
3. Use C++'s template class construct to build parameterized classes where the
user of the class can provide information,
4. Such as array sizes or data types, that the compiler needs to generate the
actual machine code for the class
5. Use memory dynamically allocated from the C++ heap to store variables
6. Use the following software constructs:
       a.Dynamically resized arrays
       b.Linked lists (singly linked and doubly linked)
       c.Stacks and queues
       d.Binary trees
       e.Heaps
7. Write functions that use recursion
8. Use various techniques for traversing a binary tree
9. Use various sorting techniques

understand what object-oriented programming is by having done it. Know about classes, objects, constructors, destructors, data hiding, encapsulation, operator overloading, templates.
program a stack, a linked list, a binary search tree
know how various sorting and searching algorithms work and about their relative efficiencies
dynamically allocate and deallocate memory, a core activity of all real-world software
use the important technique of recursion
analyze the run time of an algorithm and categorize its efficiency
know what the basic data structures used in all computer programming / computer science / software engineering are and what they are used for.

REQUIRED TEXTBOOK:
C++ Plus Data Structures, by Nell Dale, 2nd Edition, Jones & Bartlett Publishers
Warning: do not get the 3rd edition!

The CMIS 140 textbook makes good supplemental reading material.

EVALUATION: Your final grade will be based on a proctored examination and some homework (programs) in the following proportions:

Homework           65%
Proctored Exam     35%

Proctered exam FAQ
The grade of 'A' means "outstanding", i.e. mastery of the material. The grade of 'B' means "good". The grade of 'C' means "satisfactory".
Grades are curved and related to the class average. "Significantly above" the class average are the A's, "above" (or sometimes even at) the class average are the B's, at or below the class average are the C's. Significantly below the class average are the D's and F's.
Usually, in the 90's is an A, 80's is a B, 70's is a C.

Schedule

Week 1 Chapter 1: software engineering
Week 2 Chapter 2: abstraction, encapsulation, classes
Week 3 Chapter 3: lists, binary search
Week 4 Chapter 3: big-O, ctors&dtors, operator overloading
Week 5 Chapter 4: stacks, templates
Week 6 Chapter 4: pointers, dynamically allocated arrays, queues
Week 7 Chapter 5: linked lists
Week 8 Chapter 6: copy ctor
Week 9 Chapter 7: recursion 
Week 10 Chapter 7: recursion part 2
Week 11 catch up/ review
Week 12 Proctored Exam. 
Week 13 Chapter 8: binary search trees
Week 14 Chapter 10: sorting
Week 15 Chapter 10: searching