Algorithms

 

CS341/CM339    Fall 2009

 

 

Instructor:

Forbes Burkowski

DC1309

 


 

 

Assignments Fall 2009:

Assignment #1   Assignment # 1 Solutions

Assignment #2   Assignment # 2 Solutions

Assignment #3   Assignment # 3 Solutions Full Path Solution Short Path Solution

Assignment #4   Due date:  Mon. Nov. 16   Assignment #4 Data: Skynet Node Locations

 

Assignment #5   Due date:  Thurs. Dec. 3

 

 

Midterm Solutions

 

Office Hours Information

 

Overview

Calendar description: The study of efficient algorithms and effective algorithm design techniques. Program design with emphasis on pragmatic and mathematical aspects of program efficiency. Topics include divide and conquer algorithms, recurrences, greedy algorithms, dynamic programming, graph search and backtrack, problems without algorithms, NP-completeness and its implications.

 

Text:

[CLRS] Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms
(2nd ed.), MIT Press, 2001 (QA76.6.C662)

 

Copies of all transparencies used in class will be made available:

 

Course Notes

 

Workload

 

•         There will be five assignments corresponding to various major topics of the course. 

 

–        Marking scheme:    Assignments 30%,   Midterm 20%,   Final 50%.

 

 

 

Academic Honesty

 

The usual penalties for academic dishonesty will apply: -100% on an assignment if there is evidence of copying or plagiarism.

 

So that there are no future misunderstandings, please read the following:

 

In any program you write, each line of code should come from your effort only.

 

If you are writing text that is part of the assignment, each sentence that you write will fall into one of the following categories:

 

1.    The sentence is expressed in your own words and expresses your own ideas.

2.    The sentence is expressed in your own words but the ideas or concepts are from somebody else.

In this case you must supply a reference at the end of your document and a pointer to that reference must be associated with that sentence (for example, the pointer is either within the sentence or immediately after the paragraph if the entire paragraph contains your sentences but are describing someone else’s ideas.

3.    The sentence is copied from work done by somebody else.

In this case you must use indentation and quotation marks to clearly specify the limits of the copied material.  You must then provide a pointer to a reference as described in the previous point.

 

 

University Policies (University required text)

Academic Integrity:

In order to maintain a culture of academic integrity, members of the University of Waterloo community are expected to promote honesty, trust, fairness, respect and responsibility. All members of the UW community are expected to hold to the highest standard of academic integrity in their studies, teaching, and research. The Office of Academic Integrity's website ( http://www.uwaterloo.ca/academicintegrity) contains detailed information on UW policy for students and faculty. This site explains why academic integrity is important and how students can avoid academic misconduct. It also identifies resources available on campus for students and faculty to help achieve academic integrity in - and out - of the classroom.

Grievance:

A student who believes that a decision affecting some aspect of his/her university life has been unfair or unreasonable may have grounds for initiating a grievance. Read Policy 70 - Student Petitions and Grievances, Section 4, http://www.adm.uwaterloo.ca/infosec/Policies/policy70.htm .

Discipline:

A student is expected to know what constitutes academic integrity, to avoid committing academic offenses, and to take responsibility for his/her actions. A student who is unsure whether an action constitutes an offense, or who needs help in learning how to avoid offenses (e.g., plagiarism, cheating) or about "rules" for group work/collaboration should seek guidance from the course professor, academic advisor, or the Undergraduate Associate Dean. When misconduct has been found to have occurred, disciplinary penalties will be imposed under Policy 71 - Student Discipline. For information on categories of offenses and types of penalties, students should refer to Policy 71 - Student Discipline, http://www.adm.uwaterloo.ca/infosec/Policies/policy71.htm.

Avoiding Academic Offenses:

Most students are unaware of the line between acceptable and unacceptable academic behaviour, especially when discussing assignments with classmates and using the work of other students. For information on commonly misunderstood academic offenses and how to avoid them, students should refer to the Faculty of Mathematics Cheating and Student Academic Discipline Policy, http://www.math.uwaterloo.ca/navigation/Current/cheating_policy.shtml .

Appeals:

A student may appeal the finding and/or penalty in a decision made under Policy 70 - Student Petitions and Grievances (other than regarding a petition) or Policy 71 - Student Discipline if a ground for an appeal can be established. Read Policy 72 - Student Appeals, http://www.adm.uwaterloo.ca/infosec/Policies/policy72.htm .