Search Results

Catalog Description Prerequisite: Completion of CSCI 0012 and MATH 0012 with grades of "C" or better Hours: 72 (54 lecture, 18 laboratory) Description: Introduction to the essential discrete structures used in Computer Science, with emphasis on their applications. Includes elementary formal logic and set theory, elementary combinatorics, recursive programming and algorithm analysis, Boolean algebra, digital logic, combinatorial circuits, graph theory, circuit design and minimization, and computer arithmetic. (C-ID COMP 152) (CSU, UC) Course Student Learning Outcomes CSLO #1: Describe how formal tools of symbolic logic are used to model real-life situations, including those arising in computing contexts such as program correctness, database queries, and algorithms. CSLO #2: Relate the ideas of mathematical induction to recursion and recursively defined structures. CSLO #3: Analyze a problem to create relevant recurrence equations. CSLO #4: Demonstrate different traversal methods for trees and graphs. CSLO #5: Apply the binomial theorem to independent events and Bayes’ theorem to dependent events. 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. Convert between decimal, hexadecimal and binary representation of numbers. 2. Convert negative decimal numbers to two's complement binary form. 3. Analyze sets for complement, union and intersection. 4. Construct Venn diagrams to illustrate set relationships and operations. 5. Evaluate sets for reflexivity, symmetry, and transitivity. 6. Encrypt and decrypt a string of text using the RSA algorithm and modular arithmetic. 7. Identify problems appropriately solved with recursive functions. 8. Convert floating point notation (IEEE-754) to decimal and binary. 9. Recognize digital logic gates and their representation in graphical, algebraic, and truth table form. 10. Convert Boolean functions between algebraic expressions, truth tables and circuit diagrams. 11. Convert an English-language statement of compound propositions (including and, or, not, and quantifiers) to a symbolic form. 12. Identify and solve combinatorial word problems using permutations, combinations, pigeonhole principle, inclusion/exclusion principle, and/or product rule. 13. Compute discrete probabilities of conditional events using Bayes' Theorem. 14. Compare and contrast the "Big-O" running time of common searching and sorting algorithms. 15. Minimize circuits and Boolean expressions by creating Karnaugh Maps. 16. Analyze a graph for the shortest path between two vertices and the minimal spanning tree. 17. Create regular expressions for sets of strings. 18. Create a finite-state automaton from a written description of a set of strings. Laboratory Objectives: 1. Design and construct logic circuits using AND, OR, NOT, NAND, and/or XOR gates from written descriptions. 2. Analyze inputs and outputs for the creation of functions that manipulate numbers, strings, lists, sets, and tuples; 3. Write and test recursive functions on numbers, lists, strings, sets, and tuples; 4. Analyze strings to derive appropriate regular expressions and test them against a corpus of text; 5. Analyze a regular language and construct a regular expression for it; and 6. Write and test functions to encrypt and decrypt strings using shift, linear, and RSA ciphers. 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 Classroom Discussions Example: Example: What could be some of the consequences of discovering a fast algorithm for factoring a number into its prime factors? Problem Solving Examinations Example: Example: Compute the 2's Complement form of -29 using an 8-bit representation. Solution: Calculate the binary representation of +29: 00011101 Invert the bits: 11100010 Add 1: 11100011 Projects Example: Derive a regular expression to match ZIP codes (both 5-digit and 9-digit). The student will be provided a text file containing sample data that includes names, addresses, and phone numbers. The regular expression should match and display all the zip codes from the file. The student solution can be checked by comparing the student output to a solution file that the instructor has created. Repeatable No Methods of Instruction Laboratory Lecture/Discussion Distance Learning Lab: Following an instructor lecture and demonstration, students write a computer program to calculate the union and intersection of two sets. The sets can be defined in the program (for example, in Python: A = {3, 9, 5, 1, 2}, B = {1, 2, 3, 4, 5}) and the set operations applied to these sets with the results shown on the screen. Have the students work through problem sets. (Laboratory Objective 3) Following an instructor lecture and demonstration, students use software such as Logisim to construct a half-adder using only NAND gates. Demonstrate on a projector, then have the students do it themselves on a computer. Compare this circuit to one that uses AND, OR, and XOR gates. Verify correct operation using a truth table and compare it to the one that Logisim can automatically generate. (Laboratory Objective 1) Lecture: Instructor lecture and demonstration on how to calculate a minimal spanning tree of a graph with at least 10 nodes and 20 edges. Draw a sample graph on the board (or use a projector) and walk through the algorithm, showing how the minimal spanning tree is derived. Hand out exercise sheets to the students with pre-drawn graphs on them and have the students apply the algorithm to the graphs. Check the graphs for correctness. (Lecture Objective 16) Following an instructor lecture, students using Venn diagrams, calculate the union and intersection of two sets: for example, the set of students with blonde hair and the set of students wearing green shirts. This could be done as a kinesthetic exercise with students standing at the front of the classroom and being grouped according to their characteristics. Show how these groups of students correspond to Venn diagrams. (Lecture Objective 4) Instructor lecture and demonstration on various algorithms for converting decimal numbers to binary and hexadecimal. Solicit suggestions from students for numbers to convert. After demonstrations are complete, students work through exercise sheets. (Lecture Objective 1) Distance Learning The instructor will provide a video lecture and demonstration on sets and relations. Students are then expected to solve problems related to the topic. Typical Out of Class Assignments Reading Assignments 1. Read the section in the textbook on modular arithmetic to learn how to compute the multiplicative inverse. Be prepared to discuss in class. 2. Read the Wikipedia article on the RSA encryption system to learn who invented it, the underlying computations used, and its strengths and weaknesses. Be prepared to discuss in class. Writing, Problem Solving or Performance 1. Using the "repeated division" method, convert the decimal number 29 to binary and hexadecimal. Answer: 29 / 2 = 14 r 1; 14 / 2 = 7 r 0; 7 / 2 = 3 r 1; 3 / 2 = 1 r 1; 1 / 2 = 0 r 1. The solution can be read in the remainders from right to left: 11101. Hexadecimal follows from the binary solution by partitioning into groups of 4 and converting each group to hexadecimal: 1 | 1101 -> 1D 2. Compute at least three strings recognized by this regular expression: b(c|d)*b Sample answers: bb, bcb, bdb, bcccd, bcdcd, bcdcccdb Other (Term projects, research papers, portfolios, etc.) Required Materials Discrete Structures, Logic, and Computability Author: James L. Hein Publisher: Jones & Bartlett Publishers, Inc. Publication Date: 2015 Text Edition: 4th Classic Textbook?: Yes OER Link: OER: Discrete Structures Author: Fell, Harriet, et al Publisher: Cognella Academic Publishing Publication Date: 2016 Text Edition: 1st Classic Textbook?: Yes OER Link: OER: Mathematical Structures for Computer Science Author: Gersting, Judith Publisher: W H Freeman Publication Date: 2014 Text Edition: 7th Classic Textbook?: Yes OER Link: OER: Discrete Mathematics and Its Applications Author: Kenneth Rosen Publisher: McGraw-Hill Education Publication Date: 2018 Text Edition: 8th Classic Textbook?: Yes OER Link: OER: Discrete Structures (Undergraduate Texts in Mathematics) Author: Andreas Klappenecker (Author), Hyunyoung Lee Publisher: Springer Publication Date: 2025 Text Edition: 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.