Skip to Main Content

Introduction to Discrete Structures

Computer Science Department

  CS 205 – Introduction to Discrete Structures I

All CS205 lectures follow a common set of topics. The order of topics coverage may vary based on the lecture/section you are attending. Please visit your section canvas page for more information about the lectures. Some topics (eg. induction) may take more lectures to cover than others. Click on each topic learning objectives to see an expanded list. Learning objectives are used to maintain consistency across all lectures. The exams (midterm, finals) will be designed around learning objectives.
:Lecture Slides/Outlines/Notes are available from  canvas page

Topics

Learning Objectives (LOs)

Resources 

[1] The Foundations of Logic and Proofs (6 Lectures)

1.A. Be able to explain how propositional logic can be applied to solving various statements that are either true or false 

1.B. Be able to apply the rules of propositional logic to solve application problems 

1.C. Be able to prove the equivalence of two or more propositional statements. 

1.D. Explain the ideas of predicates and quantifiers 

1.E. Be able to negotiate order of operations in nested quantifiers 

1.F. Be able to prove P implies Q directly 

1.G. Be able to prove P implies Q using contraposition 

1.H. Be able to prove P using contradiction 

1.I. Be able to prove P implies Q using cases 

1.J. Be able to select the appropriate technique to solve P implies Q

Practice Problems

  • Rosen Textbook Chapter 1

    3, 11, 15, 23, 35, Rosen 1.2

    9, 17, 27, 45, 47 , Rosen 1.5

    5,9,15,23, 31, Rosen 1.6

    3, 7, 11, 15, Rosen 1.7

    3, 7, 13, 27, 31, Rosen 1.8

    1, 5,11,14,17,29

Supplemental Videos

[2] Sets, Relations, Functions and Sequences (5 Lectures)

2.A. be able to explain the standard sets R, R+, Q, Z, Z+ and their properties.

2.B. be able to apply set operations and describe verbally what they mean.

2.C. be able to describe domain, range, and properties of a function.

2.D. be able to define and analyze relations between sets and composition of relations.

2.E. be able to derive and sum sequences and prove the sum of finite and infinite sequences using induction.

2.F. be able to describe cardinality of sets and differentiate finite, countable, and uncountable sets, and their properties.

Practice Problems

  • Rosen Textbook Chapter 2 

    Rosen 2.1-2.3

  • (2.1) 3,9,19,25,27,43 

  • (2.2)3,13,19,29,53

  • (2.3) 1, 3, 7, 15, 21, 51

  • (2.4) 5, 9, 11, 19, 23, 31, 33

  • (2.5) 1, 3, 11, 19

Supplemental Videos

[3] Induction (5 Lectures)

3.A. Be able to identify problems that is better suited for inductive proofs

3.B. Be able to explain the similarities and differences between induction and recursion

3.C. Be able to formulate base step and inductive step of a proof by induction

3.D. Explain why mathematical induction is valid

3.E. Identify proofs where induction arguments are incorrectly applied

3.F. Be able to properly argue that P(n) implies P(n+1)

3.G. Explain situations where strong induction is a better approach

  • Practice Problems

    • Rosen Textbook Chapter 5 

    • (5.1) 3, 5, 7, 11

      15, 19, 21, 31, 41, 51

    • (5.2) 3, 5, 7, 11, 25, 29, 33

    • (5.5) 11,3,7,13

    • (2.4) 5, 9, 11, 19, 23, 31, 33

    • (2.5) 1, 3, 11, 19

Supplemental Videos

[4] Modeling Computation (5 Lectures)

4.A. Be able derive language sentences from rules of grammar

4.B. Be able to build a FSM from given specification

4.C. Be able to trace output from FSM and identify what the machine does.

4.D*. Be able to build a Turing Machine (TM) from specifications.

Practice Problems

  • Rosen Textbook Chapter 13

  • (13.1) 1, 3, 7, 13, 17, 23

  • (13.2) 1, 3, 5, 7

  • (13.3) 11, 19, 23, 29, 33, 49

  • (13.5)  1, 3, 7, 9, 11

Supplemental Videos

[5] Boolean Functions (2 Lectures)

5.A. Be able to derive Boolean functions from truth tables

5.B. Be able to build a truth table from a given Boolean function

5.C. Be able to derive sum-of-product representation of multi-variable Boolean functions from given specifications

5.D. Be able to prove that a set of Boolean operations is functionally complete

5.E*. Be able to design a logic gate design to implement a Boolean function.

5.F*. Be able to apply Boolean function properties to reduce circuits into simpler ones

Practice Problems

  • Rosen Textbook  Chapter 12
  • (12.1) – 1, 5, 25, 35
  • (12.2) – 1, 3, 13

Supplemental Videos

[6] Number Theory (3 Lectures)

6.A. Be able to apply the properties of divisibility to solve modular arithmetic problems.

6.B. Be able to convert across different bases

6.C. Be able to identify the properties of prime numbers and their applications.

6.D* Be able to derive private and public keys using two large primes

6.E*. be able to demonstrate the encryption and decryption process using public/private keys

Practice Problems

  • Rosen Textbook Chapter 4
  • (4.1) 1, 7, 11, 13, 17, 29
  • (4.2) 3, 9, 17, 21, 27, 31
  • (4.3) 3, 17, 19, 23, 33
  • (4.6) 1, 3, 5, 7

Supplemental Videos