Fundamentals of Computing
MSc-PGDip in Computer Science (2017-18)
Tutorials with Dr Stanislav Kikot:
Wednesdays 18:00-19:30 (part-time students). Location: UCL Bedford Way G03.
Thursdays 15:30-17:00 (full-time students). Location: Main Building, 403.
If you have questions about the module, please send them via email, or email for an appointment.
For MSc DS: Every second Thursday 18:00-21:00, first tutorial on 12 October.
Address: UCL Christopher Ingold XLG1 Chemistry LT.
For all others: Every second Tuesday 18:00-21:00, first tutorial on 10 October.
Address: UCL Medawar G01 Lankester LT.
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
slides (Chapter 2 of "Logic and Computer Design Fundamentals")
Solutions to exercises
- 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.
answers. Bonus: building
- Elements of set theory. slides (Chapter 1 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")
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. slides (Sections 4.1 and 4.2 of "Theory of Computing. A gentle introduction")
- Universal Turing machines.
- The halting problem. Undecidable problems.
- 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. 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.
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 and answers
To be issued on 8 December 2017. Submission deadline: 19 January 2018; late submission deadline: 2 February 2018.
Coursework Term 2