THE UNIVERSITY OF WESTERN ONTARIO
DEPARTMENT OF COMPUTER SCIENCE LONDON CANADA
Computer Science 3340b Analysis of Algorithms Course Outline – January 2021
Course Information
Computer Science 3340b
Analysis of Algorithms
Course Outline – Winter Term 2021
Prerequisites
Computer Science 2210, 2211, Computer Science 2214 or Mathematics 2155.
Unless you have either the requisites for this course or written special permission from your Dean 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.
Instructor
Dr. Kaizhong Zhang
372 Middlesex College
Tel: 661-3826, ext. 83826
Course Email: cs3340b
Office Hours: Zoom: by appointment only (arranged at least one day prior)
Course Description
Algorithms are precisely stated, general problem solving methods suitable for computer implementation. Data Structures are methods of organizing data involved in computation.
Algorithms and data structures are central objects of study in computer science. Once appropriate algorithms and data structures are chosen, all that remains in most computer programs is routine coding. Moreover, algorithms and data structures go hand in hand: neither can be studied fruitfully without knowledge of the other.
The course studies techniques for designing and analyzing algorithms and data structures. The course concentrates on the logical process that leads to the creation of the algorithm, rather than the algorithm itself, and the techniques for evaluating the performance of algo- rithms. The central idea is that Computer Science is more than mere recipes; it is about computational thinking.
1
Topics
The topics are drawn from the following lists:
• algorithm design basics: algorithm design with mathematical induction, asymptotic notation, and solving recurrence relations.
• algorithm design techniques: divide and conquer, dynamic programming, greedy algo- rithms, and backtracking.
• searching, sorting, and union-find.
• trees and red-black trees.
• string matching, sequence comparison, and Huffman codes.
• graph algorithms.
• NP-completeness.
Class Schedule
Available drop in/office hours times:
• Tuesday 2:30pm – 3:30pm (EDT/EST London Ontario)
– (7:30pm – 8:30pm GMT January 10 – March 13 2021) – (6:30pm – 7:30pm GMT March 14 – May 1 2021)
• Thursday 2:30pm – 4:30pm (EDT/EST London Ontario)
– (7:30pm – 9:30pm GMT January 10 – March 13 2021)
– (6:30pm – 8:30pm GMT March 14 – May 1 2021)
• Note: The time frames above will be used for individual student meetings and class drop in sessions. Details on dates, times, and sign in sheets will be posted the OWL site.
• Key sessional dates
– Classes begin: January 11
– Reading week: February 13-21 – Classes end: April 12
2
Scheduled Lectures
This course is ”asynchronous”. All lecture materials will consist of videos and accompanying course notes. The scheduled lacture hours will be used for drop in sessions and office hours.
Lecture materials will be available on the course website. These will be made available at the beginning of each week for the duration of the semester.
Teaching Assistant Consulting:
Consulting will take place online through Zoom. Questions regarding assignments or lecture materials can be directed to a Teaching Assistant (TA) or through the Assignment Discus- sions in the OWL Forums section on OWL. Questions requiring further information can be dealt with by contacting the course instructor through the course email. A list of teaching assistants and their contact information will be posted to OWL once available.
Technical Requirements
Completion of this course will require you to have a reliable internet connection and a computer with working microphone and webcam that meets the system requirements for Zoom.
Required Textbook
T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, Introduction to Algorithms (third edition), The MIT Press and McGraw-Hill Book Company, 2009.
Suggested Textbook
M.T. Goodrich and R. Tamassia, Algorithm Design and Application, John Wiley & Son, Inc., 2014.
Course Website
The CS3340b website is accessible through OWL: http://owl.uwo.ca/portal. Lecture notes and videos, assignments, and class information will be posted on this website. You are responsible for reading this information frequently.
Lecture Notes and Videos
Course notes and videos will be available online through the course web page. Students are cautioned, however, that getting course notes and videos may not be a sufficient substitute for textbook and/or attending drop in sessions.
Computing Facilities
Each student will be given an account on the Computer Science Department senior under- graduate computing facility, GAUL. In accepting the GAUL account, a student agrees to abide by the department’s Rules of Ethical Conduct.
3
Email Contact
Emails related to the course should be directed to the course email account at cs3340b@uwo.ca which will be attended by the instructor and the designated TAs. Students could ask ques- tions via email, however if there are any large, somewhat complicated issues, it is recom- mended to discuss them during office hours. Moreover, you must use your UWO account in order to write to the course email account.
Online Conduct
All of the remote learning sessions for this course may be recorded. The data captured during these recordings may include your image, voice recordings, chat logs and personal identifiers (name displayed on the screen). The recordings will be used for educa- tional purposes related to this course, including evaluations. The recordings may be disclosed to other individuals participating in the course for their private or group study purposes. Please contact the instructor if you have any concerns related to session recordings.
All Zoom contact will require that your video is turned on and that you can be seen by the instructor. Not only is this a simple curtesy and the standard of Zoom classes, but it allows for a positive interaction. Any student who is in attendance of a Zoom contact and does not have their video active may be removed from the session.
All Zoom contact will require that your audio is turned off and that you cannot be heard by the instructor (unless you are interacting directly with the professor during the Zoom contact). Not only is this a simple curtesy and the standard of Zoom classes, but it allows for a positive interaction. Any student who is in attendance of a Zoom contact and does have their audio active will be first muted by the professor and if this persists will be removed from the session.
Participants in this course are not permitted to record the sessions, except where recording is an approved accommodation, or the participant has the prior written permission of the instructor.
Student Evaluation
There are two components that will be used for the evaluation. • Assignments, worth 45%
• Exams, worth 55%
To obtain a passing mark in the course, the weighted average of the Midterm and Final exam marks must be at least 40%, and weighted average on the assignment marks must be at least 40%.
To achieve a final mark equal or higher than 60% in the course, the weighted average of the Midterm and Final exam marks must be at least 50%, and weighted average on the assignment marks must be at least 50%.
4
Examinations
There will be a Midterm exam and a Final exam. Midterm weights 20% and final weights
about 35%.
The Midterm exam will be (tentative) on Thursday March 11 at 2:30-4:20PM. The Final
exam will be in April (date and time: TBA).
• The makeup midterm exam will be scheduled for one week after the original midterm.
A student must have an approved absence to be eligible to take the makeup midterm exam. If for any reason the student cannot complete the original midterm and then cannot complete the makeup midterm, then the weight of the midterm missed due to documented and approved medical or compassionate grounds will be placed on the final exam.
• Every effort will be made to have midterm exam marked within two weeks of the exam date, preferably sooner.
Assignments
There will be three assignments in this course. Assignments will be graded by their cor- rectness, preciseness, clarity, and efficiency. In addition, programming questions are also evaluated by coding styles, comments, etc.
All assignment are individual assignments. Students may discuss approaches to assignment problems. However, actual work (answering assignment questions, coding assignment ques- tions, etc.) must be the student’s individual effort.
The assignments have to be typed. We do not accept handwritten assignment. However, you can include handwritten figures, but not text and formula, in your assignment.
One can use Microsoft Word, LaTex, and possibly Vim and then convert to pdf format. By far, the best language for scientific writing is LaTeX. While LaTeX is not required, it is a useful and very-easy-to-learn tool. It is freely available for all platforms. A very short and useful introduction to LaTeX can be found in this document. A not so short, more complete, introduction to LaTeX can be found in this document. While unbeatable for all your academic writings, it is a bonus for your CV as well!
Programming parts of the assignments have to be able to run on compute.gaul.csd.uwo.ca. This is the only platform we will test your programs.
Students must write their essays and 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.
The standard departmental penalty for assignments that are judged to be the result of academic dishonesty is described in this website.
5
You are also responsible for reading and respecting the Computer Science Department’s policy on Scholastic Offences and Rules of Ethical Conduct.
The approximate assignment (tentative) due dates, and mark distribution are given below: • Assignment 1 – Tuesday, February 2, 15%
• Assignment 2 – Tuesday, March 2, 15%
• Assignment 3 – Tuesday, April 6, 15%
Assignment Submission Policies
All assignments are submitted electronically through owl course website. Instructions for the submission of assignments will be posted on the course website. It is each student’s responsibility to read and follow the instructions.
All assignments are due by 11:55PM of the due date. Late assignments will be accepted for up to five days after the due date. After that the late work is no longer accepted. The late penalty in percentage of the total mark of the assignment is round(2(n+1)/5) ∗ 5, where n is the number of days late (one day: 5%, two days: 10%, three days: 15% four days: 30%, five days: 65%). Lateness is based on the time the assignment is received, not the time it was created.
If you have submitted a self-reported absence or an academic consideration for an assignment, we acknowledge the university policy and the arrangement of the course is that you must provide documentation in the CS3340 Assignment Submission Form when you submit your assignment for penalty reduction. You do not need to contact the instructor and we will not reply any such inquiry.
The documentation will either be in the form of the approved self-reporting document or the document or email from student services allowing the extension. The teaching assistant grading the assignment will then apply the supplied extension to the grade.
Self-reported absence cannot be used to further extend the five late days of an assignment. The two days requested must be within the five late days.
Programming parts of the assignments must be able to run on Computer Science Department senior undergraduate computing facility, GAUL, In particular, programming parts of the assignments must be able to run on compute.gaul.csd.uwo.ca.
Assignment Marking
Assignments will be marked by the Teaching Assistant’s who follow marking schemes pro- vided by the instructor.
Every effort will be made to have assignments marked within two weeks of the submission date, preferably sooner.
You should direct any questions regarding assignment marks or marking in the first instance to your T.A. If you and the T.A. cannot agree, then the T.A. will discuss the situation with the instructor.
6
Such request for an adjustment of an assignment mark must be made within 2 weeks from the day in which it was first available to students. After 2 weeks, all assignment marks are considered to be final.
Requests for mark adjustments will only be considered when they are for adjustments of 5 marks or greater.
Accommodation and Accessibility
Accommodation Policies
Students with disabilities work with Accessible Education (formerly SSD) which provides recommendations for accommodation based on medical documentation or psychological and cognitive testing. The Academic Accommodation for Students with Disabilities policy can be found at this website.
Academic Consideration for Student Absence
Students will have up to two (2) opportunities during the regular academic year to use an on- line portal to self-report an absence during the semester, provided the following conditions are met: the absence is no more than 48 hours in duration, and the assessment for which consideration is being sought is worth 30% or less of the student’s final grade. Students are expected to contact their instructors within 24 hours of the end of the period of the self- reported absence, unless noted on the syllabus. Students are not able to use the self-reporting option in the following circumstances:
• for exams scheduled by the Office of the Registrar (e.g., December and April exams) • absence of a duration greater than 48 hours,
• assessments worth more than 30% of the student’s final grade,
• if a student has already used the self-reporting portal twice during the academic year
If the conditions for a Self-Reported Absence are not met, students will need to provide a Student Medical Certificate if the absence is medical. Otherwise the student must provide appropriate documentation if there are compassionate grounds for the absence in question. Students are encouraged to contact their Faculty academic counselling office to obtain more information about the relevant documentation.
Students should also note that individual instructors are not permitted to receive documen- tation directly from a student, whether in support of an application for consideration on medical grounds, or for other reasons. All documentation required for absences that are not covered by the Self-Reported Absence Policy must be submitted to the Academic Counselling office of a student’s Home Faculty.
For policy on Academic Consideration for Student Absences – Undergraduate Students in First Entry Programs, see: this website and for the Student Medical Certificate (SMC), see: this website
Religious Accommodation
7
Students should consult the University’s list of recognized religious holidays, and should give reasonable notice in writing, prior to the holiday, to the Instructor and an Academic Counsellor if their course requirements will be affected by a religious observance. Additional information is given in the Western Multicultural Calendar.
Academic Policies
The website for Registrarial Services is http://www.registrar.uwo.ca.
In accordance with policy, see this website, the centrally administered e-mail account pro- vided 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 the following web site: see this website.
Computer-marked multiple-choice tests and exams may be subject to submission for simi- larity review by software that will check for unusual coincidences in answer patterns that may indicate cheating.
All required papers may be subject to submission for textual similarity review to the com- mercial 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).
Completion of this course will require you to have a reliable internet connection and a device that meets the system requirements for Zoom. Information about the system requirements are available at the following link: https://support.zoom.us/hc/en-us.
Support Services
Please visit the Science & Basic Medical Sciences Academic Counselling webpage for infor- mation on add/drop courses, academic considerations for absences, appeals, exam conflicts, and many other academic related matters: https://www.uwo.ca/sci/counselling/.
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 Student Accessibility Services (SAS) at (519) 661-2147 if you have any questions regarding accommodations.
Western University is committed to a thriving campus as we deliver our courses in the mixed model of both virtual and face-to-face formats. We encourage you to check out the Digital Student Experience website to manage your academics and well-being.
Students who are in emotional/mental distress should refer to Mental Health@Western (at this website) for a complete list of options about how to obtain help.
Additional student-run support services are offered by the USC, see this website. 8