Comment 1:
Are there other algorithms to find the shortest path that use recursion or dynamic programming?
Follow-up:
Yes there is one called Floyd-Warshall algorithm that uses dynamic programming to find all-pairs
shortest paths. This algorithm can also handle graphs with negative link weights.
Comment 2:
What happens in the shortest path greedy algorithm (i.e., Dijkstra) when two distances surrounding the node are equal?
Follow-up:
Good observation. We will usually just “randomly” choose one to break the tie.
Comment 3:
Any technical and systematic ways to calculate the time-complexity of an algorithm?
Follow-up:
Yes sure. For more complicated situation, we usually end up having a bunch of summations of series in the counting of number of key steps. Then, we will need to use some mathematical tools to obtain closed-form expressions. These are computer science topics, though.
Comment 5:
If 3G and Wi-Fi on my smartphone are similar things, why do I notice a significant difference between the speed of loading the same page on 3G and Wi-Fi?
Follow-up:
3G and Wi-Fi are similar in that they are both wireless communication technologies. But the similarity ends there. The wireless communication mechanisms used are highly different in many aspects. For example, 3G is based on cellular communication which is designed for longer range and thus, speed is lower (as electromagnetic signals deteriorate significantly over a distance). Wi-Fi is of a much shorter range and can therefore afford to provide a higher speed. There are many other technical differences, which are topics of a wireless communication and networking course.
Comment 6:
The “shortest path algorithm” can be demo-ed on 9 slides with animation instead of using just one slide. It is a bit too small.
Follow-up:
Thanks for the comment! You are right! Will improve this. Sorry for the inconvenience.
Comment 7:
How come MapQuest/Google-Map is so fast on a map that has billions of nodes?
Follow-up:
One trick is that MapQuest/Google-Map generally does not do the computations “on-demand”, i.e., they pre-computed many routes which are then stored in the database. When someone posts a query, majority of the routes are pulled out from the database.
Comment 9:
How to resolve the conflict when there is negative weight in the graph when using Dijkstra’s
algorithm?
Follow-up:
Dijkstra’s algorithm fails when there is negative weight in the graph. We will need to use a different technique, e.g., the Bellman-Ford algorithm. See also Comment 1 above.
Comment 10:
You have mentioned that researchers in the field of computer try to giving everything an unique ID (a unique IP address), for example, a microwave oven. However, I don’t really understand why we are going to do so. What are the purposes? If that applies widely, will there be any privacy problems?
Follow-up:
Yes sure I believe there will be significant privacy problems! Maybe you can consider using this as your survey topic?
Comment 11:
How do we obtain (e + n log n) for Dijkstra’s algorithm?
Are there other algorithms to find the shortest path that use recursion or dynamic programming?
Follow-up:
Yes there is one called Floyd-Warshall algorithm that uses dynamic programming to find all-pairs
shortest paths. This algorithm can also handle graphs with negative link weights.
Comment 2:
What happens in the shortest path greedy algorithm (i.e., Dijkstra) when two distances surrounding the node are equal?
Follow-up:
Good observation. We will usually just “randomly” choose one to break the tie.
Comment 3:
Any technical and systematic ways to calculate the time-complexity of an algorithm?
Follow-up:
Yes sure. For more complicated situation, we usually end up having a bunch of summations of series in the counting of number of key steps. Then, we will need to use some mathematical tools to obtain closed-form expressions. These are computer science topics, though.
Comment 5:
If 3G and Wi-Fi on my smartphone are similar things, why do I notice a significant difference between the speed of loading the same page on 3G and Wi-Fi?
Follow-up:
3G and Wi-Fi are similar in that they are both wireless communication technologies. But the similarity ends there. The wireless communication mechanisms used are highly different in many aspects. For example, 3G is based on cellular communication which is designed for longer range and thus, speed is lower (as electromagnetic signals deteriorate significantly over a distance). Wi-Fi is of a much shorter range and can therefore afford to provide a higher speed. There are many other technical differences, which are topics of a wireless communication and networking course.
Comment 6:
The “shortest path algorithm” can be demo-ed on 9 slides with animation instead of using just one slide. It is a bit too small.
Follow-up:
Thanks for the comment! You are right! Will improve this. Sorry for the inconvenience.
Comment 7:
How come MapQuest/Google-Map is so fast on a map that has billions of nodes?
Follow-up:
One trick is that MapQuest/Google-Map generally does not do the computations “on-demand”, i.e., they pre-computed many routes which are then stored in the database. When someone posts a query, majority of the routes are pulled out from the database.
Comment 9:
How to resolve the conflict when there is negative weight in the graph when using Dijkstra’s
algorithm?
Follow-up:
Dijkstra’s algorithm fails when there is negative weight in the graph. We will need to use a different technique, e.g., the Bellman-Ford algorithm. See also Comment 1 above.
Comment 10:
You have mentioned that researchers in the field of computer try to giving everything an unique ID (a unique IP address), for example, a microwave oven. However, I don’t really understand why we are going to do so. What are the purposes? If that applies widely, will there be any privacy problems?
Follow-up:
Yes sure I believe there will be significant privacy problems! Maybe you can consider using this as your survey topic?
Comment 11:
How do we obtain (e + n log n) for Dijkstra’s algorithm?
Follow-up:
A rough sketch as follows: We need to examine all the links (during the updating of the estimated distances labelled on the nodes) so that is why we have the e term. We need to sort the nodes in an increasing order of estimated distances and that is why we have the n log n term.
Comment 12:
Why greedy approach usually results in a fast algorithm?
Follow-up:
This is because as we make a greedy choice in each step, we reduce the problem size by 1. Thus, after making n greedy choices (i.e., n steps), we will finish the problem. Consequently, we usually end up having an algorithm that takes O(n) time, together with the time needed in some pre-processing (e.g., sorting, which takes another n log n time).
Comment 13:
Knapsack problem. It can e applied to daily life. Is it similar to linear programming taught in Maths at cert level?
Follow-up:
Yes it is similar. Wait until Tutorial 3 to find out more details.
Comment 14:
Dynamic programming is a bit difficult to understand. Also the DNA sequence example.
Follow-up:
The theme of Tutorial 3 is about dynamic programming. Hope you would feel better after going
through this tutorial cycle. The DNA sequence example is interesting and I think you can understand at least 70% of it by studying the Web page mentioned in class.
Comment 15:
I am a bit confused of the graph that represent the different representation of running time that results in different value.
Follow-up:
I think you are talking about the “estimated distances” labelled on the nodes in the example graph for showing how Dijkstra’s algorithm works. Those values are NOT running time (of an algorithm). Those are used for representing, for example, the time it takes to travel from one place to another geographically (when we use the graph to represent a map).
Comment 16:
Why “99” is used to represent the information that has not been processed?
A rough sketch as follows: We need to examine all the links (during the updating of the estimated distances labelled on the nodes) so that is why we have the e term. We need to sort the nodes in an increasing order of estimated distances and that is why we have the n log n term.
Comment 12:
Why greedy approach usually results in a fast algorithm?
Follow-up:
This is because as we make a greedy choice in each step, we reduce the problem size by 1. Thus, after making n greedy choices (i.e., n steps), we will finish the problem. Consequently, we usually end up having an algorithm that takes O(n) time, together with the time needed in some pre-processing (e.g., sorting, which takes another n log n time).
Comment 13:
Knapsack problem. It can e applied to daily life. Is it similar to linear programming taught in Maths at cert level?
Follow-up:
Yes it is similar. Wait until Tutorial 3 to find out more details.
Comment 14:
Dynamic programming is a bit difficult to understand. Also the DNA sequence example.
Follow-up:
The theme of Tutorial 3 is about dynamic programming. Hope you would feel better after going
through this tutorial cycle. The DNA sequence example is interesting and I think you can understand at least 70% of it by studying the Web page mentioned in class.
Comment 15:
I am a bit confused of the graph that represent the different representation of running time that results in different value.
Follow-up:
I think you are talking about the “estimated distances” labelled on the nodes in the example graph for showing how Dijkstra’s algorithm works. Those values are NOT running time (of an algorithm). Those are used for representing, for example, the time it takes to travel from one place to another geographically (when we use the graph to represent a map).
Comment 16:
Why “99” is used to represent the information that has not been processed?
Follow-up:
Yes in computer programming we usually use such tricks to ease processing.
Comment 18:
Google-Maps are more developed than MapQuest these days. For example, it can alert that friends are located close by to you.
Follow-up:
Thanks!
Comment 21:
I am not quite clear about how two determinant factors will affect the efficiency of greedy approach.
Follow-up:
The main factors are the “greedy choices”. If you pick the right greedy choice at each step, the
algorithm would end up giving “optimal” result. In terms of speed, please refer to Comment 12 above.
What a great presentation! I agree with you that each could be its own lesson for students and they would be engaging and fun! Actually, I start my next semester of courses in April and this would be a great introduction lesson to get my adult students speaking!
ReplyDeleteElectrical Engineering
Grateful to check out your website, I seem to be ahead to more excellent sites and I wish that you wrote more informative post for us. Well done work.
ReplyDelete