**Syllabus****Submit homework****Make appointment****Dropbox**For submitting projects and tracking grades.

**Blackboard**For viewing recordings of the in-person class sessions.

**Teaching assistant office hours**For asking questions during Dr. Olsen's office hours, Monday and Wednesday, 11:30-1:00.

**Tutoring details**Tutoring for this class is available both in person and remotely.

**[2020-08-20] Class 0**Welcome. Discussion of class format and procedures. (video)

**Welcome**Watch this video (1:27).

**Review of course format**Review the syllabus.

Complete the First Day Survey.

Watch this video (28:12) reviewing the format and expectations for the class.

[optional] Peruse Homework 0.

[optional] Watch this video (50:16) response to the first day survey results.**[2020-08-28] Complete the Startup Quiz.**

**[2020-08-27] Class 01**Discussion of HW1–HW3. (video)

**What is an algorithm?**Read Section 1.1.

Watch this video (12:47) about the definition of algorithm.

Watch this video (12:39) about an example algorithm (Euclid's).

Watch this video (24:20) about how to describe algorithms.

Review these notes.

**[2020-08-28] Complete Homework 1. (solutions)****The algorithm design process**Read Section 1.2.

Watch this video (13:37) about the algorithm design process.

Review these notes.

**[2020-08-28] Complete Homework 2. (solutions)****Important problem types**Read Section 1.3. This section is a preview of later parts of the course. No video nor homework for this section.

**Basic data structures**Read Section 1.4.

Watch this video (14:51) review of basic data structures.

Watch this video (26:30) about data structures for representing graphs.

Review these notes.

**[2020-08-28] Complete Homework 3. (solutions)**

**[2020-09-03] Class 2**Review of HW1, HW2, HW3 solutions. Questions and discussion about HW4 and HW5. Preview of HW6. (video)

**What is algorithm analysis?**Read Section 2.1.

Watch this video (43:10) for an overview of the process of analyzing algorithms.

Review these notes.

**[2020-09-04] Complete Homework 4. (solutions)****Asymptotic notations: Big-$\Theta$ and friends**Read Section 2.2.

Watch this video (27:29) which defines Big-$\Theta$ notation.

Watch this video (9:43) example of using this definition.

Watch this video (9:46) which defines Big-$O$ and Big-$\Omega$ notation.

Watch this video (21:09) which shows some asymptotic notation shortcuts.

Watch this video (6:05) about common efficiency classes.

Review these notes.

**[2020-09-04] Complete Homework 5. (solutions)****[2020-09-10] Class 3**Introduction of Project Format Quiz and Project 1. Review of HW4 and HW5 solutions. Questions and discussion about HW6 and HW7. (video)

**Analysis of non-recursive algorithms**Read Section 2.3.

Watch this video (14:32) about using summations to analyze non-recursive algorithms.

Watch this video (17:20) for another example of analysis using summations.

Review these notes.

**[2020-09-11] Complete Homework 6 (solutions).****Analysis of recursive algorithms**Read Section 2.4.

Watch this video (16:24) about writing recurrences to analyze recursive algorithms.

Watch this video (14:59) about solving recurrences using backward substitution.

Watch this video (10:55) introduction to the Tower of Hanoi.

Watch this video (21:33) analysis of the Tower of Hanoi algorithm.

Watch this video (14:06) about an additional trick for solving recurrences.

Review these notes.

**[2020-09-11] Complete Homework 7 (solutions).**

**Review the imaginary assignment Project 0.****[2020-09-14] Complete the project format quiz.**

**[2020-09-21] Project Description****Sample Inputs**project1-1.in

project1-2.in

project1-3.in**Sample Outputs**project1-1.out

project1-2.out

project1-3.out

**[2020-09-17] Class 4**Review of HW6 and HW7 solutions. Discussion of HW8. Discussion of Exam Dry Run and Test A, including Review Sheet for Test A. (video)

**Selection sort**Read Section 3.1.

Watch this video (9:28) introduction to brute force.

Watch this video (25:18) about selection sort.

Review these notes and these notes.**[2020-09-18] Complete Homework 8. (solutions)****String matching**Read Section 3.2.

Watch this video (22:04) about string matching using brute force.

Review these notes.

**[2020-09-18] Complete Homework 9. (solutions)****Exhaustive search**Read Section 3.4.

Watch this video (31:06) about using exhaustive search for the traveling salesman and knapsack problems.

Review these notes.

**[2020-09-18] Complete Homework 10. (solutions)**

**[2020-09-24] Class 5**Discussion of Test A and its dry run. Review of HW08, HW09, and HW10 solutions. (video)

**[2020-10-01] Class 6**No class on 10/01.

**Test Dry Run**The

**required dry run**, worth 10 points, was active 2020-09-22 until 2020-09-24. Details about Test Dry Run (solutions)**Test A**The first test, worth 100 points, will be conducted in a take-home format, between

**September 29**and**October 1**. Review sheet for Test A**Results**The average score was 79.84. Solutions are here.

**[2020-10-19] Project Description****Sample Inputs**project2-1.in

project2-2.in

project2-3.in

project2-4.in**Sample Outputs**project2-1.out

project2-2.out

project2-3.out

project2-4.out

**Insertion sort**Read Section 4.1.

Watch this video (18:47) introduction to decrease and conquer.

Watch this video (22:14) about insertion sort.

Review these notes and these notes.**[2020-10-02] Complete Homework 11. (solutions)****Binary Search**Read Section 4.4.

Watch this video (13:42) about binary search.

Review these notes.**[2020-10-02] Complete Homework 12.****Partitioning and selection**Read Section 4.5.

Watch this video (27:17) about array partitioning.

Watch this video (18:30) about quickselect.

Review these notes.**[2020-10-02] Complete Homework 13. (solutions)**

**[2020-10-08] Class 7**Introduction of Project 2. Discussion of techniques for testing Project 2. Review of Project 1 solution. (video)

**Mergesort**Read from the beginning of Chapter 5 through the start of Section 5.1.

Watch this video (5:55) introduction to divide and conquer.

Watch this video (17:32) about the Master theorem.

Read Section 5.1.

Watch this video (16:35) about Mergesort.

Review these notes and these notes.**[2020-10-09] Complete Homework 14. (solutions)****Quicksort**Read Section 5.2.

Consider re-watching this video (27:17) about array partitioning.

Watch this video (18:05) about quicksort.

Review these notes.**[2020-10-09] Complete Homework 15. (solutions)****Multiplication of Large Integers**Read Section 5.4.

Watch this video (16:48) about representing very large numbers using arrays.

Watch this video (29:52) about the Karatsuba multiplication algorithm.

Review these notes.**[2020-10-16] Complete Homework 16.**

**[2020-10-15] Class 8**Test 1 solutions. Discussion of Project 2. Review of homework solutions. (video)

**Presorting**Read the beginning of Chapter 6 and Section 6.1.

Watch this video (10:32) introduction to decrease and conquer, including the presorting technique.

Review these notes.**[2020-10-16] Complete Homework 17. (solutions)****AVL Trees**Read the first part of Section 6.3.

Watch this video (13:33) review of binary search trees.

Watch this video (24:55) about AVL trees.

Watch this video (18:37) for some examples of AVL tree rebalancing.

Review these notes.**[2020-10-16] Complete Homework 18. (solutions)****[2020-10-22] Class 9**Questions about Project 2. Review of HW18 solutions. Early preview of Test B. (video)

**2-3 Trees**Read the second part of Section 6.3.

Watch this video (20:19) about 2-3 trees.

Watch this video (10:36) for an example of 2-3 tree construction.

Review these notes.**[2020-10-23] Complete Homework 19.****Heaps**Read Section 6.4.

Watch this video (42:45) about heaps.

Review these notes.**[2020-10-23] Complete Homework 20.**

**[2020-11-05] Class 11**No class on 11/05.

**Test B**The second test, worth 100 points, will be conducted in a take-home format, between

**November 3**and**November 5**. A review sheet will be posted by October 27.

**Hash tables**Read the introductory portion of Chapter 7.

Read Section 7.3.

Watch this video (52:15) about hash tables.

Review these notes.**[2020-11-06] Complete Homework 21.**

**Part 8: Dynamic Programming****Part 9: Greedy Algorithms****Part 10: Graph Algorithms****[2020-12-11] Final Exam**