Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP 2402AB Fall 2022 − Abstract Data Types and Algorithms

Course Outline – last updated August 31 st, 2022

Introduction to the design and implementation of abstract data types and to complexity analysis of data structures. Topics include: stacks, queues, lists, trees, heaps, hash tables, and graphs. Special attention is given to abstraction, interface specification and hierarchical design using an object-oriented programming language (Java). Precludes additional credit for SYSC 2100. Prerequisite(s): (COMP 1006 or COMP 1406 or SYSC 2004) with a minimum grade of C-.

Course Delivery

• This course will be delivered in-person. This means that lectures and office hours will be in-person on campus.

• Students of both sections will share the same course website hosted on Brightspace. Students are required to be familiar with everything posted there. It is recommended to check our course website at least three times a week.

• The instructor and TAs will be available on campus during scheduled hours to answer questions about course content and assignments. A list of teaching assistants and their contact/office hours information together with room locations will be posted once the course starts.

• We will use Discord as our course forum. The forum is non-anonymous - students will be required to use an alias that includes their first and last name, as listed on Brightspace.

Required Textbook

The textbook for the course is Pat Morin's “Open Data Structures”. Free PDF and HTML versions of the book are available at opendatastructures.org. We will use the Java version.

Necessary Equipment and Software

There will be a lot of Java programming throughout the course. You will need a Java compiler and your favorite editor. If you do not have Java installed on your computer, you can download it for free from Oracle Java.

Learning Outcomes

By the end of this course, successful students will have demonstrated their ability to:

• Discuss basic types of data structures, their implementation, application, strengths, and weaknesses.

• Analyze the pros and cons of various solutions to a given problem and make educated decisions which code is best for the given situation.

• Design better code (efficient, reliable, fast, and elegant), leading to software that runs faster and consumes less memory.

Topics Covered

Below is a summary of topics the course will cover:

• Interfaces and Implementation (The Java collections Framework)

• Sequences: lists, stacks, queues, deques

• Array-based implementations of sequences

• Linked-list based implementations of sequences

• Unordered sets - hash tables

• Ordered sets - balanced search trees, skiplists

• Priority queues - heaps

• Sorting algorithms

• Applications of data structures

• Graphs

• Performance issues

A detailed breakdown of topics and a tentative calendar are available on the course website.

Assessment Scheme

Your performance in this course will be assessed using several components:

• There are 5 programming assignments (in Java). The best 4 are worth 40% of your final grade. The lowest assignment grade will be dropped. The assignments are marked by an automatic submission server. This means that you will get instant feedback, and you can submit as often as you want - your best grade is recorded. No late assignments are accepted.

• Weekly quizzes give you high-level practice on the lecture-specific course material. The quizzes are mostly multiple-choice questions on Brightspace. They are not timed and will be open for several days. You will be given two attempts on each quiz, with your best score recorded.

• The midterm will be in-person during our class time. It will be one hour and twenty minutes long.

• The final exam will be in-person and scheduled by the University during the exam period. The final exam is cumulative. There is no double-pass rule.

The grades you achieve on these components will be weighted using the following scheme:

5 Programming Assignments (4 best are counted)                     40%

Weekly (on-line) quizzes                     15%

Midterm (in-person)                          15%

Final Exam (in-person)                        30%

Other important dates and deadlines can be found here, including class suspension for fall, winter breaks, and statutory holidays.

Important Considerations

Late assignments are never accepted for any reason. Assignment submissions are handled by an automatic submission server, and there is no "grace period" with respect to a deadline. Technical problems do not exempt you from this requirement, so if you wait until the last minute and then have issues with your connection, you will still receive a mark of zero. Consequently, you are advised to:

• periodically submit your progress (assignments consist of several parts, and you can receive partial marks even if some of the parts are incomplete),

• attempt to submit your final submission at least one hour in advance of the due date and time.

For each assignment, you will be given a skeleton code and files with very specific names – if you change any of these names or a package your class is in, then the server will not be able to compile your submission. If your submission is improperly packaged, or your code is not compiling for whatever reason, you will get a mark of zero.

