CS173: Discrete Structures
Spring 2019, Margaret Fleck
Examinations


Final Exam information

The final exam is Thurday May 9th, 1:30-4:30pm. Room assignments are based on the first letter of your last name:

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 copies of 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, 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.

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