| |
Close Window/Tab
PRINT VIEW -- Opens in new, second window. Use browser controls to close when finished.
| Credit- Degree applicable | | Effective Quarter: Fall 2017 | I. Catalog Information
| CIS 22C | Data Abstraction and Structures | 4.5 Unit(s) |
| | Formerly: Requisites: Prerequisite: CIS 22B, 22BH or 35A.
Advisory: MATH 212 or equivalent. Repeatability: Hours: Lec Hrs: 48.00
Lab Hrs: 18.00
Out of Class Hrs: 96.00
Total Student Learning Hrs: 162.00 Description: Application of software engineering techniques to the design and development of large programs; data abstraction and structures and associated algorithms: stacks, queues, linked lists, trees, graphs, and hash tables; internal and external sorting; use of recursion; team project. |
| Student Learning Outcome Statements (SLO)
| | | • Student Learning Outcome: Read, analyze and explain advanced data structures programs. |
| | | • Student Learning Outcome: Design solutions for advanced problems using appropriate design methodology incorporating advanced data structures programming constructs. |
| | | • Student Learning Outcome: Create and analyze efficiency of advanced level data structures algorithms, code, document, debug, and test advanced data structures programs using multiple source and header files. |
|
II. Course Objectives | A. | Create programs which implement the stack data structure. |
| B. | Create programs which implement the queue data structure. |
| C. | Create programs which implement complex linear lists. |
| D. | Create recursive algorithms and relate efficiency to uses of recursion. |
| E. | Create programs which implement the binary tree, binary search tree, AVL tree, priority queues, and binary heaps data structures. |
| F. | Create programs which implement hashed tables. |
| G. | Demonstrate knowledge of advanced sorting algorithms and discuss the usage and relative advantages of various sorts and their efficiency. |
| H. | Demonstrate knowledge of external sorting algorithms. |
| I. | Create programs which implement the graph data structure. |
| J. | Apply software engineering principles including structured programming, object-oriented programming, and abstract data types. |
| K. | Design and implement a team project with multiple classes in multiple files. |
| L. | Demonstrate usage of templates/generics. |
III. Essential Student Materials IV. Essential College Facilities | | Access to a computer laboratory with Java and C++ compilers available |
V. Expanded Description: Content and Form | A. | Create programs which implement the stack data structure. |
| 1. | Implementation by linked lists. |
| B. | Create programs which implement the queue data structure. |
| 1. | Implementation by linked lists. |
| C. | Create programs which implement complex linear lists. |
| D. | Create recursive algorithms and relate efficiency to uses of recursion. |
| 1. | The concept of recursion |
| 2. | Recursive mathematical functions |
| 3. | Simple recursive algorithms |
| 4. | Divide-and-Conquer strategies |
| 6. | Implementation of recursion using stacks |
| E. | Create programs which implement the binary tree, binary search tree, AVL tree, priority queues, and binary heaps data structures. |
| F. | Create programs which implement hashed tables. |
| 2. | Clustering and collision resolution |
| 3. | Selecting hash functions |
| G. | Demonstrate knowledge of advanced sorting algorithms and discuss the usage and relative advantages of various sorts and their efficiency. |
| H. | Demonstrate knowledge of external sorting algorithms. |
| I. | Create programs which implement the graph data structure. |
| 4. | Depths first and breadth first traversals |
| J. | Apply software engineering principles including structured programming, object-oriented programming, and abstract data types. |
| 3. | Principles of object-oriented programming and structured programming |
| 4. | Type parameters and parameterized types |
| 5. | Modules in programming languages |
| 6. | Strategies for choosing the right data structure |
| K. | Design and implement a team project with multiple classes in multiple files. |
| 1. | Organizing a multiple-file project |
| L. | Demonstrate usage of templates/generics. |
VI. Assignments | A. | Required reading from the text |
| B. | Programs: 4-6 individual programming assignments implemented in C++ or Java which include design as well as coding, debugging, and testing, covering the Lab Topics specified in X. below. |
| C. | Team Project: Design and development of a large program with three or more programmer-written files. |
VII. Methods of Instruction | | Lecture and visual aids
Discussion of assigned reading
Discussion and problem solving performed in class
Quiz and examination review performed in class
Homework and extended projects
Collaborative learning and small group exercises
Collaborative projects
Laboratory discussion sessions
|
VIII. Methods of Evaluating Objectives | A. | Successful completion of programming assignments with output verifying program correctness; use of structured design principles, documentation, programming style, efficiency, and testing methods. |
| B. | Evaluation of the team project for correctness, use of structured design principles, documentation, programming style, and efficiency. |
| C. | One or more examinations requiring some algorithm development. Evaluation based on correctness. |
| D. | A comprehensive final examination requiring some algorithm development |
IX. Texts and Supporting References | A. | Examples of Primary Texts and References |
| 1. | Frank M. Carrano, "Data Structures and Abstractions with Java", 4th edition, Walls and Mirrors, 2014. |
| 2. | Frank M. Carrano, "Data Abstraction & Problem Solving with C++", 7th edition, Walls and Mirrors, 2016. |
| B. | Examples of Supporting Texts and References |
| 1. | Savitch, Walter: Data Structures and Other Objects Using C++, fourth edition, Addison-Wesley, 2010 |
X. Lab Topics | A. | Design algorithms, code solutions, debug and test programs employing the stack ADT. |
| B. | Design algorithms, code solutions, debug and test programs employing the queue ADT. |
| C. | Design algorithms, code solutions, debug and test programs employing complex ADT linked list structures, such as doubly linked lists, multi-linked lists, circularly linked lists. |
| D. | Design recursive and/or iterative algorithms, code solutions, debug and test programs employing ADT binary trees, binary search trees, AVL trees, priority queues, or binary heaps.
|
| E. | Design algorithms, code solutions, debug and test programs employing hashed tables. |
| F. | Analyze and compare simple and advanced sorting algorithms, such as Shell Sort, Insertion Sort, Heap Sort, Selection Sort, Quick Sort. |
| G. | Design algorithms, code solutions, debug and test programs employing graphs. |
| H. | Demonstrate the building and running of a large program with three or more programmer-written files. |
|
