CS173: Discrete Structures
Summer 2019, G. Carl Evans
Examinations

Basic examlet instructions

Weekly examlets will be given in class on Monday and Wednesday, starting in the second week of classes.

The table below shows which time each group should report.

Before the first examlet, you must read the exam instructions and the exam logistics information. These instructions will NOT be reprinted with each examlet.

The listed chapters and skills are the new skills for each examlet. The examlet will focus on these new skills. However, be aware that you're still expected to remember concepts from earlier in the term.

Study problems should be done before the corresponding examlet. You do not need to turn in your solutions. Write up your answers, as if you planned to turn them in. Then check your work against the annotated solutions. Actually writing up the answers is important, since it forces you to work through the details and practice composing a polished proof.

Additional practice problems may be found on the Exams section of the web pages for previous offeringsn of this course.

You are encouraged to compare study problem solutions with your classmates, bring them into office hours to consult with course staff, etc. High-level discussion on Piazza is ok, as is discussion of very specific issues and possible bugs. However, significant pieces of solutions should be posted only privately to the course staff.

The information (e.g. skills list, study problem) for each examlet should be viewed as tentative until a week before the examlet date. We don't expect large changes but there might be small ones.


 
Examlet Date Textbook sections Skills list Study Problems Examlet Solutions
#1: Prerequisites and Logic 17 Jun Chapters 1 and 2
excluding 1.5-1.6
Examlet 1 math prerequisites
logic
full examlet full examlet
#2: Number theory 19 Jun Chapters 3 and 4
excluding 4.12-4.14
Examlet 2 proofs
number theory
full examlet full examlet
#3: Modular arithmetic
Set theory
24 Jun 4.12-4.14, Chapter 5 Examlet 3 modular arithmetic
set theory
full examlet full examlet
#4: Relations 26 Jun Chapter 6 Examlet 4 relations full examlet full examlet
#5: Functions 1 Jul Chapters 7 and 8 Examlet 5 functions full examlet full examlet
#6: Graphs 8 Jul Chapter 9 Examlet 6 graphs full examlet full examlet
#7: Two-way bounding
Easy Induction
10 Jul 1.5, Chapter 10, 11.1-11.7 Examlet 7 two-way bounding
easy induction
full examlet full examlet
#8: Induction
Recursive Definition
15 Jul Chapters 11 and 12 Examlet 8 unrolling
induction
full examlet full examlet
#9: Trees, Grammars 17 Jul 1.6, Chapter 13
excluding 13.6, 13.7
Examlet 9 tree induction full examlet full examlet
#10: Big-O
Recursion Trees
22 Jul 13.6, 13.7, Chapter 14 Examlet 10 recursion trees
inequality induction
full examlet full examlet
#11: Algorithms, NP 24 Jul Chapters 15, 16 Examlet 11 algorithms full examlet full examlet
#12: Contradiction
Collections of Sets
29 Jul Chapters 17, 18 Examlet 12 contradiction
collections of sets
full examlet full examlet
Final: State Diagrams
Countability
Friday
2 Aug
3:30-5:30pm
Chapters 19, 20 Final examlet state diagrams
countability
final final