CS173: Discrete Structures
Tutorials and Study Problems

Tutorials

Many of our tutorial problems will be taken from this manual of discussion problems. Additional problems will be posted below, as needed. Answers to tutorial problems will be posted on Thursday nights. 

You will work with the people sitting near you; feel free to sit near the same people each week or to move around and meet new people.

Study problems

Each week, you should do the study problems listed below. You should write up a solution to each problem on your own, as if you were taking an exam or turning in a graded homework, before checking your answers against the posted solutions. Writing up the answers is important, since it forces you to work through the details and practice composing a polished proof.

As motivation, you will need to submit a typed answer to one study problem. These answers will be typed directly into a PrairieLearn editing window (not uploaded as pdf) so that you can get used to the editor before you have to use it on examlets. Although study problems come with answers, we're expecting to see your answer written in your own words. This will be graded for good-faith completion, not correctness. We'll give you some choice about which problem to write up, but we will exclude some easy warm-up problems.

When writing equations in PrairieLearn, it's often helpful to know some basic latex commands. Here is a brief guide

You may freely consult friends and/or course staff for help checking your answers and for hints if you get stuck. You can also post questions on piazza. However, significant pieces of solutions should be posted only privately to the course staff.

Additional practice problems, sample exams, etc may be found on the web pages for previous offerings of this course. There are differences from term to term and online exams are obviously a bit different from paper ones, but you'll find that the basic techniques and concepts are similar.

Schedule

This schedule is somewhat tentative: problems will be finalized around the start of each week. Study problems are due on the Monday after the related tutorial (i.e. at the same time as the autograded homework).

Week Topic Tutorial problems (do in class on Thursdays; no need to turn it in) Study problems (turn one in on PL as part of the HW)
Week 1 Prerequisites
+
Logic		 Get to know the rest of your team
Do this problem
Do problem 1.5 in the discussion manual

math prerequisites
logic

Turn in a logic problem, not a prerequisites problem
Week 2

Proofs
+
Number theory

 Do problems 1.2bc, 1.3d, 1.4a, 2.2ab, 2.3a,
and 2.4a in the discussion manual

proofs
number theory

Pick any problem other than number theory #1 or #6

Week 3

Modular arithmetic
+
Set theory

Do 2.1 in the discussion manual. For 2.1a, include at least two positive and two negative values.
Do these problems
Do 3.1, 3.2, and 3.3b in the discussion manual

modular arithmetic
set theory

Turn in set theory problem 2, 3, or 4
Week 4 Relations Do these problems

relations

Pick any problem
Week 5 Functions

Do discussion manual problems 5.1bd, 5.2, 5.4, 7.3, 7.5c
Do this sanity check for 7.5c
Do this problem

functions

Pick any problem
Week 6

Graphs
+
Two-way bounding

 Discussion manual problems (it looks like a lot but most are short): 
8.1a, 8.3b, 8.4, 8.5, 9.2b, 9.1b, 9.3a, 10.2d, 10.1b
Do this problem

graphs
two-way bounding

Pick any problem
Week 7 Induction

Do these discussion manual problems: 11.1bc
Do this problem
Do these discussion manual problems: 11.4, 11.2
Do this problem
easier induction
 
Pick any problem
Week 8 Recursive Definition Do these discussion manual problems: 12.1d, 12.2ac
Do this problem
Do discussion manual problem 12.3abcd
Do this problem

unrolling
induction

Pick any problem except induction #2 and the unrolling problem
Week 9

Trees
+
Grammars

Discussion manual problems: 13.3b, 13.2a, 13.4

tree induction

Turn in problem 1, 2, or 3
Week 10 Big-O
+
Algorithms		 Discussion manual problem 13.1ab
Do this big-O problem
Discussion manual problem 14.1ac

recursion trees
inequality induction

Pick any problem
Week 11 Algorithms
+
NP		 Discussion manual problems: 15.5, 15.3, 15.4, 15.4 supplement, 15.2

algorithms

Pick any problem
Week 12 Collections of Sets Discussion manual problems from section 17: 1a-e, 2a, 3abc, 4a-f, 5ae, 6ab
Do these problems

collections of sets

Turn in problem 1, 2, or 3
Week 13 Contradiction
State Diagrams

Discussion manual problems: 2.2a (using proof by contradiction), 16abc, 18.1, 18.2
Do this problem

contradiction
state diagrams

Pick any problem except state diagrams #1
Fall
Break		      
Week 14 Countability Discussion manual problems: 19.1, 19.2
Do this problem

countability

Pick any problem
Week 15 No new topic    

An AI-generated image based on the prompt below
"A room with dozens of tables and at each table students are working collaboratively on a math problem, impressionist style", by DALL-E (+Ben)