Foothill CollegeApproved Course Outlines

Physical Sciences, Mathematics & Engineering Division
C S 1MINTERMEDIATE ALGORITHM & DATA STRUCTURE METHODOLOGIES IN JAVAWinter 2014
4 hours lecture, 3 hours laboratory.5 Units

Total Quarter Learning Hours: 84 (Total of All Lecture, Lecture/Lab, and Lab hours X 12)
 
 Lecture Hours: 4 Lab Hours: 3 Lecture/Lab:
 Note: If Lab hours are specified, see item 10. Lab Content below.

Repeatability -
Statement: Not Repeatable.

Status -
 Course Status: ActiveGrading: Letter Grade with P/NP option
 Degree Status: ApplicableCredit Status: Credit
 Degree or Certificate Requirement: AS Degree
 GE Status:

Articulation Office Information -
 Transferability: BothValidation: 4/15/13; 10/01/13

1. Description -
Systematic treatment of intermediate data structures, algorithm analysis and abstract data types in the Java programming language intended for Computer Science transfer majors. Coding topics include large program software engineering design, multi-dimensional arrays, string processing, primitives, compound types, and allocation of instance and static data. Concept topics include dynamic memory, inheritance, polymorphism, hierarchies, recursion, linked-lists, stacks, queues, trees and hash tables.
Prerequisite: C S 1A
Co-requisite: None
Advisory: None

2. Course Objectives -
The student will be able to:
  1. Use instance members, static members, and dynamic data structure allocation as appropriate in object-oriented Java class design.
  2. Analyze and demonstrate the use of multi-dimensional arrays in Java.
  3. Design, implement, and test Java programs that use object-orientation and class inheritance as a key ingredient to good software design, and explain why sub-classing is an example of the is-a relationship.
  4. Describe the difference between deep copies and shallow copies in Java, and write programs that effectively handle deep memory.
  5. Demonstrate a working knowledge of data abstraction through various data types, data structures and their Java-based API classes, and choose the appropriate data structure to model a given problem.
  6. Give examples of the proper use of recursion and describe when iterative solution is more efficient.
  7. Explain what abstract classes and Java interfaces are and how they are used.
  8. Describe declaration models for runtime storage allocation and garbage collection.
  9. Use the Java Collections Framework to write efficient and portable application programs.
  10. Define various types of Java generics and show how each is specialized to a class by the client program.
  11. Design, implement, test, and debug intermediate-level Java programs that use each of the following fundamental programming constructs: user interaction and communication, string processing, numeric computation, simple I/O, arrays and the Java API.
  12. Analyze the basic algorithms of a general tree ADT.
  13. Use object-oriented programming (OOP) to create alternative implementations of binary search trees in Java, and verify or compare the logN behavior of each.
  14. Analyze, classify and measure the main non-NlogN sorts and write a clear report of the results.
  15. Write applications that solve problems in one or more application area: mathematics, physics, chemistry, cellular automata, 3-D simulation, astronomy, biology, business, Internet.
3. Special Facilities and/or Equipment -
  1. Access to a computer laboratory with Java compilers.
  2. Website or course management system with an assignment posting component (through which all lab assignments are to be submitted) and a forum component (where students can discuss course material and receive help from the instructor). This applies to all sections, including on-campus (i.e., face-to-face) offerings.
  3. When taught via Foothill Global Access on the Internet, the college will provide a fully functional and maintained course management system through which the instructor and students can interact.
  4. When taught via Foothill Global Access on the Internet, students must have currently existing e-mail accounts and ongoing access to computers with internet capabilities.

