uoft aristotle boole goedel frege cantor turing

CSC165: Mathematical Expression and Reasoning for Computer Science (Summer 2014)

Announcements

(Aug. 27) Exam marks (broken down by question) are up on Portal, and marks are up on ROSI. The exam paper is here. The average on the exam was 67/100. For the people who wrote the exam, the average mark for the course was 72.9. For people who didn't write the exam, the exam grade was entered as 0, since that is the Faculty rule. If you haven't written the exam, contact your registrar ASAP if you haven't already done so. The raw final marks were calculated according to the marking scheme, and marks were recalculated for people who missed the midterm etc. Please let me know by email if I missed anything there. Exam regrading requests go through the Faculty of Arts and Science.

(Aug. 20) Q6 from the exam + goodbye

(Aug. 18) Aug 18 office hours are in 1-3 in the Help Centre

(Aug. 10) By popular request, A6 is now due at 2PM on Tuesday

(Aug. 9) Additional office hours: Monday Aug 12 1-3 in the Help Centre, Tuesday after lecture as usual, Wednesday 1-3, 6-7 in the Help Centre, Friday 1-3 in the Help Centre, Monday Aug 18 1-3 in BA4237 the Help Centre

(Aug, 7) Final Exam information

(Aug. 7) More hints/summaries of office-hour discussions posted on the message board

(Aug. 5) Extra office hours this week: Thursday 1-4, Friday 1-4

(Aug. 5) Some hints/FAQ for A6 were posted in the course forum

(Aug. 1) The solutions for A5 have now been posted

(Jul. 29) Note: for Q4, you can't use gcd(), or anything else from the fractions module, since that would defeat the point of the question

(Jul. 29) Assignment 6 is up! It includes a bonus question (to be submitted separately), which means that you can earn up to 112.5% on the assignment. I've postponed the due date to Aug. 12 at 12:01 PM to avoid conflicts with due dates for other courses. I cannot accepts late assignments after that deadline since classes end on Aug. 12 (documented medical/personal circumstances excepted). Note: Q4 was updated shortly after posting and now has two subquestions.

(Jul. 22) Sorry if anyone showed up for office hours after 6:30 and didn't find me -- I didn't feel well and had to leave. Extra office hours: Thursday 1-4 in BA4273.

(Jul. 20) A4 marks are out! The average for the assignments was about 70%.

(Jul. 20) The wording for A3 in A5 was tweaked a little to make it clearer

(Jul. 19) A primer on inequalities is now available under the lecture notes for Jul. 15/16.

(Jul. 17) A5 has been updated.

(Jul. 16) Accessibility Services is looking for a volunteer notetaker (also see here).

(Jul. 15) The exam timetable is up. Reminder: the drop deadline is on Jul. 20.

(Jul. 15) The first several question for A5 are posted. More to come

(Jul. 15) Midterm solutions are posted below. If you disagree with the midterm grading, please submit a clearly-written remarking request, indicating precisely where you think the marking error is and why it is an error. As always, I reserve the right to reamrk the entire midterm paper.

(Jul. 14) The midterm grades are now on Portal. The average was 64/90 (i.e., 71/100). I'll return the midterm papers tomorrow.

(Jul. 11) A5 partner search

(Jul. 7) I will draw a "V" on the board tomorrow if this team wins after 6pm, and I will draw an "X" if the other team wins (don't look if you don't want to)

(Jul. 7) Midterm format: about 4 full detailed structured proofs (similar in style to what you saw on A3 and A4 and in lecture) and about 7 short-answer questions. This formula sheet will be handed out.

(Jul. 2) A common issue I see in the assignments; a list of common mistakes in CSC165

(Jun. 21) The midterm will be held on July 9 from 6:10pm to 9:00pm in EX100. Problems related to anything that we've done in the course might potentially appear on the midterm. Topics mentioned briefly and not covered in the notes (e.g., the Tit-for-Tat strategy, the Hangman Paradox, etc.) might appear on the midterm, but any definitions you need will be given on the midterm. The list of standard logical equivalences (Section 2.17) and the list of inference rules (Section 3.15) will be provided. You may be required to write detailed structured proofs. The problems on the midterm will be similar to the problems that we solved in class and in the assignments. There will probably be one "Google interview-style" problem, similar in style to what we did in the problem sessions. Previous terms' offerings of CSC165 are linked at the bottom of the page. There are plenty of practice problems to solve there, and solving them (not just looking at the solutions) is the best way to prepare for the midterm.

