CS173: Discrete Structures
Fall 2017, Margaret Fleck
Examinations

Remember to bring your ID to the final. Process for final exams:

When we call time on the main exam, a line often forms to turn it in and get the retakes. Do not worry about the delay. The deadline for the retake exam is 30 minutes after we've gotten rid of the line.


The final exam is 1:30-3:30 on Friday the 15th. It will be in two rooms, assigned as follows:

Please go to the correct room, as we have almost no spare seats.

At the final exam, you can optionally retake one examlet (for a score up to 24/30 aka 80%). Make your selection on this form no later than 6am on Thursday the 14th. (Or, said another way, before you go to bed on Wednesday.) Examlet 12 grades will be in moodle by about noon on Wednesday.


If you missed an examlet and have not yet made it up, makeups will be held the morning of Thursday the 14th (Reading Day) in 0216 Siebel. Please come at the following times:

If you need to make up more than one examlet, you should come at 9:30 and stay correspondingly longer.

If this cannot work for you, e.g. you have a conflicting course presentation, email the details to Margaret right away.


Weekly examlets will be given in class on Thursdays, starting in the third week of classes. There will be two sittings of each exam, one at 9:30 and one at 10:10. The class is divided into two groups, based on the first letter of your last name.

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.

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 9:30 sitting Examlet Solutions
#1: Prerequisites and Logic 14 Sept Chapters 1 and 2
excluding 1.5-1.6
Examlet 1 math prerequisites
logic
Group 1 A sheet
B sheet
A sheet
B sheet
#2: Number theory 21 Sept Chapters 3 and 4
excluding 4.12-4.14
Examlet 2 proofs
number theory
Group 1 A sheet
B sheet
A sheet
B sheet
#3: Modular arithmetic
Set theory
28 Sept 4.12-4.14, Chapter 5 Examlet 3 modular arithmetic
set theory
Group 1 A sheet
B sheet
A sheet
B sheet
#4: Relations 5 Oct Chapter 6 Examlet 4 relations Group 1 A sheet
B sheet
A sheet
B sheet
#5: Functions 12 Oct Chapters 7 and 8 Examlet 5 functions Group 1 A sheet
B sheet
A sheet
B sheet
#6: Graphs 19 Oct Chapter 9 Examlet 6 graphs Group 1 A sheet
B sheet
A sheet
B sheet
#7: Two-way bounding
Easy Induction
26 Oct 1.5, Chapter 10, 11.1-11.7 Examlet 7 two-way bounding
easy induction
Group 2 A sheet
B sheet
A sheet
B sheet
#8: Induction
Recursive Definition
2 Nov Chapters 11 and 12 Examlet 8 unrolling
induction
Group 2 A sheet
B sheet
A sheet
B sheet
#9: Trees, Grammars 9 Nov 1.6, Chapter 13
excluding 13.6, 13.7
Examlet 9 tree induction Group 2 A sheet
B sheet
A sheet
B sheet
#10: Big-O
Recursion Trees
16 Nov 13.6, 13.7, Chapter 14 Examlet 10 recursion trees
inequality induction
Group 2 A sheet
B sheet
A sheet
B sheet
#11: Algorithms, NP 30 Nov Chapters 15, 16 Examlet 11 algorithms Group 2 A sheet
B sheet
A sheet
B sheet
#12: Contradiction
Collections of Sets
7 Dec Chapters 17, 18 Examlet 12 contradiction
collections of sets
Group 2 A sheet
B sheet
A sheet
B sheet
Final: State Diagrams
Countability
Friday
15 Dec
1:30-3:30pm
Chapters 19, 20 Final examlet state diagrams
countability
N/A version 1
version 2
version 1
version 2