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.

CSE 114 (Computer Science I)

• 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]