Course information sheet

Summer 2014 course information sheet

Instructor

Michael Guerzhoy. Office: BA4237 (sometimes), Email: guerzhoy at cs.toronto.edu (please include CSC165 in the subject, and please ask questions on the course forum if they are relevant to everyone.)

Getting help

Michael's office hours: Tuesday 6-7 (or until everyone leaves) in BA2230; Wedesnday 1-3 in BA4237; or by appointment.

CS Help Centre hours: Monday-Thursday from 4pm to 6pm in in BA2230.

Course forum

Lectures

Tuesdays 4-6 (BA1170), Wednesdays 6-9 (BA1190)

Course notes

We will be generally (but not always) following the CSC165 course notes.

Evaluation

40%: Six assignments
15%: A three-hour midterm
45%: A final exam

You must receive at least 40% on the final exam to pass the course.

Midterm

Midterm paper; solutions. codes for q4

Assignments

The assignments will be submitted and graded using MarkUs. You should be able to login to MarkUs starting May 16th.

The assignments are to be done by each student or team alone. Any discussion of the assignments with other students should be about general issues only, and should not involve giving or receiving written, typed, or emailed notes. Please refer to François Pitt's Guidelines for Avoiding Plagiarism.

Assignment 1: handout (worth 3%, due on May 23 at 2:00 pm), LaTeX source. Solutions, LaTeX source.
Assignment 2: handout (worth 5%, due on Jun 6 at 2:00 pm), LaTeX source. Solutions, LaTeX source.
Assignment 3: handout (worth 8%, due on Jun 20 at 2:00 pm), LaTeX source. Solutions, LaTeX source. Preliminary marking instructions.
Assignment 4: handout (worth 8%, due on Jul 4 at 2:00 pm), LaTeX source. Solutions, LaTeX source
Assignment 5: handout (worth 8%, due on Jul 25 at 2:00 pm), LaTeX source. Solutions, LaTeX source, Python code
Assignment 6: handout (worth 8%, due on Aug 12 at 2:00 pm), LaTeX source. Solutions, LaTeX source, a6.py, a6b.py
.

Lecture notes

May 13: Introductory slides; the square root of 2 is irrational; sets of numbers: Section 1.5 in the notes; there are infinitely many primes: see Section 3.6 in the notes; we started talking about LaTeX

May 14: The Three Logicians comic; the coins puzzle (think about it before Tuesday!); LaTeX: we saw how to use WriteLaTeX; some examples of tables and lists in LaTeX; sets and Venn Diagrams: see this tutorial; Donald Knuth; logical notation: Sections 2.1-2.4, some stuff from Section 2.5, Section 2.7; affirming the consquent; formal fallacies in general.

May 20: Sheldon Cooper on the fallacy of affirming the consequent; Lisa Simpson on the fallacy of affirming the consequent; the coins puzzle, with a story and a link to the solution; we've now covered everything up to Section 2.9 in the notes.

May 21: The Venn Diagram cartoon; we've now covered everything up to Section 2.12 in the notes; Shermanesque statements; Tutorial 1 (solutions); Tutorial 2 (solutions)

