Winter 2018 -- Department of Computer Science, University of Western Ontario

CS3340 - Analysis of Algorithms

Course description

Computer Science is the new queen of sciences. The computer revolution expanded from the computational devices into intelligent information processing and is therefore affecting every discipline. The role computer scientists play in advancing the world is amazing and they have to live up to the task. The goal of this course is to help making sure they do.

The course concerns all aspects of algorithms: general designing techniques, data structures, mathematical analysis and applications. It assumes knowledge of basic data structures and algorithms (that were studied in CS2210): stacks, queues, lists, trees, (balanced) binary search trees, heaps, hash tables (Chapters 1-6 of textbook). These topics will be quickly reviewed in this course; some new extensions and applications will be discussed. New topics to be studied include: union-find structures, advanced sorting and selecting, greedy algorithms, divide-and-conquer methods, dynamic programming, graph algorithms (Chapters 7-16) and, as time permits, approximation algorithms, randomized algorithms, and string algorithms (Chapters 18, 19, 23).

The central idea is that Computer Science is more than mere recipes; it is about computational thinking. Thinking the correct way is key for becoming a true computer scientist. That's why the course will discuss as well numerous questions selected from interviews at major software companies, where the focus will be on the logical process that leads to the solution, rather than the solution itself.


Computer Science 2210, 2211, Computer Science 2214 or Mathematics 2155.
Unless you have either the prerequisites for this course or written special permission from your Dean to enrol 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.


Textbook (required)

Evaluation (tentative due dates) -- Assignments will be available on OWL

Class time

TAs and office hours



Appeals of Assignment Marks

Computing Facilities

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 Ethical Conduct.

Adherence to Deadlines

There is no penalty for late submissions up to three days. After that the late work is no longer accepted.

Accommodation and Accessibility

If you are unable to meet a course requirement due to illness or other serious circumstances, you must provide valid medical or supporting documentation to the Academic Counselling Office of your home faculty as soon as possible. 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 scibmsac@uwo.ca.
For further information, please consult the university's medical illness policy at http://www.uwo.ca/univsec/pdf/academic_policies/appeals/accommodation_medical.pdf.
If you miss the Final Exam, please contact your faculty's Academic Counselling Office as soon as you are able to do so. They will assess your eligibility to write the Special Exam (the name given by the university to a makeup Final Exam).
You may also be eligible to write the Special Exam if you are in a "Multiple Exam Situation" (see http://www.registrar.uwo.ca/examinations/exam_schedule.html).

Academic Policies

The website for Registrarial Services is http://www.registrar.uwo.ca.
In accordance with policy, http://www.uwo.ca/its/identity/activatenonstudent.html, the centrally administered e-mail account provided to students will be considered the individual's official university e-mail address. It is the responsibility of the account holder to ensure that e-mail received from the University at his/her official university address is attended to in a timely manner.
Scholastic offences are taken seriously and students are directed to read the appropriate policy, specifically, the definition of what constitutes a Scholastic Offence, at this website: http:// www.uwo.ca/univsec/pdf/academic_policies/appeals/scholastic_discipline_undergrad.pdf.
All required papers may be subject to submission for textual similarity review to the commercial plagiarism detection software under license to the University for the 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 (http://www.turnitin.com).

Support Services

Please contact the course instructor if you require lecture or printed material in an alternate format or if any other arrangements can make this course more accessible to you. You may also wish to contact Services for Students with Disabilities (SSD) at 661-2111 ext. 82147 if you have questions regarding accommodation.
The policy on Accommodation for Students with Disabilities can be found here: http://www.uwo.ca/univsec/pdf/academic_policies/appeals/accommodation_disabilities.pdf.
The policy on Accommodation for Religious Holidays can be found here: http://www.uwo.ca/univsec/pdf/academic_policies/appeals/accommodation_religious.pdf.
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 Health@Western (http://www.health.uwo.ca/mental_health) for a complete list of options about how to obtain help.
Additional student-run support services are offered by the USC, http://westernusc.ca/services.