Fundamentals of Computing
MSc-PGDip in Computer Science (2018-19)
Tutorials with Abul Hasan and Alan Mosca:
Wednesdays 18:00-19:30 (part-time students). Location: MAL B34.
Thursdays 15:30-17:00 (full-time students). Location: MAL 404-405.
Surgeries with Muawya Eldaw:
If you have questions about the module, please send them via email, or email for an appointment.
For MSc Data Science: every second Thursday, UCL Darwin B40 (first tutorial is on 11 October)
For all others: every second Tuesday, MAL B33 (first tutorial is on 9 October)
Module Structure and Assessment
- 15 credits, 33 lecture hours over 22 weeks
- 2 assessed courseworks
- written examination in May
- final mark = CW (20%) + exam (80%)
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."
- upload on Moodle a pdf file with your answers by the deadline indicated below (this is Moodle time not your PC's time; in case you are planning to upload your files whilst at a remote location, make sure you check Moodle's time and take into account time zone differences);
- hand in a hard copy to the Postgraduate Administrator.
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
slides (Chapter 2 of "Logic and Computer Design Fundamentals")
- Arithmetic for computers.
slides Converting decimal to binary is
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.
- 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")
- 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.
Nondeterministic automata. Determinism vs. nondeterminism.
slides (Sections 2.2 and 2.3 of "Theory of Computing. A gentle introduction")
Regular languages. slides (Section 2.4 of "Theory of Computing. A gentle introduction")
- Context-free languages and pushdown automata. slides (Sections 3.1 and 3.3 of "Theory of Computing. A gentle introduction")
- Turing machines. The halting problem. Undecidable problems. slides
Video (Sections 4.1 and 4.2 of "Theory of Computing. A gentle introduction")
- Turing machines (unabridged version).
- The Church-Turing thesis (unabridged version).
- Universal Turing machine. The halting problem. Undecidable problems. (unabridged version)
- Data structures: representations and operations.
- Lists, trees, forests, binary trees.
- Tree traversal and other operations; binary search trees.
- Organisation of disk storage; methods of file organisation; B-trees.
- Algorithms: design and analysis; algorithmic complexity; space utilisation.
- Sorting and searching.
- All the material needed for a successful exam is covered by the slides, web resources below, exercises and coursework.
- Video tutorials.
- The material of the first term is covered by any two textbooks: (1) on computer architecture, and (2) on the theory of computing. (Some of them are available on the Web.) For example:
M. Morris Mano and Charles R. Kime. Logic and Computer Design Fundamentals. Fourth Edition. Pearson, 2008.
S.S. Epp. Discrete Mathematics with Applications. Fourth Edition. Brooks/Cole, 2011.
- Kenneth H. Rosen. Discrete mathematics and its applications. Seventh Edition. McGraw Hill.
D. Patterson and J. Hennessy.
Computer Organization and Design: The Hardware/Software
Interface. Fourth Edition. Morgan Kaufmann, 2008.
H.R. Lewis and C.H. Papadimitriou.
Elements of the Theory of Computation. 2nd Edition, Prentice Hall, 1998.
E. Kinber and C. Smith.
Theory of Computing. A gentle introduction. Prentice Hall, 2001.
D. Harel with Y. Feldman.
Algorithmics: The Spirit of Computing.
3rd ed., Addison-Wesley, 2004. ISBN 0-321-11784-0
Computers Ltd. What They Really Can't Do.
Oxford University Press, 2000. ISBN 0-19-850555-8
- You can also use Web resources such as:
Questions-10 and answers
Questions-17 and answers