CIS 3130 Data Structures

Basic Information and Requirements

• Instructor: Prof. Neng-Fa Zhou
• Class hours: 6:30-10:10PM, Wednesday (room 234NE)
• Office hours: 5:00-6:00 Thursday (room Ingersoll 1161)
• Textbook: Data Structures with C++ Using STL, 2nd ed., by - William H. Ford and William R. Topp, Prentice-Hall. (Example programs and PPT slides are available here)
• Homework
  • There will be one homework assignment each week. Sample answers will be given and selected homework questions will be reviewed in class.
• Exams
  • There will be two tests, one midterm exam, and one final exam, all closed-book. Each test counts for 15%, the midterm 30%, and the final 40%.

Course Outline and Homework Assignments

1. Introduction to Data Structures (What is this Book About? Abstract View of Data Structures. An ADT as a Class. Implementing C++ Classes. Declaring and Using Objects. Implementing a Class with Inline Code. Application Programming Interface(API). Strings.)
   • H.W. - Chapter 1: 14, 21, 24, 33
2. Object Design Techniques (Software Design. Handling Runtime Errors. Object Composition. Operator Overloading.)
   • H.W. - Chapter 2: 12, 18, 20
3. Introduction to Algorithms (Selection Sort. Simple Search Algorithms. Analysis of Algorithms. Analyzing the Search Algorithms. Making Algorithms Generic. The Concept of Recursion. Problem Solving with Recursion.)
   • H.W. - Chapter 3: 15, 17, 28, 30, 42, 50.
4. The Vector Container (Overview of STL Container Classes. Template Classes. The Vector Class. Vector Applications.)
   • H.W. - Chapter 4: 6, 7, 9, 20, 27.
   • Test-1
     
5. Pointers and Dynamic Memory (C++ Pointers. Dynamic Memory. Classes Using Dynamic Memory. Assignment and Initialization. The Minivector Class. The Matrix Class.)
   • H.W. - Chapter 5: 24, 30, 31, 35, 37, 38.
     
6. The List Container and Iterators (The List Container. Iterators. General List Insert And Erase Operations. Case Study: Graduation Lists.)
   • H.W. - Chapter 6: 15, 20, 25, 29, 32
     
7. Stacks (The Stack ADT. Recursive Code and the Runtime Stack. Stack Implementation. Postfix Expressions. Case Study: Infix Expression Evaluation.)
   • H.W. - Chapter 7: 15, 17, 18, 28, 31
     
   • Extra credit H.W. - Charpter 10, question #43
8. Queues and Priority Queues (The Queue ADT. The Radix Sort. Implementing the Miniqueue Class. Case Study: Time-Driven Simulation. Array Based Queue Implementation. Priority Queues.)
   • H.W. - Chapter 8: 14, 18, 21, 25, 27
     
9. Linked Lists (Linked List Nodes. Building Linked Lists. Handling The Back of the List. Implementing a Linked Queue. Doubly Linked Lists. Updating A Doubly Linked List. The Josephus Problem. The Minilist Class. Selecting a Sequence Container.)
   • H.W. - Chapter 9: 17, 18, 28, 29.
     
10. Binary Trees (Tree Structures. Binary Tree Nodes. Binary Tree Scan Algorithms. Using Tree Scan Algorithms. Binary Search Trees. Using Binary Search Trees. Implementing the Stree Class. The Stree Iterator (Optional).)
    • H.W. - Chapter 10: 6, 23, 31, 35, 43.
11. Test-3
12. Associative Containers (Overview of Associative Containers. Sets. Maps. Multisets. Implementing Sets And Maps.)
    • H.W. - Chapter 11: 15, 17, 23, 27.
13. Advanced Associative Structures (Hashing. Designing Hash Functions. Designing Hash Tables. The Hash Class. Hash Table Performance. 2-3-4 Trees. Red-Black Trees. The Rbtree Class.)
    • H.W. - Chapter 12:
14. Inheritance and Abstract Classes (Inheritance in C++. The Graphics Hierarchy. The Graphics System. Safe Vectors. Ordered Lists. Polymorphism and Virtual Functions. Abstract Classes.)
    • H.W. - Chapter 13:
15. Heaps Binary Files and Bit Sets (Array Based Binary Trees. Heaps. Implementing a Priority Queue. Binary Files. Bitsets. Case Study: Huffman Compression.)
    • H.W. - Chapter 14:
16. Recursive Algorithms (Divide and Conquer Algorithms. Combinatorics. Dynamic Programming. Backtracking: The Eight-Queens Problem.)
    • H.W. - Chapter 15:
17. Graphs (Graph Terminology. The Graph Class. Graph Class Design. Graph Traversal Algorithms. Graph Traversal Applications. Graph Minimization Algorithms.)
    • H.W. - Chapter 16: