CS173: Discrete Structures
Spring 2019, David Varodayan
Examinations
Final Exam information
The final exam is Wednesday May 8th, 8-11am. Room assignments are based on your discussion:
- 1404 Siebel: sections BDA, BDB, BDC (11am, noon, 1pm)
- 1320 DCL: sections BDD, BDE, BDF (2pm, 3pm, 4pm)
If you wish to retake one of examlets 1-11 (capped at 80%),
please fill out
this form.
The deadline for submitting the form is midnight Sunday (so we have time to xerox the right number of copiesof each retake examlet).
We will start with the 4-page final (i.e. examlet 13 plus review).
You will have an hour to do it.
After that, we'll do makeups for (examlets 11 and 12) and retakes.
Basic examlet instructions
Weekly examlets will be given in class on Thursdays at 11:00, 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
|
#1: Prerequisites and Logic |
Jan 31 |
Chapters 1 and 2 excluding 1.5-1.6 |
Examlet 1 |
math prerequisites
logic
|
colored sheet
white sheet
|
colored sheet
white sheet
|
#2: Number theory |
Feb 7 |
Chapters 3 and 4 excluding 4.12-4.14 |
Examlet 2 |
proofs
number theory
|
colored sheet
white sheet
|
colored sheet
white sheet
|
#3: Modular arithmetic Set theory |
Feb 14 |
4.12-4.14, Chapter 5 |
Examlet 3 |
modular arithmetic
set theory
|
colored sheet
white sheet
|
colored sheet
white sheet
|
#4: Relations |
Feb 21 |
Chapter 6 |
Examlet 4 |
relations
|
colored sheet
white sheet
|
colored sheet
white sheet
|
#5: Functions |
Feb 28 |
Chapters 7 and 8 |
Examlet 5 |
functions
|
colored sheet
white sheet
|
colored sheet
white sheet
|
#6: Graphs |
Mar 7 |
Chapter 9 |
Examlet 6 |
graphs
|
colored sheet
white sheet
|
colored sheet
white sheet
|
#7: Two-way bounding Easy Induction |
Mar 14 |
1.5, Chapter 10, 11.1-11.7 |
Examlet 7 |
two-way bounding
easy induction
|
colored sheet
white sheet
|
colored sheet
white sheet
|
#8: Induction Recursive Definition |
Mar 28 |
Chapters 11 and 12 |
Examlet 8 |
unrolling
induction
|
colored sheet
white sheet
|
colored sheet
white sheet
|
#9: Trees, Grammars |
Apr 4 |
1.6, Chapter 13 excluding 13.6, 13.7 |
Examlet 9 |
tree induction
|
colored sheet
white sheet
|
colored sheet
white sheet
|
#10: Big-O Recursion Trees |
Apr 11 |
13.6, 13.7, Chapter 14 |
Examlet 10 |
recursion trees
inequality induction
|
colored sheet
white sheet
|
colored sheet
white sheet
|
#11: Algorithms, NP |
Apr 18 |
Chapters 15, 16 |
Examlet 11 |
algorithms
|
colored sheet
white sheet
|
colored sheet
white sheet
|
#12: Contradiction Collections of Sets |
Apr 25 |
Chapters 17, 18 |
Examlet 12 |
contradiction
collections of sets
|
colored sheet
white sheet
|
colored sheet
white sheet
|
Final: State Diagrams Countability |
Wednesday May 8, 8-11am |
Chapters 19, 20 |
Final examlet |
state diagrams
countability
|
final |
final |