Last updated: 11 July 2018

Fundamentals of Computing

MSc/PGDip in Computer Science/Data Science/IT/Information Systems & Management 2017/18


Lecturers:   Lectures (Term 2):   Tutorials (optional but highly recommended): Term 2   Alternate Fridays 18:00-21:00 on:
    26 January, 9 February, 23 February, 9 March, 23 March (cancelled).
    Term 3 Tutorial: Friday 27 April.
***Tutorials will be in Malet Street, MAL B35 (except Term 3 tutorial)***

If you have questions about the module, please send them via email, or email or phone for an appointment.


See below for Miniquiz on Stacks and Queues

SEE BELOW FOR QUESTIONS FOR TUTORIAL 1
SEE BELOW FOR ANSWERS FOR TUTORIAL 1
SEE BELOW FOR QUESTIONS FOR TUTORIAL 2
SEE BELOW FOR ANSWERS FOR TUTORIAL 2
SEE BELOW FOR QUESTIONS FOR TUTORIAL 3
SEE BELOW FOR ANSWERS FOR TUTORIAL 3
SEE BELOW FOR QUESTIONS FOR TUTORIAL 4
SEE BELOW FOR ANSWERS FOR TUTORIAL 4
***SEE BELOW FOR ANSWERS FOR 2017 Exam Paper

SEE BELOW FOR MODEL ANSWER FOR ASSIGNMENT Q.6

See below for a note on LIST NOTATION
See below for a simple revision test on Data Structures
(and answers to some of the questions)

Course Structure and Assessment


Syllabus

    Term 1

  1. Digital logic.
  2. Arithmetic for computers.
  3. Elements of set theory. Elements of graph theory.
  4. Finite state machines (automata).
  5. Nondeterministic automata. Determinism vs. nondeterminism.
  6. Regular languages.
  7. Context-free languages and pushdown automata.
  8. Turing machines.
  9. The halting problem. Undecidable problems.
  10. Term 2

  11. Data structures: representations and operations .
  12. Lists; stacks, queues and deques.
  13. Trees, forests, binary trees
  14. Binary tree traversal and other operations. Representation of trees.
  15. Binary search trees.
  16. Organisation of disk storage; methods of file organisation; B-trees.
  17. Algorithms: design and analysis; algorithmic complexity; space utilisation.
  18. Sorting and searching.

Term 2: Data Structures, File Organisation and Algorithms
Course notes and other materials

DATA STRUCTURES

Newer textbooks that use JAVA or PYTHON: Questions for TUTORIAL 1:
    Question 1     Question 6 on FoC exam papers 2009-2016
NOTE: Some of these questions require knowledge of material to be covered in week 3.

ANSWERS for Tutorial 1: 
  Q1   Q6/2009   Q6/2010   Q6/2011   Q6/2012   Q6/2013   Q6/2014   Q6/2015   Q6/2016

Questions for TUTORIAL 2:
    Question 8 on FoC exam papers 2009-2013     Question 9 on FoC exam papers 2009 and 2012
NOTE: Some of these questions refer to a binary tree constructed in an earlier question.
            As you do not have that tree, use instead this binary tree.

ANSWERS for Tutorial 2: 
  Q8/2009   Q8/2010   Q8/2011   Q8/2012   Q8/2013   Q9/2009   Q9/2012
NOTE: These are the answers for the binary trees referred to in the exam paper
            not the binary tree referred to above.
Here is a simple revision test on Data Structures
The questions are easier than those you can expect in the coursework assignment and in the exam.
  ---   and some model answers: here

  • Questions for TUTORIAL 3:
        Questions 7 and 8 on FoC exam papers 2009-2016     Question 9 on FoC exam papers 2009, 2011, 2012
    NOTE: Some of these questions were covered in Tutorial 2 using the binary tree referred to above.
    ANSWERS for Tutorial 3: 
      Q7/2009   Q8/2009   Q7/2010   Q8/2010   Q7/2011   Q8/2011   Q7/2012   Q8/2012   Q7/2013   Q8/2013   Q7/2014   Q8/2014   Q7/2015   Q8/2015   Q7/2016   Q8/2016   Q9/2009   Q9/2011   Q9/2012
  • FILE ORGANISATION


  • Additional Questions from exam papers on File Organisation for TUTORIAL 4:
        2011 Q.10(a);   2013 Q.9(a);   2015 Q.9(a);   2016 Q.9(a) (i) & (iii)
    ANSWERS for Tutorial 4 :  
      Q10/2011   Q9/2013   Q9/2015   Q9/2016
  • ALGORITHMS

    The two lectures on algorithms are based on material from
    "Programming Pearls" by Jon Bentley (2nd edition):

    Maximum subsequence sum problem


    Sorting

    ***MODEL ANSWERS to 2017 EXAM PAPER   Q6/2017   Q7/2017   Q8/2017   Q9a/2017



    Coursework Term 2

    Issued on Wednesday, 21 February 2018
    Submission deadline: Monday, 23 April (before noon)
    Late submission deadline: Monday, 7 May (before noon)
    Return date by Monday, 14 May

  •       Assignment model answer for Q.6