CSE214

CSE214

Computer Science II

3

Michael A. Bender

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 used. Fundamental sorting and searching algorithms are examined along with informal efficiency comparisons.

C or higher in CSE 114

• To provide students with additional programming experience using an object-oriented language, with emphasis on larger-scale programs that require the use of sophisticated data structures.
• To enhance student understanding of abstract data types, pointers, recursion, and algorithmic design.
• To introduce students to the importance of time and memory efficiency in algorithm design.

Data Abstraction and Problem Solving with Java Walls and Mirrors

Carrano and Prichard , 1st update Edition 2004 packaged with CSE214, Supplement, Addison Wesley ISBN: 0536744874

• Software Design: Specifications; memory and execution time efficiency; introduction to Big Oh notation; abstract data types and examples; review of object-oriented techniques. (2 weeks)
• 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. (2 weeks)
• 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). (2 weeks)
• Recursion: Recursion and activation records, backtracking, introduction to dynamic programming, tail recursion. (1 week)
• 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. (2 weeks)
• Balanced Trees: B-trees; 2-3-trees; 2-3-4-trees; red-black trees; AVL trees; splay trees; examples. (1.5 weeks)
• Searching: Sequential and binary search algorithms; hashing and hash tables; time analysis. (1 week)
• Sorting: Quadratic sorting algorithms; divide and conquer sorts (quick sort and merge sort); heap sort, time analysis. (1 week)
• Introduction to Graphs: Terminology; implementations using arrays and linked nodes; graph traversals. (1 week)
• Midterm(s) (0.5 week)

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]