Computer Science 501
Data Stuctures and Algorithm Analysis

Fall 2013, The College of Saint Rose

Home     Syllabus     Schedule     Style Guide

Agenda

• Announcements
  • Study cluster
  • Programming Project 1: Timing Java [HTML] [PDF] now due
  • Lab 3: Analysis [HTML] [PDF] discussion
• Lecture 4 assignment recap
• Lab 4: More Analysis [HTML] [PDF] "mini lab" out
• Analyzing recursive algorithms
• Generic types in Java 1.5+
• Searching

Lecture 5 Assignment

Due at the start of class, Wednesday, October 2.

Please submit answers to these questions in Submission Box under "LA5" 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.

• Bailey Exercise 5.34, p. 114, parts a-c. Set up and solve a recurrence to answer part b. (5 points)
• Solve the following recurrence relations. (10 points)

  a. x(n)= x(n-1) + 6 for n > 1, x(1)= 0

  b. x(n)= 2x(n-1) for n > 1, x(1)= 4

  c. x(n)= x(n-1) + n for n > 0, x(0)= 0

  d. x(n)= x(n/2) + n for n > 1, x(1)= 1 (solve for n=2^k)

  e. x(n)= x(n/3) + 2 for n > 1, x(1)= 1 (solve for n=3^k)

Examples

• Spells/SpellsVectorT.java
• PocketChange/PocketChangeT.java
• BinSearch