Course Description

• The Course's Academic Focus and Scope: This course covers the basics of design and analysis of algorithms. Several commonly used algorithms and fundamental techniques are studied in depth including greedy algorithms, divide-and-conquer technique and dynamic programming algorithms. The course includes formal techniques for analysis of the running time of algorithms. The emphasis is made on designing algorithms appropriate for solving application problems and on analysis of algorithms: correctness and complexity of algorithms. Prerequisites: CPS305 and MTH210.
• Educational Objectives: enable students to learn some of the fundamental ideas in algorithm analysis and design, to know and understand the basic mathematical properties of algorithms, to be able to apply standard formal techniques to algorithms and data structures, to learn the basic techniques of proving correctness of algorithms, to implement algorithms, to evaluate available algorithms and data structures, and select those that are fit for purpose within a given application domain, to develop basic skills of designing algorithms based on fundamental techniques covered in class.
• Teaching methods: Lectures and labs.
• Required Text Book:  Algorithm Design, by Jon Kleinberg and Iva Tardos, ISBN: 0-321-29535-8, (C) 2006, 864 pp, publisher: Addison-Wesley/Pearson Education (online purchase price $63). The Chapters 1-6 of this textbook cover the material related to CPS616. The remaining Chapters 7-13 include more advanced material. Click to read a detailed table of contents.
• Topics (tentative list): Introduction to algorithm analysis, order notations, heaps and priority queues, the greedy method, interval scheduling, correctness of greedy algorithms, an exchange argument (these topics will take about 3 weeks), divide and conquer techniques, recurrence equations, the master method, integer multiplications (these topics will take next 3 weeks), dynamic programming, matrix chain-product, the knapsack problem, the longest common subsequence problem (these material will take about 2.5 weeks after the winter break), representations of graph and graph algorithms: minimum spanning trees, single-source shortest paths, all-pairs shortest paths (these topics will take approximately 2-3 weeks), text processing and pattern matching techniques with applications to DNA analysis and processing of documents on Internet, the Huffman coding algorithm, approximation algorithms. A moderate amount of programming may be required as part of the course. Lectures may contain coarse notations, mathematical language, discussion of mature Computer Science themes and explicit proofs. Student's discretion is strongly advised.

Course Policies

• The students are strongly encouraged to take notes in class, and study their notes after each class. Learning can be a gradual process that requires time and efforts. The students benefit from attending lectures and labs since some important details will be discussed only there. For this reason, attending lectures and tutorials/labs is mandatory.
• Examinations: The quizzes, midterm test, and the final exam may include problem solving, short essay questions, yes/no questions, as well as writing algorithms in pseudo-code. The duration of these examinations will be 15-45 min, 1h40min, and 2h30min, respectively. There will be no supplemental examination. The final exam will concentrate on topics covered after the midterm test.


• Brief quizzes may be given without notice. A mark for a quiz will be given to a student only if (1) s/he attends the entire class for which the participation occurs, and (2) the instructor observed the student actively participating, and (3) the student signs the quiz (including a student number); (4) quizzes must be submitted at the end of class; late quizzes will not be accepted; (5) there will be no supplemental quizzes. A student who missed a quiz is encouraged to solve the quiz independently and discuss it with the peers. The marks for quizzes will be given for effort, but also for solution correctness.


• Grades are earned for the demonstration of knowledge. If you miss a midterm test, a final exam or a deadline for an assignment for medical reasons, you have to provide an official medical certificate AND Academic Consideration form to the department of Computer Science within 3 working days. You have to bring your documents yourself to the CS office. Similarly, all documentation related to special accomodation or academic consideration should be submitted to the CS program office within the specified time limits.


• Dates are subject to change, all changes will be announced in class and on the course Web pages.
• Assignments should be submitted on or before the deadline specified in the assignment (you are encouraged to submit assignments earlier). Your assignment is considered late if any part of the assignment is late. (even if it is just 1 minute late). Printed copies of the assignments should be handed in before class starts. The penalty for a late assignment is 10% off. No assignments will be accepted if more than 24 hours late. Start solving your assignment on the same day when it is posted. Do not procrastinate. No make-up assignments. Late assignments: to hand in your printout, you can give it in person to a secretary at the CS reception desk and ask her to put a stamp on your assignment to confirm that you handed in your assignment in time. Send email to the TA who is responsible for marking this assignment: inform that a hard copy of your assignment is available from the front desk.
• To submit your assignment remotely (not from the lab), you have to establish a ssh connection from your home machine to moon.scs.ryerson.ca : make sure that you have adequate software installed on your home computer that will allow you to connect remotely (if not, submit your assignments from labs). Once you have connected to moon, run submit-cps616 [filename] command. All moons are Linux machines; to work there you have to know basic Unix commands. It is your responsibility to make sure that your CS account is in good standing and that you know both your login name and your password. Talk to one of the system administrator if you have questions about your CS account.
• From time to time, I will hand out exercises. The students are expected to solve the exercises, but they will not be graded. However, working on exercises will improve your understanding of this course (and will help you to get better marks on tests).
• Up to 5% extra credit may be assigned for active class participation throughout the term: a student attends most of the classes, participates actively by asking/answering questions, solves exercises in class. Unexplained lack of attendance can negatively affect one's grade.
• Tutorials/Labs are mandatory. Each student must attend only the section where s/he is assigned. Lab Marks: are given for participation and for submission of specific lab questions, as specified by T.A. The lab mark will be given only if
  1. the student attends the entire lab, and
  2. the T.A. observed the student actively working on the lab (and if finished, on other questions from course notes), and
  3. the T.A. has recorded the student's attendance, and the student was present when attendance was taken, which may be at any point during the lab.
  4. The lab mark will be given for effort and for solution correctness.
  5. Late labs will not be accepted: solutions are due by the end of each lab. Labs are posted in advance: make sure you know what work is expected before you go to the lab.
  6. There will be no make-up labs. The student who missed a lab should try to solve independently the exercises given during the lab time and verify the solutions with the T.A., or with lab partners.
  7. Lab groups can be different from assignment groups (see policy on collaboration below).
