Today 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).
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.)
- The add/drop deadline is Tue 20 Jan. (We’d love to have you stay, but if you intend to drop, don’t miss the deadline!)
- Fill out the optional start-of-term survey (by the add/drop deadline tomorrow!) to help me learn a bit more about you and help the department learn about our courses. It’s worth 2 bonus points!
- Today’s pre-class quiz went OK with some hiccoughs:
- Functions like lg n and n lg n are within the class of “polynomial” functions as far as we’re concerned (because they’re upper-bounded by a polynomial).
- Linear functions (like the simplest one: n) are definitely in the class “polynomial”!
- If you thought it takes O(5^n) time to investigate all subsets of size 5 of a set of size n, be sure to read the chapter!
We’re in our new classroom today! (Swing 121)
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! I think 2.3 and 2.4 are especially valuable for applied review of asymptotic analysis.
- Finish Monday’s pre-class quiz. 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 Thursday.
- Register for a tutorial if you haven’t already.
- Go to tutorial! You’ll work on assignment problems, and some TAs are considering mini-lectures on topics that have been causing trouble.
- WARNING: Tutorial T1B (Mon 3-4PM) may move. We’re looking for a closer room to Swing. We think we’ve found one that’s at least a little better. KEEP AN EYE ON PIAZZA!
- Here’s a sample solution to our reduction notes.
Now that all the tutorials are done, here’s the full assignment version of the first set of quizzes. Note that there’s no additional problem, but there are additional parts to some of the problems from the tutorial quizzes.
READ THE ACADEMIC CONDUCT GUIDELINES! We give you a lot of freedom to collaborate in order to better learn and succeed in the course. We hate having to prosecute cheating cases, but we do so when you ignore these guidelines. If in doubt, ask!
Today we’ll finish the first stable marriage handout and start talking about the critical concept of reductions.
Important notes for today:
- In class starting today, you’re welcome to use screens (laptops, phones, etc.) for course-related tasks but not for anything else. Exception: if you’re sitting in the back row, you may do what you like with your screens (within legal limits). Please always keep the volume off. (Justification at end of message.)
- A classroom switch (and allowing the waitlist in) looks likely, more news ASAP!
- Here’s our new handout on reductions and stable marriage.
- The pre-class quiz went well. Despite being “any submission gets full credit”, the vast majority of people answered the first two pre-class quiz questions right, and a majority answered the third right. To the 40% of people who got the third one wrong: finish that worked example by Wed!
- For next class, review the syllabus.
- The next pre-class quiz is due by noon on 2016/09/14 (Wed) and is about the syllabus.
- The assignment version of the first tutorial quiz question has already been posted. Others will be posted as those tutorials finish (including the full assignment after the Wed tutorial).
Justification of our in-class screen policy: Research has shown that you inhibit your own learning (or at least grades) by using screens for unrelated purposes during class. But, you’re adults; so, that’s your choice. However, you also inhibit the learning of those around you, which you have no right to do. (Similarly, no smoking in the classroom, please.)
As the tutorials conclude, I’ll post the individual quiz questions here so you can get to work on them even before your tutorial. (Normally, I’ll schedule these to release at the end of each tutorial.) At the end of the last tutorial of the week (usually the Wed tutorial except possibly in Thanksgiving week), I’ll post the collected assignment.
Here’s the Mon 9AM question in its assignment version. (Assignment versions may have an extra part or two.)
We are in the process of negotiating a new room for lecture. If and when it goes through, we’ll move everyone in the waitlist as of today (12 people) into the class. However, we’re also blocking further registration. This is because (1) with the waitlist move, we’ll already have expanded the course twice and more registration will stretch us thin, (2) we’re already solidly into the course at this time, and (3) this will allow both we (the course staff) and students to resolve the current uncertainty about who’s in the class sooner.
I’ll update students in the class and waitlist with Piazza announcements as more information comes in but wanted the reason for shutting the waitlist down to be public!
Thanks to many people in the department for arranging the room swap and managing the waitlist!
Today we continue the first stable marriage handout, although we’re skipping some pieces that you have a good sense of from the reading.
I report on the pre-class quiz below. Short version: 85% of those who took the quiz earned 2/2; only 2% earned 0/2. Thanks for doing the readings!
Next time, we 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, plus possibly an extra problem, 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). I was behind on this; so, the pre-class quiz is worth full credit if you answer it at all. (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 noon on 2016/09/12 and will be e-mailed to your ugrad.cs.ubc.ca account by 5PM today. It is about the worked example. Because I was behind on posting the worked example, you get full credit on the pre-class quiz if you submit it at all. So, submit it! (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.
- A sample solution to the first set of notes is available.
- If you wish to read ahead, I expect us to read at least these sections in this order (changes may happen but probably not drastic ones):
- The rest of Chapter 1 (and, for every chapter we read, the chapter intro)
- Chapter 2 (largely review), with emphasis on 2.3
- Chapter 3
- Sections 4.1-4.7 of Chapter 4 (a bit of which is likely review)
- Sections 5.1-5.4 of Chapter 5, plus the Master Theorem on Wikipedia
- Sections 6.1-6.6 and 6.8 (which is likely review) of Chapter 6
- Sections 8.1-8.5, maybe 8.6, 8.7, 8.8, and 8.10 of Chapter 8. Note that 8.10 is useful to read early and reread as you work through this chapter.
P.S. Our first pre-class quiz went well! 151 people responded (out of 187 registered and on the waitlist). Of those, 128 earned 2/2, 20 earned 1/2, and 3 earned 0/2. (The marking scheme partly responsed to how hard the questions proved to be. The scheme was more complicated than this, but I believe in the end this is also coincidentally correct: correct response to the two easiest questions (about increasing and decreasing preference orders for men and women) plus any one other earned a 2/2, correct responses to either of the easiest questions earned a 1/2. Incorrect responses to both earned a 0/2.
P.P.S. If you don’t receive next class’s pre-class quiz by the end of today, please e-mail firstname.lastname@example.org with your name, student #, ugrad.cs.ubc.ca login ID, and whether you are on the waitlist or in the course.