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
Data structures and the Java collections framework" (3rd ed.), William J. Collins.
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.