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 not be posted. If you miss tutorial, feel free to consult with friends and staff.

Tutorial groups will be assigned randomly and stay stable for the whole term. If your group is working out badly, please contact your instructor.

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 moodle 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 moodle, 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: tutorial problems will appear and study problems will be finalized around the start of each week. Study problems are due on the Saturday at the end of each week.


 
Week Topic Study Problems Tutorial problems Comments
Week 1 Prerequisites and Logic math prerequisites
logic
Get to know the rest of your team
Do problem 1.5 in the discussion manual
Do this problem
Turn in a logic problem, not a prerequisites problem.
Week 2 Proofs
Number theory
proofs
number theory
Do problems 1.2bc, 1.3d, 1.4a, 2.2ab, 2.3a, and 2.4a in the discussion manual. Don't worry if you don't finish - treat the rest as extra study problems (but don't turn them in)
 
Turn in one of the proof problems. Do not turn in problem 1 or 6 in the number theory problems.
When writing up a study problem on moodle, indicate clearly which problem you are solving. That is, which topic section of the study problems and which problem number, e.g. "number theory 3".
Week 3 Modular arithmetic
Set theory
modular arithmetic
set theory

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

Turn set theory problem 2, 3, or 4
Week 4 Relations relations Do these problems any relations problem
Week 5 Functions functions Do discussion manual problems 5.1bd, 5.2, 5.4, 7.3, 7.5c
Do this problem
any functions problem
Week 6 Graphs
Two-way bounding
graphs
two-way bounding

Do these discussion manual problems (it looks like a lot but most are much shorter problems than usual): 8.1a, 8.3b, 8.4, 8.5, 9.1b, 9.2bc, 9.3a, 10.2d, 10.1b
Do this problem

Turn in any graphs or two-way bounding problem
Week 7 Induction easy induction

Do these discussion manual problems: 11.1bcd, 11.2, 11.4
In this other textbook, do problem 5.16acdefh. (it's on p170 of the pdf, p162 by printed numbers)
Do this problem

Turn in either induction problem
Week 8 Recursive Definition unrolling
induction

Do these discussion manual problems: 12.1d, 12.2ac
Do this problem
Do discussion manual problem 12.3abcd
Do this problem

Turn in an induction problem other than problem 2 (so NOT induction #2 and NOT the unrolling problem)
Week 9 Trees, Grammars tree induction Do these discussion manual problems: 13.3b, 13.2a, 13.4 Turn in tree induction problem 1, 2, or 3.
Week 10 Big-O
Algorithms
recursion trees
inequality induction

Do these discussion manual problems: 13.1ab, 14.1ac
Do these big-O problems

Turn in a recursion tree or inequality induction problem
Week 11 Algorithms
NP
algorithms Do these discussion manual problems: 15.5, 15.3, 15.2, 15.4 Turn in either algorithms study problem.
Week 12 Collections of Sets collections of sets Do these discussion manual problems from section 17: 1a-e, 2a, 3abc, 4a-f, 5ae, 6ab
Do these problems
Turn in Collections of Sets problem 1, 2, or 3
Week 13 Contradiction
State Diagrams
contradiction
state diagrams

Do these discussion manual problems: 2.2a (justify your answer using proof by contradiction), 16abc, 18.1, 18.2
Do this problem

Do not turn in State Diagram problem 1.
Week 14 State Diagrams
Countability
countability Do these discussion manual problems: 19.1, 19.2
Do this problem
Turn in either countability problem.