May 27: The Hangman Paradox; (we also briefly discussed the Liar Paradox and Venus, the Morning Star, and the Evening Star, but you're not responsible for that material); we covered equivalence (Section 2.8) in more depth and went in detail over examples from Section 2.12; we covered the solutions of Tutorial 2.

May 28: Lather, rinse, repeat; checking whether a statement about databases is true using Python: check_truth.py (108 students: we will cover this in more details later in the course; people who have taken 108: you should be able to understand everything there except perhaps the class definition); we covered Sections 2.13-2.15, plus some of 2.16 (De Morgan's laws); pleonasms on tvtropes; we briefly discussed how logical AND and logical OR are similar to addition and multiplication; there are more details e.g. here; we discussed the solutions for Tutorial 1.

Jun. 3: We proved that 7/2 is not natural; we started talking about proofs; Modus Ponens and Modus Tollens: details here; optional reading: What the Tortoise said to Achilles by Lewis Carroll; we covered 2.13-2.15 in more detail: proofs of equivalences, proofs of satisfiability, proofs of unsatisfiability, proofs of tautologies; proofs of equivalences using transformations of expressions; we started looking at 2.17.

Jun. 4: Problem session: the Pirates problem (SPOILER ALERT: be careful, the solution is included below the problem); after you get the solution, check out a 165 student's awesome illustration; sample proofs (LaTeX source); Sections 2.18-2.19 in the notes; Tutorial 3 (solutions, to be discussed on Tuesday)

Jun. 10: Prisoner's dilemma; the Tit-for-Tat strategy; we covered Tutorial 3 (note that I gave different solutions than what's in the solutions handout); how to win at Rock Paper Scissors (just for fun, mentioned only briefly); computer Rock Paper Scissors tournament at the U. of Alberta, with sample code (again, just for fun); Section 3.3 (please also read Sections 3.1-3.2)

Jun. 11: Sections 3.4-3.7; proof that there is an infinite number of even numbers: {0, 2, 4, 6, 8, ...} is an infinite set (since there we implictly gave a recipe for generating an infinite number of evens; (just for fun: a recipe that sometimes works for generating prime numbers, The Great Internet Mersenne Prime Search ; Fermat's Last Theorem); Tutorial 4 (solutions)

Jun. 17: Problem session: the reunion problem (SPOILER ALERT solution to be discussed tomorrow); Tutorial 5 (solutions, we'll finish discussing them tomorrow)

Jun. 18: Jean Chretien on proofs; Sections 3.8-3.10; Section 3.13; some additional material

Break week youtube viewing (just for fun): Vi Hart's video on how the Pythagoreans could prove that √ 2  is irrational without using algebra. Also: an excerpt from Plato's Theaetetus, where the theorem is stated.

Jul. 2: Russell's paradox: why there's no such thing as a set of sets; things Bertrand Russell said; we went over Assignment 3; a few examples that are not in the notes; Sections 3.14-3.15; derivation of the quadratic formula; just for fun: you can use a soccer ball to signify the end of your proof using this line: \hspace*{13cm}\includegraphics[height=0.5cm]{soccer2} if you upload soccer2.pdf to wherever you're compiling your TeX file

Jul. 8: Cargo cult programming (Cargo cult science; we went over common proof errors: see also the announcment from Jul. 2; the Feynman problem-solving algorithm; an example of a bad application of the Law of Excluded Middle: "All that is not prose is verse; and all that is not verse is prose"; induction examples (LaTeX source), also see Section 4.15; (suggested reading: pp. 9-14 here); all integers are interesting

Jul. 15, 16: Section 4.3-4.7; read 4.11, though we will not be doing things at that level of formality; Section 4.15; primes.py, seating.py, bin_search.py, bubble_sort.py, bozo_sort.py; we'll be doing more big-Oh next week; a primer on inequalities (source)

Jul 23, 23: Just for fun: How (not) to prove it; Section 4.7, 4.9, 4.10; Tutorial 6 (solutions)

Jul. 29: Section 5.4; just for fun: Vi Hart on the same subject (we did everything up to 4min10sec)

Jul. 30: Problem session: the Two Eggs problem (SOLUTION SPOILERS WITHIN) (a famous Microsoft interview question); the subsection "Cantor's Proof" from Section 5.5; just for fun: the rest of the Vi Hart video; just for fun: is there a set that's larger than N but smaller than R? it's complicated; Q: is there a set that's larger than R? A: Yes, for example, the set of all the functions from R to R; Q: what's a practical application of all this stuff A1: you can tell it to people in pubs and get them to buy you a drink A2: it's a bit complicated, since if the physical world is not continuous, you won't see a lot of real numbers around. Still, you might say that if you pick a real number at random, it will be irrational with probability 1 because there are more reals than rationals (you decide if that's practical); aside: what's the largest number that you can write down? (search for "Unfortunately it doesn’t work"); aside: the set of all the numbers that you can write down is countable, since you can just list the alphabetically/lexicographically. That means you can't write down most real numbers.

Aug. 5: Just for fun: some quines in Python: quine.py; from an anonymous student: DogeSharp (trying writing a quine in DogeSharp!); Section 5.1-5.2; if you could write halt(), you could easily prove Fermat's Last Theorem; just for fun: Gödel's Incompleteness Theorem (look for "As I said, once you have Turing's results"); Does Gödel Matter? by Jordan Ellenberg (Math professor at U. of Wisconsin) (note: this is somewhat controversial and Jordan Ellenberg's opinion is not the only one; people in Computer Science are generally more excited about Gödel); we went over some questions from A5

Aug. 6: Section 5.3; Alan Turing (I forgot to mention to Alan Turing is also one of the first people to start thinking about artificial intelligence; he proposed the Turing Test to determine whether a machine is intelligent); Tutorial 7: additional proof examples (we covered the first two proofs).

Weekend youtube viewing: (just for fun) Vi Hart on Fibonacci numbers; also, some students wanted to implement Euclid's Algorithm for Q4 (I'm not recommending that, though), and its worst-case runtime actually also has to do with Fibonacci numbers!

Aug. 12: Don't assume what you're trying to prove; we went over the solutions to A6 (see Solutions section); what next: you should now be prepared for CSC236; if you liked proofs, consider MAT157; in my experience, people talk about it for decades after having taken it; if you like CS theory, plan to take CSC463, preferably with Stephen Cook; if you liked this class and did well in it, think about CSC240/CSC265/CSC375; if you liked the connection between language and logic, try Philosophy of Language PHL351H1 (disclaimer: I sat in on it but never took it); thanks everyone for a great term, and good luck on the exam!

LaTeX

Web-based LaTeX interfaces: WriteLaTeX, ShareLaTeX

TeXworks, a cross-platform LaTeX front-end. To use it, install MikTeX on Windows and MacTeX on Mac

Detexify2 - LaTeX symbol classifier

The LaTeX Wikibook.

Additional LaTeX Documentation, from the home page of the LaTeX Project.

LaTeX on Wikipedia.

MarkUs

All project submission will be done electronically, using the MarkUs system. You can log in to MarkUs using your CDF login and password.

To submit as a group, one of you needs to "invite" the other to be partners, and then the other student needs to accept the invitation. To invite a partner, navigate to the appropriate Assignment page, find "Group Information", and click on "Invite". You will be prompted for the other student's CDF user name; enter it. To accept an invitation, find "Group Information" on the Assignment page, find the invitation listed there, and click on "Join". Only one student must invite the other: if both students send an invitation, then neither of you will be able to accept the other's invitation. So make sure to agree beforehand on who will send the invitation! Also, remember that, when working in a group, only one person must submit solutions.

To submit your work, again navigate to the appropriate Exercise or Assignment page, then click on the "Submissions" tab near the top. Click "Add a New File" and either type a file name or use the "Browse" button to choose one. Then click "Submit". You can submit a new version of any file at any time (though the lateness penalty applies if you submit after the deadline) — look in the "Replace" column. For the purposes of determining the lateness penalty, the submission time is considered to be the time of your latest submission.

Once you have submitted, click on the file's name to check that you have submitted the correct version.

Policy on special consideration

Special consideration will be given in cases of documented and serious medical and personal cirumstances.

Feedback

You can send me anonymous feedback at this link.

Links (not required reading/viewing)

Dara Ó Briain: School of Hard Sums: a British show with comedians doing problem solving.

Quantum Computing Since Democritus: course notes (and now a book) for a course on computability, complexity, and quantum computing given by Scott Aaronson (then a post-doc at the Perimeter Institute at Waterloo, now an MIT prof) at Waterloo. In CSC165, we touch on a few of the topics covered in Lectures 2 and 3 of Aaronson's course. The course is more advanced than CSC165 (in fact, some parts of the course are more advanced than CSC463), but parts of it are fairly accessible, and I recommend taking a look at the first few lectures if you're interested.

Web pages of past offerings of the course

CSC 165 (Winter 2014)
CSC 165 (Fall 2013)
CSC 165 (Summer 2013)
CSC 165 (Winter 2013)
CSC 165 (Fall 2012)
CSC 165 (Summer 2012)

Valid HTML 4.01 Transitional