CompSci 161 Winter 2023

Announcements

Date	Announcement
February 11	It was brought to my attention that the version of Problem Set 5 had a paragraph of instructions that conflicted with this quarter's instructions, an artifact from a former quarter. The document has been fixed. The copy on GradeScope is still correct.
January 11	At 7:30 this morning, the first batch of additions to the GradeScope page were made. If you still aren't on GradeScope, you know what to do to fix that!
January 9	Welcome to CompSci 161 for Winter 2023! Be sure to read the syllabus and the related common policy documents.

Key documents about the course:

Everything begins with the syllabus. Among other things, this document tells you what you can expect from me for the class.
The following Common Policy Documents are referenced in the syllabus and are incorporated into it by reference:
- Exam Rules. Note that all exams this quarter are in-person and there will not be a remote option.
- Artifact Submission and Grading Policies. The lab manual (below) covers submitting programming assignments.
- Academic Honesty Guide
We also have a Projected Schedule, complete with exam dates as well as due dates for problem sets and programming assignments.

Students enrolled should also have access to the EdDiscussion board for the class, which will be used frequently. Homework solutions will appear on the resources page there. Click the downward-facing arrow in the top-right of the EdDiscussion window to access those.

Lecture Handouts:

Lecture 2 - Proofs. Depending on timing, we may finish this during lecture three. You do not need to write these proofs before lecture; rather, these are three proofs we'll go over in class as we review the concept.
Lecture 3 - Inductive Proofs. We also finished the last proof from the previous lecture.
Unit 1: Divide and Conquer. This covers from Wednesday of week two until Monday of week four.
Unit 2: Dynamic Programming. This covers from Friday of week four until Wednesday of week six.
Unit 3: Greedy. Updated 3/3
- Somehow a list of suggested practice questions didn't make its way into the handout. I suggest the following as additional practice for this unit:
  - In the G/T textbook, R-10.4, R-10.5, R-10.6, R-10.7, R-10.8, R-10.9, R-10.10, R-10.4, R-10.5, R-10.6, R-10.7, R-10.8, A-10.4, A-10.5, A-10.7, A-15.1, A-15.2, A-15.3, A-15.4, A-15.5, A-15.6, A-15.7
  - In the textbook of Erickson, Chapter 4, questions 1 (be sure to prove the three correct algorithms to be correct), 3, 4, 5, 6, 14, 15, 16, 17, 20, 21 (a,b for sure; c is good too), 22, 23, 24.
- Unit 3 Supplemental 1: an illustration of some of the ideas behind the proof of the cycle property from lecture 16.
- Unit 3 Supplemental 2 : interval scheduling (Lecture 17) as if it were a homework or exam answer.
- Unit 3 Supplemental 3 : earliest deadline first (Lecture 18) as if it were a homework or exam answer.
Week 10 is review lectures. Friday's was conducted Wednesday of Week 9; video links are available on EdDiscussion. Monday of Week 10 will be the remaining two:
- Closest Pair : Divide and Conquer.
- Dynamic Programming : two problems.

Problem Sets:

Problem Sets are always to be submitted to GradeScope. For instructions on how to get access to the course GradeScope, consult the syllabus, linked above. Be sure to also read carefully the section about artifact submission policies and the section about academic honesty; you are responsible for following those.

Problem Set 0 is not going to be collected. It is a review of a concepts you have seen in prerequisites. If you could use a quick reminder of O notation, counting, probability, data structures, proofs, and the like, I encourage you to try this set. We will discuss some of this week one in lecture and discussion.
Problem Set 1 mostly covers prerequisite material and is due on Wednesday, January 18.
Problem Set 2 is the first Divide and Conquer homework. It is due Wednesday, January 25.
Problem Set 3 is the second Divide and Conquer homework. It is due TUESDAY, January 31.
Problem Set 4 is the first Dynamic Programming homework. It is due FRIDAY, February 10.
Problem Set 5 is the second Dynamic Programming homework. It is due Wednesday, February 15.
Problem Set 6 is the first greedy algorithms homework. It is due Wednesday, March 1.
Problem Set 7 is the second greedy algorithms homework. It is due Wednesday, March 8.

Discussion Handouts

Discussion 1 is a review of probability and counting.
Discussion 2 is a review of running time analysis.
Discussion 3 is a review of running time analysis and proofs.
Discussion 4 covers the Master Theorem in the Divide and Conquer handout.
Discussion 5 covers Divide and Conquer algorithms.
Discussion 6 covers Divide and Conquer algorithms.
Discussion 7 covers the diagnostic exam solutions.
Discussion 8 covers the real exam solutions.
Discussion 9 is the first about dynamic programming.
Discussion 10 is about dynamic programming.
Discussion 11 is about dynamic programming.
Discussion 12 covers the diagnostic exam solutions.
Discussion 13 covers the real exam 2 solutions.
Discussion 14 is about minimum spanning trees.
Discussion 15 is about greedy algorithms and their proofs.
Discussion 16 is about greedy algorithms and their proofs.
Discussion 17 is about greedy algorithms and their proofs.
Discussions 18 and 19 will review Quiz 3 and course material.

Annotated Slides:

Week 10: One More Time!

Lecture 23 : Time-shifted Friday of week 10 lecture, covering additional topics in greedy algorithms.
Lecture 24 (or 23, depending how you want to count). Monday of Week 10, covering an additional topic (Closest Pair of Points) in Divide and Conquer. This was the only in-person lecture week 10.
Lecture 25 (or 24, depending how you want to count). Recorded Monday of Week 10 in the afternoon, to replace Wednesday of Week 10 lecture. This covers two topics in Dynamic Programming.

Unit 3: Greedy Algorithms

A key feature of greedy algorithms is the proofs of correctness.

Lecture 16 : Jarnik's Algorithm and Minimum Spanning Trees
Lecture 17 : Interval Scheduling
Lecture 18 : Scheduling with Deadlines
Lecture 19 : Introduction to Huffman Trees
Lecture 20 : Finishing Huffman Trees, Fractional Knapsack
Lecture 21 : Kruskal's Algorithm and the Union-Find Data Structure.
Lecture 22 : Greedy Algorithms on Trees

Unit 2: Dynamic Programming

Lecture 10 : Interval Scheduling.
Lecture 11 : Longest Common Subsequence
- What would this look like as a homework? I recommend you write it from your notes first, then check the answer and also with commentary
Lecture 12 : Subset Sum
Lecture 13 : Longest Increasing Subsequence. I encourage you to turn the second algorithm into an iterative version for practice and try with the demonstration vector (that was present in your warm-up).
Lecture 14 : Optimal Binary Search Trees. We will finish the lecture on Wednesday.
Lecture 15 : Optimal Binary Search Trees, dynamic programming on trees.

Unit 1: Divide and Conquer

Lecture 4 : counting inversions in a vector.
Lecture 5 : QuickSort and QuickSelect
Lecture 6 : Multiplication Algorithms.
Lecture 7 : Minima Set
Lecture 8 : Concurrent min and max. Binary exponentiation was not covered.
Lecture 9 : Deterministic selection

Review Topics

Lecture 1 : the "celebrity problem".
Lecture 2 : review of proofs.
Lecture 3 : more proofs.

Diagnostic Exams:

Topic Exam 1: Divide and Conquer
- Diagnostic 1
- Diagnostic 2
Topic Exam 2: Dynamic Programming
- Diagnostic 1
- Diagnostic 2
Topic Exam 3: Greedy Algorithms
- Diagnostic 1
- Diagnostic 2