## Lecture Notes 2016/09/21

We’ll finish up our review of asymptotic analysis today. Don’t spend the whole day on that crazy square-root-of-n-to-the-square-root-of-n function! 🙂

A few notes:

**The first assignment is due Thursday (tomorrow) at 5PM**on handin. Click the “assignment” category on the blog to see more information!**Name your PDF file solution.pdf.****Our second tutorial quiz will happen in tutorial next week**, with the same format as this tutorial quiz. Likely topics include stable marriage, reductions, asymptotic analysis, and graphs.**Read Sections 3.1-3.3 in the textbook and complete the pre-class quiz for Friday.**(Invitations have already been sent.)- Here’s a sample solution to our asymptotic analysis notes.

## Lecture Notes 2016/09/19

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**!

- Functions like lg n and n lg n

## Lecture Notes 2016/09/16

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)**We’re looking for a closer room to Swing. We think we’ve found one that’s at least a little better.*may*move.**KEEP AN EYE ON PIAZZA!**- Here’s a
**sample solution to our reduction notes**.

## Lecture Notes 2016/09/14

**Pre-class quiz review**: I really won’t curve down, and we should briefly discuss the outside-of-group collaboration policy.- Reminder:
**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. **A classroom switch (and allowing the waitlist in) is happening! We’re moving to Swing Space 121 as of Friday 16 Sep.**- And now off to the
**handout on reductions and stable marriage**. - For next class,
**read section 1.2**(but no pre-class quiz yet). **The assignment version of the first tutorial quizzes**has been posted and is due a week from tomorrow via handin.

## Full Assignment/Quiz 1 (post Wed 12PM tutorial)

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!

## Assignment/Quiz 1, Tue 1PM Question

Here’s the assignment version of the Tue 1PM question.

## Assignment/Quiz 1, Mon 3PM Question

Here’s the assignment version of the Mon 3PM question.

## Lecture Notes 2016/09/12

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.)

## Assignment/Quiz 1, Mon 9AM Question

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.)