Department of Computer Science
CS4445/9544 Analysis of Algorithms II
- Roberto Solis-Oba
- Office: MC 417
- Email: firstname.lastname@example.org
- Lectures: Wednesday from 10:30 am to 11:30 pm and Friday from 1:30pm to 3:30pm at FNB 2240.
- Office hours: Monday and Wednesday from 3:30 pm to 5:00 pm and Friday from 3:45 pm to 5:00 pm.
- Course's website: http://www.csd.uwo.ca/courses/CS4445a
Tentative List of Topics
- Maximum flows
- Approximation algorithms
- Randomized algorithms
- Online algorithms
- Parallel algorithms
- Algorithm Design, Kleinberg and Tardos, Addison Wesley, 2005.
- Randomized algorithms, Motwani and Raghavan. Cambridge University Press, 1997.
- Online computation and competitive analysis, Borodin and El-Yaniv. Cambridge University Press, 1998.
- An introduction to parallel algorithms, JaJa. Addison Wesley, 1992.
- Introduction to algorithms, Cormen, Leiserson, and Rivest. The MIT Press, Third edition, 2009.
- Algorithm Design, Goodrich and Tamassia, Addison Wesley, 2001.
Grades will be based on
Tentative. Some of these dates might change
- 4 assignments, worth 50% of the final mark
- a project, worth 40% of the final mark.
- class participation, worth 10% of the final mark. Attending class will be
worth 3% of final mark, your level of participation will decide how much
of the remaining 7% you will be given.
- Assignment 1, due October 4 during class.
- Assignment 2, due October 25 during class.
- Assignment 3, due November 15 during class.
- Assignment 4, due December 6 during class.
- The project is due on December 8 during class.
- All assignments will be made available on the course's web site.
The availability of assignments will be announced on class and/or via email.
Students are responsible for checking their e-mail on a regular basis.
- The late penalty for assignments is 2.5i (2.5 to the ith power), where
i > 0 is the number of days you are late. So if you hand in your assignment 1 day
late, you will be penalized 2%, a delay of 2 days will decrease your grade by 6%, 3 days
is penalized 16% and 4 days takes 39% off your grade. You cannot be more than 4 days late.
- The assignments are worth 50% of the overall mark for the course. If an
assignment has to be cancelled for any reason, the remaining assignment weights will be
prorated to add up to 50%.
Academic Accommodation for Medical Illness
If you are unable to meet a course requirement due to illness or other serious
circumstances, you must provide valid medical or other supporting documentation to
your Dean's office as soon as possible and contact your instructor immediately.
It is the student's responsibility to make alternative arrangements with their
instructor once the accommodation has been approved and the instructor has been
If you are a Science student, the Academic Counselling Office of the Faculty
of Science is located in WSC 140, and can be contacted at 519-661-3040 or
email@example.com. Their website is
A student requiring academic accommodation due to illness should use the Student
Medical Certificate when visiting an off-campus medical facility or request a
Record's Release Form (located in the Dean's Office) for visits to Student Health
Services. The form can be found here:
For further information, please consult the university's medical illness policy at
- CS3340 Analysis of Algorithms I.
Unless you have either the
requisites for this course or written special permission to enroll in it, you will be removed
from this course and it will be deleted from your record. This decision
may not be appealed. You will receive no adjustment to your
fees in the event that you are dropped from a course for failing to
have the necessary prerequisites.
We will occasionally need to send email messages to the whole class, or
to students individually. Email will be sent to the UWO email address assigned to
students by Information Technology Services (ITS), i.e. your email
It is each student's responsibility to read this email on a frequent and regular
basis, or to have it forwarded to an alternative email address if
preferred. See the
ITS website for directions on forwarding email.
However, you should note that email at ITS (your UWO
account) and other email providers such as hotmail.com or
yahoo.com may have quotas or limits on the amount of space
they can use. If you let your email accumulate there, your
mailbox may fill up and you may lose important email from
your instructors. Losing email that you have
forwarded to an alternative email address is not an excuse
for not knowing about the information that was sent.
If you send email to instructors from a commercial account,
send a carbon copy (cc) to your UWO email address.
The instructors will respond to your UWO address.
Scholastic offences are taken seriously and students are directed to read the
appropriate policy, specifically, the definition of what constitutes a Scholastic
Offence, at the following Web site:
Plagiarism: Students must write their assignments in their own words.
Whenever students take an idea, or a passage from another author, they must
acknowledge their debt both by using quotation marks where appropriate and by proper
referencing such as footnotes or citations. Plagiarism is a major academic offence.
All assignments are individual assignments. You
may discuss approaches to problems among yourselves;
however, the actual details of the work (assignment coding,
answers to concept questions, etc.) must be an individual
effort. Assignments that are judged to be the result of
academic dishonesty will, for the student's first offence,
be given a mark of zero with an additional penalty equal to
the weight of the assignment also being applied. You are
responsible for reading and respecting the Computer Science
Department's policy on
Scholastic Offences and
Rules of Ethical Conduct.
The University of Western Ontario uses software for plagiarism checking.
Students may be required to submit their written work
and programs in electronic form for plagiarism checking.
All required papers may be subject to submission for
review to the commercial plagiarism detection software under license
to the University for
detection of plagiarism. All papers submitted for such checking will
be included as source
documents in the reference database for the purpose of detecting
plagiarism of papers
subsequently submitted to the system. Use of the service is subject
to the licensing
agreement, currently between The University of Western Ontario and Turnitin.com
Each student will be given an account on the Computer
Science Department senior undergraduate computing facility,
GAUL. In accepting the GAUL account, a student
agrees to abide by the department's Rules of
Note: After-hours access to certain Computer
Science lab rooms is by student card. If a student card is
lost, a replacement card will no longer open these
lab rooms and the student must bring the new card to a
member of the Systems Group in Middlesex College Room
Please contact the course instructor if you require material
in an alternate format or if you require any other arrangements
to make this course more accessible to you. You may also wish to
contact Services for Students with Disabilities (SSD) at
661-2111 x 82147 for any specific question regarding an accommodation.
Learning-skills counsellors at the Student Development Centre
(http://www.sdc.uwo.ca) are ready to help you improve your learning
skills. They offer presentations on strategies for improving time
management, multiple-choice exam preparation/writing, textbook
reading, and more. Individual support is offered throughout the
Fall/Winter terms in the drop-in Learning Help Centre, and
year-round through individual counselling.
Students who are in emotional/mental distress should refer to Mental
http://www.uwo.ca/uwocom/mentalhealth) for a
complete list of options about how to obtain help.
Please consult the Web site for Registrarial Services
and for USC (http://westernusc.ca/services
) for a list of student support services and programs.