4. Course Content (Body of knowledge) -
  1. The proper use of class members and methods
    1. Primitive vs. compound types
    2. Types as collection of values (data members) and operations (method members).
    3. Type checking and incompatibility in classes.
    4. When to use instance members and methods
    5. When to use static members and methods
    6. Implicit and explicit use of the "this" object
  2. Multi-dimensional arrays
    1. 2-D arrays
    2. Ragged 2-D arrays
    3. Instantiation of objects in multi-dimensional arrays
  3. Inheritance in Software Design
    1. The "is a" relationship
    2. Base classes
    3. Derived classes (subclasses) and class heirarchy
    4. Derived class constructors
    5. Member method overriding vs. simple overloading
    6. Private, protected, public and default members
    7. Encapsulation and Polymorphism
    8. Separation of behavior and implementation and other attributes of good software design
  4. Deep vs. Shallow Copies of Objects
    1. Instantiation of member objects in constructors
    2. Cloning objects
    3. Deep copy cloning and its uses
    4. Shallow copy cloning and its uses
  5. Topics in Abstract Data Types (ADTs)
    1. The vector ADT and Java's ArrayList
    2. The linked-list ADT and Java's LinkedList
    3. The Stack and Queue ADT
    4. Implementing ADTs through inheritance
    5. Using existing ADTs from java.util
  6. Recursion
    1. Base case vs. general case.
    2. Divide-and-conquer strategies
    3. Analysis of recursive solutions which are not appropriate due to exponential time complexity vs. iterative polynomial complexity
    4. Recursive backtracking
  7. Abstract Classes and Interfaces
    1. Defining and using abstract classes
    2. Defining and using interfaces
    3. Implementing interfaces and abstract classes
  8. Storage Allocation Methods
    1. Run time binding and storage management of activation records.
    2. Consequences of reference declarations and parameter-passing in Java and the relationship between Java references and the values/pointer mechanism of other languages.
    3. Strong type-checking and run-time vs. compile time error detection.
    4. Effect of declaration strategy on binding, visibility and lifetime of variables.
    5. Effect of declaration strategy on scope and persistence of variables.
  9. Java Collections Frameworks
    1. Java ArrayLists and ListIterators
    2. Java LinkedLists and ListIterators
    3. Java PriorityQueues
  10. Java Generics
    1. Generic classes
    2. Type Parameters
    3. The occasional need for wrapper classes
    4. Autoboxing
    5. Static generic methods
    6. Type bounds
    7. Wildcards
  11. Essential examples and Assignment Areas
    1. String/text processing
    2. Numeric computation
    3. User interaction
    4. Multi-class projects and compound data types
    5. Inheritance-based projects
  12. General Trees
    1. Tree nodes, roots, leaves, children and siblings
    2. Binary node implementation of a general tree
    3. Insertion and deletion in general trees
    4. Traversal with recursion
  13. Searching and Binary Search Trees (BSTs)
    1. Ordering condition and structure condition
    2. OOP (object-oriented-programming) Implementation
    3. Time complexity consequence of the divide-and-conquer algorithm in of BSTs
  14. NlogN Sorts
    1. Merge sort
    2. Heap sort
    3. Quicksort
  15. Applications used throughout course in selected areas
    1. Math
    2. Physics
    3. Chemistry
    4. Biology
    5. Astronomy
    6. Business and finance
    7. Internet
5. Repeatability - Moved to header area.
 
6. Methods of Evaluation -
  1. Tests and quizzes
  2. Written laboratory assignments which include source code, sample runs and documentation.
  3. Final examination
7. Representative Text(s) -
Weiss, A. Mark Allen. Data Structures and Algorithm Analysis in Java. Third Edition. Addison Wesley, 2011.

8. Disciplines -
Computer Science
 
9. Method of Instruction -
  1. Lectures which include motivation for syntax and use of the Java language and OOP concepts, example programs, and analysis of these programs.
  2. On-line labs (for all sections, including those meeting face-to-face/on campus) consisting of
    1. A programming assignment web-page located on a college-hosted course management system or other department-approved Internet environment. Here, the students will review the specification of each programming assignment and submit their completed lab work.
    2. A discussion web-page located on a college hosted course management system or other department-approved Internet environment. Here, students can request assistance from the instructor and interact publically with other class members.
  3. Detailed review of programming assignments which includes model solutions and specific comments on the student submissions.
  4. In person or on-line discussion which engages students and instructor in an ongoing dialog pertaining to all aspects of designing, implementing and analyzing programs.
  5. When course is taught fully on-line:
    1. Instructor-authored lecture materials, handouts, syllabus, assignments, tests, and other relevant course material will be delivered through a college hosted course management system or other department-approved Internet environment.
    2. Additional instructional guidelines for this course are listed in the attached addendum of CS department on-line practices.
 
