CMPS 261: Advanced Data Structures and Software Engineering
Fall 2009
Instructor: Dr. Mark G. Radle
Office: ACTR 225
Phone: 482-5708
CLID: mgr5211
Email: mgr@louisiana.edu
Office Hours: M: 11:00am – 1:30pm
TTR: 9:00am – 11:00am
W: 12:30pm – 1:30pm
Course Description:
Programming methodology, software testing techniques, and algorithm analysis. Data structures topics include construction, traversal, and modification of trees, hash tables, and heaps. Sorting and searching techniques on linear structures including arrays and sequential files.
Goals:
To provide a framework of software engineering models and issues concerned with the development of high quality software.
To gain experience in working with large software systems, including the specification, development, and documentation of such systems, the use (or reuse) of existing modules in the development of new systems, and the employment of a variety of software testing techniques for verifying systems.
To provide students with a working knowledge of a variety of search and information retrieval structures, including trees, heaps, and hash tables.
To study a variety of internal sorting techniques.
To learn to choose the most appropriate data structures and algorithms for solving particular problems, taking into consideration the run-time complexity, space complexity, and conceptual complexity of each choice.
Course Outcomes:
Students will have experience implementing and reusing complex data structures.
Students will be competent in documenting the specification, design, and verification of software systems.
Students will be minimally competent in analysis of algorithms.
Students will be experienced in implementing and testing large software systems.
Prerequisites:
A grade of C or better in CMPS 260 and Math 270.
Text:
Required:
Weiss, M., Data Structures and Algorithm Analysis in C++, Third Edition, Addison Wesley, 2006.
“Programming Documentation Standard”, Object-Oriented Version, January 2000, available from http://web.cacs.louisiana.edu/~mgr/261
Topics:
Preliminaries
Abstract Data Types
Mathematical background
Recursion
Proof Techniques
Algorithms
Case analysis
Asymptotic analysis
Space bounds
Trees
Binary Trees
Binary Search Trees
Heaps and Priority Queues
General Trees
Sorting
Insertion sort
Divide and Conquer – Quicksort
Merging sorted sequences – Mergesort
Lower bound for sorting by comparison of keys
Heapsort
Searching
Searching Arrays and Self-Organizing Lists
Dynamic Sets and Searching
Hashing
Union/Find
Tests and Final Exam:
There will be 3 one-hour in-class tests and a comprehensive two-hour final exam. No make up tests will be given without compelling justification.
Grading Policy:
The following will be used in computing final class averages and letter grades:
90% - 100% A
80% - 89% B
70% - 79% C
60% - 69% D
0% - 59% F
Distribution:
30% Programming and written homework assignments
45% Tests
25% Comprehensive final exam
Course Policy:
The attendance policy outlined in the Departmental Policies will be followed. You are responsible for any material missed during your absences.
Students must average a passing grade (70% or better) in each of the 3 portions of the course in order to receive a passing grade in the course.
Assignments must be turned in within the first 10 minutes of class on the due date or they will not be accepted and the student will receive a 0 for that assignment.
Programming assignments that exhibit translation-time (compiler or interpreter) errors will not be graded and the student will receive a 0 for that assignment. However, for programming assignments, partial solutions (with no translation time errors) turned in on time will be graded.
During the 24 hours immediately before the time an assignment is due I will not answer any questions regarding that assignment.
Incomplete grades (I grades) will not be assigned unless there are extraordinary and compelling justifications for such grades.