Computer Science 431
Algorithms

Spring 2015, The College of Saint Rose

Home     Syllabus     Schedule

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.

Lecture 12 Assignment

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

• Insertion Sort at Sorting Algorithm Animations