CSCI 255
Introduction to algorithms & Discrete Structures
**Major Requirement (for B.A. and B.S.)**
Course Description:
Students frequently ask, “What math do I need to know to be
a computer science major?” The answer is: the math that makes
up CSCI 250, Discrete Structures.
This course collects together all of the math topics that are important in the core of computer science and presents them to you in seven weeks. The topics here are essential for success both as a computer science student in later coursework and as a computer scientist in the workplace.
The topics covered and their application in computer science are:
| Propositional Logic | Determining the logical structure of programs and reasoning about the correctness of programs |
| Sets |
Finding efficient data structures and understanding how to manipulate them effectively |
| Relations |
Important for creating algorithms and understanding the organization of databases |
| Functions |
Useful for doing recursion efficiently and effectively and in determining the efficiency of any program |
| Probability |
Important tool for analysis of algorithms and programs for efficiency and for understanding how machines execute code |
| Combinatorics |
Facilitates the construction of algorithms so that all possible cases are handled |
| Boolean Algebra | Know how logic circuits are designed and operate and improve ability to apply logic to program design |
| Positional Number Systems | Know how numbers are represented in the computer and how to exploit that knowledge to do computations with less error and more efficiently |
Offerings:
Offered each year during the Fall semester.
Instructor:
This course is usually taught by Dr. Cusack or Dr. DeJongh.
Prerequisites:
CSCI 112 and CSCI 235, or equivalent. See the department
policy on prerequisites.
Comments from Previous Students:
- "In a short period of time I learned and understood a great deal of material that will be essential for my future in computer science instead of just memorizing information."
- "I learned how to think logically and was prepared for the next course of computer organization."
- "The material taught in this course was applicable to my life."
- "The course material was interesting and made me think."
- "I learned a new way of thinking in here."
Catalog Description:
An introduction to the design and analysis of algorithms along with some of the discrete mathematical structures that are fundamental to the field of Computer Science. This course builds on the data structures topics from CSCI235 by exploring efficient ways of using them to solve problems.
Algorithm analysis topics include best, worst, and average case analysis of iterative and recursive algorithms; asymptotic notation; and solving recurrence relations. Algorithm design techniques include brute force, greedy, divide-and-conquer, transform-and-conquer, dynamic programming, and space/time tradeoff.
Discrete structures topics include propositional logic, proof techniques (especially induction), sets, matrices, sequences and summations, and basic combinatorics.
Four Credits Staff Fall Semester