Winter 2018 -- Department of Computer Science, University of Western Ontario
CS3340 - Analysis of Algorithms
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.
- Prof. Lucian Ilie, MC368, e-mail: ilieuwo.ca
- Office hours: Tuesdays, 4:00 - 5:00pm, MC368
M.T. Goodrich and R. Tamassia, Algorithm Design and Application, John Wiley & Son, Inc., 2014. ISBN 978-1-118-33591-8.
Evaluation (tentative due dates) -- Assignments will be available on OWL
- Assignment 1 (10%) -- due Feb. 6
- Assignment 2 (10%) -- due Mar. 6
- Assignment 3 (10%) -- due Apr. 7
- Midterm Exam (25%) -- two-hour exam, in class; Tuesday, Feb. 27, 7:00 - 9:00pm.
- Final Exam (45%) -- three-hour exam, date TBA
- The final will override the midterm if its grade is higher. (That is, the final will count 70% and the midterm will be discarded.)
- Tuesdays, 7:00 - 10:00pm, SH-3345
Nick DelBen (ndelbenuwo.ca)
Saby Patajoshi (spatajosuwo.ca)
Qiang Zhou (qzhou48uwo.ca)
- No books, no devices, no cheat sheets are allowed (as you won't be allowed one in the interviews either).
- There won't be any makeup midterm exam. If you missed the midterm exam, you need to obtain academic accommodation (see the procedure below) and the weight of the midterm exam will be moved to the final exam.
- Assignment will contain reinforcement exercises, creativity questions, and applications. The assignments have to be typed. By very far, the best language for scientific writing is LaTeX. While LaTeX is not required, it is a useful and very-easy-to-learn tool. A very short and useful introduction to LaTeX can be found here (it is much shorter than 139 minutes). It is freely available for all platforms. While unbeatable for all your academic writings, it is a bonus for your CV as well!
- All programs will be written in Python. For those who do not know Python, it is very easy to learn when you know another language already. Python focuses on code readability and has excellent productivity: its code is 5 times shorter than Java and 10 times shorter than C++. That explains why Python is widely used; it has topped the charts in recent years, over C++ and Java. Not knowing Python will place you at disadvantage when looking for jobs!
- All assignments will be made available on the course web site. The availability of assignments will be announced on class and/or via e-mail. Students are responsible for checking their e-mail on a regular basis.
Appeals of Assignment Marks
- Appeals of assignment marks should be addressed to the T.A. first. If you and the T.A. cannot agree, then the T.A. will discuss the situation with the lecturer.
- Appeals must occur within 1 week from the first day that the marked assignments were made available to students. After that 1 week period has gone by, no more appeals will be considered.
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 email@example.com.
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).
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://
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).
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:
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.