CS173: Discrete Structures
Spring 2020, Yael Gertner
Examinations


Basic examlet instructions


Weekly examlets will be given in class on Thursdays, starting in the third week of classes.

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 offerings 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 DRES/makeup Solutions
#1: Prerequisites and Logic 6 Feb Chapters 1 and 2
excluding 1.5-1.6
Examlet 1 math prerequisites
logic
colored
white
colored
white
DRES
makeups
#2: Number theory 13 Feb Chapters 3 and 4
excluding 4.12-4.14
Examlet 2 proofs
number theory
colored
white
colored
white
DRES
makeups
#3: Modular arithmetic
Set theory
20 Feb 4.12-4.14, Chapter 5 Examlet 3 modular arithmetic
set theory
colored
white
colored
white
DRES
makeups
#4: Relations 27 Feb Chapter 6 Examlet 4 relations colored
white
colored
white
DRES
on time makeups
#5: Functions 5 Mar Chapters 7 and 8 Examlet 5 functions colored
white
colored
white
DRES
#6: Graphs 12 Mar Chapter 9 Examlet 6 graphs This examlet was cancelled in the Great Shutdown
#7: Two-way bounding
Easy Induction
26 Mar 1.5, Chapter 10, 11.1-11.7 Examlet 7 two-way bounding
easy induction
This examlet was a mixture of examlet 6 and 7 content long proof solutions
#8: Induction
Recursive Definition
2 Apr Chapters 11 and 12 Examlet 8 unrolling
induction
This examlet contained some examlet 7 content. long proof solutions
#9: Trees, Grammars 9 Apr 1.6, Chapter 13
excluding 13.6, 13.7
Examlet 9 tree induction Grammar inductions moved to examlet 10. long proof solutions
#10: Big-O
Recursion Trees
16 Apr 13.6, 13.7, Chapter 14 Examlet 10 recursion trees
inequality induction
Proofs were grammar inductions plus easily-formatted inequality inductions. long proof solutions
#11: Algorithms, NP 23 Apr Chapters 15, 16 Examlet 11 algorithms Exam was entirely autograded. Answers should be visible on moodle.
#12: Contradiction
Collections of Sets
30 Apr Chapters 17, 18 Examlet 12 contradiction
collections of sets
long proof solutions
Final: State Diagrams
Countability
Friday May 8
7pm to 10pm
Chapters 19, 20 Final examlet state diagrams
countability