Catalog Description
This class is a continuation of CIS162. Additional work with data structures and algorithms to implement them is presented. Topics will include: Review of basic Big Oh, review of last term data structures, implementations of Stack, Queue, Linked List, Trees, Hash Tables, (graph algorithms as time allows). All programs will also focus on basic algorithm analysis and appropriate use of data structures.  Java library data structures will also be examined.
 
Expect a continuing emphasis on proper programming disciplines. (4 credits)
 
Prerequisite(s):
CIS 162 -- Introduction to Computer Science II
MTH 232 -- Elements of Discrete Mathematics II
 
Prerequisite for (OSU CS Courses):
CS 311 -- Operating Systems I
CS 321 -- Introduction to Theory of Computation
CS 325 -- Analysis of Algorithms
CS 361 -- Fundamentals of Software Engineering
CS 381 -- Programming Language Fundamentals
CS 440 -- Database Management Systems
 
Textbook
Classic Data Structures in Java, Timothy Budd, Addison-Wesley.
 
Syllabus
Goals: Expose the student to classic data structures used in almost all nontrivial programs. Investigate some of the techniques used to analyze and discover properties of programs (running time, correctness, etc.) Acquaint the student with software engineering and problem solving skills (including object-oriented programming). Hone student skills in Java programming.

Topics:

  1. Stacks and queues, priority queues, sets, bags, dictionaries, tables.
  2. Hashing and hash tables.
  3. Trees and heaps.
  4. Introduction to graphs and graph processing.
  5. Searching and sorting including binary trees.

Laboratory projects: Between Seven and Nine programming assignments.
 

Goals/Outcomes
  1. Continued improvement of programming disciplines
  2. Learn to use a variety of data structures
  3. Learn to evaluate pros/cons of data structures
  4. Learn to use Java Collection API routines
     
  5. Ability to select correct data structure for an application
  6. Ability to explain pros/cons of Selection/Quick/Heap sorts
  7. Ability to select correct sort for an application
  8. Ability to select and use Java collection classes
  9. Ability to analyze approximate runtime behavior of algorithms
  10. Ability to integrate data structures into applications 
Evaluation
Programs written in Java 40%
Quizzes 10%
Midterm (1) ................. 15%
Final Exam .................. 35%

Thanks to OSU CS Department for elements of this Syllabus.