Fundamentals of Computing

MSc-PGDip in Computer Science (2017-18)


Lecturers:   Lectures:   Tutorials with Dr Stanislav Kikot:   Extra tutorials:   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. 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")
  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
    Extra tutorial 1: questions and answers
    Extra tutorial 2: 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. The halting problem. Undecidable problems. slides Video
    Tutorial 5: questions and answers
    Tutorial 6: questions and answers
  10. Data structures: representations and operations.
  11. Lists, trees, forests, binary trees.
  12. Tree traversal and other operations; binary search trees.
  13. Organisation of disk storage; methods of file organisation; B-trees.
  14. Algorithms: design and analysis; algorithmic complexity; space utilisation.
  15. Sorting and searching.


Course Notes


Exercises

Questions-10 and answers
Questions-17 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