ENG 515A Lecture Notes - Mohammad Ali Jinnah University, Travelling Salesman Problem, Theoretical Computer Science
CS Freshman Seminar:Mr.Shahid Hussain
aj03471
September 2017
1 Introduction:
Shahid Hussain,Bachelors in Computer science from Mohammad Ali Jinnah
University,Masters in Computer science from King Fahd University of Petroleum
and Minerals,Phd in Computer science from King Abdullah University of Sci-
ence and Technology,discussed some insights of theoretical computer science.His
work involves databases and algorithms as well.Now,he works at Habib Uni-
versity as an assistant professor.His work on decision tree construction and
optimization and especially multi-stage and bi-criteria optimization have led
to many different applications in various fields such as machine learning/data
mining and knowledge representation, analysis of Boolean functions, diagnosis
of faults in circuits,etc.His research interests are: design and analysis of efficient
algorithms, graph theory, discrete and combinatorial optimization, and machine
learning/data mining.[1]
2 Theoretical Computer Science-TCS:
Theoretical computer science, or TCS, is a subset of general computer science
and mathematics that focuses on more mathematical topics of computing and
includes the theory of computation.[2]
3 A simple map:
The term map is used to mean a function, sometimes with a specific property
of particular importance to that branch. For instance, a ”map” is a continuous
function in topology, a linear transformation in linear algebra, etc.
3.1 The map problem-Travelling Salesperson problem:
The Travelling Salesman Problem (often called TSP) is a classic algorithmic
problem in the field of computer science. It is focused on optimization.
The travelling salesman problem (TSP) asks the following question: ”Given
a list of shops and the distances between each pair of shops, what is the shortest
possible route that visits each shop exactly once and returns to the origin shop?”
1
Document Summary
Shahid hussain,bachelors in computer science from mohammad ali jinnah. Theoretical computer science, or tcs, is a subset of general computer science and mathematics that focuses on more mathematical topics of computing and includes the theory of computation. The term map is used to mean a function, sometimes with a speci c property of particular importance to that branch. For instance, a map is a continuous function in topology, a linear transformation in linear algebra, etc. The travelling salesman problem (often called tsp) is a classic algorithmic problem in the eld of computer science. For example,suppose there are six points(a,b,c,d,e,f) and we need to. Nd the shortest possible route. in this case,one of the shortest routes could be c,b,e,f,a,d with a total distance of 170. It is the theoretical problem of determining whether a computer program will halt (produce an answer) or loop forever on a given input.
