## CSC 208 - Introduction to Discrete Structures at Germanna Community College

### Course Description

Effective: 2013-01-01

Covers Boolean algebra, combinatorial and sequential circuits, algorithms and algorithm analysis, recursion, recurrence relations, graphs, and trees.
Lecture 3 hours. Total 3 hours per week.
3 credits

### General Course Purpose

Most students who enroll in the Computer Science specialization of the Science AS degree at J. Sargeant Reynolds Community College transfer to VCU. VCU has an introduction to discrete structures course in the second year of the Computer Science BS degree that must be taken before students can complete upper level courses in Computer Science. Students who have not taken this course are not allowed in the upper level Computer Science courses and are at a disadvantage trying to finish the Computer Science BS degree in two years at the transfer institution. The Introduction to Discrete Structures course will be taken as an approved elective so that students transferring to institutions in Computer Science not requiring this course will not have to take it at the community college.

### Course Prerequisites/Corequisites

Prerequisite: CSC 201

### Course Objectives

• Analyze algorithms and their complexity, referring to the time and space required to execute them.
• Discuss recursive algorithms and determine if a recursive solution is more efficient than an iterative one.
• Introduce recurrence relations and analyze how they relate to recursive algorithms and what types of problems are solved using these methods.
• Explain how recurrence ties to complexity analysis.
• Solve 1st and 2nd order homogenous relations with constant coefficients.
• Discuss graph theory, ways of representing graphs, and applications of graphs.
• Discuss the terminology, subclasses, and applications of trees.
• Explore the relationship of Boolean algebra and electronic circuits.
• Give an introduction to network models and Karnaugh maps.

### Major Topics to be Included

• Algorithm analysis
• Recurrence relations
• Graph theory
• Trees
• Boolean algebras and combinatorial circuits

<- Back to CSC 208

<- Show content outlines for all CSC courses