Schedule

Week 1

Reading topics:

• Basic counting principles - the Product Rule and the Sum Rule (Sec 6.1)
• Permutations and Combinations (Sec 6.3)
• Inclusion-Exclusion principle (Sec 8.5)
• Binomial Coefficients and identities (Sec 6.4)

Notes:

• Lecture 01 - Tuesday 04/02 - Slides - Annotated notes (QB) - Annotated notes (MJ)
• Lecture 02 - Thursday 04/04 - Slides - Annotated notes (QB) - Annotated notes (MJ)
• No discussion this week.

Review Quiz 1 due Sunday 04/07 at 11:59pm - Link HERE

Week 2

Reading topics:

• Binomial Coefficients and identities (Sec 6.4)
• Recursion and recurrence relations (Sec 5.3, 5.4, and 8.1)
• Solving linear recurrence relations (Sec 8.2)

Notes:

• Lecture 03 - Tuesday 04/09 - Slides - Annotated notes (QB) - Annotated notes (MJ)
• Lecture 04 - Thursday 04/11 - Slides - Annotated notes (QB) - Annotated notes (MJ)
• Discussion - Wednesday 04/10 - Notes

Review Quiz 2 and Homework 1 due Sunday 04/14 at 11:59pm - Link to the quiz HERE

Week 3

Reading topics:

• Asymptotic notations, growth rate of functions, order notation, and time complexity of algorithms (Sec 3.1, 3.2, and 3.3)
• Sorting algorithms (Sec 3.1)

Notes:

• Lecture 05 - Tuesday 04/16 - Slides - Annotated notes (QB) - Annotated notes (MJ)
• Lecture 06 - Thursday 04/18 - Slides - Annotated notes (QB) - Annotated notes (MJ)
• Discussion - Wednesday 04/17 - Notes

Review Quiz 3 and Homework 2 due Sunday 04/21 at 11:59pm - Link to the quiz HERE

Week 4

Midterm 1 - Tuesday 04/23, 7:00pm - 8:50pm

Reading topics:

• Sorting algorithms (Sec 3.1)
• Loop invariant and using loop invariant to prove algorithm correctness (Sec 5.5)

Notes:

• Midterm 1 Review - Tuesday 04/23 - Slides - Annotated notes (QB) - Annotated notes (MJ)
• Lecture 07 - Thursday 04/25 - Slides - Annotated notes (QB) - Annotated notes (MJ)
• Discussion - Wednesday 04/24 - Notes

Review Quiz 4 due Sunday 04/28 at 11:59pm - Link to the quiz HERE

Week 5

Reading topics:

• Searching algorithms (Sec 3.1)
• Recursive algorithms and correctness of recursive algorithms (Sec 5.3)
• Time analysis of sorting, searching, and recursive algorithms (Sec 3.2 and 5.4)
• Divide and conquer and the Master Theorem (Sec 8.3)

Notes:

• Lecture 08 - Tuesday 04/30 - Slides - Annotated notes (QB) - Annotated notes (MJ)
• Lecture 09 - Thursday 05/02 - Slides - Annotated notes (QB) - Annotated notes (MJ)
• Discussion - Wednesday 05/01 - Notes

Review Quiz 5 and Homework 3 due Sunday 05/05 at 11:59pm - Link to the quiz HERE

Week 6

Reading topics:

• Encoding/decoding: theoretical bound for optimal encoding, lexicographic order, and the Huffman coding (Sec 11.2)
• Stars and Bars problem and the Twelve-fold way (Sec 6.5)

Notes:

• Lecture 10 - Tuesday 05/07 - Slides - Annotated notes (QB) - Annotated notes (MJ)
• Lecture 11 - Thursday 05/09 - Slides - Annotated notes (QB) - Annotated notes (MJ)
• Discussion - Wednesday 05/08 - Notes

Review Quiz 6 dues Sunday 05/12 at 11:59pm - Link to the quiz HERE

Homework 4 dues Monday 05/13 at 11:59pm

Week 7

Reading topics:

• Discrete Probability (Sec 7.1, 7.2)
• Bayes' Theorem and Expected Value (Sec 7.4)

Notes:

• Lecture 12 - Tuesday 05/14 - Slides - Annotated notes (QB) - Annotated notes (MJ)
• Lecture 13 - Thursday 05/16 - Slides - Annotated notes (QB) - Annotated notes (MJ)
• Discussion - Wednesday 05/15 - Notes

Review Quiz 7 and Homework 5 due Sunday 05/19 at 11:59pm Link to the quiz HERE

Week 8

Midterm 2 - Tuesday 05/21, 7:00pm - 8:50pm

Reading topics:

• Bayes' Theorem and Expected Value (Sec 7.4)
• Randomized Algorithms (Sec 7.3, 7.4)
• Intro to Graphs (Sec 10.1, 10.2, 10.3)

Notes:

• Midterm 2 Review - Tuesday 05/21 - Slides - Annotated notes (QB) - Annotated notes (MJ)
• Lecture 14 - Thursday 05/23 - Slides - Annotated notes (QB) - Annotated notes (MJ)
• Discussion - Wednesday 05/22 - Notes

Review Quiz 8 dues Sunday 05/26 at 11:59pm - Link to the quiz HERE

Homework 6 dues Monday 05/27 at 11:59pm

Week 9

Reading topics:

• Intro to Graphs (Sec 10.1, 10.2, 10.3)
• Eularian and Hamiltonian tours (Sec 10.5)
• DAGs and trees (Sec 10.4, 10.5)
• Graph search (Sec 10.4, 11.1, 11.2)

Notes:

• Lecture 15 - Tuesday 05/28 - Slides - Annotated notes (QB) - Annotated notes (MJ)
• Lecture 16 - Thursday 05/30 - Slides - Annotated notes (QB) - Annotated notes (MJ)
• Discussion - Wednesday 05/29 - Notes

Review Quiz 9 dues Sunday 06/02 at 11:59pm - Link to the Quiz HERE

Homework 7 dues Monday 06/03 at 11:59pm

Week 10

Reading topics:

• Intro to Graphs (Sec 10.1, 10.2, 10.3)
• Eularian and Hamiltonian tours (Sec 10.5)
• DAGs and trees (Sec 10.4, 10.5)
• Graph search (Sec 10.4, 11.1, 11.2)

Notes:

• Lecture 17 - Tuesday 06/04 - Slides - Annotated notes (QB) - Annotated notes (MJ)
• Discussion - Wednesday 06/05 - Notes
• Final Review - Thursday 06/06 - Slides - Annotated notes (QB) - Annotated notes (MJ)

Homework 7 dues Monday 06/03 at 11:59pm

Final Exam - Saturday 06/08 3:00pm to 6:00pm. Location: PETER 108 and CENTER 216 (seat assignment will be up on TritonED)