CS 3304 Data and Information
Structures
Fall 2005 (CRN: 10966, 3 credit hours)
Instructor: Dr. Hong Lin
Office: 717
South, Phone: 713-221-2781, e-mail: linh@uhd.edu
URL:
http://cms.dt.uh.edu/faculty/linh/courses/cs3304
Catalog description: (3-3-0) Development of methods for organizing and
processing large data sets. Types of
data structures analyzed include linear lists, matrices, stacks, queues, and trees. Algorithm analysis methods are used throughout to analyze the
various data structures and algorithm design alternatives.
Textbook: ADTs, Data Structures, and Problem Solving with C++, 2nd Edition, by Larry Nyhoff (ISBN: 0-13-140909-3)
Prerequisite: CS 2310 and MATH 2305.
Course Objectives: Upon the completion of this course, students are expected to know the major data structures used in computer programming. These include lists, stacks, queues, hash tables, trees, and (optionally) graphs. Students should also be able to design algorithms based on the data structures to solve application problems; and evaluate the algorithms using the asymptotic notation. Advanced C++ programming with Standard Template Library is also covered by this course.
Grading
Breakdown
Labs
and Participation
10%
3 Projects
20%
2 Midterm Tests
40% (20% each)
Final Exam 30%
Grading
Scale
90 -100 A, 80 - 89 B, 70 - 79 C, 60 - 69 D,
Below 60 F
Class Policies: Students are required to attend all classes on time. Absence, tardiness and early withdraw will be recorded and sanctioned in the "Labs and Participation" part of the course work. No makeup exams will be given. With the presence of the proof of emergency, the grade for one missing exam will be replaced by the grade of the final exam. Students are responsible for the materials assigned from the book and the lecture notes. To pass this course a passing grade on both programming assignments and exams is required. You are expected to turn in your own work on time. No late submission will be accepted. All missed grades will be recorded as zero.
Academic
Dishonesty: For this class, all work must be done
individually -- no group work is allowed. You are encouraged to generally
discuss assignments with fellow students, but may not copy their solution or code.
Significant identicalness constitutes duplication. This includes but not be
limited to: the main body of the programs is the same; only variable names are
different; etc. Doing so constitutes academic dishonesty, which will be
sanctioned with a grade of F in the course.
General University Policies and Procedures: All students are subject to UH-Downtown's Academic Honesty Policy and to all other university-wide policies and procedures as they are set forth in the UH-Downtown University Catalog and Student Handbook. The Academic Honesty Code is embraced by all members of the University of Houston-Downtown academic community and is an essential element of the institution’s academic credibility. The Honesty Code states "We will be honest in all our academic activities and will not tolerate dishonesty." The purpose of the Academic Honesty Policy is to deal with alleged violations of the Honesty Code in a fair and consistent manner. The policy is administered jointly by students and faculty. It is each student's responsibility to read and understand the Academic Honesty Policy. It may be found in the Student Handbook.
Statement on reasonable accommodations:
UHD adheres to all
applicable federal, state, and local laws, regulations, and guidelines with
respect to providing reasonable accommodations for students with
disabilities. Students with disabilities
should be notified to register with Disabled Student Services and contact the
instructor in a timely manner to arrange for appropriate accommodations.
Topics:
1.1 Problem Analysis and Specification
1.2 Design
1.3 Coding
1.4 Testing, Execution, and Debugging
1.5 Maintenance
4 More About OOP and ADTs —
Classes
4.1 Procedural vs. Object-Oriented Programming
4.2 Classes
4.3 Example: A First Version of a User-Defined Time Class
4.4 Class Constructors
4.5 Other Class Operations
An article about operator overloading
6 Lists
6.1 List as an ADT
6.2 An Array-Based Implementation of Lists
6.3 An Array-Based Implementation of Lists with Dynamic Allocation
6.4 Introduction to Linked Lists
6.5 A Pointer-Based Implementation of Linked Lists in C++
6.6 An Array-Based Implementation of Linked Lists
7
Stacks
7.1 Introduction to Stacks
7.2 Designing and Building a Stack
Class ---- Array-Based
7.3 Linked Stacks
7.4 Use of Stacks in Function Calls
7.5 Case study: Postfix (RPN) Notation
8 Queues
8.1 Introduction to Queues
8.2 Designing and Building a Queue Class ---- Array-Based
8.3 Linked Queues
8.4 Application of Queues: Buffers and Scheduling
8.5 Case Study: Information Center Simulation
9 ADT Implementations --- Templates and Standard Containers
9.1 Introduction: The Evolution of Reusability and Genericity
9.2 Function Genericity --- Overloading and Templates
9.3 Class Genericity --- Templates
9.4 The vector Container
9.5 Case Study: Counting Computer Logins
9.6 Other Standard Containers --- Deque, Stack, and Queue
9.7 Bitsets and Valarrays
10 ADT Implementation --- Recursion, Algorithm Analysis, and Standard Algorithms
10.1 Recursion
10.2 Examples of Recursion: Towers of Hanoi; Parsing
10.3 Implementing Recursion
10.4 Algorithm Efficiency
10.5 Standard Algorithms in C++
10.6 Proving Algorithms Correct
11 More Linking Up with
Linked Lists
11.1 Some Variants of Singly-Linked Lists
11.2 Linked Implementation of Sparse Polynomials
11.3 Doubly-Linked Lists and the Standard C++ list
11.4 Case Study: Large-Integer Arithmetic
11.5 Other Multiply-Linked Lists
12 Searching: Binary Trees and Hash Tables
12.1 Review of Linear Search and Binary Search
12.2 Introduction to Binary Trees
12.3 Binary Trees as Recursive Data Structures
12.4 Binary Search Trees
12.5 Case Study: Validating Computer Logins
13 Sorting
13.1 Some O(n2) Sorting Schemes
13.2 Heaps, Heapsort, and Priority Queues
13.3 Quicksort
13.4 Mergesort
13.5 Radix Sort
15 Trees
15.1 Case Study: Huffman Codes
15.2 Tree Balancing: AVL Trees
15.3 2-3-4 Trees, Red-Black Trees, B-Trees, and Other Trees
15.4 Associative Containers in STL ---- maps
Course Schedule for Fall 2005 (Tentative)
The schedule, together with assignments, is subject to change in the progress of the course.
Announcements made in the class override the schedule in case of conflicts.
|
Week |
Monday |
Wednesday |
|
1 |
8/22 |
|
|
2 |
8/29 |
8/31
Chapter
6
- Part 2 |
|
3 |
9/5 Labor Day
holiday |
9/7 Lab
exercise 1 |
|
4 |
9/12 |
|
|
5 |
9/19 |
9/21 |
|
6 |
9/26 |
9/28 |
|
7 |
10/3 |
10/5 |
|
8 |
|
10/12 |
|
9 |
10/17 |
10/19 |
|
10 |
|
10/26 Chapter
10
- Part 2 |
|
11 |
10/31 Project
2 Due |
|
|
12 |
11/7 |
11/9 |
|
13 |
11/14 |
11/16 |
|
14 |
11/21 |
|
|
15 |
11/28 Homework: Exercises 12.7 1 (p714) |
11/30 Review
for Final Test |
|
16 |
12/5 Reading Day (no class) |
12/7 Final Exam 5:30pm - 7:55pm |