Students with an illness during the span of time a midterm is offered might be granted an exemption only if they provide a copy of the Carleton University Self Declaration Form. The weight of the midterm will then be applied to the final exam mark. Furthermore, because assignments are posted well in advance of their due dates, illness does not excuse a student from completing an assignment. No provision is made for missed assignments, and no extra credit assignments will be available.

A student may miss up to 1 assignment and 2 quizzes for medical, compassionate, or other reasons without penalty.

If you miss more than that, a mark of zero will be used for the missed items when the final grade is computed.

If you wish to appeal a mark (assignment, quiz, or midterm) you must make the appeal within 10 days of the mark being posted on Brightspace. After that we will not be obliged to accept appeals or change marks.

Students are asked to pose all questions related to course content using the official Discord forum; students should avoid emailing the instructor directly unless the question contains confidential information or is of a personal nature.

Course Copyright

All materials created for this course (i.e., video recordings, course notes, coding examples, PowerPoint slides, assignments, quizzes, assignment code bases, tests, and exams) remain the intellectual property of the instructor and are protected by copyright. They are intended for the personal and non-transferable use of students registered in the course. Reproducing, reposting, and/or redistributing any course materials, in part or in whole, without the written consent of the instructor, is a copyright violation and is strictly prohibited.

Academic Integrity

Everything you submit for marks in this course (i.e., assignments, quizzes, examinations, etc.) must be the result of your own work and must be completed individually. Collaborating on any course work is strictly disallowed and will be reported as an academic integrity offence. You are never permitted to copy (or copy and modify) solutions (even if incomplete) from anyone or from the Internet. It is also a serious offense to help someone else commit plagiarism. You are never permitted to provide another person access to the rough work, assignment specifications, or source code that you or anyone else has written. If you suspect that someone has been able to acquire a copy of your work, then you must inform the instructor of the course immediately. Please also note that electronic tools may be used to analyze and compare submissions to ensure that no instances of academic misconduct have been committed.

If you are unsure of the expectations regarding academic integrity (how to use and cite references, how much collaboration with classmates is appropriate), ask your instructor. Sharing assignment or quiz/exam specifications or posting them online (to sites like Chegg, CourseHero, OneClass, etc.) is considered academic misconduct. You are never permitted to post, share, or upload course materials (including lecture slides and recordings) without explicit permission from your instructor. Academic integrity offences are reported to the office of the Dean of Science. Penalties for such offences can be found on the ODS webpage: https://science.carleton.ca/academic-integrity/.

SCS Computer Laboratory

SCS students can access one of the designated labs for your course. The lab schedule can be found at: https://carleton.ca/scs/tech-support/computer-laboratories/. All SCS computer lab and technical support information can be found at: https://carleton.ca/scs/technical-support/. Technical support is available in room HP5161 Monday to Friday from 9:00 until 17:00 or by emailing [email protected].

Undergraduate Academic Advisor

The Undergraduate Advisor for the School of Computer Science is available in Room 5302C HP; or by email at [email protected]. The undergraduate advisors can assist with information about prerequisites and preclusions, course substitutions/equivalencies, understanding your academic audit and the remaining requirements for graduation. The undergraduate advisors will also refer students to appropriate resources such as the Science Student Success Centre, Learning Support Services and Writing Tutorial Services.

COVID-19 policies

It is important to remember that COVID is still present in Ottawa. The situation can change at any time and the risks of new variants and outbreaks are very real. There are number of actions you can take to lower your risk and the risk you pose to those around you including being vaccinated, wearing a mask, staying home when you’re sick, washing your hands and maintaining proper respiratory and cough etiquette.

Feeling sick? Remaining vigilant and not attending work or school when sick or with symptoms is critically important. If you feel ill or exhibit COVID-19 symptoms do not come to class or campus. If you feel ill or exhibit symptoms while on campus or in class, please leave campus immediately. In all situations, you must follow Carleton’s symptom reporting protocols.

