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

Wednesdays 18:0019:30 (parttime students). Location: UCL Roberts 106.

Thursdays 15:3017:00 (fulltime students). Location: Main Building, 403.
Tutorials with Dr Stanislav Kikot:

For MSc DS: Every second Thursday 18:0021:00, first tutorial on 12 October.
Address: UCL Christopher Ingold XLG1 Chemistry LT.

For all others: Every second Tuesday 18:0021:00, first tutorial on 10 October.
Address: UCL Medawar G01 Lankester LT.
Extra tutorials:
 on 16 and 30 November (Thursdays) 18:0021:00.
Address: UCL Christopher Ingold XLG1 Chemistry LT.
If you have questions about the module, please send them via email, or email for an appointment.
Course Structure and Assessment
 15 credits, 33 lecture hours over 22 weeks
 2 assessed courseworks
 written examination in May
 final mark = CW (20%) + exam (80%)
Syllabus and Slides

Digital logic.
slides (Chapter 2 of "Logic and Computer Design Fundamentals")
Solutions to exercises
 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. Bonus: building
circuits
 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")

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 3:
questions and
answers
Extra tutorial 1:
questions and
answers
Extra tutorial 2:
questions and
answers
 Turing machines. slides (Sections 4.1 and 4.2 of "Theory of Computing. A gentle introduction")
Tutorial 4:
questions and
answers
 The halting problem. Undecidable problems.
slides Video
Tutorial 5:
questions and
answers
Tutorial 6:
questions and
answers
 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
To be issued on 8 December 2017. Submission deadline: 19 January 2018; late submission deadline: 2 February 2018.
Answers
Coursework Term 2
Up