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.)
Prerequisites: 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.
  • Students will be able to design, implement and evaluate their solutions to problems assigned in lab and in the classroom.
  • 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.
  • 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.
  • 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.

Student Outcomes:

ABET/CAC Outcome 1 Analyze a complex computing problem and to apply principles of computing and other relevant disciplines to identify solutions..
ABET/CAC Outcome 2 Design, implement, and evaluate a computing-based solution to meet a given set of computing requirements in the context of the program’s discipline.
ABET/CAC Outcome 5 Function effectively as a member or leader of a team engaged in activities appropriate to the program’s discipline.
ABET/CAC Outcome 6 Apply computer science theory and software development fundamentals to produce computing-based solutions.

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