Masks: Carleton has paused the COVID-19 Mask policy, but continues to strongly recommend masking when indoors, particularly if physical distancing cannot be maintained. It may become necessary to quickly reinstate the mask requirement if pandemic circumstances were to change.

Vaccines: While proof of vaccination is no longer required as of May 1 to attend campus or in-person activity, it may become necessary for the University to bring back proof of vaccination requirements on short notice if the situation and public health advice changes. Students are strongly encouraged to get a full course of vaccination, including booster doses as soon as they are eligible, and submit their booster dose information in cuScreen as soon as possible. Please note that Carleton cannot guarantee that it will be able to offer virtual or hybrid learning options for those who are unable to attend the campus.

All members of the Carleton community are required to follow requirements and guidelines regarding health and safety which may change from time to time. For the most recent information about Carleton’s COVID-19 website and review the Frequently Asked Questions (FAQs). Should you have additional questions after reviewing, please contact [email protected].

University Policies

Academic Calendar. For information about Carleton's academic year, including registration and withdrawal dates, see Carleton's Academic Calendar.

Notice the important changes to the academic calendar:

• New withdrawal date: The academic withdrawal date has been moved up from the last day of term to earlier in the term; this Fall it is November 15, 2022.

• Compassionate Grading Policy: The compassionate grading policy from the previous two years (SAT/UNS) is no longer in effect.

Pregnancy Obligation. Please contact your instructor with any requests for academic accommodation during the first two weeks of class, or as soon as possible after the need for accommodation is known to exist. For more details, visit Equity Services.

Religious Obligation. Please contact your instructor with any requests for academic accommodation during the first two weeks of class, or as soon as possible after the need for accommodation is known to exist. For more details, visit https://carleton.ca/equity/focus/discrimination-harassment/religious-spiritual-observances/.

Academic Accommodations for Students with Disabilities If you have a documented disability requiring academic accommodations in this course, please contact the Paul Menton Centre for Students with Disabilities (PMC) at 613-520-6608 or [email protected] for a formal evaluation or contact your PMC coordinator to send your instructor your Letter of Accommodation at the beginning of the term. You must also contact the PMC no later than two weeks before the first in-class scheduled test or exam requiring accommodation (if applicable). After requesting accommodation from PMC, meet with your instructor as soon as possible to ensure accommodation arrangements are made. For more details, visit the Paul Menton Centre website.

Survivors of Sexual Violence. As a community, Carleton University is committed to maintaining a positive learning, working and living environment where sexual violence will not be tolerated, and survivors are supported through academic accommodations as per Carleton's Sexual Violence Policy. For more information about the services available at the university and to obtain information about sexual violence and/or support, visit: carleton.ca/sexual-violence-support

Accommodation for Student Activities. Carleton University recognizes the substantial benefits, both to the individual student and for the university, that result from a student participating in activities beyond the classroom experience. Reasonable accommodation must be provided to students who compete or perform at the national or international level. Please contact your instructor with any requests for academic accommodation during the first two weeks of class, or as soon as possible after the need for accommodation is known to exist. For more details, see the policy.

Student Academic Integrity Policy. Every student should be familiar with the Carleton University student academic integrity policy. A student found in violation of academic integrity standards may be awarded penalties which range from a reprimand to receiving a grade of F in the course or even being expelled from the program or University. Examples of punishable offences include: plagiarism and unauthorized co-operation or collaboration. Information on this policy may be found here.

Plagiarism. As defined by Senate, "plagiarism is presenting, whether intentional or not, the ideas, expression of ideas or work of others as one's own". Such reported offences will be reviewed by the office of the Dean of Science. Standard penalty guidelines can be found here.

Unauthorized Co-operation or Collaboration. Senate policy states that "to ensure fairness and equity in assessment of term work, students shall not co-operate or collaborate in the completion of an academic assignment, in whole or in part, when the instructor has indicated that the assignment is to be completed on an individual basis". Please refer to the course outline statement or the instructor concerning this issue.