QUEEN'S UNIVERSITY

QUEEN'S UNIVERSITY

SCHOOL OF COMPUTING

Computing Beyond Turing

CISC-490 Topics in Computing Science
CISC-879 Topics in Theoretical Computing
Fall Term 2020

http://www.cs.queensu.ca/home/akl/cisc490-cisc879/2020/info20.html

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 and Schedule

The instructor of this course is:

Instructor E-mail
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.

Additional Help

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.

Back to top

Grading

Your grade for this course is the mark obtained on a course project as described further down.

Course Requirements

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).

Course Description

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.

Prerequisite

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.

Back to top

Course Material

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.

Calendar

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.

Back to top

Readings and Practice Problems

Below is a list of sections to read and problems to work on from the textbook. Solutions to these problems will be presented at our online meetings. There are also papers to read for each assignment; these are available here.

Working on the problems and completing the readings are very important: They are essential to a successful completion of the course project.

  1. Assignment 1:   Read Sections 1.1-1.4, solve problem 1.16. Read papers 1, 2, and 36.
  2. Assignment 2:   Read Sections 2.1-2.4, solve problems 2.6, 2.8, (and problem 2.9 for CISC-879 students only). Read papers 3, 15, and 37.
  3. Assignment 3:   Read Sections 3.1-3.4, solve problem 3.22. Read papers 12 and 4.
  4. Assignment 4:   Read Sections 4.1-4.8, solve problem 4.20 (and problem 4.22 for CISC-879 students only). Read papers 10, 11, 38 and 39.
  5. Assignment 5:   Read Sections 5.1-5.4, solve problem 5.16. Read papers 7, 21 and 22.
  6. Assignment 6:   Read Sections 6.1-6.3, solve problem 6.4. Read papers 6, 8 and 27.
  7. Assignment 7:   Read Sections 7.1-7.3, solve problem 7.6 (and problem 7.15 for CISC-879 students only). Read papers 17, 18 and 40.
  8. Assignment 8:   Read Sections 8.1-8.3, solve problem 8.12 (and problem 8.15 for CISC-879 students only). Read papers 14 and 41.
  9. Assignment 9:   Read Sections 9.1-9.2, solve problem 9.2 (and problem 9.7 for CISC-879 students only). Read papers 24, 25, and 31.
  10. Assignment 10: Read Sections 10.1-10.3, solve problem 10.16 (and problem 10.45 for CISC-879 students only). Read paper 19.
  11. Assignment 11: Read Sections 11.1-11.3, solve problem 11.6 (and problem 11.9 for CISC-879 students only). Read papers 30 and 32.
  12. Assignment 12: Read Sections 12.1-12.6, solve problem 12.17 (and problem 12.23 for CISC-879 students only). Read papers 28 and 35.

Back to top

Slide Presentations

Slide presentations will appear here after our meeting every week.
  • September 10
  • September 17
  • September 24
  • October 1
  • October 8
  • October 15
  • October 22
  • An exercise for the fall break

    Solutions To Assignment Problems

    Solutions will appear here after our meeting every week.
  • Assignment 1
  • Assignment 2
  • Assignment 3
  • Assignment 4
  • Assignment 5
  • Assignment 6

    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 after 48 hours.

    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.

    Recommended Additional Reading

    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

    Back to top

    THE QUEEN'S SCHOOL OF COMPUTING IS COMMITTED TO EQUITY, DIVERSITY, INCLUSION, AND INDIGENEITY.