Computer Science 431

Algorithms

Spring 2015, The College of Saint Rose

Agenda

- Announcements
- Sign up for the programming contest - Monday, March 9, 2:30-4:00! Be there. Let me know by tomorrow if you plan to come so we can make enough copies, order enough pizza, etc.

- Exam 1 take-home due
- Problem Set 4: Brute Force and Decrease and Conquer [HTML] [PDF] out
- Brief exam recap and discussion
- Graph traversal wrapup
- Decrease and conquer
- exponentiation
- insertion sort
- topological sort
- generating combinational objects

- Have a great break! Go somewhere warm or enjoy the snow or work or sleep or something.

Due at the start of class, Monday, March 9.

Please submit answers to these questions in Submission Box under "LA12" 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 3.5.10, part b, p. 130 (2 points)
- Levitin Exercise 4.1.7, p. 137 (3 points)
- Levitin Exercise 4.1.12, parts a and b, p. 138 (5 points)

Terminology

- decrease and conquer
- decrease by one
- decrease by constant factor
- insertion sort
- directed acyclic graph/dag
- topological sort
- source removal algorithm for topological sort
- generating permutations of a list
- generating subsets of a list
- lexicographic order
- squashed order
- Gray code ordering

Examples

- Powers

Links