- Teams
- Sprint Duration: 2/22 - 3/15
- Quiz: Thurs Mar 15
- Requirements due:
- Sort Demonstrations: Thursday, March 1 in class
- Problem Sets: Tues, Mar 13
- Programming Project: Thurs, Mar 15
The time and space efficiencies of many algorithms depend on which data structure you decide to use. For example, with an array I can locate the ith element in constant time. But with a LinkedList it takes time O(n). So if I need to request items from the middle of a collection, it is more efficient to use an array. However, if I need to delete a given item, it takes O(n) for an array, but O(1) for a linked list. The most efficient data structure depends on the operations you expect to do with that data structure.
We will begin this sprint with a review of data structures you know: Stacks, queues, arrays, lists, and so forth. I'll have you get a brief overview of some data structures you probably have seen in Discrete: graphs, trees; and we will introduce our first new data structure: Heaps.
Secondly, we will study the very important algorithmic problem of sorting. We will look at various sorting algorithms, analyze them, and discuss their pros and cons. You will learn that in general, sorting cannot be done in less than O(nlgn) time, but if you can make assumptions about your data, you can sometimes sort in as little as O(n) time.
Responsibilities (What you need to know):
- Review of Basic Data structures and their operation times:
- Stacks
- Queues
- Linked List
- Array
- Sets
- Dictionary
- Graph
- Trees, Binary Trees
- New Data Structure: Heap (Used to implement Priority Queues)
- Heap Property (Min heap or Max heap)
- What the underlying array looks like
- Height of a Heap
- Algorithms:
- Heapify
- Build-Heap
- Heapsort
- Insert
- Sorting properties: In-place, Comparison-based, Stable
- General Sorting Algorithms - Know basic algorithm idea, running times, space requirements, properties
- Heapsort
- Mergesort
- Quicksort (Vanilla and Randomized)
- Selection Sort
- Insertion Sort
- Bubble Sort
- Special-Case Sorting Algorithms
- Count sort
- Radix sort
- Bucket sort
Requirements (What you need to do):
Individual Requirements:
Team Requirements:
- Complete the Problem Set on Data Structures
- Complete the Problem Set on Sorting
- Do a Sort Demonstration:
- Your team is assigned one sorting algorithm (See the Teams spreadsheet above). You must "perform" the algorithm for the class. That is, your team should stand, perhaps recruit other participants to help, and show how to physically sort yourselves based on some criteria. For example, you could sort based on height, birthdays, or just hold cards with numbers. You should use this opportunity to "teach" the class your assigned sort. Tell what the best-case, worst-case, and average case running times are, and give any sort properties such as in-place or stable.
- Textbook readings:
- Practice:
- Lecture Notes:
- Videos / Algorithm Visualizations:
- Thursday, Feb 22: Sprint planning meeting. For homework, read textbook chapters on basic data structures and heaps
- Thursday, Mar 1: Perform and watch sort algorithms. Go over any questions on general sorting. For homework, read anything you didn't understand on general sorting and read chapter on linear sorts.
- Tuesday, Mar 6: Go over any sorting questions and work practice problems. For homework, do the sorting problem set.
- Thursday, Mar 8: Get problem sets checked and work more practice problems on any material that is still unclear. Work on Auctions program. For homework, work on Auctions program.
- Tuesday, Mar 13: Turn in problem sets and review for quiz. For homework, finish up Auctions program and practice for the quiz.
- Thursday, Mar 15 : Have quiz & Sprint planning meeting