Lectures: 4:00pm -- 4:50pm Monday/Wednesday/Friday in EN-2007
Instructor: Antonina Kolokolova
Office: ER-6033
Instructor office hours: TBD or by appointment
Communication: We will use Brightspace course shell for course materials, discussions, and, most importantly, for the announcements. To get the announcements promptly (that is, in your email), please subscribe to notifications.
Email: kol@mun.ca.
Textbook: There will be no required textbook for this course; slides will be posted.
That said, we will mostly follow Michael Sipser's "Intro to the theory of computation" (3rd edition preferred, 2nd OK).
For more advanced material we might use Sanjeev Arora and Boaz Barak "Computational complexity: a modern approach" and research papers. .
Marking scheme ( tentative! ):
Note that the last test and some presentations might be during the last week or two of the semester.
Missed work. If you cannot come to class on the day of a written test, email me as soon as possible (no later than 2 days after, if circumstances allow). If you miss one written test, your mark will be based on the other three; there will be no make-up tests. If you miss an oral exam, it can be taken as soon as you are well.
Prerequisites/background
This is one of the most abstract/conceptual courses in our curriculum. There will be no implementations, some pseudocode, and a lot of proofs. It will mostly build upon the material and skills from COMP 1002 (formulas, circuits, proofs), and the non-programming parts of COMP 1003 (finite automata, Turing machines and the Halting problem), as well as the basic knowledge of algorithms and data structures at the extent of COMP 2002 . Overall, expect to spend more time thinking and less time writing.
Tentative course description
What is an algorithm? What does it mean for a problem to be computationally easy, hard or unsolvable? What can be solved by a computer with only small finite memory or by circuits of a limited size? This course is about what is known and what is open about the power of computation, and its connections to areas from logic (including Gödel's incompleteness theorems) to cryptography. Time permitting, we may touch upon more advanced topics such as complexity of learning, Kolmogorov complexity, communication complexity, and/or quantum computing.
Academic Misconduct:
Students are expected to adhere to those principles which constitute proper academic conduct. A student has the responsibility to know which actions, as described under Academic Offences in the University Regulations, could be construed as dishonest or improper. Students found guilty of an academic offence may be subject to a number of penalties commensurate with the offence including reprimand, reduction of grade, probation, suspension or expulsion from the University. For more information regarding this policy, students should refer to the University Regulations for Academic Misconduct (Section 6.12) in the University Calendar, revisit the INTG 1000 course in Brightspace, or see the undergraduate page about academic integrity.
Academic misconduct for this course includes (but is not limited to) the following:
Handing in any material for evaluation that was not completed entirely by yourself
Obtaining solutions from any non-class source, including, from peers in the course, previous course offerings, stack overflow, and/or LLMs (i.e. ChatGPT, etc.)
Sharing questions and/or solutions on practice problems, drills and tests outside of the course for any reason, including assignment sharing websites (e.g. Chegg), forums (e.g. stack overflow), or online repositories (e.g. GitHub).
Academic Accommodations:
Memorial University of Newfoundland is committed to fostering equitable and accessible learning environments for all students. Accommodations for students with disabilities are provided in accordance with the Accommodations for Students with Disabilities Policy (www.mun.ca/policy/site/policy.php?id=534) and its related procedures. Students who feel that they may require formal academic accommodations to address barriers or challenges they are experiencing related to their learning are encouraged to contact Accessibility Services (the Blundon Centre, www.mun.ca/blundon) at the earliest opportunity to ensure any required academic accommodations are provided in a timely manner. You can contact Accessibility Services (Blundon Centre) by emailing blundon@mun.ca. Students using Blundon services for tests and the final exam are strongly recommended to contact the Blundon Centre at least 3 weeks ahead of the test/exam date to allow for arrangements to be made. Students who are registered with the Blundon Centre are also encouraged to contact the course instructor to discuss accommodations.
Copyright:
All material (lectures, practice problems, labs, tests, exams) delivered or provided by Dr. Antonina Kolokolova, including any visual or audio recording thereof, are subject to copyright. It is prohibited to record or copy by any means, in any format, openly or surreptitiously, in whole or in part, in the absence of express written permission from Dr. Antonina Kolokolova any of the lectures, materials provided or published in any form during or from the course. This includes posting any course content online.
Student support for the course:
Discussion board : You’re encouraged to discuss course material, including practice exercises, with peers on the Brightspace discussion board.
Use the board for clarifications and announcements, and check it regularly.
If you have questions, first check the discussion board to see if they’ve already been addressed. If not, start a new thread under the relevant topic or post in an existing thread if related. Feel free to contribute answers to unanswered questions, as peer explanations can be very helpful.
The Computer Science department runs a Student Help Centre where students can request help with first- and second-year Computer Science lab courses. The Help Centre is located in EN-2026. See the Help Centre Schedule (https://www.mun.ca/computerscience/undergraduates/help-centre-schedule/). This link is also available in the course Brightspace shell.
Any email messages to the instructor should contain COMP3602 in the subject line. Every effort will be made to respond to emails within 48h, with the exceptions of evenings, weekends and holidays.
All students should be aware of the supports that Memorial University offers, which include:
MUNUp is an online hub which hosts supports and services to help all students succeed.
The Academic Advising Centre (SN–4053) serves prospective, first-year, undeclared and students transitioning between programs at the undergraduate level. If you are unsure what you want to study, schedule an appointment with an academic advisor.
The Student Wellness and Counselling Centre (SWCC) (UC–5000) provides counselling, health, and wellness support for students including primary health care, counselling, health promotion, disease prevention, and wellness education. Services are available online and in person.
The Student Experience Office (ASK UC-3005) is a hub to help students:
transition to university life
develop leadership and teamwork skills, and
learn how to get involved through volunteering and experiential learning.
The Indigenous Student Resource Centre (ISRC) (208 Elizabeth Avenue) supports Indigenous students by creating a welcoming community, by providing an engaging and inclusive space, and by offering an array of programs and resources to ensure success. It also assists the non-Indigenous University Community to walk a good path and build positive relationships with Indigenous peoples.
The Internationalization Office provides a variety of programmes to support international students’ transition to MUNL and to our province. To learn more about the Internationalization Office’s supports and services, please connect with their office. There is a staff directory for the Internationalization Office to help you find the supports you are looking for.
For help with finances and funding, there are a number of resources available.
The Student Support Office can provide support to students in distress concerning a financial, academic or personal matter. The Student Support Office can also assist students who wish to raise a concern and seek a resolution to a matter related to their student experience at MUNL. The Student Code of Conduct outlines the expectations of students at Memorial University and provides an avenue to address behaviours that deviate from the Code. The Student Support Offices also coordinates the Non-Academic Appeal procedures for students, who need to raise concerns about a university employee or situation. This process ensures that student complaints are dealt with in a fair and equitable manner.
The Sexual Harassment Office (Earth Sciences E-6038) prevents sexual harassment and sexual assault through education, mitigates the effects of sexual harassment and sexual assault, and identifies methods for timely resolutions of complaints of sexual harassment and sexual assault which may arise at Memorial University. While working towards a resolution of a complaint, the Sexual Harassment Office can coordinate interim accommodations as necessary.
Reach out to the many Student Clubs and Societies which can help you deepen learning in your discipline or pursue your interests outside the classroom and get connected with others.
MUNSU Resource Centres, as follows:
Intersections: A Resource Centre for Marginalized Genders
MUN Sexual and Gender Advocacy Resource Centre (MUN SAGA)
Disability Information & Support Centre (MUN DISC)
International Student Resource Centre (ISC)
The Circle: First Nations, Inuit, & Métis Students Resource Centre
Students Older Than Average (SOTA)
Student Parent Assistance & Resource Centre (SPARC)