Assignments Information

Assignments:

• Please note that a portion of the marks will be on the organization of the submitted assignment.

• Assignment No 1.




• Assignment No 2. Answer to Question 2.




• Homework Problems No 1: Chapter 4 (Divide and Conquer) and Chapter 8 (Dynamic Programming).
  - 9 in Exercises 4.1, 8 in Exercises 4.2, and 1 in Exercises 4.3.
  - 6 and 7 in Exercises 8.1, 7 in Exercises 8.2, 3 and 8 in Exercises 8.3.
  - Answers




• Assignment No 3.
  Sample Code for DCMaxProfit




• Homework Problems No 2: Chapter 9 (Greedy Technique).
  - questions 7 and 9, in Exercises 9.1; questions 2 and 4, in Exercises 9.3; and questions 1 and 3, in Exercises 9.4.
  - Answers




• Optional Assignment No 1.
  - Answers




• Assignment No 4.




• Homework Problems No 3: Chapter 11 (Limitations of Algorithm Power).
  - questions 2 in 11.1; questions 1(a) and 6 in 11.2; and questions 1, 2, 7(a), and 8 in 11.3.
  - Answers




• Assignment No 5. Please note that the handout on Independent Set and Vertex Cover is highly relevant for this assignment.
  - Answer to Question 2(b)
  - Answer to Question 2(a)




• Homework Problems No 4: Chapter 12.
  - questions 1, 6, 8(a), and 9 in 12.2; questions 2, 3, and 5 in 12.3.
  - Answers

Due Date Policy:

1. If a student can't meet the deadline, he/she is encouraged to communicate with me. I
   will accommodate the student's need by arranging an alternative date.
   Generally, an extra day or two will be granted for light excuses. Longer
   extensions can be accommodated depending on the situation (supporting documents
   may be required).
2. If a student can't meet the deadline and does not make arrangement for an
   alternative submission date, marks will be deducted at the rate of 10% per day
   from the assignment due date up to 50% deduction. After that, the assignment
   will not be marked and a zero mark will be given.

Notes on programming questions:

• Programming Language:
• For students' convenience, C, C++, or Java may be used, depending on preference and experience. If you are not sure and looking for a recommendation, I would recommend C. The programming questions will be designed to be easy to implement. The main goal is to give students a hands-on experience by implementing some algorithmic designs on a few problems and by conducting an empirical analysis of algorithms.




• Working in a Muli-user Environment (Unix):
• You could use your Unix account (engage). As a student,
  you have a Waterloo Nexus account which also gives an account on a FreeBSD Unix machine called engage with the same password. For more information, please refer to engineering computing.
• In this case, when you need to record the runtimes of your implemented algorithm, you would do that using the Unix command time. When you type
  time -p ./program_name [arguments...],
  the time command runs the program and returns three time measurements, the second is the user time, which is what you need to record. For more details, please refer to the man pages.




• Working on a PC:
• You would use a library function to get the system time before and after the program implementing the algorithm. For example, in C and C++, you would include the header time.h and you can use the function clock(). Below is a simple example.

#include <stdio.h>
#include <time.h>

int main() 
{ 
  clock_t t1=clock(); 
  
  /* Algorithm goes here*/

  clock_t t2=clock();
    
  printf("The algorithm runtime = %.4lf seconds\n", 
  (t2-t1)/(double)CLOCKS_PER_SEC);
}