• Handouts and assignments will be made available on the Web only. More specifically, they will be linked from the cps616 online course shell on Blackboard. Also, you are responsible for visiting the course Web pages regularly and reading assignments and tests related information that is provided or linked from these Web pages. In particular, Frequently Answered Questions (FAQs) related to cps616 home work will be linked from this Web page. These FAQs are considered to be an integral part of the assignment. Before sending your questions by e-mail to the instructor, check these Web pages whether similar questions have been already answered.
• Email communication: please send me email from local Ryerson's email addresses only: you can use either your departmental account (preferred) or your university account to send email. Email sent from Yahoo, Hotmail and other external domains can be filtered out as spam and might not each me. Students can usually expect a brief reply within 24 hours to email messages sent Monday to Friday, but emails received on weekend might not be answered until the following Monday. Students who have questions that need a long time to answer are advised to ask questions in person during the posted office hours.
• Grades for tests and assignments will be posted on Ryerson Blackboard no later than two weeks after the due date (test date). Handouts and some other course related documents will be posted on the Ryerson Blackboard only. Graded assignments, tests and labs will be usually returned to students within two weeks. Those students who missed a class when their graded work was returned are welcome to pick it up from the instructor during the posted office hours.

Policy on collaboration in homework assignments and in labs

ACADEMIC MISCONDUCT
Committing academic misconduct, such as plagiarism and cheating, will trigger academic penalties including failing grades, suspension and possibly expulsion from the University. As a Ryerson student, you are responsible for familiarizing yourself with the Student Code of Academic Conduct.

Policy on Non-Academic Conduct
No disruption of instructional activities is allowed. Among many other infractions, the Code specifically refers to the following as a violation: ``Disruption of Learning and Teaching - Students shall not behave in disruptive ways that obstruct the learning and teaching environment." In particular, the students can use the laptops (and similar electronic devices) in class only for taking notes. In difficult cases, penalties can be imposed by the Student Conduct Officer.

Remarking Policy

1. Grades are earned for the demonstration of knowledge.
2. Read carefully the marking guide for the assignment or test you'd like to be remarked. Your grade may go up, down, or remain the same.
3. Fill in this remarking form (available online). Attach this form to the hard copy of your assignment. Same rules apply if you request recalculation to correct an arithmetical error in calculating your total score.
4. Forward your assignment and the remarking request form to the TA/GA who marked your assignment. To do this, either hand in your remarking request to the TA at the Lab time, or leave your remarking request attached to the hard copy of your assignment at the Computer Science reception desk (ask for a stamp with the date). Send email to the TA/GA to inform that you left a remarking request. Normally, the marking guide posted on Blackboard includes the name of the TA/GA who was responsible for marking the assignment/test. It is your responsibility to forward your remarking request to the right contact person.
5. Remarking request can be only submitted within 10 working days of the return of the graded work (quiz/assignment/test) in class. It is your responsibility to pick up your quiz/assignment/test as soon as possible. Late regrading requests will not be accepted. It's your responsibility to pick up your work ASAP.
6. Mark can decrease if TA finds something that was incorrectly awarded too high a mark.

Tentative Course Calendar (all changes of dates will be announced)

Course Work	Due Date	Grade Value (%)
Assignment  1	February 11, Tuesday	5
Midterm	Friday, February 28, 4-6pm	20
Assignment 2	March 18, Tuesday	5
Assignment 3	April 1, Tuesday	5
10 Labs	In assigned lab time	20
Class participation & quizzes	In assigned class time	5
Final Exam	Exam period	40
		100

The total grade (100%) is the sum of marks for assignments (15%), quizzes(5%), labs (20%), midterm (20%) and the final exam (40%).