CS 2ME3: Software Design Fundamentals
Winter 2010

• Instructor: Michael Soltys, email: my last name at mcmaster.ca
• TA: Amir Tavasoli
• Course Information
• Lectures: Mo,We,Th 10:30-11:20 in ABB/136
• Office Hours:
  • TA: Tuesdays, 1:30-2:30 in ITB-101A.
  • Instructor: Wednesdays, 11:30-12:20 in ITB-214.
• Course outline: Algorithm design and correctness techniques, and implementation using Perl .
• Textbook:

  Michael Soltys An introduction to the analysis of algorithms. 2009 Published by World Scientific (available from the McMaster bookstore and also available from Amazon).

• Please Read: McMaster Academic Integrity Statement.
• Previous versions of this course: 2004, 2005, 2006, 2007, 2009.

Announcements:

• Apr 24: The exam and the solutions have been posted below.
• Mar 31: Check http://www.proproco.co.uk/million.html for a worked example of the millionaire's problem.
• Mar 26: Sample inputs on which the program in assignemnt 2 was tested have been posted below (and here).
• Mar 17: There will be TA office hours on Monday March 29 instead of a lecture. This will be an opportunity for you to ask the TA questions, clear up marking concerns, etc. The office hour will be during the usual lecture time in the usual lecture room.
• Mar 15: Solutions to assignment 2 have been posted below.
• Mar 14: The programming part of assignment 2 must be submitted before 11pm on Monday March 15.
• Mar 9: Two interesting articles:
  • www.osnews.com/story/22973/RSA_1024-bit_Private_Key_Encryption_Cracked pointed out by Amir, and
  • gcn.com/articles/2010/03/03/rsa-sha-competition.aspx
• Mar 2: Remember that Test 2 will take place on Monday March 8, during the usual lecture time. The test will contain 4 questions, where 2 will be on Greedy algorithms (chapter 2), and 2 questions on dynamic programming (chapter 4). Note that there will be no questions on divide and conquer, and that the dynamic programing section of the test will cover only what we see up to and including the Thursday lecture (which should be most of the dynamic programming chapter).
• Feb 16: Assignment 2 (due on March 15) has been posted below.

  Just for fun, the md5 signature of the pdf with assignment 2 has been added to the table; you can read about it here. I use Mac OS X, which comes with OpenSSL, which implements many basic cryptographic functions (you can read about it here). To obtain the md5 and the sha1 “digests” I use the following commands:

  openssl md5 a2.pdf
  output: a601886a807b164a5ec492e5b5ad5056
  
  openssl sha1 a2.pdf
  output: e482486024ede12db4aabed2bd73a2789885e6d4
  

  An article about sha family of hash functions can be found here.
• Feb 15: Here are the two sample inputs (together with the correct signature-pair output) that were used as tests for the perl program in the first assignment:

  sign 23 7 6 5
  The quick brown fox jumps over the lazy dogs
  (17,6)
  
  sign 19 10 16 5
  hello world
  (3,12)
  

• Feb 13: I will return the tests in class the first Monday after reading week.
• Feb 11: Tests are now ready for pick up the instructor's office (as of 3:20pm).
• Feb 8: The solutions to assignment 1 part B have been posted below.
• Feb 5: Amir points out that there is a good tool for subversion for windows: TortoiseSVN is a free and open source tool that makes working with subversion in windows very simple. Install the tool and right click the folder that you want to work on and select “SVN Checkout...” and give it the repository address https://websvn.mcmaster.ca/cs2me3/your-username. Then if you add, create or edit your source file, and want to commit the source to the repository, right click on it and select “SVN Commit...” and the files will be committed online. Here is where you can download TortoiseSVN: http://tortoisesvn.tigris.org/.
• Feb 4: Click here for the mathematically curious.
• Feb 4: Assignment 1 is due on Monday (Feb 8). Please bring the written part to the lecture - one copy per group, but the names of both group members must be placed on the assignment. You may submit the perl code until 11pm on Momday Feb 8. After 11pm the TA will download the programs for grading.
• Feb 4: Please note that appendix A in the textbook, page 113, contains all the necessary number theory background that you need for the assignment. It is important to know how to compute the “inverse” of an integer modulo another integer. That is, if working module a number p, the inverse of x mod p is a number y such that xy is 1 mod p. For example, the inverse or 2 mod 5 is 3 since 2 times 3 is 6 and 6 is 1 mod 5. All of this is captured by proposition A.4 on page 114 in the textbook.
• Feb 3: There is a small revision in assignment 1 - it is highlighted in yellow in the new version of the assignment given below. It has to do with a mistake in the example digital signature (-19 is 1 mod 10, not 6).
• Feb 2: The TA (Amir Tavasoli) office hours will take place on Tuesdays from 1:30pm to 2:30pm in ITB-101A. Please keep in mind that you can also make an appointment by email (with the TA or the instructor).
• Feb 2: The first test has been posted below.
• Jan 28: Subversion repository address for the course is websvn.mcmaster.ca/cs2me3. As you can works in groups of two, one submission per group is sufficient - but make sure that the name of all the group members are included in the code, as comments.
• Jan 19: On Thursday January 28, Amir Tavasoli, the TA for this course, will conduct a pre-test tutorial during the usual lecture time (10:30-11:20 in ABB/136). The first test is coming up (on Monday February 1, again during the usual lecture time, 10:30-11:20 in ABB/136).
• Jan 12: A Linux Tutorials for beginners has been scheduled on Wednesday (Jan 13th), 9:30am to 11:30 in ITB 235. The same tutorial will be repeated at the same location on Thursday, Jan 14th, from 2:30pm to 4:30pm. You do not have to attend this tutorial, but you might find it useful. You can go to www.cas.mcmaster.ca/support/faq to view the tutorials' contents. Signing up for a tutorial is not required.
• Jan 8: On Thursday January 14, Robert Li will give a tutorial on using subversion (for submitting your Perl programs).
• Jan 8: The dates for assignments and tests have been posted below.
• Jan 7: As the textbook is not yet available in the bookstore, you can download the first chapter (in PDF) here.
• Jan 7: Click here to read about Chomp on Wikipedia.

Assignments and Tests:

	due date	pdf file	solutions	md5 signature
Test 1	February 1	test1.pdf	test1-sol.pdf
Assignment 1	February 8	a1.pdf (revised Feb 3)	a1-sol.pdf
Test 2	March 8	test2.pdf	test2-sol.pdf
Assignment 2	March 15	a2.pdf (revised Feb 21)	a2-sol.pdf sample-sscrypt.txt	a601886a807b164a5ec492e5b5ad5056
Exam	April 23	exam.pdf	exam-sol.pdf