10. Lab Content -
  1. Exploring advanced array constructs in class design
    1. Gain experience in effectively using single and multi-dimensional arrays as class members.
    2. Apply nested loops to process multi-dimensional arrays.
    3. Use the IDE to debug errors in multi-dimensional arrays.
    4. Solve problems using fixed-size and dynamic sized arrays, as appropriate.
  2. Building a program that uses class inheritance to demonstrate how re-use is handled in OOP.
    1. Create a project that contains at least one class intended to be used as a base class.
    2. Derive (sub-class) one or more classes from the base class.
    3. Use function chaining to avoid code duplication between base classes and derived classes.
    4. Differentiate between, and document in your lab, the distinct use of method overloading and method overriding.
  3. Incorporating basic queue and stack abstract ions in programming projects
    1. Implement a fundamental queue and stack abstract data type (ADT) in a programming lab.
    2. Use a previously written ADT from the programming language's application programmer interface (API) .
    3. Incorporate inheritance in a project that uses ADTs.
    4. Provide a client program that tests and demonstrates the correct behavior of the ADT.
  4. Building projects that use generics (A.K.A. templates)
    1. Demonstrate the difference in a lab project between deriving from a base class and specializing a generic.
    2. Practice writing a generic as well as using a language-defined generic (template) in a project.
    3. Use generics to exercise some aspect of ADTs such as specializing a generic ADT to make its behavior specific to an assigned project specification..
    4. Employ debugging techniques to solve problems that arise when designing with generic (template) classes.
  5. Using linked-list ADTs to optimize for size-varying or space-sensitive data types
    1. Demonstrate the ability to use programming language-supplied linked-list structures in a problem that is not easily solved using fixed-size ADTs such as arrays.
    2. Incorporate generics so as to allow the algorithm to work on various underlying data types.
    3. Try different sized data for the linked-list and demonstrate that it handles growth properly.
  6. Demonstrating competence with binary search trees
    1. Implement a binary search tree (BST) from scratch, or make significant assigned adjustments to an existing BST data structure supplied by your instructor.
    2. Use recursion as appropriate for some of the BST methods.
    3. Demonstrate that the class works on various underlying base type by use of generic specialization.
  7. Incorporating hash tables into programs
    1. Produce a lab that creates or modifies a hash table and hashing function.
    2. Write a client that tests out the hash table on various data.
    3. Using a large data set, demonstrate that near-constant time access is produced by the hashing function and hash table.
    4. Supply runs and report results with varying sized data sets.
  8. Analysis of a single sort algorithm
    1. Implement a single sort algorithm as directed by the instructor.
    2. Experiment with coding adjustments to try to improve the performance.
    3. Compare the known time complexity of that algorithm with what you observe using increasingly larger data sets.
    4. Attempt to explain any discrepancies in the expected vs. observed growth rate of the sort algorithm.
  9. Analysis of multiple sort algorithms
    1. Implement multiple sort algorithms, at least two of which involve Shell sort and quicksort.
    2. Experiment with coding adjustments to try to improve the performance on any one of them to see if you can beat the fastest of the algorithms.
    3. Time the algorithms on very small to very large data sets.
    4. Report on which algorithms work better on small sets, and which on large sets.
 
11. Honors Description - No longer used. Integrated into main description section.
 
12. Types and/or Examples of Required Reading, Writing and Outside of Class Assignments -
  1. Reading
    1. Textbook assigned reading averaging 30 pages per week.
    2. Reading the supplied handouts and modules averaging 10 pages per week.
    3. Reading on-line resources as directed by instructor though links pertinent to programming.
    4. Reading library and reference material directed by instructor through course handouts.
  2. Writing
    1. Writing technical prose documentation that supports and describes the programs that are submitted for grades.
13. Need/Justification -
This course is a restricted support course for the A.S. degree in Computer Science.


Course status: Active
Last updated: 2014-06-18 17:03:33


Foothill CollegeApproved Course Outlines