Show/hide main menu

Modules

5CCS2FC2 Foundations of Computing II

Credit value: 15

Lecturer: Dr Christopher Hampson  (office hours)
Semester: 2 (Semester 1 from 2018-19)
Teaching pattern: weekly 2-hour lecture and 1-hour small-group tutorial (mandatory attendance)

Assessment 

Formative assessment: weekly exercise sheets

Learning aims & outcomes

To introduce the basic concepts of computational mathematics which are needed in other modules.

After studying this module, you will be able to reason about solvability and complexity of problems; model and solve practical problems by using the taught methods and design efficient algorithms for different problems in computer science.

Syllabus
 

Computational Models and Complexity:

  • Turing Machines
  • Decidability and recognisability
  • Mapping reductions
  • Complexity classes: P, NP, co-NP
  • Polynomial reductions
  • NP-completeness, SAT, and examples of classic NP-complete problems

Graph algorithms:

  • Graph traversal algorithms DFS and BFS
  • Algorithms based on DFS: Minimum spanning trees, topological sort, strongly connected components and an algorithm for finding maximal strongly connected components, Dijkstra's shortest paths in a graph algorithm

Algorithmic approaches and techniques:

  • Greedy algorithms
  • Dynamic programming
  • Divide and conquer (recurrence relations + analysis via Master Theorem)
  • Mixed integer-linear programming (MILP)
  • Branch and bound for MILP
  • Approximation ratio + examples of approximable and unapproximable problems
  • Efficient SAT solving (DPLL)
  • Local search: neighbourhoods and local minima
  • Relaxation heuristics

 


Suggested Reading and Resources (Link to MyReadingLists)

 


22 February 2018
Sitemap Site help Terms and conditions  Privacy policy  Accessibility  Modern slavery statement  Contact us

© 2018 King's College London | Strand | London WC2R 2LS | England | United Kingdom | Tel +44 (0)20 7836 5454