You can view or download the course outline as a PDF document.

Course Informartion

Term: Winter 2012
Instructor:Carlos Moreno (cmoreno, EIT-4103)
Where and when:RCH-103, MWF 16:30 – 17:20 (Plus every other Wed, 12:30 @ RCH-103)
Office hours:By appointment

Course Description

The course focuses on strategies and techniques to efficiently store data (Data Structures) and to perform processing on such data in efficient ways (Algorithms), as well as on the analysis and design of such techniques.

Course Objectives

Upon successfully completing this course, students will have gained an in-depth understanding of the various types of data structures as well as types of situations where they're applicable; this includes sequential storage (lists, queues, stacks), hierarchical storage (trees), and association/adjacency storage (graphs).

Students will also become familiar with algorithm analysis and design techniques. This will include familiarity with some of the fundamental sorting techniques.

Course Contents

The following topics will be covered:
Mathematical review • Asymptotic and algorithm analysis • Relationships and Data structures • Sequential storage: Lists, queues, stacks, deques • Hash tables • Trees • Priority queues and heaps • Sort algorithms • Graphs and graph algorithms • Algorithm design techniques • Complexity classes and NP completeness

Textbooks

No textbook is required for this course.  The following two textbooks are recommended:

Though not required, I strongly encourage you to purchase a copy of the second reference, Introduction to Algorithms (known as CLRS or CLR), as it is a valuable reference for later on during your career.

Evaluation

The grade corresponding to the assignments portion may not be higher than 20 marks above the grade obtained in the final exam. (see printed or PDF version of the course outline for details and formula)

To pass the course, you must achieve a weighted average of at least 50 for the exams AND a weighted average of at least 50 for the Labs and assignments. (again, see printed version or PDF version of the course outline for details)

Assignments, Due dates and Deadline policies:

Assignments will be posted on the course web site; though these will be announced in class, it is each student's responsibility to check the web site on a daily basis for posted assignments, new material, announcements, etc. Failing to attend class or in any way miss any announcements about posted assignments does NOT constitute justification for submitting late or missing an assignment.

Late submissions are NOT allowed, and no work shall be accepted or graded if handed in after the deadline.  If an assignment allows for an exception to this rule, it would be explicitly indicated in the assignment itself, along with details on penalties for late submissions (similarly for Lab projects).

There will be five assignments, and these will be due in class, with due dates on: Jan 13, Jan 27, Feb 10, Mar 16, and Mar 30.  There will be four Lab projects, and these must be submitted through LEARN (\URL{learn.uwaterloo.ca}), with due dates on: Jan 31, Feb 14, Mar 6, and Apr 2.

Missing Exams or Deadlines

If a student misses any deadline or exam, he or she would receive a grade of 0 for the missed evaluation item, except in cases of a medical emergency or some documented medical condition that justifies the incident. ~Notice that medical emergency refers to unplanned events — that is, things like medical appointments for exams or treatment do not constitute acceptable justification. ~In all cases, any medical incident must be accompanied by the proper documentation, as per Department policy and protocols.

In those cases of justified medical situations, the following rules apply:  (1) If the missed item is the midterm, then the grade assigned for the midterm is the same grade obtained in the final.  (2) If the missed item is the final exam, then the student will be given the opportunity to write the final exam during the next offering of the course (presumably Fall 2012).  (3) If the missed item is an assignment, the grade assigned to that assignment would be the average of the grades of the remaining (submitted) assignments.  (4) If the missed item is a Lab project, the grade assigned to that project would be the average of the grades of the remaining Lab projects.

Academic Dishonesty Incidents

In the (hopefully unlikely) event of any student(s) discovered in an incident of academic dishonesty, every student involved will receive a grade of 0 (zero) for the corresponding evaluation item, and additionally will receive a deduction of 5 (five) marks from the final grade of the course.  Additionally, the student(s) will be reported to the Associate Dean of Undergraduate Studies, who may impose additional penalties (see last page for information on Academic Integrity).  In cases where the incident consists of submitting common work, every student involved will be subject to the above penaltyi — no student will be allowed to &ldquo'take full responsibility”, regardless of who copied and who is the genuine author of the work submitted.  This is unconditional.

All of the above applies to multiple instances — a student caught in several incidents of academic dishonesty will be subject to the above penalties for each of the incidents.

