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. 

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.1

    1, 5, 7, 9, 19 ,29, 41 Rosen 1.2

    3,7,13,27, 31, Rosen 1.7

    3, 7, 11, 15, Rosen 1.6

    1, 5, 11, 14, 17, 29, Rosen 1.8

    3, 9,17,23,27,35 -Rosen 1.4

  • 3, 9, 17, 21, 31, 63 – Rosen 1.3

  • 5, 9, 15, 23, 31 – Rosen 1.5

Supplemental Videos

[2] Sets, Functions and Sequences (4 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 determine if a given function is one to one, onto, bijective

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

2.E. 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 (4 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] Relations (4 Lectures)

4.A. Be able to explain the concept of relation

4.B. Be able to represent relations using graphic and matrix approaches

4.C. Be able to compute the result of operations on relations

4.D. Be able to determine relation properties (symmetric, reflexive, antisymmetric, transitive)

4.E*. Be able to compute closures of relations  (symmetric, reflexive, antisymmetric)

4.F*. Be able to explain equivalence relations and classes.
4.G. Be able to describe partially ordered sets.

4.H. Be able to explain total orders,

Practice Problems

  •  

Supplemental Videos

 

[5] Modeling Computation (5 Lectures)

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

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

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

5.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

[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