Scribd
Upload
6 views

Computational Thinking Project Notes

Singapore Management University Computational Thinking Project Notes

Uploaded by

Xin Yi
Copyright
© © All Rights Reserved
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
6 views

Computational Thinking Project Notes

Singapore Management University Computational Thinking Project Notes

Uploaded by

Xin Yi
Copyright
© © All Rights Reserved
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 10

NP vs P/ Intractable vs Tractable

Most intractable problems have an algorithm to solve them (the same algorithm) which is the
brute force algorithm. The reason there is no efficient algorithm for these problems is that
they are so close to random. [source]
Backtracking:

Questions for consultation:


- What does it mean when all problems in P can be transformed to NP?
- What is the difference between topological sorting and merge sort/ insertion sort?
- What is the point of reducing/ mapping an NP hard problem to another NP hard
problem?
- How can a problem become computationally intractable? (problem e.g. from mock
paper)
- Can you go over topological sorting again? (problem e.g. from mock paper)
Question 21 from mock paper 1, qn22, qn23
Proj
For a knowledge graph consisting of users, items, objects and their relationship
weights, when given a starting user and an end item, you are required to find path(s)
with a high path score between the starting user and the end item. Your algorithm
will return the path score and the corresponding path(s). If there are more than one
path with the same high score, you should return all such paths.

The knowledge graph (KG) represents a collection of interlinked descriptions of


entities – real-world objects and events, or abstract concepts (e.g., documents) –
where:

● Descriptions have formal semantics that allow both people and computers to
process them in an efficient and unambiguous manner;
● Entity descriptions contribute to one another, forming a network, where each
entity represents part of the description of the entities, related to it, and
provides context for their interpretation.

the real power of knowledge graphs comes when we transform our own data into
RDF triples and then connect our proprietary knowledge to open global knowledge.

https://www.ontotext.com/knowledgehub/fundamentals/what-is-a-knowledge-
graph/

What is RDF?
RDF is a standard for data interchange that is used for representing highly
interconnected data. Each RDF statement is a three-part structure consisting of
resources where every resource is identified by a URI. Representing data in RDF
allows information to be easily identified, disambiguated and interconnected by AI
systems.

https://www.ontotext.com/knowledgehub/fundamentals/what-is-rdf/

What is a triple?
How to find the max value path?

https://stackoverflow.com/questions/15559950/tree-graph-traversal-find-maximum-
value-path

https://www.techiedelight.com/maximum-cost-path-graph-source-destination/- has
code

https://www.geeksforgeeks.org/find-longest-path-directed-acyclic-graph/- has code

https://www.khanacademy.org/computing/computer-science/algorithms/breadth-
first-search/a/the-breadth-first-search-algorithm

Using UCS:

Dijkstra's algorithm searches for shortest paths from root to every other node in a graph,
whereas uniform-cost searches for shortest paths in terms of cost to a goal node.

https://www.youtube.com/watch?v=dRMvK76xQJI

https://www.youtube.com/watch?v=-FY7t2kqWX4

https://www.youtube.com/watch?v=Z7_A3Ih-VjY

Using A*:
Resources
Youtube tutorials- Gerry Jenkins
Textbook resource! (easy to digest chapters)
8 Time Complexities
Notes- graphs
Use adjacency list instead of adjacency matrix for sparse graphs
Adjacency matrices:
Index to look up a row is the from vertex
Index for the column is the to vertex
For vertices with connections, the weight is stored in the cell of the intersection
Undirected graphs need two entries for every edge
Adjacency lists:
you have a vertex object containing info about the vertex (its ID) along with a dictionary of
edges to other vertices

Undirected vs directed graphs: for undirected graphs, you need two entries for each
connection

Precedence or dependency relationship


Directed edges indicate direction of dependency
A to B relationship indicate that B depends on A
Cycles in such settings may be problematic

Directed Acyclic graphs


No cycles

Topological graphs & topological sorting


Topological ordering: a sequence or permutation where all edges point forward
For every edge in G, the source vertex appears before the target
Everyone DAG has at least one topological ordering
Trees
Balanced trees
By using a well-balanced tree, it's possible to ensure that all decisions can be made
with a small number of yes/no questions.
Notes
LInear Algorithm

Polynomial algorithm

Exponential algorithm

Optimization and the Knapsack Problem

What is an optimization model?


