Computer Science 431

Algorithms

Spring 2015, The College of Saint Rose

Agenda

- Announcements
- Exam 2 comes out next week
- In class on Wednesday, April 8, with a take-home component due at the start of class on Monday, April 13.
- Focus on topics since exam 1:
- divide and conquer: merge sort, quicksort, binary search, Strassen's algorithm, closest pairs
- decrease and conquer: exponentiation examples, insertion sort, graph traversals, topological sort
- binary search trees: tree sort, balanced trees, AVL trees, 2-3 trees
- array representation of trees, priority queues, heaps, heapsort
- counting sorts

- Still be aware of previous topics: you may need to analyze algorithms or compare sort procedures

- More previous problem set recaps
- Counting sorts
- Problem Set 7: Working with Map Data [HTML] [PDF] out

Due at the start of class, Wednesday, April 1.

Please submit answers to these questions in Submission Box under "LA19" or in hard copy by the start of our next class. We will discuss these questions at the start of class, so no late submissions are accepted. Please be sure that your name is clearly indicated in all submissions.

- Levitin Exercise 7.1.3, p. 257 (3 points)
- Levitin Exercise 7.1.4, p. 258 (2 points)

Terminology

- comparison counting sort
- distribution counting sort