<A NAME="title"></A> QUEEN'S UNIVERSITY <BR>

QUEEN'S UNIVERSITY

SCHOOL OF COMPUTING
Computing Beyond Turing
CISC-879
Fall Term 2019
http://www.cs.queensu.ca/home/akl/cisc879/2019/info19.html

This page provides information on the course. It tells you about the instructor, course schedule, and method of grading. It also contains a course description, textbook title, and some important dates. Practice problems can also be found here.

Instructor and Schedule

The instructor of this course is:

Instructor Office E-mail Phone
Selim Akl 722 Goodwin Hall akl@cs.queensu.ca 36062

One session per week is scheduled for this course as follows:

Day Time Place
Monday 1:30 p.m. - 4:00 p.m. Goodwin Hall 521

Office Hours

I will be glad to meet with you any time you need to see me in my office. Please talk to me in class to arrange an appointment.

Back to top

Grading

Your grade is the total of marks obtained on a final exam.

Course Description

The course will cover several topics in the field of unconventional computing, including parallel, quantum, and biomolecular algorithms, cellular automata, non-standard computational problems, computations in nature, and non-universality in computation.

Prerequisite

An undergraduate course on the design and analysis of algorithms.

Back to top

Textbook

S.G. Akl, Parallel Computation: Models and Methods, Prentice Hall, Upper Saddle River, New Jersey.

Calendar

Week Date Material covered, Practice problems to work on
1 Sept 9 Introduction, Models of Computation, Unconventional paradigms, Assignements 1 and 2
2 Sept 16 Combinational Circuits, Non-universality in computation, Assignment 3
3 Sept 23 Parallel Prefix Computation, The role of time in computation, Assignment 4
4 Sept 30 Divide and Conquer, Cellular automata, Assignment 5
5 Oct 7 Pointer-Based Data Structures, Sensor networks, Assignment 6
6 Oct 21 Linear Arrays, Quantum computation and quantum cryptography, Assignment 7
7 Oct 28 Meshes and Related Models, Quantum computing in nature, Assignment 8
8 Nov 4 Hypercubes and Stars, Information and energy, Assignment 9
9 Nov 11 Models Using Buses, The meaning of life, Assignment 10
10 Nov 18 Broadcasting with Selective Reduction, Parallel Synergy, What is compuation?, Assignments 11 and 12
11 Nov 25 Unconventional Computation

Back to top

Practice Problems and Readings

Below is a list of problems from the textbook. Solutions to these problems will be presented in class. There are also papers to read from the references.

  1. Assignment 1: Problem 1.16. Papers 1, 2 and 36.
  2. Assignment 2: Problems 2.6, 2.8, and 2.9. Papers 3 and 15.
  3. Assignment 3: Problem 3.22. Papers 12 and 4.
  4. Assignment 4: Problems 4.20 and 4.22. Papers 10 and 11.
  5. Assignment 5: Problem 5.16. Paper 7.
  6. Assignment 6: Problem 6.4. Papers 6 and 8.
  7. Assignment 7: Problems 7.6 and 7.15. Papers 17 and 18.
  8. Assignment 8: Problems 8.10, 8.12, 8.15, 8.16 and 8.26. Papers 14 and 19.
  9. Assignment 9: Problems 9.2 and 9.7. Papers 21 and 22.
  10. Assignment 10: Problems 10.4, 10.16, 10.24, 10.26 and 10.45. Papers 24, 25, and 31.
  11. Assignment 11: Problems 11.6, 11.9 and 11.12. Papers 30 and 32.
  12. Assignment 12: Problems 12.17 and 12.23. Paper 35.

Back to top

Final

This will be a two-hour written, `closed-book', exam. No electronic devices will be allowed. The details are as follows:

Date Time Place
Monday, December 2, 2019 12:00 - 2:00 Goodwin 521

Recommended reading

An example illustrating the memory access unit for the Broadcasting with Selective Reduction model of computation is available here.

A list of references is available here, as well as a summary of the texbook.

Back to top