Fall 2017 Course (Fri, 17 Mar 2017)

This is the preserved website for the Fall 2016 course.

cs2102 will be offered again in Fall 2017, co-taught by Mohammad Mahmoody and David Evans. For the Fall 2017 course site, see https://uvacs2102.github.io/.

Some things about the course are likely to change substantially for Fall 2017, but you can see what was done in the Fall 2016 course here.

Final Exam Solutions (Thu, 15 Dec 2016)

The solutions to Final Exam are here: Final Exam Solutions. (I promise, no Harambe mentions, other than in quotes.)

Problem Set Omega Highlights (Wed, 14 Dec 2016)

Here are some interesting submissions for Problem Set Omega (roughly grouped by topic). Thanks for all the entertaining and illuminating submissions!

Class 26: Wrap-Up (Tue, 6 Dec 2016)

Schedule

Your final (optional) submission for Problem Set Omega is due by 11:59pm tonight (Tuesday, 6 December). You may revise and update earlier submissions until this deadline.

The final exam is scheduled by the registrar for Saturday, 10 December, 9am-noon in our normal classroom. See the Final Exam Preparation handout for more information and some practice problems.

Practice Problems Solutions (Fri, 2 Dec 2016)

After you have tried to solve the practice problems on your own, you can obtain solutions to them using this form: https://goo.gl/forms/qZVZJD8HHMc2C5XQ2.

Class 25: Cryptography (Thu, 1 Dec 2016)

Schedule

Lighting of the Lawn is tonight! (Starts around 7pm)

If you would like to present something to the class, you need to submit Problem Set Omega by Sunday, 4 December at 6:29pm. Your submission should include an answer to “Presentation option” question:

Presentation option: if you would like to present in class Tuesday, write a brief explanation of what you would like to do and how much time you are requesting for it. You can also include anything you want to make a compelling case for why your project should be selected (depending on how many requests for presentation their are, it may be necessary to select only as many as fit into the class).

Your final (optional) submission is due Tuesday, 6 December. You may revise and update earlier submissions until this deadline.

The final exam is scheduled by the registrar for Saturday, 10 December, 9am-noon in our normal classroom. See the Final Exam Preparation handout for more information and some practice problems.

Class 24: Halting Problems (Tue, 29 Nov 2016)

Schedule

Problem Set Omega is due on Sunday, 4 December or Tuesday, 6 December (see problem set for details). It is not like the others, and counts as a “bonus” optional assignment.

The final exam is scheduled by the registrar for Saturday, 10 December, 9am-noon in our normal classroom. See the Final Exam Preparation handout for more information on the final and some practice problems.

def paradox():
   if halts('paradox()'):
       while True:
          pass

Final Exam Preparation (Mon, 28 Nov 2016)

Final Exam

The final exam is scheduled by the registrar for Saturday, 10 December, 9am-noon in our normal classroom. The final will cover everything in the course, with an emphasis on the most important concepts that have appeared in at least two places.

Most of the questions on the final will be small variations on problems you have already seen on previous exams or problem sets. Doing well on these questions will make a strong case for earning at least a B in the class. A few of the problems will be designed to see how well you can use concepts you have learned in the class to solve problems unlike ones you have already seen. Doing well on many of these questions will make a strong case for earning an A in the class.

The format will be fairly similar to Exam 1 and Exam 2, but because of the extended time for the final, and the desire to give as much opportunity as possible for students to demonstrate what you can do, will be a bit longer than those exams.

As with Exam 1 and Exam 2, you will be permitted to use a single paper page of notes that you prepare and bring to the exam, but no other resources. It is fine to collaborate with others to prepare your notes. The page should be no larger than a US Letter size page ($8.5 \times 11$ inches), and you may write (or print) on both sides of the page.

Unlike the previous exams, you must turn in your notes page with your exam. If you would like to keep your own copy of it, you should make a copy to save before the exam.

Expected Problems

Although the exam covers the whole class, you should not be surprised if it includes problems for you to demonstrate:

• Your understanding of logical formulas, inference rules, and an ability to reason about and manipulate formulas using quantifiers.

• Your fluency with standard proof techniques including proof-by-contradiction.

• Your understanding of well-ordering and how to construct proofs using the well ordering principle.

• Your understanding of sets, how the set operators are defined, and what they mean.

• That you can do a regular induction proof similar to ones you have seen on previous exams very well. That you can do an induction proof that requires some creativity to define a good induction predicate and then to complete the proof.

• Your understanding of state machines, and ability to use the invariant principle to prove a property of the reachable states for a given state machine.

• Your understanding of recursive data types, ability to define functions on recursive data types, and to use structural induction to prove a property about all objects of a recursive data type.

• Your understanding of infinite cardinalities including the ability to determine if a set is countable or uncountable, and to support your answer with a convincing proof.

• Your understanding of Turing Machines and computability. (See practice problems.)

Practice Problems

Since there was no problem set covering Classes 23–25, here are some practice problems to help you prepare for the final. You do not need to turn in your solutions to these problems, but it is highly recommended that you approach them similarly to a problem set to be well prepared for the final. You should not be surprised to see problems similar to these on the final exam.

Trees Challenge (Mon, 28 Nov 2016)

Henry Spece has solved Challenge 7:

Henry’s proof is below:

The set of Tree objects is countable.

The following already proven theorems are used:

• The set of all strees is countably infinite.
  
• the set of all finite sequences of natural numbers is countable.
• The cartesian product of two countable sets is also countable.
• The sub-set of a countable set is countable.

We prove that the set of all trees with natural number labels is countable by finding a total injective mapping between the set of all trees and a set which is known to be countably infinite.

The set to which we are mapping the trees is the cartesian product of the set of finite sequences of natural numbers and the set of all strees. We already know that the set of all strees is countable, as well as the set of all finite sequences of natural numbers. Because the cartesian product of two countable sets is also countable, the cartesian product of these two sets must be countable, and a total injective mapping between the trees and this set would prove the set of all trees to also be countably infinite.

It is possible to imagine a mapping that links a tree to a stree, representing its structure, and a list of its labels, “in-order.” This is effectively “breaking apart” the tree into its components, resulting in two more manageable data types, or one element of the set defined above.

The function is defined more rigorously below, in two parts:

Part 1 (helper function):

   getStree := tree -> stree
   getStree(null) = null
   getStree(combine(t1,N,t2)) = combine(getStree(t1),getStree(t2))
   

Part 2 (helper function):

   getSequence := tree -> sequence
   getSequence(null) = empty sequence
   getSequence(combine(t1,N,t2)) = concatenate(getSequence(t1),N,getSequence(t2))
   

Combined (the relation being defined for the proof):

   splitTree := tree -> (stree, sequence)
   splitTree(t) = (getStree(t),getSequence(t))
   

This relation is defined for all trees, making it total, and produces a unique stree-sequence combination for each tree, making it injective.

Because we have defined a total injective relation between the trees and another set which is known to be countable, the set of all trees must be countable.

Problem Set 9 Solutions and Comments (Sun, 27 Nov 2016)

The Problem Set 9 solutions are now posted: [PDF]

Its a good idea, of course, to read this carefully and ask questions about anything that is unclear.