Category: Handouts

Today we’ll start (or continue, depending on where your section is right now!) working with graphs. We’re going to play around with the concepts of “diameter” and “articulation point” just to get some experience with graphs. We’ll also spend some time with the DFS and BFS algorithms.

• Here are today’s notes on graphs, diameter, and articulation points.
• We need to spend a minute or two on some items from today’s pre-class quiz.
• The sample solution to the first assignment is out on the blog under the assignments category (and will generally be out immediately after the slightly late deadline we leave as slack in case you have technical troubles). You need the password posted on Piazza.
• The second tutorial quiz is coming in your next tutorial!
• Read Section 3.5 in the textbook for Wednesday.
• There is a pre-class quiz for Wednesday.

Today we’ll finish up asymptotic analysis and start working with graphs. We’re going to play around with the concepts of “diameter” and “articulation point” just to get some experience with graphs. We’ll also spend some time with the DFS and BFS algorithms.

• Here are today’s notes on graphs, diameter, and articulation points.
• The first assignment is due Friday at 10PM. A sample solution will be released tonight shortly after the deadline. (It’ll be password-protected with the password posted on Piazza.)
• The second tutorial quiz is coming in your tutorial next week!
• Read Section 3.4 in the textbook for Monday.
• There is no pre-class quiz for Monday.

We’ll finish talking about the resident/hospital matching problem and start talking about asymptotic analysis!

We’ll review and play with asymptotic analysis. These notes will have a different feel, as we’re not solving an algorithmic problem but performing analysis on algorithms (or, in some cases, performing bits and pieces of that analysis). That said, they’re in service, as always, of solving algorithmic problems!

A few notes:

• Here are today’s notes on asymptotic analysis.
• Here is a handout describing little-o and little-ω notation.
• Read Section 3.1 of the textbook introducing graphs. (But, no pre-class quiz for Wednesday. However, the following pre-class quiz has been sent out already, if you want to get a start on it.)
• The add/drop deadline is Tue 17 Jan. (We’d love to have you stay, but if you intend to drop, don’t miss the deadline!)
• As of ~1PM on Saturday, today’s pre-class quiz was going well. The only question that was below a 70% correct rate was whether lg n is in the class of polynomial functions (in particular, the set of “efficient algorithms” or “efficiently solvable problems”).

It’s Friday the 13th, and we’re studying reductions!! (Boo.)

Right, um.. on to regular business.

We’ll continue working on the resident-hospital matching problem.

A few notes:

• Read Chapter 2 of the textbook for Monday. Most of this should be review! Sections 2.3 and 2.4 are especially valuable for applied review of asymptotic analysis. This is what you should be good at to be awesome computer scientists.
• Finish the pre-class quiz due Sunday at 10PM. You may find that you can answer most questions without having to read the chapter. Please do at least skim the chapter anyway!
• Work on your assignment! It’s due in a week (20 Jan at 10PM).
• Register for a tutorial if you haven’t already.
• Go to tutorial! Next week, the format is up to your TAs. They are thinking about reviewing critical topics and working on assignment and assignment-like problems.
• Here’s a sample solution to our reduction notes.

We’re continuing with stable marriage with an eye to reductions today. No new handouts, but an old one and plenty of notes:

• Pre-class quiz review: As of 3PM Sunday, this was going very well, with fictional clicker questions we’re supposedly asking in class causing the most trouble. (Well, and the soulless candy, but we said we’d give credit for that.) There are no clicker questions in class, and the worksheets aren’t graded… BUT CPSC 320 is a hard course, and the practice and mini-lectures you get in class will make a big difference to your success. So, please do attend!
• And now off to the handout on reductions and stable marriage.
• For next class, read section 1.2 (but no pre-class quiz yet). Be aware that the reading for Monday will be all of Chapter 2. That’s because much of Chapter 2 should be review. You may want to start early, however!
• Tutorial quizzes are posting as each tutorial finishes. Start solving them, since your assignment will be composed of the tutorial quizzes! Your assignment will be due 10PM on 20 Jan (Friday).

Today we’ll continue the first stable marriage handout and (maybe!) start talking about the critical concept of reductions on our next worksheet.

Important notes for today:

• Here’s our new handout on reductions and stable marriage.
• As of ~3PM (before the 10PM deadline), the pre-class quiz was going well. The vast majority of people (well over 80%) answered each of the three pre-class quiz questions correctly. Be sure to finish going through the worked example if you had trouble, and ask on Piazza if you’re still unsure about the quiz!
• For next class, review the syllabus.
• The next pre-class quiz is due by 10PM on 2017/01/10 (Tue) and is about the syllabus. We hope you’ll find this a lighter pre-class quiz :). It should already have been mailed to you.(There won’t be a pre-class quiz due Thursday. Yay!)
• Before your tutorial, read the quiz pre-readings. These are (vague, wordy) problem domains that would take too much time to read and understand during the quiz.
• The assignment version of the tutorial quiz questions will release shortly after each tutorial. Start looking those over and working on them!

Today we continue the first stable marriage handout, although we may skip some pieces that you have a good sense of from the reading.

Brief notes on the pre-class quiz: The vast majority of students who took the quiz will earn 2/2. (We’re downweighting the hardest question, which (CORRECTION) just over half of students got correct: “Independent of execution order, with the same preference lists, a particular man always proposes to the exact same number of women.”) Thanks for doing the readings!

Next time, we expect to continue stable marriage but introduce reductions, which we’ll use frequently to relate one problem to another. (We’ll use reductions to solve new problems in terms of old ones. Intriguingly, we’ll also eventually use reductions in the opposite way: to establish that we don’t know how to (or cannot) efficiently solve new problems by relating them to—reducing to them from—old ones.)

Important notes for today:

• Come to tutorial next week prepared for your tutorial quiz. The collected quizzes will become your assignment. (We’ll post each tutorial’s quiz question as the tutorial ends so everyone can start the assignment at the same time.)
• Follow along with the worked example in the screencast (and a blank copy of the problem). (Suggestion: print the blank problem and try it, but after each major section or if you’re stuck even briefly, let the screencast help! This is not the way to study for an exam, but it will prepare you for class.)
• The next pre-class quiz is due by 10PM (CORRECTED!) on 2017/01/08 and will be e-mailed to your ugrad.cs.ubc.ca account by 5PM today. It is about the worked example. (Our normal pre-class quiz pace will be ~1-2 per week, but the start of term is so exciting!!)
• Also read the syllabus on the course website. Early next week we’ll have a light-weight pre-class quiz about it.