URI CSC 212
Reminder that you must complete the pre-reading before each class.
On this page:
✔️ Pre-reading for Tuesday 3/2
✔️ Pre-reading for Thursday 3/4
Pre-Reading for Mergesort, Tuesday 3/2
Essential Questions
Before attending class, please complete the material below and use the following questions to guide your note-taking:
✔️ How does the mergesort algorithm work?
✔️ What’s the time complexity of mergesort algorithm?
Read/Watch/Review
Before attending class, please complete the material below:
- Read Merge Sort Algorithm
- Watch Merge Sort, GeeksforGeeks (2 min)
- Watch Algorithms: Merge Sort (10 min)
- Note that the implementation is in Java but the only differences for C++ would be using a pointer to an int array since we can’t pass arrays in C++, and manually copying the array.
- Read Analysis of Merge Sort
- Watch Why Is Merge Sort O(n * log(n))? (37 min)
In Class
In today’s class we’ll be debugging broken implementations of mergesort.
Pre-Reading for Analyzing Recursive Algos, Thursday 3/4
Essential Questions
✔️ What is a recurrence relation and why is it useful?
✔️ How do we derive a recurrence relation from code?
✔️ How do we solve a recurrence relation to get the time complexity of a function?
Read/Watch/Review
Notes:
- A lot of the pre-readings will mention induction. If you’re unfamiliar with induction, please read this introduction before continuing.
- The first reading below is a textbook chapter. You may choose to read the textbook chapter OR the three articles beneath it.
- They all give relatively the same information, with the textbook going more in-depth and having better-explained examples.
- Don’t be overwhelmed by the proofs– you won’t be doing formal proofs in this class, but you should understand how to confirm with yourself that your answers are correct for when we do practice problems.
Before attending class, please complete the material below:
- Read Chapter 10: Recurrences
- You can ignore sections 10.4.3-10.4.5
- Read Recurrence Relation
- Read Solving Recurrence Relations (Part I)
- Read Solving Recurrence Relations (Part III)
- Purposely skipping Part II
- Watch Recurrence Equations Overview (6 min)
- Watch Recurrence Relations Discrete Mathematics (15 min)
In Class
In today’s class we’ll be practicing using recurrence relations to analyze recursive algorithms.