URI CSC 212
Reminder that you must complete the pre-reading before each class.
On this page:
✔️ Pre-reading for Tuesday 2/9
✔️ Pre-reading for Thursday 2/11
Pre-Reading for Basic Sorting Algos (Analysis), Tuesday 2/9
Essential Questions
Before attending class, please complete the material below and use the following questions to guide your note-taking:
✔️ What is the time complexity of selection sort and why?
✔️ What is the time complexity of bubble sort and why?
✔️ What is the time complexity of insertion sort and why?
Read/Watch/Review
Order is important for the material below– especially the videos. Lalitha’s videos show you how to analyze the algorithms in the way we’re used to– by explicitly counting primitive operations, whereas Back To Back SWE’s videos show you how to do it at a more abstract level, which is where we’re headed for future analyses.
Before attending class, please complete the material below:
- Read Selection Sort Algorithm
- If you’re comfortable with how the algorithm works and is implemented, you can scroll halfway down and only read Complexity Analysis of Selection Sort
- Watch Selection Sort - Time Complexity (Lalitha, 11 min)
- Read Bubble Sort Algorithm
- If you’re comfortable with how the algorithm works and is implemented, you can scroll halfway down and only read Optimized Bubble Sort Algorithm and Complexity Analysis of Bubble Sort
- Watch Bubble Sort - Time Complexity (Lalitha, 11 min)
- Watch An In-Depth Algorithmic Analysis of Bubble Sort (Back to Back SWE, 29 min)
- Keep in mind that the Best Case analysis assumes using the optimized version of Bubble Sort, where if you don’t swap for an entire iteration then you stop altogether because the array is sorted.
- Read Insertion Sort Algorithm
- If you’re comfortable with how the algorithm works and is implemented, you can scroll halfway down and only read Complexity Analysis of Insertion Sort
- Watch Insertion Sort - Time Complexity (Lalitha, 13 min)
- Watch A Detailed Algorithmic Analysis of Insertion Sort (Back to Back SWE, 37 min)
In Class
In today’s class we’ll be doing a brief review of the time complexity for the sorting algorithms above and the rest of the time will be for you to start working on Deep Dive 2.
Pre-Reading for Dynamic Arrays (Implementation), Thursday 2/11
Essential Questions
Before attending class, please complete the material below and use the following questions to guide your note-taking:
✔️ How does a dynamic array work?
✔️ What’re the pros and cons of using dynamic vs static arrays?
Read/Watch/Review
Before attending class, please complete the material below:
- Read the Lab 3 Handout
- If you’d like an additional written explainer on dynamic arrays, read Dynamic Array Data Structure
- Watch The Simple and Elegant Idea behind Efficient Dynamic Arrays (8 min)
- He refers to a “previous video” which is What if you had to invent a dynamic array? (14 min)– this “previous video” isn’t required but it’s strongly recommended if you’re confused by the starting point in the assigned video.
- Watch Dynamic array and Static array (12 min)
- The code example is in JavaScript but the description applies to C++ as well.
In Class
In today’s class we’ll be continuing to work on our lab’s dynamic array implementation.