King's College London
Area of Study
Computer Programming, Computer Science, Information Sciences
Taught In English
Course Level Recommendations
ISA offers course level recommendations in an effort to facilitate the determination of course levels by credential evaluators.We advice each institution to have their own credentials evaluator make the final decision regrading course levels.
Recommended U.S. Semester Credits4
Recommended U.S. Quarter Units6
Hours & Credits
To introduce various discrete optimisation problems, efficient algorithms for solving these problems, and general
algorithmic techniques which can be applied to a wide range of optimisation problems. The emphasis is put on
network optimisation problems and on general optimisation techniques. To discuss applications of optimisation
problems in communication systems, computer networks, manufacturing, scheduling, and resource allocation.
Students who successfully complete this module will be able to express computational problems from various
application areas as (discrete) optimisation problems; will be familiar with commonly used algorithms and main
algorithmic techniques for optimisation problems; will be able to select an appropriate algorithm for a given
optimisation problem or to develop a new algorithm based on a general algorithmic technique; will be familiar with
the running time of the discussed algorithms; will be aware of the principles underpinning the discussed
Single-source shortest-paths problem:
The Bellman-Ford algorithm
Shortest paths in directed acyclic graphs
All-pairs shortest paths:
Network flow problems:
Maximum flows, Minimum-cost flows, Multicommodity flows
Maximum matching problem
The Ford-Fulkerson method for the maximum-flow problem
The Successive-shortest-paths algorithm for the minimum-cost flow problem
Linear programming (LP):
Basic properties of LP problems
LP formulation of network flow problems
Computationally hard optimisation problems:
Polynomial-time problems and NP problems
NP-hard optimisation problems
Optimisation techniques for NP-hard problems:
Branch-and-bound method for finding exact solutions
Courses and course hours of instruction are subject to change.
Eligibility for courses may be subject to a placement exam and/or pre-requisites.
Some courses may require additional fees.
Credits earned vary according to the policies of the students' home institutions. According to ISA policy and possible visa requirements, students must maintain full-time enrollment status, as determined by their home institutions, for the duration of the program.
Please reference fall and spring course lists as not all courses are taught during both semesters.
Please note that some courses with locals have recommended prerequisite courses. It is the student's responsibility to consult any recommended prerequisites prior to enrolling in their course.