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

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.

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.

An undergraduate course on the design and analysis of algorithms.

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

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 |

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

Date
| Time
| Place |

Monday, December 2, 2019 | 12:00 - 2:00 | Goodwin 521 |

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.