Search Results

Catalog Description Prerequisite: Completion of CSCI 0012 with grade of "C" or better Hours: 72 (54 lecture, 18 laboratory) Description: Application of software engineering techniques to the design and development of large programs; data abstraction and structures and associated algorithms. (C-ID COMP 132) (CSU, UC) Course Student Learning Outcomes CSLO #1: Implement linear lists with arrays and linked objects. CSLO #2: Write programs that use the stack and queue data structures, based on provided specifications. CSLO #3: Produce intermediate-sized programs using Object-Oriented design principles, with a combination of written and provided code. CSLO #4: Identify effective techniques to test, debug, and document larger programs. CSLO #5: Write a program that uses recursive algorithms operating on a binary tree. Effective Term Fall 2026 Course Type Credit - Degree-applicable Contact Hours 72 Outside of Class Hours 90 Total Student Learning Hours 162 Course Objectives Lecture Objectives: 1. Discuss the representation and use of primitive data types and built-in data structures. 2. Describe how the data structures are allocated and used in memory. 3. Describe common applications for each data structure. 4. Compare alternative implementations of data structures with respect to performance. 5. Compare and contrast the costs and benefits of dynamic and static data structure implementations. 6. Choose the appropriate data structure for modeling a given problem. 7. Describe the concept of recursion and give examples of its use. 8. Identify the base case and the general case of a recursively defined problem. 9. Compare iterative and recursive solutions for elementary problems such as factorial. 10. Describe the divide-and-conquer approach. 11. Describe how recursion can be implemented using a stack. 12. Discuss problems for which backtracking is an appropriate solution. 13. Determine when a recursive solution is appropriate for a problem. 14. Explain the value of declaration models, especially with respect to programming-in the-large. 15. Identify and describe the properties of a variable such as its associated address, value, scope, persistence, and size. 16. Discuss type incompatibility. 17. Defend the importance of types and type-checking in providing abstraction and safety. 18. Evaluate trade-offs in lifetime management (reference counting vs. garbage collection). 19. Explain how abstraction mechanisms support the creation of reusable software components. 20. Defend the importance of abstractions, especially with respect to programming-in-the-large. 21. Describe how the computer system uses activation records to manage program modules and their data. 22. Justify the philosophy of object-oriented design and the concepts of encapsulation, abstraction, inheritance, and polymorphism. 23. Describe how the class mechanism supports encapsulation and information hiding. 24. Compare and contrast the notions of overloading and overriding methods in an object-oriented language. 25. Explain the relationship between the static structure of the class and the dynamic structure of the instances of the class. 26. Describe how iterators access the elements of a container. 27. Discuss the properties of good software design. 28. Compare and contrast object-oriented analysis and design with structured analysis and design. Laboratory Objectives: 1. Implement the user-defined data structures in a high-level language. 2. Write programs that use each of the following data structures: arrays, records, strings, linked lists, stacks, queues, and hash tables. 3. Implement, test, and debug simple recursive functions and procedures. 4. Demonstrate different forms of binding, visibility, scoping, and lifetime management. 5. Demonstrate the difference between call-by-value and call-by-reference parameter passing. 6. Design, implement, test, and debug simple programs in an object-oriented programming language. 7. Design, implement, and test the implementation of "is-a" relationships among objects using a class hierarchy and inheritance. General Education Information Approved College Associate Degree GE Applicability CSU GE Applicability (Recommended-requires CSU approval) Cal-GETC Applicability (Recommended - Requires External Approval) IGETC Applicability (Recommended-requires CSU/UC approval) Articulation Information CSU Transferable UC Transferable Methods of Evaluation Objective Examinations Example: Multiple choice and short answer questions such as: 1. Which of the following is not a valid Java identifier? a) pressureA b) ppO2 c) 4counter d) all of the above are valid Java identifiers Answer: c Identifiers must begin with an upper or lowercase letter. Problem Solving Examinations Example: 1. Write a static method that computes the arithmetic mean of a list of numbers. Your methods should accept the list of numbers as a parameter. Answer: public static double mean(double[] x) { double average=0; //sum the values in the list for(int i=0; i average=average+x[i]; return average/x.length; } 2. Laboratory assignments covering computer science principles and applications such as: 1. Implement the infix to postfix conversion program discussed in class. Your solution should make use of a reference-based stack. Your program should also check the validity of the input stream. Projects Example: Create a program that simulates the flight of a model rocket. Your program should allow the user to specify the mass of the rocket, total impulse of the motor, and burn time of the motor. Your simulation should use the formulas discussed in class. For the simulation output, create a chart that shows the altitude of the rocket each 10th of a second. Repeatable No Methods of Instruction Laboratory Lecture/Discussion Distance Learning Lab: Prior to the lab, ask the class to read the data structures chapter and pay close attention to the design and implementation of the queue. Instructor initiate the discuss for the following: How would you use the queue to simulate waiting in line for a ride at an amusement park? Students will be asked to create a Java program for this simulation. Lecture: Assume students have read the chapter on data structures. Instructor gives a 20 to 30 minute lecture discussing the array implementation of the stack. Make use of the whiteboard and a handout about the stack during the lecture. Discuss postfix notation and how a stack is used to process a postfix expression. Ask the students to develop pseudocode for processing a postfix expression using a stack. Ask three students to put their solution on whiteboard. Discuss each solution with class. Discuss optimal pseudocode using presentation software. Distance Learning The instructor will present a video lecture on inheritance. After the student views the lecture, they will then be asked to write the GeometricObject class, Circle class and rectangle class using the inheritance. Typical Out of Class Assignments Reading Assignments 1. Read and study the chapter on fundamental data structures. Focus your reading on the stack and queue. Be prepared to compare and contrast these two structures and their various implementations in class. 2.Read and study the handout on overloading and overriding. Compare and contrast the notions of overloading and overriding methods in an object-oriented language and be prepared to discuss in class. Writing, Problem Solving or Performance Typical early lab assignment: Goals: Cutting a string into pieces.Counting words. Description Write two separate Java programs for cutting a string (sentence) into individual tokens (words). Part 1 Write a Java program that uses the StringTokenizer class (in java.util) to break a string into tokens. Your program should print each word from the string on a separate line. In addition, your program should print the number of tokens found in the string. You may assume the tokens in the string are separated by one or more spaces and the string is terminated with a period. This first program may be written entirely in a main method. Please use the string under test data to test your program. Part 2 Your second program should also slice a string into tokens, but without the aid of the StringTokenizer class. Using the charAt( ) method, and the string length constant, to tokenize the test data string. Add each token from the string into an ArrayList object (see the Java API under java.util). Your program can simply add each token to the ArrayList as the tokens are discovered. Other (Term projects, research papers, portfolios, etc.) Required Materials Introduction to Java Programming Author: Y. Daniel Liang Publisher: Pearson Education Publication Date: 2014 Text Edition: 10th Classic Textbook?: Yes OER Link: OER: Starting out with Java Author: Tony Gaddis Publisher: Pearson Publication Date: 2017 Text Edition: 6th Classic Textbook?: Yes OER Link: OER: Java Illuminated Author: Julie Anderson and Hervé J. Franceschi Publisher: Jones & Bartlett Learning Publication Date: 2022 Text Edition: 6th Classic Textbook?: OER Link: OER: Other materials and-or supplies required of students that contribute to the cost of the course.

