Computer Science 255 — Advanced Data Structures
Winter 2023
Course Description
This course provides a deep investigation of foundational data structures and algorithms. Criteria for selecting appropriate data structures and algorithms for a given problem are presented. General problem solving is emphasized throughout the course. Specific topics include stacks, queues, lists, trees, searching, sorting, traversals, recursion, graphs, hashing, and complexity analysis.
The course programming language is Java.
Prerequisites
CSCI-162
Instructor
Dr. Jean-Alexis Delamer
Office: Annex 9C
Office Hours:
Monday 1:15pm – 3:15pm
Tuesday 9:00am – 11:00am
Thursday 9:00am – 11:00am
Email: jdelamer at stfx.ca
Class Times
Monday 10:15am – 11:05am
Wednesday 9:15am – 10:05am
Friday 8:15am – 9:05am
Lab
Tuesday 3:15pm – 5:05pm
Website
Mostly this website
MOODLE
Textbook and Lecture Notes
Lecture notes will be posted to the website. Assignments will be submitted through Moodle.
Topics
We will not necessarily cover everything listed here, nor in this order. Due to the way the class is being taught, the material covered will adapt to the interests, and abilities, of the class. Many of the things near the end of the list are fairly optimistic and we’ll probably not get to them, but whatever.
Algorithm analysis
Binary Search Trees
AVL Trees
Red-Black Trees
B-Trees
Hashing
Hash Table without linked list
Universal Hashing
Priority Queues
Binomial Heap
Sorting
Quicksort
Disjoint Sets Class
Student Evaluation (Tentative Dates)
Worth |
Due |
|
---|---|---|
Assignment 1 |
5% |
TBD |
Assignment 2 |
5% |
TBD |
Assignment 3 |
5% |
TBD |
Assignment 4 |
5% |
TBD |
Labs |
10% |
Throughout |
Midterm Exam |
30% |
TBD, in class |
Final Exam |
30% |
TBA |
Assignment Submission
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. Failure to follow the submission instructions may result in the assignment receiving a mark of zero.
You will be required to submit each programming assignment electronically. Details will be given in the assignment descriptions. We reserve the right to use similarity detection software to detect possible cheating cases.
Assignment Due Dates
The date and exact time assignments are due will be given in the assignment specifications.
No submissions will be taken after the due date; there are no late submissions.
No extensions will be given for assignments.
Assignment Marking
Assignments are marked by the Teaching Assistants, who follow marking schemes provided by instructors.
A request for adjustment in an assignment mark must be made within 2 weeks of the date on which it was first available after marking. (Beyond that date, regrading will not be considered, regardless of whether you retrieved your assignment.) Such a request must be submitted to the course instructor in writing, and must include specific reasons why you believe you deserve more marks. The request must be accompanied by all materials that were originally handed in, as well as the original marker’s grade summary sheet. The instructor will inform you by email when the reevaluation process is complete.
It is each student’s responsibility to keep up-to-date backups of assignment disk files in case of system crashes or inadvertently erased files. Students must keep disk copies of all material submitted, as well as the actual graded assignment, to guard against the possibility of errors in recording marks. It is not safe to discard these materials until you are satisfied that your final mark for the course has been computed properly.
Tests
No cheating of any form is allowed
Tests and exams are closed book/laptop/notebook/etc.
Calculators will not be permitted
Use of a cell phone is not permitted
The possession of unauthorized devices during tests and examinations constitutes violation of academic integrity, as per section 3.8.2(b)(v) of the academic calendar
Anything that a reasonable person would deem as cheating is not permitted
Labs
The purpose of the weekly labs is to give students hands-on experience. Labs will have required assigned work and will revolve around LeetCode.
Lab exercises must be completed for marks; attendance and lab completion is mandatory. Each completed lab is worth 1% of your final grade (to a maximum of 10%). It is your responsibility to ensure your attendance and exercise completion is recorded.
There is a total of 10 labs, however there is potential for additional labs. In the case where there are more than 10 labs, the marks for your best 10 will be recorded.
You may only attend the lab session for which you are registered.
Students must bring their student identification to all labs.
Email Contact
I may need to send email messages to the whole class or to students individually. Email will be sent to the StFX email address assigned to students. It is the responsibility of the student to read this email on a regular basis. You may wish to have mail forwarded to an alternative email address.
Note that StFX and most other email providers establish quotas or limits on the amount of space available to you. If you let your email accumulate there, your mailbox may fill up and you may lose important email from your instructors. Losing email is not an acceptable excuse for not knowing about the information that was sent.
Students are encouraged to contact their course instructor via email with brief, email appropriate questions regarding lecture materials or clarification of assignments. However, before sending email to an instructor, the student should check the course website to see if the requested information is already there. Students must send email from their StFX account and include CSCI 255 in the subject line of the email. Lengthy and in-depth questions are to be asked during office hours.
Email etiquette — Emails should be addressed to Dr./Prof. Delamer.
Attendance
Students missing three classes without reasonable cause will be reported to the Associate Dean. See section 3.7 of the academic calendar for more details.
You will be reported to Dr. Cathy MacDonald, Associate Dean, Academic Affairs’ Office if you are repeatedly delinquent in assignments or attendance at classes or laboratories.
Copyright Policy
The materials in CSCI 255 at StFX are the property of the instructor, unless stated otherwise by the instructor. Online posting or selling this material to third parties for distribution without permission is subject to Canadian Copyright law and is strictly prohibited.
The course copyright policy will be aggressively enforced.
Class Recording Policy
Students may not create audio and/or video recordings of classes. Students creating unauthorized recording of lectures violate an instructor’s intellectual property rights and the Canadian Copyright Act. Students violating this policy will be subject to disciplinary actions.
Statement of Academic Offenses
Scholastic offenses are taken seriously and students are directed to read the appropriate policy, specifically, the definition of what constitutes a Scholastic Offense. See section 3.8 of the academic calendar.
It is your responsibility to understand what academic misconduct is. Ignorance of the rules is not an admissible excuse for academic misconduct. I will pursue academic offenses fully. I will apply -100% (not 0) as a grade. I will also advocate for an automatic failure in the course, or expulsion from the university when allowed.
Use of Plagiarism-Checking Software
All required papers/submissions 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 Cheating-Analysis Software
All submitted work may be subject to submission for similarity review by software that will check for unusual coincidences in answer patterns that may indicate cheating (MOSS).
Tutoring
The role of tutoring is to help students understand course material. Tutors should not write assignments or take-home tests for the students who hire them.
If you need help though, please just come by my office, or go see the TAs. We’re here to help and most office hours are criminally underused (unless there’s an assignment due… then it looks like Main st. at 4:45pm).
Statement on Accommodation of Religious Observances
Requests for accommodation of specific religious or spiritual observance must be presented in writing to the instructor within the fist two weeks of class.
Statement for Students with Disabilities
Students who have a disability and who require academic accommodations must register with the Centre for Accessible Learning as early as possible in order to receive accommodations. http://sites.stfx.ca/accessible_learning/
The Tramble Center for Accessible Learning welcomes students with documented permanent disabilities and offers them a student-centered program of support. Located in Room 108 of the Angus L. MacDonald Library, new and returning students meet with program staff to discuss options for support. Deadline for registering with the Center is two weeks prior to the end of classes each semester and 3 Business Days’ notice is required for booking all accommodated tests and exams.
To book an appointment please use the following:
Phone — 902 867 5349
Email — tramble@stfx.ca
Academic Accommodation for Medical Illness
Those unable to attend class, submit an assignment, or write a test, should refer to sections 3.7 and 3.9 of the academic calendar.
Scent Policy
For the benefit of the many students that have a scent sensitivity, my classroom is a no-scent zone; please respect this policy.
Equity
Everyone learns more effectively in a respectful, safe and equitable learning environment, free from discrimination and harassment. We invite you to work with me to create a classroom space – both real and virtual – that fosters and promotes values of human dignity, equity, non-discrimination and respect for diversity.
Please feel free to talk with us about your questions or concerns about equity in our classroom or in the STFX community in general. If we cannot answer your questions or help you address your concerns, we encourage you to talk to the Chair/Coordinator of the Department/Program or the Human Rights and Equity Advisor. Please note that a Human Rights and Equity Advisor will soon be appointed. In the meantime, students, faculty, or staff may also contact the Director of Human Resources at hr@stfx.ca or the Office of the AVP&P.
Preferred Pronouns
Professional courtesy and sensitivity are especially important with respect to individuals and topics dealing with differences of race, culture, religion, politics, sexual orientation, gender, gender variance, and nationalities. Class rosters are provided to the instructor with the student’s legal name. Please advise me of this preference early in the semester. See policies at http://www2.mystfx.ca/equity/policies