Fundamentals of Computing

MSc-PGDip in Computer Science (2018-19)


Lecturers:   Lectures:   Tutorials with Abul Hasan and Alan Mosca:   Surgeries with Muawya Eldaw:   If you have questions about the module, please send them via email, or email for an appointment.


Module Structure and Assessment


Courseworks

The aims of the coursework are (i) to give you experience of using the basic notions and techniques introduced in the lectures as well as (ii) to prepare you for the examination. The questions in the courseworks are similar to those discussed in the tutorials. To submit the completed assignment, you should The submitted work MUST have a page entitled "Academic Declaration" by the author, which certifies that the author has read and understood the sections on plagiarism in the document that describes the College's Policy on assessment offences. Confirm that the work is your own, with the work of others fully acknowledged. Submissions must also be accompanied by a declaration giving us permission to submit your report to the plagiarism testing database that the College is using. Reports without a Declaration form are not considered as completed assignments and are not marked. The Academic Declaration should read as follows: "I have read and understood the sections of plagiarism in the College Policy on assessment offences and confirm that the work is my own, with the work of others clearly acknowledged. I give my permission to submit my report to the plagiarism testing database that the College is using and test it using plagiarism detection software, search engines or meta-searching software."

Coursework Term 1

CW1 issued on 8 December 2018. Submission deadline: 21 January 2019; late submission deadline: 28 January 2019.


The maximum mark one can get for a late submission is 50%. If you believe you have good cause to be excused the penalty for late submission, you must make a written request using a mitigating circumstances application form and attach any evidence. Your form should be handed in or emailed to the MSc Programme Administrator as soon as possible, but not more than 10 days after the cut-off deadline. The Department will not accept coursework after this date. As soon as you know that you will not be able to meet the deadline, it will be useful for you to inform the module lecturer and the MSc Programme Director.
For further details concerning the rules and regulations consult College Regulations and Mitigating Circumstances.


Syllabus and Slides

  1. Digital logic. slides (Chapter 2 of "Logic and Computer Design Fundamentals")
  2. Arithmetic for computers. slides Converting decimal to binary is here and here. A brief and gentle introduction to binary numbers is available here. (Sections 1.2-1.4, 4.1-4.3 and 10.7 of "Logic and Computer Design Fundamentals")
    Appendix: a brief history of numbers. slides
    Tutorial 1: questions and answers.
  3. Elements of set theory. Elements of graph theory. slides (Chapters 1 and 10 of "Discrete Mathematics with Applications"; Section 1.4 of "Theory of Computing. A gentle introduction")
    Tutorial 2: questions and answers
  4. Finite state machines (automata). slides (Section 2.1 of "Theory of Computing. A gentle introduction")
    JFLAP is software for experimenting with finite automata, pushdown automata, Turing machines, regular and context-free languages.
  5. Nondeterministic automata. Determinism vs. nondeterminism. slides (Sections 2.2 and 2.3 of "Theory of Computing. A gentle introduction")
    Tutorial 3: questions and answers
  6. Regular languages. slides (Section 2.4 of "Theory of Computing. A gentle introduction")
  7. Context-free languages and pushdown automata. slides (Sections 3.1 and 3.3 of "Theory of Computing. A gentle introduction")
    Tutorial 4: questions and answers
  8. Turing machines. The halting problem. Undecidable problems. slides Video (Sections 4.1 and 4.2 of "Theory of Computing. A gentle introduction")
    Tutorial 5: questions and answers
    Tutorial 6: questions and answers
  9. Turing machines (unabridged version). slides
  10. The Church-Turing thesis (unabridged version). slides
  11. Universal Turing machine. The halting problem. Undecidable problems. (unabridged version) slides
  12. Data structures: representations and operations.
  13. Lists, trees, forests, binary trees.
  14. Tree traversal and other operations; binary search trees.
  15. Organisation of disk storage; methods of file organisation; B-trees.
  16. Algorithms: design and analysis; algorithmic complexity; space utilisation.
  17. Sorting and searching.


Course Notes


Exercises

Questions-10 and answers
Questions-17 and answers

2010 exam paper

2011 exam paper



Up