This page provides information on the course. It tells you about the instructor, teaching assistant, course schedule, course requirements, and method of grading. It also contains a course description, course material, assignments, and some important dates.
Instructor | |
Selim Akl | akl@cs.queensu.ca |
One on-line sessions per week is scheduled for this course as follows (Kingston, Ontario time):
Section | Day | Time | Place |
CISC-490 and CISC-879 | Thursday | 12:30 p.m. - 1:30 p.m. | Zoom meeting |
The link to the Zoom weekly meeting will be mailed to all students registered in either CISC-490 or CISC-879.
A note from your instructor
Dear CISC-490 and CISC-879 students:
Welcome to Computing Beyond Turing. I am very happy to have you in my class and sincerely hope that you will like the course. While I am sorry that we will not meet in person, I trust that the course material and our online meetings will provide a useful and enjoyable learning experience.
Please note: All my communications with you will be either (1) through this web page or (2) during our weekly meeting, or (3) by email. I do not plan on using any other medium unless circumstances warrant it, in which case I will let you know in advance. (There is an onQ page for the course; however, it's only purpose is to point you to this web page and give you information regarding our class meetings.)
During our weekly meeting I will:
1. Go over the solutions to the week's practice problems.
2. Give a brief slide presentation as an introduction to the papers that you will have to read for the following week.
3. Answer any questions you may have.
If you have concerns not addressed during the weekly meeting, then:
1) If you are a CISC-490 student, please address your questions to the teaching assistant for the course Fraser Raney 1wefr@queensu.ca
2) If you are a CISC-879 student, please send your questions to me.
Here is what you are expected to do in this course:
1. Attend the weekly meeting.
2. Do all the assinments (you do not need to hand in your weekly work).
3. Complete a course project (your mark on the course will be based on this component).
An introduction to computation beyond the Turing machine model. Several topics in the field of unconventional computing are covered, including parallel, quantum, and bio-molecular algorithms, cellular automata, non-standard computational problems, computations in nature, and non-universality in computation. The emphasis is on computational models, design of algorithms and mathematical analysis.
For CISC-490: A minimum grade of B+ in CISC-365 and registration in a Computing plan.
For CISC-879: A minimum grade of B+ in an undergraduate course on the design and analysis of algorithms.
1. Textbook
S.G. Akl, Parallel Computation: Models and Methods, Prentice Hall, Upper Saddle River, New Jersey.
2. Papers:
The papers to read for the assignments are available here.
Week | Starting | Material covered, Assignment for next week (readings and problems to work on) |
1 | Sept 10 | Course overview (schedule, topics, grading method), Introduction to parallel computation, Assignment 1 |
2 | Sept 17 | Models of Computation, Unconventional paradigms and nonuniversality in computation, Assignment 2 |
3 | Sept 24 | Combinational Circuits, The role of time in computation, Assignment 3 |
4 | Oct 1 | Parallel Prefix Computation, Cellular automata, Assignment 4 |
5 | Oct 8 | Divide and Conquer, Sensor networks, Assignment 5 |
6 | Oct 15 | Pointer-Based Data Structures, Quantum computation, Assignment 6 |
7 | Oct 22 | Linear Arrays, Quantum cryptography, Assignment 7 |
8 | Nov 5 | Meshes and Related Models, Nature computes, Assignment 8 |
9 | Nov 12 | Hypercubes and Stars, Information and energy, Assignment 9 |
10 | Nov 19 | Models Using Buses, The meaning of life, Assignment 10 |
11 | Nov 26 | Broadcasting with Selective Reduction, Parallel Synergy, What is compuation?, Assignment 11, Assignment 12 |
12 | Dec 3 | Conclusion: Unconventional computation, current state and future prospects. |
Note: The week of October 26-30 is the Fall mid-term Break. There will be no on-line meeting on October 29, 2020.
Working on the problems and completing the readings are very important: They are essential to a successful completion of the course project.
For your course project, you are required to write (and submit to me by email) a report on a number of papers selected from a list.
The list of papers for the course project will be posted here in the third week of November and removed in the first week of December.
Your report, in PDF format, is due to me by 5 p.m. EST on Friday, December 18, 2020.
CISC-490 students: Select from the list at least two papers, covering different topics. The total length of the selected papers should be at least 30 pages. Your report should be 20 pages long, double spaced in 12pt type and 1 inch margins. The report is to include: a cover page, a one-page summary, the main body, a conclusion, and a list of references. The main body is to include the following parts for each paper you selected: a description of the paper's contents and a critique of the paper (advantages and disadvantages). It can also include any improvenments you could suggest.
CISC-879 students: Select from the list at least three papers, covering different topics. The total length of the selected papers should be at least 40 pages. Your report should be 30 pages long, double-spaced in 12pt type and 1 inch margins. The report is to include: a cover page, a one-page summary, the main body, a conclusion, and a list of references. The main body is to include the following parts for each paper you selected: a description of the paper's contents and a critique of the paper (advantages and disadvantages). It can also include any improvenments you could suggest.
All information about Quantum Chess is available here.
An example illustrating the memory access unit for the Broadcasting with Selective Reduction model of computation is available here.
Available as well is a summary of the texbook.
CISC-490 students, please refer to the following page for some general information
THE QUEEN'S SCHOOL OF COMPUTING IS COMMITTED TO EQUITY, DIVERSITY, INCLUSION, AND INDIGENEITY.