Catalog Description Prerequisite: Completion of CSCI 0066 with grade of "C" or better; and completion with grade of "C" or better, or concurrent enrollment in CSCI 0026 Advisory: Completion of CSCI 0013 with grade of "C" or better Hours: 72 (54 lecture, 18 laboratory) Description: A comprehensive introduction of data structures for computer science. Topics include: lists, stacks, trees, hash tables, and heaps. Associated algorithms are also covered: searching, sorting, traversal, path finding, spanning tree, and network flow. C++ is used as the implementation language. (CSU, UC) Course Student Learning Outcomes CSLO #1: Apply algorithm analysis to the operations on data structures and interpret the results. CSLO #2: Describe and evaluate the operations and possible implementations of abstract data types for lists and trees. CSLO #3: Describe the operation and characteristics of sorting algorithms. CSLO #4: Describe the operation and application of graph algorithms. CSLO #5: Select and justify appropriate data structures and algorithms for complex programming tasks. Effective Term Fall 2026 Course Type Credit - Degree-applicable Contact Hours 72 Outside of Class Hours 90 Total Student Learning Hours 162 Course Objectives Lecture Objectives: 1. Describe the structure and operations on the following abstract data types: lists, stacks, queues, binary trees, AVL trees, splay trees, tries, B-trees, hash tables, and heaps; 2. Describe the operation of the following sorting algorithms: insertion sort, shell sort, heapsort, mergesort, quicksort, bucket sort, and radix sort; 3. Describe the operation and application of the following graph algorithms: depth first search, breadth first search, shortest path, minimum spanning tree, network flow, and topological sort; 4. Analyze the time and space complexity of the above data structures and algorithms using Big-O notation; 5. Analyze a problem specification to select appropriate data structures and algorithms; and 6. Describe the BP vs. NP problem and its implications. Laboratory Objectives: 1. Write programs that implement the above data structures and algorithms; 2. Test the implementations to verify time and space complexity; 3. Write source code that is easy to read, well organized, well commented; and 4. Employ debugging techniques to assist in programming. General Education Information Approved College Associate Degree GE Applicability CSU GE Applicability (Recommended-requires CSU approval) Cal-GETC Applicability (Recommended - Requires External Approval) IGETC Applicability (Recommended-requires CSU/UC approval) Articulation Information CSU Transferable UC Transferable Methods of Evaluation Essay Examinations Example: You've been assigned to design an assembly line for an automobile manufacturing plant. An assembly line is a linear set of stations. At each station, people begin and complete specific task(s). For each task your will program will receive: 1) The time it takes to complete the task, and 2) the previous task(s) that the current task is directly dependent upon being completed before it can start. There are T tasks, and a total of D dependencies for all of the tasks. Objective Examinations Example: Given the following AVL tree, draw a representation of the tree after an insert(10) operation has been executed. (Tree shown here in Lisp notation) (5 (2 nil 3) (12 (8 7 11) (15 14 19))) Problem Solving Examinations Example: What is the best estimate of the time complexity of the following method using the big-O notation? public static void f(int N) { int sum = 0; for(int i = 1; i <= N; i = i*2) { for (int j = 0; j <= N; j=j+1) { sum = sum + 1 } } } } Projects Example: You are to write an efficient program that will determine the number of people to assign to each job in a large project. Instructor provided the driver program ProjectDriver.cpp, and the necessary class stubs in scheduler.h, and scheduler.cpp. You may add any classes and/or code you wish to scheduler.cpp, and scheduler.h. The constructor for the Scheduler class accepts an array of Job that contains all of the information about the project. When Scheduler::run() is called, your program will decide which person to assign to which job. The scheduler indicates its choices by placing the person’s ID in the peopleIDs array of the job, and setting the numPeopleUsed of that job accordingly. Before returning from run(), the scheduler must set each job’s startTime. No job may start before all of its ancestors are finished. All jobs in the project must be completed. Each person is assigned to a job for its duration, and may not work on another job during that time. Repeatable No Methods of Instruction Laboratory Lecture/Discussion Distance Learning Lab: Following an instructor discussion or presentation on red-black tree, the students are expected to have written an implementation of a red-black tree. They then must write a C++ program that measures the time it takes to insert items into their tree implementation. The program should insert an item into trees with 10, 100, 1,000, 10,000, and 100,000 items. Measurements are taken by averaging the number of nodes touched in memory across 100 insertions for each tree. Plot the averages. Students compare their experimental results with the theoretical ones determined by analysis. The instructor leads a discussion of why the results may or may not differ from the analysis. Lecture: The topic is singly-linked lists. Using the whiteboard or other drawing surface, the instructor demonstrates the "addToHead" operation on the list, showing the before and after pictures. The instructor then draws a picture of a list with five elements in it, showing pointers to the head of the list and each node's pointer to the next element. The instructor prompts the students to draw a new picture showing the data structure after a new element is added to the head of the list. The students are further prompted to write pseudo-code with the instructions needed to perform the operation. Distance Learning The same instructor led lecture and lab activities for red-black tree and singly-linked lists can be done in a DL environment through the use of video lectures and online presentation slides/images. However, instead of turning in an analysis on paper, the students can take a picture of their drawings and upload them to the learning management system. Programs, likewise, can be uploaded along with an analysis document. The instructor can either grade the assignments individually or use a peer review process for facilitating group discussions of results. Typical Out of Class Assignments Reading Assignments 1. Read the sections from the textbook about hash tables. Pay particular attention to the hash function, its domain of inputs, and range of outputs. Identify the application of a hash table. Be prepared to discuss in class. 2. Consult the Standard Template Library documentation for the built-in implementation of the singly-linked list. Determine the class name, constructor, and methods to add and remove elements from the list. Be prepared to discuss in class. Writing, Problem Solving or Performance Laboratory assignment per week solving problems with different data structure discussed in class 1. Apply the hash function shown in the textbook to the inputs "hello", "hola", and "bonjour". What are the outputs of the hash function for each input? Construct a table on paper showing the inputs and corresponding outputs. Come up with at least three of your own inputs and show the corresponding outputs. Are there any duplicate outputs? 2. Determine the Big-O running time of inserting an element into a random location of a singly-linked list. Express the answer in terms of the number of elements already in the list. 3. Draw a picture of a red-black tree with at least ten elements in it. A new element will be inserted somewhere in the middle of the tree. Show the intermediate steps (with a new drawing for each) as the tree is re-balanced. Draw a picture of the final tree, which must also be balanced. Other (Term projects, research papers, portfolios, etc.) Required Materials Data Structures and Algorithms in C++ Author: Michael Goodrich, et al Publisher: Wiley Publication Date: 2011 Text Edition: 2nd Classic Textbook?: Yes OER Link: OER: C++ Plus Data Structures Author: Nell Dale Publisher: Jones & Bartlett Learning Publication Date: 2016 Text Edition: 6th Classic Textbook?: Yes OER Link: OER: Data Structures and Algorithm Analysis in C++ Author: Mark Allen Weiss Publisher: Addison Wesley Publication Date: 2014 Text Edition: 4th Classic Textbook?: Yes OER Link: OER: Problems Solving in Data Structures and Algorithms Using C++: A practical approach to competitive programming Author: Hemant Jain Publisher: BPB Publications Publication Date: 2024 Text Edition: 1st Classic Textbook?: OER Link: OER: Other materials and-or supplies required of students that contribute to the cost of the course.