Fundamentals of Computing
MScPGDip in Computer Science (201819)
Lecturers:
Lectures:

Wednesdays 18:0019:30 (parttime students). Location: MAL B34.

Thursdays 15:3017:00 (fulltime students). Location: MAL 404405.
Tutorials with Abul Hasan and Alan Mosca:

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)
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
 15 credits, 33 lecture hours over 22 weeks
 2 assessed courseworks
 written examination in May
 final mark = CW (20%) + exam (80%)
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
 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.
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 metasearching 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 cutoff 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

Digital logic.
slides (Chapter 2 of "Logic and Computer Design Fundamentals")
 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.21.4, 4.14.3 and 10.7 of "Logic and Computer Design Fundamentals")
Appendix: a brief history of numbers.
slides
Tutorial 1:
questions and
answers.
 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
 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 contextfree languages.

Nondeterministic automata. Determinism vs. nondeterminism.
slides (Sections 2.2 and 2.3 of "Theory of Computing. A gentle introduction")
Tutorial 3:
questions and
answers

Regular languages. slides (Section 2.4 of "Theory of Computing. A gentle introduction")
 Contextfree languages and pushdown automata. slides (Sections 3.1 and 3.3 of "Theory of Computing. A gentle introduction")
Tutorial 4:
questions and
answers
 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
 Turing machines (unabridged version).
slides
 The ChurchTuring thesis (unabridged version).
slides
 Universal Turing machine. The halting problem. Undecidable problems. (unabridged version)
slides
 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; Btrees.
 Algorithms: design and analysis; algorithmic complexity; space utilisation.
 Sorting and searching.
Course Notes
 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.

Background reading:

D. Harel with Y. Feldman.
Algorithmics: The Spirit of Computing.
3rd ed., AddisonWesley, 2004. ISBN 0321117840

D. Harel.
Computers Ltd. What They Really Can't Do.
Oxford University Press, 2000. ISBN 0198505558
 You can also use Web resources such as:
Exercises
Questions10 and answers
Questions17 and answers
Up