CPSC 413, Design and Analysis of Algorithms I (Winter 2005)

Prof. Scheidler's office hours for this week are:

NOTE:Neither Prof. Jacobson nor Prof. Scheidler will be available for consultation on Thursday (we are both attending a conference all day), so make sure you see us with any questions before then!

Term grades (up to and including the midterm) are available here. Please bring any errors to our attention.

The midterm exam will take place Thursday, March 17, 18:00-20:00, SB 103. Please note that no books or calculators will be permitted, but you will be given the definitions of the asymptotic notations and the Master Theorem on the exam sheet.

The final exam will take place Friday, April 22, 8:00-11:00, ICT 122. Please note that no books or calculators will be permitted, but you may bring one 8.5 x 11 sheet of notes, double or single sided.

• April 20 - Solutions to assignment 5 have been posted (see the "handouts" page).
• April 13 - Lectures on Friday, April 15 have been cancelled.
• April 11 - A sample final exam has been
• April 13 - Lectures on Friday, April 15 have been cancelled.
• April 11 - A sample final exam has been posted (see the "handouts" page).
• April 8 - The CSUS review for CPSC 413 will take place on April 18, 1-3 PM in ICT 121.
• April 1 - Assignment 5 has been posted.
• March 22 - Two example proofs (one reduction and one proof of membership in NP) have been posted (see the "handouts" page).
• March 22 - Lab exercises on greedy approximation algorithms and complexity theory have been posted (see the "labs" page).
• March 11 - Lab exercises on greedy algorithms have been posted (see the "labs" page). These will be covered in the labs on the week starting March 21 (i.e., after the midterm).
• March 11 - A sample midterm has been posted (see the "handouts" page).
• March 11 - Assignment 4 has been posted. Solutions to assignment 3 will be discussed in the MTW labs next week.
• March 1 - Handouts on bounding sums, recurrences and FFT have been posted (see the "handouts" page).
• Feb 18 - Lab exercises on dynamic programming have been posted (see the "labs" page). These will be covered in the labs starting March 7.
• Feb 18 - Assignment 3 has been posted. Solutions to assignment 2 will be discussed in the MTW labs following reading week, and Quiz 2 (covering the same material as assignment 2) will take place in the Thursday evening lab on March 3.
• Feb 11 - Lab exercises on divide and conquer algorithms have been posted (see the "labs" page). Quiz 1, any remaining exercises on the recurrences lab sheet, and these exercises wiil be covered in next week's labs.
• Feb 11 - The last part of Assigment 2, Question 2 has been modified slightly (to simplify the problem). An updated version has been posted. In addition, note that to receive full credit for your algorithm in Question 2, it must be a divide and conquer algorithm and its runtime must be in o(n lg n).
• Feb 4 - Assignment 2 has been posted. Solutions to assignment 1 will be discussed in the MTW labs next week, and Quiz 1 (covering the same material as assignment 1) will take place in the Thursday evening lab on Feb 10.
• Jan 31 - Sample LaTeX source files (corresponding to the currently-posted assignments and lab exercises) can be found on the "latex" page. There is also a link to an online LaTeX help guide on our "links" page.
• Jan 31 - In Assignment 1, Question 1, you do not need to assume that the degree of the degree of the polynomial has at most m bits.
• Jan 27 - Lab exercises on recurrence relations have been posted (see the "labs" page). Any remaining exercises on the summations lab sheet, Question 2 of the runtime functions lab sheet, and Questions 2 (a,b,f,g,h) will be covered in next week's labs.
• Jan 24 - Minor correction to Assignment 1. Line 3 of the function PolyEval-Horner in Question 1 should be while (i >= 0).
• Jan 20 - Lab exercises on runtime functions of algorithms and summations have been posted (see the "labs" page). Question 1 of the runtime functions problems and all of the summation problems will be covered in the next week's labs.
• Jan 17 - Assignment 1 has been posted. In addition, a sample algorithm analysis, meant to give guidance on the level of detail we expect for the assignment solutions, has been posted on the "handouts" page.
• Jan 15 - 2 handouts related to asymptotic notation have been posted (see the "handouts" page).
• Jan 14 - Lab exercises on asymptotic notation have been posted (see the "labs" page).
• Nov 16 - Some math review problems are available (see the "handouts" page).