CS 220-3
Programming with Data Structures
Catalog Description
A course in advanced programming, data structures and algorithm design with an increased emphasis on structured design techniques and program development. Topics include advanced language features, data abstraction and object-oriented programming, classes and dynamic data, recursion, stacks, queues, linked lists, trees and graphs, sorting and searching.
Prerequisite:
202 and 215 each with a grade of C or better.
Objectives
1.To provide an increased level of exposure to structured programming techniques. This is done, in part, through the lecture material but primarily through the programming assignments with an emphasis on discussions of the algorithm design phase, the program development phase, and the testing phase in the software life cycle.
2.To provide a thorough treatment of data abstraction and an introduction to object-oriented programming.
3.To provide a thorough treatment of the fundamental data structures including stacks, queues, linked lists, and trees.
4.To provide a more in-depth coverage of sorting and searching techniques and their analysis.
5.To lay the foundation for further study in computer science.
| Course Outline | Lectures | |
| The following is not necessarily intended as a sequential ordering. | ||
| 1. | Review of Programming
Arrays, pointers, structures |
3 |
| 2. | Programming Methodology
Note: A more in-depth treatment of programming design techniques is presented than that given in 202. Specification of the requirements to solve the problem Design techniques: In-depth treatment of procedural and data abstraction, further emphasis on top-down design, choice of data structures Coding: Additional emphasis on programming style, structured programming, and documentation, Information hiding Correctness: Testing and test data, testing end cases, debugging techniques, verification of algorithms, invariants |
3 |
| 3. | Data Abstraction and Object-Oriented Programming
Levels of abstraction Polymorphism, inheritance, encapsulation |
2 |
| 4. | Pointers and Dynamic Allocation
Pointer variables Dynamic allocation Pointers as parameters |
5 |
| 5. | Implementation of Data Structures
Lists and linear structures Stacks and queues Trees and graphs |
14 |
| 6. | Recursion
Examples Implementation: Memory and time considerations Simulating recursion Efficiency considerations: Recursive vs. iterative solutions |
6 |
| 7. | Searching and Sorting
Linear search Binary search Introduction to formal analysis of algorithms N2 sorts: Analysis of buble sort, insertion sort, and selection sort NlogN sorts: Quicksort, mergesort, analysis of these sorts |
7 |
| Total | 40 | |
| Lab Assignments | ||
| There should be a minimum of five lab assignments including two dealing with advanced data structures. One lab should emphasize recursion and one should emphasize sorting and searching. Design considerations and efficiency of the algorithms is to be stressed on all the lab assignments | ||