Classroom Etiquette

The main and most important etiquette rule to follow is to maintain complete and absolute silence when the instructor is delivering the lecture. This is not simply (or even mainly) out of respect for the instructor; rather, it is mainly out of respect for your classmates, who want to: (1) be able to hear and listen to what the instructor is saying, and (2) not be distracted. (obvious exceptions to this rule are times when the class is interactive, or when the instructor asks questions to the audience or to specific students).

Laptops and Smartphones Etiquette

For the same reason, the use of smartphones is strictly prohibited. You may keep yours on, but in \emph{completely silent mode}, to receive any emergency calls or texts.

Laptop or netbook (or any Internet-connected device) usage is strictly prohibited for any purpose other than taking notes (a practice that is discouraged anyway, since it distracts you from the flow of material being covered and discussed, and you will have notes available on the course web site anyway).

Not only laptop usage (for non-class purposes, that is) is unfair to your classmates, since it can distract them and disrupt the class for them, but it is also detrimental to your performance in the course — psychologists and neuroscientists have presented very solid evidence that the human brain, regardless of training, is not capable of handling several high-level cognitive functions at a time. Thus, by “multitaskingrdquo;, you're only jumping from one task to another, while handling just one task at a given time. Since the flow of class does not stop to accomodate your “task switching” and wait until your brain decides to switch back to the class task, your performance in the course will be negatively affected.

If you want to use a laptop or similar device for taking notes, but you also want to multitask, or if you simply can not resist the temptation of opening your e-mail or browser, etc. while in class, I ask that you sit at the back of the room, preferably the last row, so that no other students will be behind your screen to be distracted.

Keep in mind that class attendance is optional, and while you're strongly encouraged to attent every class, you're also invited to not attend a class if you're not going to focus on the class itself, and distract your classmates while doing any non-class related activities.

Food and Beverages Etiquette

Food and beverages are discouraged in the classroom. This follows exactly the same rationale as for the previous items: out of consideration to your classmates, you want to avoid distracting them — from the noise of unpacking bags or opening cans to the smell of something that you may find “yummyrdquo; but that to others it may be unpleasant or in any case distracting. If you really need to make an exception to this etiquette rule, in this case also I ask that you sit at the back of the room.

Scents/Perfumes/Fragrances Etiquette

I happen to be allergic to most perfumes/colognes and in general scented cosmetics. For this reason, I ask that you avoid, as much as possible, the use of any perfumes/cologne or any cosmetics with fragrance. This also goes with the same rationale as the previous items: out of consideration to your classmates, you may want to avoid the use of any fragrances, since it could be unpleasant to some people, in addition to possibly harmful.

In cases where you drop by to see me during office hours, unfortunately I will have to make this guideline quite strict, to the point that I may be forced to refuse to allow you in my office if I can sense any fragrance. Please avoid them!

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. [Check www.uwaterloo.ca/academicintegrity/ for more information.]

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. When in doubt please be certain to contact the department's administrative assistant who will provide further assistance.

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. 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. For typical penalties check Guidelines for the Assessment of Penalties, http://www.adm.uwaterloo.ca/infosec/guidelines/penaltyguidelines.htm.

Plagiarism-detection software will be used on any submitted projects.

Appeals

A decision made or penalty imposed under Policy 70, Student Petitions and Grievances (other than a petition) or Policy 71, Student Discipline may be appealed if there is a ground. A student who believes he/she has a ground for an appeal should refer to Policy 72, Student Appeals, http://www.adm.uwaterloo.ca/infosec/Policies/policy72.htm.

Note for students with disabilities

The Office for Persons with Disabilities (OPD), located in Needles Hall, Room 1132, collaborates with all academic departments to arrange appropriate accommodations for students with disabilities without compromising the academic integrity of the curriculum. If you require academic accommodations to lessen the impact of your disability, please register with the OPD at the beginning of each academic term.

Turnitin.com:

Plagiarism detection software (Turnitin) will be used to screen assignments in this course. This is being done to verify that use of all material and sources in assignments is documented. In the first week of the term, details will be provided about the arrangements for the use of Turnitin in this course.

Note: students must be given a reasonable option if they do not want to have their assignment screened by Turnitin. See: http://uwaterloo.ca/academicintegrity/Turnitin/index.html for more information.