Older Announcements

• Project corrections / clarifications:
  1. Updated the .zip file for the project with two modifications: a Makefile with some additional lines to avoid link errors some people were experiencing, and a correction to the Part1b.example file, changing "PrintFeedBackLoops 5 a" to "PrintFeedBackLoops a 5".
  2. Our test cases will never ask you to make self-loops (there will never be an edge from a gene to itself).
  3. The loops found by PrintFeedBackLoops must be simple meaning that they are not allowed to visit the same gene twice.
• Corrections to the earlier version of Homework 3:
  • Problem 1 asks you to design a data structure that allows deletion of any item by key in O(log n) time. Remember, in class we saw a way to delete an item only if you have a pointer to the node containing it. For this problem, you are not given such a pointer.
  • Problem 2 has a serious typo: it should say "amortized CONSTANT time" rather than "amortized linear time". In other words, argue why it is not possible to perform a series of n makeheap, insert, extract_min operations in TOTAL O(n) time. (I believe the answer can be communicated in 1 sentence. Section 7.9 in Shaffer might be helpful.)
  • The Extra Credit Problem is similar to a problem on the previous homework. For the extra credit, you have to show how to implement the other operations (insert and delete) in addition to access. For the previous homework, there were two acceptable ways to implement access(L, i), but for the Extra Credit on Homework 3, I think only one of them will work.
• Homework 3 is now available. Due March 11.
• Class schedule: 3/4 - Homework 2 due, Homework 3 handed out; 3/11 - Homework 3 due; 3/13 - Midterm; 4/3 Project Part 1 due, part 2 handed out; 5/13 - Project part 2 due. There will be approximately two additional homeworks after the midterm.
• 2/26: Homework 2 is now available. Due March 4.
• 2/26: Part 1 of the Project is now available. Due April 3. This zip file contains a Makefile, a suggested file organization for your project, and two example sessions.
• 2/19: For homework 1, problem 2, you can give a solution for for either binary trees or general rooted trees. (The solution I have in mind will work for both, but if yours only works for binary trees that is fine.)
• 2/14: Extra credit homework problem, due Feb 26.
• 2/12: For problem 1 on homework 1, you can assume the stacks support the operation S.empty which returns true iff the stack S contains no elements.
• 2/12: Homework 1 is now available. Due FEB 26.
• 2/4: Updated location for TA office hours (see below).