Introduction to Data Structures

Course
Course Catalog URL: 
http://catalog.iastate.edu/azcourses/com_s/
Identifier: 
COM S 228

Offered during Fall and Spring Semesters each year.

  1. Credits and contact hours: 3 credits, 4 contact hours
  2. Instructor’s or course coordinator’s name: Jeremy Sheaffer, Georgi Batinov, Donald Stull, Trent Muhr
  3. Text book, title, author, and year: Carrano, Data Structures and Abstractions with Java (5th Edition), Pearson, 2018
  4. Other supplemental materials: None

Specific course information

  1. Brief description of the content of the course: An object-oriented approach to data structures and algorithms. Object-oriented analysis, design, and programming, with emphasis on data abstraction, inheritance and subtype polymorphism, and generics. Abstract data type specification and correctness. Collections including lists, stacks, queues, trees, heaps, maps, hash tables, and graphs. Big-O notation and algorithm analysis. Searching and sorting. Graph search and shortest path algorithms. Emphasis on object-oriented design, writing and documenting medium-sized programs. This course is designed for majors.
  2. Prerequisites or co-requisites: Minimum of C- in COM S 227, credit or enrollment in MATH 165
  3. Required, elective, or selected elective? Required

Specific goals for the course

  1. Specific outcomes of instruction: This course satisfies two major student outcomes.
  • Be able to write and debug well-structured object-oriented programs, sometimes requiring significant amount of Java code. (1)
  • Be able to implement a Java class given a specification, and to be able to apply OO principles such as encapsulation and inheritance. (1)
  • Be able to implement basic data structures in Java including expandable arrays, linked lists, trees, heaps, hashtables, and graphs, and utilize these data structures in applications. (2)
  • Understand abstract data types (ADTs) including lists, stacks, queues, sets, and maps, be familiar with different ways of implementing these ADTs, know common algorithms for using or manipulating these ADTs.
  • Be able to perform runtime analysis of simple algorithms and know several searching and sorting algorithms and their runtime analysis.

Brief list of topics to be covered

  • Java and Object-Oriented Concepts
  • Exception Handling
  • Analysis of Algorithms
  • Sorting Algorithms
  • Generics in Java
  • Collection Interface and Iterators
  • Lists
  • Stacks
  • Queues and Priority Queues
  • Trees, Binary Search Trees
  • Graphs and basic Graph Algorithms
  • Maps