CSE214

Course CSE214
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.

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 Projects

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