Course 
CSE150 
Title 
Foundations of Computer Science  Honors 
Credits 
4 
Course Coordinator 
Leo Bachmair

Description 
Introduction to the logical and mathematical foundations of computer science for computer science honors students. Topics include functions, relations, and sets; recursion and functional programming; basic logic; and mathematical induction and other proof techniques.

Prerequisite 
One MAT course that satisfies D.E.C. C or QPS or score of level 4 on the math placement exam; admission to the Computer Science Honors Program or the Honors College or WISE or permission of the instructor 
Course Outcomes 
 An ability to use logic and basic proof techniques, such as mathematical induction.
 To understand recursion as a computing paradigm.
 An ability to define and use discrete structures such as functions, graphs and tree.

Textbook 
James L. Hein, Discrete Structures, Logic and Computability, Jones and Bartlett, 9780763772062. Supplementary Material: Eric Lehman and Tom Leighton, Mathematics for Computer Science, Online.

Major Topics Covered in Course 
 Propositional logic
 Syntax and semantics (truth tables); logical equivalences and logical consequence; basic proof theory (e.g., modus ponens); boolean algebra; application: digital logic circuits; application: number systems
 Functions
 Basic concepts and standard functions; sequences; basic properties of functions; composition of functions
 Recursion
 Recursive definitions of functions and sequences; application: functional programming
 Mathematical induction
 Principle of mathematical induction; examples of induction proofs; strong induction principle
 Lists and trees
 Basic definitions and operations; for both data structures; specific examples of list operations and tree algorithms to illustrate functional programming and mathematical induction

Laboratory Projects 

Course Webpage 
CSE150
