Credits:   1 unit (4 credit hours)
Contact Hours:   3 lecture & 3 lab
Instructor:   Professor Chun Wai Liew
Last Taught:   Spring 2013
Text Book:   Data Structures & Problem Solving Using Java 4th edition. By Mark Allen Weiss. (Addison-Wesley, 2009.)
     
Description:   This course continues the development of object oriented approaches to the design and implementation of software systems. Students will learn to analyze problems, algorithms and develop object-oriented solutions to problems. Students will also learn to use multiple data structures and the accompanying algorithms to store, index and retrieve data. Lecture/laboratory. (Formerly CS 103: Principles of Computer Science II.)
     
Prerequistes:   CS104, CS105, or CS106

Specific Course Goals:

After successfully completing this course, the student will be able to:

  • Students will demonstrate the ability to analyze, design, apply and use data structures on various problems both in lab and as projects. The data structures include the important collection classes such as array list, linked list, stack, queue, binary search tree, tree map/set, heap, hash-map/-set, and weighted graph.
    (ABET/CAC Outcome A)
  • Students will be able to design, implement and evaluate their solutions to problems assigned in lab and in the classroom.
    (ABET/CAC Outcome C)
  • Students will demonstrate the ability to analyze, design, apply and use data structures to solve problems.
  • Students will be able to work in teams to analyze problems and design different solutions (based on needs) to problems presented in the classroom. The solutions will require the use of a variety of data structures and accompanying techniques/algorithms.
    (ABET/CAC Outcome D)
  • Students will demonstrate the ability to apply current data structures and algorithms to solve problems. In addition, students will use current testing tools and approaches to evaluate and test their solutions.
    (ABET/CAC Outcome I)
  • Students will learn how to experimentally and analytically determine the complexity of various algorithms and operations on data structures. The information will be used to determine the appropriate design choice of data structure and algorithms to solve problems.
    (ABET/CAC Outcome J)

Student Outcomes:

  ABET/CAC Outcome A   An ability to apply knowledge of computing and mathematics appropriate to the discipline.
  ABET/CAC Outcome C   An ability to design, implement, and evaluate a computer-based system, process, component, or program to meet desired needs.
  ABET/CAC Outcome D   An ability to function effectively on teams to accomplish a common goal.
  ABET/CAC Outcome I   An ability to use current techniques, skills, and tools necessary for computing practice.
  ABET/CAC Outcome J   An ability to apply mathematical foundations, algorithmic principles, and computer science theory in the modeling and design of computer-based systems in a way that demonstrates comprehension of the tradeoffs involved in design choices.

Topics covered:

  • Data Containers:
    • ArrayList,
    • Stack,
    • Queue,
    • List,
    • RedBlackTree (TreeMap/TreeSet),
    • 2-3 Tree,
    • Hash Table (HashMap/HashSet),
    • Heap (PriorityQueue),
    • Graph (AdjacencyList, AdjacencyMatrix).
  • Algorithms:
    • Tree traversal,
    • Graph traversal (topological sort, shortest path),
    • Sorting (Quicksort, InsertionSort, SelectionSort, MergeSort),
    • depth first search,
    • breadth first search,
    • binary search.
  • Complexity analysis – Big O
  • Recursion
  • Unit Testing
  • Experiment Design