CSCI-3110 — Design and Analysis of Algorithms
Course Syllabus
Summer 2023
Instructor Information
Instructor: Travis Gagie
Email: travis.gagie@dal.ca
Course Email: csci3110@dal.ca
Class Meeting Time: MW 13:05-14:25
Room No: LSC-COMMON AREA C240
Lab Meeting Time: F 13:05-14:25
Room No: LSC-COMMON AREA C240
Office Hours: T 13:05-14:25
Office: MC 4242
Course Homepage: https://dal.brightspace.com/d2l/home/271659
Teaching Assistants: Conrado Boeira, Nathaniel Brown, Narges Yarahmadi Gharaei,
Monzurul Ifath, Sana Kashgouli, Faezeh Moradi, Asif Samir
Email Policy
Send emails only from your Dal email account. You will be assigned a contact TA on the basis of your surname. First,
consider posting on the Brightspace bulletin board for the course; then, consider emailing your contact TA (cc’ing the
course email address); only in exceptional circumstances should you contact Travis directly. We will try to answer
emails by the end of the next business day (so if you email Friday morning, for example, you should get an answer by
Monday evening).
Important Dates
1. midterm exam: June 21
2. final exam: Tuesday, August 8th
3. warm-up assignment deadline: 23:59 Friday, May 5
4. real assignment deadlines: 23:59 Friday from May 12 to July 21 except June 16 and 23
(you can drop your worst 3 of 9 assignments)
5. May 1: first class
6. May 5: first lab, warm-up assignment due
7. May 12: last day to change or add courses, first real assignment due
8. May 22: Victoria Day (university closed)
9. May 29: last day to drop without “W”, change from audit to credit and vice versa
10. June 9: practice midterm (in lab) — optional!
11. June 12–16: Summer Break (no classes or labs)
12. June 19: review solutions to practice midterm (in class) — optional!
13. June 21: midterm exam (in class)
14. June 26: last day to drop with “W”
1
15. July 3: (late) Canada Day (university closed)
16. July 26: last class, practice final (in class)
17. July 28: last lab, review solutions to practice final (in lab)
18. August 3–14: exam period
19. August 7: Natal Day (university closed)
Course Description
This course will introduce students to the design and analysis of algorithms. Topics include paradigms of algorithm
design (divide and conquer, greedy algorithms, dynamic programming, using and augmenting data structures, network
flows), limitations of algorithms (lower bounds, NP-completeness and computability theory), and examples of im-
portant algorithms (e.g., Karatsuba’s, Strassen’s, MergeSort, QuickSort, QuickSelect, Huffman’s, Kruskal’s, Prim’s,
Dijkstra’s, Bellman-Ford, Floyd-Warshall).
Learning Outcomes
• Extend known algorithms and data structures to solve a closely related problem.
• Recognize problem statements where a solution based on divide and conquer, dynamic programming or greedy
approach is appropriate.
• Select the most appropriate proof technique to prove the correctness of a given algorithm.
• Recognize that some problems are unlikely to be efficiently solvable (NP-Hardness).
• Express an algorithm’s running time as a recurrence relation and derive a closed form.
• Apply graph exploration approaches as tool to solve a wide range of problems.
• Use standard data structures to efficiently implement graph algorithms.
• Abstract real-world problems into fundamental algorithm, data structure, and graph problems.
• Determine the complexity of an algorithm.
• Estimate the size of an input that an algorithm can process relatively quickly.
• Select and use appropriate abstract data types, data structures, and algorithms to solve moderately complex
problems.
• Understand the relevance of different theoretical performance measures: worst-case vs. average-case running
time.
• Explain the relationship between theoretical analysis and the practical performance of an algorithm.
• Solve simple algorithm design problems.
• Perform an asymptotic analysis of an algorithm’s running time.
Class Format and Course Communication
• Lectures, labs and exams will be in-person only.
• Course announcements will be posted to Brightspace and/or the course mail list, which comprises the instructor’s
and students’ Dal emails. It is the student’s responsibility to check Brightspace and their Dal e-mail on a
daily basis. To access your Dal e-mail account please see: https://www.dal.ca/dept/its/o365/
services/email.html
2
Evaluation Criteria
1. Assignments (50%)
• the warm-up assignment is worth 2%
• there are 9 real assignments with the best 6 to count 8% each
• assignments will be accepted up to 48 hours late — that is, until 23:59 Sunday — with a 20% penalty;
after that, the penalty is 100%
• students can work in groups of up to 3 on assigments
• one student from each group is to submit the assignment with all names and banner numbers on it, on
Brightspace
• the other students are to submit text files listing all names and banner numbers, on Brightspace
• students can start/disband/switch groups after each assignment
• students may discuss with other groups but someone in each group must be understand and be able to
explain each answer
• if no one in a group can explain one of their answers, they are liable to be reported to FCS for plagiarism
2. Midterm Exam (20%)
• In-person midterm during class time (but students can arrange in advance to write the practice midterm in
person as a midterm).
3. Final Exam (30%)
• In-person exam (but students can arrange in advance to write the practice final in person as a final).
• Scheduled by the university.
• Will cover all material in the course.
Notes
• A minimum C grade is required in this course if it is core to your FCS degree, or if it will be used as a prerequisite
for a subsequent CSCI course.
• As of 2019, students who receive a grade lower than C in the same required CS course twice, will be dismissed.
• The grade conversion scale in Section 17.1 of the Academic Regulations, Undergraduate Calendar will be used.
https://academiccalendar.dal.ca/Catalog/ViewCatalog.aspx?pageid=viewcatalog&
catalogid=111&chapterid=6817&topicgroupid=29869&loaduseredits=False
• A student must pass (50%) both the assignment component and the final exam to pass the course.
Required Texts and Resources
• There is no required text for the course but Cormen, Leiserson, Rivest and Stein’s Introduction to Algorithms is
recommended.
• Some students have found Laaksonen’s Competitive Programmer’s Handbook useful (available for free down-
load at https://cses.fi/book/index.php).
• Lecture notes and videos from 2021 are posted on DalSpace and YouTube but the material for this course will
differ slightly!
Prerequisites
CSCI 2110 and 2112.
3
Tentative Schedule of Topics
1. history of computability theory, Turing Machines
2. diagonalization, the Halting Problem, Kolmogorov
complexity
3. relation of computability to complexity (Recursive
vs. Recursively Enumerable compared to P vs. NP)
4. NP-completeness: basic concepts, reductions,
Cook’s Theorem
5. Clique, Independent Set, Vertex Cover, SAT, 3-
SAT, HamPath, 3-Colourability
6. approaches to handling NP-hard problems
7. applications of hardness, zero-knowledge, pro-
gramming with ILPs and SAT-solving
8. Eulerian and Hamiltonian cycles
9. graph colouring by divide-and-conquer
10. Karatsuba’s algorithm, Strassen’s algorithm, the
FFT
11. reducing k-SAT to Orthogonal Vectors
12. asymptotic notation, lower bounds, the Master The-
orem
13. MergeSort, QuickSort, QuickSelect
14. Huffman’s algorithm, Van Leeuven’s algorithm,
cannonical coding
15. Kruskal’s algorithm, Prim’s algorithm, union-find
data structure
16. Supowit’s algorithm, Vertex Cover, Fractional
Knapsack, Binary Knapsack
17. Subset Sum, Knapsack, Factoring
18. Edit Distance, Longest Common Subsequence
19. Optimal BSTs
20. Longest Increasing Subsequence, range-max data
structures
21. Dijkstra’s algorithm, Bellman-Ford, matrix multi-
plication
22. counting paths, Floyd-Warshall, shortest paths in a
DAG
23. topological sort, strongly connected components
24. network flows
25. pattern matching, group testing, finding majority el-
ements, etc
The part of the syllabus that is specific to this course ends here.
4
Midterm and Final Exam Requirements
• Photo ID is required.
• Closed book.
• No dictionaries, notes, calculators, cell phones, PDAs, talking slide rulers, or other electronic aids allowed.
Student Declaration of Absence
The Student Declaration of Absence policy shall apply. https://www.dal.ca/campus_life/safety-respect/
student-rights-and-responsibilities/academic-policies/student-absence.html. The
student has a maximum of two (2) SDAs per course per semester. The student must notify the instructor of their
inability to meet a deadline before the deadline by contacting the instructor or submitting the completed SDA. Upon
notification the student has 3 days after the deadline to submit the SDA.
Academic Standards
Failure to properly attribute sources in your work will be treated as an academic standards issue and points may be
deducted for not following citation requirements. For example, forgetting to quote text taken from other sources,
failure to include in-text citations, or a failure to include required information in the citations or references. Please
see the resources on proper citation provided by the Dalhousie Writing Center (https://dal.ca.libguides.
com/c.php?g=257176&p=5001261).
Please note that if it appears that the error was made with intent to claim other people’s work as your own such as
a lack of both citations and references, an allegation of plagiarism will be submitted to the Faculty Academic Integrity
Officer, which could result in consequences such as a course failure.
Responsible Computing Policy
Usage of all computing resources in the Faculty of Computer Science must be within the Dalhousie Acceptable
Use Policies (http://its.dal.ca/policies/) and the Faculty of Computer Science Responsible Comput-
ing Policy. (https://www.dal.ca/content/dam/dalhousie/pdf/faculty/computerscience/
policies-procedures/fcs_policy_local.pdf)
Use of Plagiarism Detection Software
All submitted assignment may be passed through a plagiarism detection software, such as the Moss Software Similar-
ity Detection System (https://theory.stanford.edu/˜aiken/moss/), or similar systems. If a student
does not wish to have their assignments passed through plagiarism detection software, they should contact the in-
structor for an alternative. Please note, that code not passed through plagiarism detection software will necessarily
receive closer scrutiny. https://cdn.dal.ca/content/dam/dalhousie/pdf/dept/university_
secretariat/policy-repository/OriginalitySoftwarePolicy.pdf
Student Health and Wellness
Taking care of your health is important. As a Dalhousie student, you have access to a wide range of resources to support
your health and wellbeing. Students looking to access physical or mental health & wellness services at Dalhousie can
go to the Student Health & Wellness Centre in the LeMarchant Building. The team includes: registered nurses, doctors,
counsellors and a social worker. Visit dal.ca/studenthealth to learn more and book an appointment today.
Students also have access to a variety of online mental health resources, including telephone/texting counselling
and workshops/training programs. Learn more and access these resources at dal.ca/mentalhealth.
5
Culture of Respect
Every person has a right to respect and safety. We believe inclusiveness is fundamental to education and learning.
Misogyny and other disrespectful behaviour in our classrooms, on our campus, on social media, and in our community
is unacceptable. As a community, we must stand for equality and hold ourselves to a higher standard.
What we all need to do 1:
1. Be Ready to Act: This starts with promising yourself to speak up to help prevent it from happening again.
Whatever it takes, summon your courage to address the issue. Try to approach the issue with open-ended
questions like “Why did you say that?” or “How did you develop that belief?”
2. Identify the Behaviour: Use reflective listening and avoid labeling, name-calling, or assigning blame to the
person. Focus the conversation on the behaviour, not on the person. For example, “The comment you just made
sounded racist, is that what you intended?” is a better approach than “You’re a racist if you make comments like
that.”
3. Appeal to Principles: This can work well if the person is known to you, like a friend, sibling, or co-worker. For
example, “I have always thought of you as a fair-minded person, so it shocks me when I hear you say something
like that.”
4. Set Limits: You cannot control another person’s actions, but you can control what happens in your space. Do
not be afraid to ask someone “Please do not tell racist jokes in my presence anymore” or state “This classroom is
not a place where I allow homophobia to occur.” After you have set that expectation, make sure you consistently
maintain it.
5. Find or be an Ally: Seek out like-minded people that support your views, and help support others in their
challenges. Leading by example can be a powerful way to inspire others to do the same.
6. Be Vigilant: Change can happen slowly, but do not let this deter you. Stay prepared, keep speaking up, and do
not let yourself be silenced.
University Statements
This course is governed by the academic rules and regulations set forth in the University Calendar and the Senate.
https://academiccalendar.dal.ca/Catalog/ViewCatalog.aspx?pageid=viewcatalog&catalogid=69&
chapterid=3457&loaduseredits=False
Territorial Acknowledgement
Dalhousie University is located in Mi’kma’ki, the ancestral and unceded territory of the Mi’kmaq. We are all
Treaty people.
Dalhousie acknowledges the histories, contributions, and legacies of the African Nova Scotia people and com-
munities who have been here for over 400 years.
Internationalization
At Dalhousie, ‘thinking and acting globally’ enhances the quality and impact of education, supporting learning
that is “interdisciplinary, cross-cultural, global in reach, and orientated toward solving problems that extend
across national borders.”
https://www.dal.ca/about-dal/internationalization.html
Academic Integrity
At Dalhousie University, we are guided in all of our work by the values of academic integrity: honesty, trust,
fairness, responsibility and respect. As a student, you are required to demonstrate these values in all of the work
you do. The University provides policies and procedures that every member of the university community is
1Source: Speak Up! ©2005 Southern Poverty Law Center. First Printing. This publication was produced by Teaching Tolerance, a project of
the Southern Poverty Law Center. Full ”Speak Up” document found at: http://www.dal.ca/dept/dalrespect.html Revised by Susan
Holmes from a document provided April 2015 by Lyndsay Anderson, Manager, Student Dispute Resolution, Dalhousie University 902.494.4140
lyndsay.anderson@dal.ca www.dal.ca/think.
6
required to follow to ensure academic integrity.
(read more: http://www.dal.ca/dept/university_secretariat/academic-integrity.html)
Accessibility
The Student Accessibility Centre is Dalhousie’s centre of expertise for matters related to student accessibility
and accommodation. If there are aspects of the design, instruction, and/or experiences within this course (online
or in-person) that result in barriers to your inclusion please contact:
https://www.dal.ca/campus_life/academic-support/accessibility.html
for all courses offered by Dalhousie with the exceptionof Truro.
Conduct in the Classroom — Culture of Respect
Substantial and constructive dialogue on challenging issues is an important part of academic inquiry and ex-
change. It requires willingness to listen and tolerance of opposing points of view. Consideration of individual
differences and alternative viewpoints is required of all class members, towards each other, towards instructors,
and towards guest speakers. While expressions of differing perspectives are welcome and encouraged, the words
and language used should remain within acceptable bounds of civility and respect.
Diversity and Inclusion — Culture of Respect
Every person at Dalhousie has a right to be respected and safe. We believe inclusiveness is fundamental to
education. We stand for equality. Dalhousie is strengthened in our diversity. We are a respectful and inclusive
community. We are committed to being a place where everyone feels welcome and supported, which is why our
Strategic Direction prioritizes fostering a culture of diversity and inclusiveness (Strategic Priority 5.2).
(read more:http://www.dal.ca/cultureofrespect.html)
Student Code of Conduct
Everyone at Dalhousie is expected to treat others with dignity and respect. The Code of Student Conduct allows
Dalhousie to take disciplinary action if students don’t follow this community expectation. When appropriate,
violations of the code can be resolved in a reasonable and informal manner—perhaps through a restorative jus-
tice process. If an informal resolution can’t be reached, or would be inappropriate, procedures exist for formal
dispute resolution.
(read more: https://www.dal.ca/dept/university_secretariat/policies/student-life/code-of-student-conduct.
html)
Fair Dealing Policy
The Dalhousie University Fair Dealing Policy provides guidance for the limited use of copyright protected
material without the risk of infringement and without having to seek the permission of copyright owners. It
is intended to provide a balance between the rights of creators and the rights of users at Dalhousie. (read more:
https://www.dal.ca/dept/university_secretariat/policies/academic/fair-dealing-policy-.
html)
Originality Checking Software
The course instructor may use Dalhousie’s approved originality checking software and Google to check the
originality of any work submitted for credit, in accordance with the Student Submission of Assignments and
Use of Originality Checking Software Policy. Students are free, without penalty of grade, to choose an alterna-
tive method of attesting to the authenticity of their work, and must inform the instructor no later than the last
day to add/drop classes of their intent to choose an alternate method. (read more: https://www.dal.ca/dept/
university_secretariat/policies/academic/student-submission-of-assignments-and-use-of-originality-checking-software-policy-.
html)
Student Use of Course Materials
These course materials are designed for use as part of the CSCI courses at Dalhousie University and are the
property of the instructor unless otherwise stated. Third party copyrighted materials (such as books, journal
articles, music, videos, etc.) have either been licensed for use in this course or fall under an exception or
limitation in Canadian Copyright law. Copying this course material for distribution (e.g. uploading material to
a commercial third party website) may lead to a violation of Copyright law.
Learning and Support Resources
Please see https://www.dal.ca/campus_life/academic-support.html