Fundamentals of Computing

MSc-PGDip in Computer Science (2017-18)


Lecturers:   Lectures:   Tutorials with Dr Stanislav Kikot:   If you have questions about the module, please send them via email, or email for an appointment.


Course Structure and Assessment


Syllabus and Slides

  1. Digital logic. slides (Chapter 2 of "Logic and Computer Design Fundamentals") Solutions to exercises
  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. Bonus: building circuits
  3. Elements of set theory. slides (Chapter 1 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")
  5. Nondeterministic automata. Determinism vs. nondeterminism. slides (Sections 2.2 and 2.3 of "Theory of Computing. A gentle introduction")
  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 3: questions and answers
  8. Turing machines. slides (Sections 4.1 and 4.2 of "Theory of Computing. A gentle introduction")
    Tutorial 4: questions and answers
  9. Universal Turing machines. slides
  10. The halting problem. Undecidable problems. slides
    Tutorial 5: questions and answers
    Tutorial 6: questions and answers
  11. Data structures: representations and operations.
  12. Lists, trees, forests, binary trees.
  13. Tree traversal and other operations; binary search trees.
  14. Organisation of disk storage; methods of file organisation; B-trees.
  15. Algorithms: design and analysis; algorithmic complexity; space utilisation.
  16. Sorting and searching.


Course Notes


Exercises

Questions and answers

2010 exam paper

2011 exam paper


Coursework Term 1

To be issued on 8 December 2017. Submission deadline: 19 January 2018; late submission deadline: 2 February 2018.

Answers

Coursework Term 2


Up