ICS 254: Discrete Structures II

​

ICS 254: Discrete Structures II

 
Course Information
Class/Laboratory Schedule: 

Class/Laboratory Schedule: Three 50 minutes lectures per week. No lab (3-0-3)

Designation: 
 Required Course
Course Level: 
 Undergraduate
Prerequisites
Prerequisite(s) by Topic: 
  • Functions, Relations and Sets
  • Proof Techniques
  • Counting Techniques
Prerequisite Courses: 
ICS 253: Discrete Structures I
Catalog Description: 

Number Theory: Modular Arithmetic, Integer Representation, Fermat’s Little Theorem. Chinese Remainder Theorem, RSA., Applications from Number Theory; Recursive Definitions; Algorithm Correctness; Relations: Closures and Equivalence Relations, Partial Orderings and Lattices, Hasse Diagrams; Automata Theory: Finite State Machines, Regular Expressions, DFA, NFA and their equivalence, Grammars and Chomsky Hierarchy; Abstract Algebra: Groups, Homomorphism and Lagrange's Theorem, Applications.

Textbook(s): 

K. H. Rosen, Discrete Mathematics and Its Applications, 6th Ed., McGraw-Hill, 2007​.

Reference(s) and Other Material: 
  • N. L. Biggs, Discrete Mathematics (revised edition), Clarendon Press, 1989.
  • Crisler, N., Fisher, P. and Froelich, Discrete Mathematics through Applications, 2nd Ed., W. H. Freeman Co., 2000.
  • R. P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 4th Ed., Addison Wesley, 1998.
Course Outcomes: 
  • Explain basic concepts in number theory and apply them in problem-solving.
  • Understand relations and their graphical representation
  • Understand foundational knowledge of group theory and automata theory
Topics Covered: 
  • Number Theory
  • Induction & Recursion
  • Relations
  • Group Theory
  • Languages, Grammars and Finite State Machines​