| Title |
Data Structures
|
| Credits |
3
|
| Course Coordinator |
Richard McKenna
|
| Description |
An extension of programming methodology to data storage and manipulation on complex data sets. Topics include: programming and applications of data structures; stacks, queues, lists, binary trees, heaps, priority queues, balanced trees and graphs. Recursive programming is heavily utilized. Fundamental sorting and searching algorithms are examined along with informal efficiency comparisons.
Bulletin Link
|
| Prerequisite |
Prerequisite: C or higher in CSE 114
|
| Course Outcomes |
- An ability to program using sophisticated features of object oriented programming.
- An ability to define and use data types, and use data structures.
- An understanding of the importance of time and memory efficiency in algorithm design.
|
| Textbook |
- Michael Main, Data Structures and Other Objects Using Java (Addison Wesley, Third ed. 2006)
- Stephen Kochan, Programming in C (Sams, Pearson Education, Third ed. 2005.)
- Supplementary Material: Frank Carrano and Janet Prichard, Data Abstraction and Problem Solving with Java (Addison Wesley, Second ed., 2006).
|
| Major Topics Covered in Course |
- Software Design: Specifications; memory and execution time efficiency; introduction to Big Oh notation; abstract data types and examples; review of object-oriented techniques.
- Linked Lists: Singly-linked lists; implementation; inserting and removing data; variations: doubly-linked lists, circularly-linked lists; comparison of arrays and linked lists to store general lists.
- Stacks and Queues: Basic operations of a stack; implementation using an array and a linked list; various stack applications (evaluating postfix, conversion of infix to postfix, etc.). Basic operations of a queue; implementation using an array and a linked list; queue applications (Josephus problem, simulations, Jai Alai).
- Recursion: Recursion and activation records, backtracking, introduction to dynamic programming, tail recursion.
- Binary Trees: Terminology; implementation of trees using nodes; Binary search trees: insertion and removal of data; Tree traversals. Heaps; implementation using arrays; use of a heap as a priority queue.
- Balanced Trees: B-trees; 2-3-trees; 2-3-4-trees; red-black trees; AVL trees; splay trees; examples.
- Searching: Sequential and binary search algorithms; hashing and hash tables; time analysis.
- Sorting: Quadratic sorting algorithms; divide and conquer sorts (quick sort and merge sort); heap sort, time analysis.
- Introduction to Graphs: Terminology; implementations using arrays and linked nodes; graph traversals.
|
| Laboratory |
There are 7-8 programming projects required for the course, typically assigned as follows:
- Review of Java, definition of an elementary ADT (e.g. polar coordinate, polynomial, etc.) [2 weeks]
- Program using doubly-linked linked lists built from scratch (e.g. storage of song information for MP3 player, grocery list, etc.) [2 weeks]
- Program using stacks (e.g. parser for XML), use of Stack ADT from Java API. [1.5 weeks]
- Program using queues (e.g. simulation of simple discrete system such as an intersection with a traffic light), definition of a subclass of Vector for queues to illustrate inheritance. [1.5 weeks]
- Program using binary trees and recursion (e.g. Hoffman codes, data storage using a binary search tree, etc.). [2 weeks]
- Program using hash table to illustrate collision handling and load factor. [1 week]
- Simple program in C to learn about pointers and memory management. [1 week]
- More substantial program in C to implement a graph or balanced tree and perform traversals on it. [2 weeks]
|
| Course Webpage |
CSE214
|