An objective function that is either to be minimized or maximized
A set of constraints

Hard to solve in a computational complexity sense-can run for a really long time
Therefore, we often use a greedy algorithm to find a solution that is good enough rather than
the optimal solution

Should we use greedy algorithms?


Easy to implement
Computationally efficient
But you won’t know how good the approximation of the locally optimal solution is
Wk 11 Heuristics
1. The travelling salesman Problem (TSP)
have to make a roundtrip tour of a number of places
If there aren’t too many places to be visited, the optimal path is usually a loop. Any crossing
would usually be a longer path than the optimal
Applications:
Transportation and logistics: school bus routes, delivering meals
Manufacturing: drilling holes in a circuit board by robots (minimize metal used)
Communications: telecommunications networks
Number of possible tours:
Exhaustive search (if direction doesn’t matter): (n-1)!/2-- grows quickly
Why that formula?) Any circular shift in order has the same distance (divide permutations by
number of “cities”?)-- n!/n
If the direction doesn’t matter, further divide the permutations by 2: n!/(n*2)
n!/(n*2)=(n-1)/2
Assumptions: round trip; symmetric distance
Need to know whether a path is a “one-way street”; does going the other way require a
detour?

What is a computational intractable problem?

Initial strategies for solving TSP


Eyeballing, exhaustive search, random search (issue: may generate bad routes)
All the above have issues. How to get around this?
Approach it as an optimization problem.
AN optimization problem is associated with an objective function. For any solution, the
objective function evaluates a value. The value indicates the goodness of this solution. The
goal is to obtain the solution with as optimal a value as possible.
Criteria for algos for optimization problems
● Fast- runs in polynomial time complexity
● General- works well on all instances of the problem
● Optimal- finds the exact optimal solution
However, This is the ideal case. We can’t get all three. We need to pick two
General + optimal: slow; e..g. Brute force
Fast + optimal: may not cover all cases?
Fast+general: good enough? Use heuristic strategies!

Heuristic techniques
- Makes a series of decisions in sequential steps
- At every step, make the best decision for the current step
- Local decision do not guarantee best global solution

Greedy algo: construct the step by step solution, only optimize one step at a time; maximize
for short term gain
Local search algo: start with a feasible solution; at every step, make a small modification to
the solution

Questions:
What were the tricks used to limit the paths (the e.g. about visiting many cities in the US)

Heuristic techniques
1st greedy algo for TSP
Pseudocode:
Let S be the set of cities; T- initial tour of one city picked randomly
Remove this first city from from S
While there are still cities in S:
Find the city x in S with the smallest distance to the last selected city & remove x from S

2nd greedy algorithm


Let S be the set of cities to be included in the tour. Let T be the initial tour of 2 cities with the
closest distance. Remove these 2 cities from S.
While there are still cities in S:
Find the city x in S with the smallest distance to any city y in the current tour T
Choose the one with lower overall distance: 1) insert x between y and its next destination z
in T 2) insert x between y and its previous destination u in T
Remove x from S

When there are 3 items, it doesn’t matter which option you pick (because they are just
different versions of the same path)

Local Search Algo


A complementary strategy to the greedy algo is the local search algo.
Start with an arbitrary complete solution (e..g random or greedy solution) and then iteratively
amek small modifications to the solution to improve the value.
Advantages:
Can run as many iterations as we can afford to and we always have a complete solution.
More-> likely to get closer to optimal value.
Disadvantage: If the starting solution turns out to be bad, it may need many iterations to get
a good solution.
1. Define a neighborhood
2. Current solution
3. Generate neighborhood
4. Evaluate neighborhood
2 opt neighborhood: delete two edges add 2 edges to restore the tour (remove the crossings
of edges in a tour)
N choose two ways to choose two edges each time
2 opt complexity:
N(N-1-2)/2= N(N-3)/2= O(N^2) for each iteration; for k iterations: O(kN^2)
-1: the edge itself
-2: cannot pick adjacent edges to the edge you pick
/2: two ways to pick the same pair-- picking the same pair gives you the same change in
path
Python implementation:
two_opt(sequence, graph)
Others:
Genetic algorithm-Improving solutions with evolution
Solutions mate and exchange their genes
Mutating genes every now and then
Simulated Annealing- as you keep improving, jump to different starting point to see if you
can improve further
Linear Program- use continuous approach first and then round

You might also like