Sunday, June 26, 2016

Course schedule I and II

There are a total of n courses you have to take, labeled from 0 to n - 1. Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1] Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses? For example: 2, [[1,0]] There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible. 2, [[1,0],[0,1]] There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

The first problem requires us to find if there is a cycle in the graph, if there is, then its a false. It does not require topological sort, yet if you use traditional DFS, it will exceed time limit. However, we can do a little bit optimization to avoid traverse already traversed path. Instead of using a boolean to track visited nodes, we can use an int array. For visited node, we mark it as 1, for the node that is visited and the path that is rooted by it does not contain cycle, we mark it as 2. So along any path if we find a node that is marked as 2, we can save our time and return "true" directly.


 public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses == 0 || prerequisites == null || prerequisites.length == 0)
            return true;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] prequisit : prerequisites) {
            int klass = prequisit[0];
            if (!map.containsKey(prequisit[0]))
                map.put(klass, new ArrayList<>());
            map.get(klass).add(prequisit[1]);
        }
        int[] visited = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (!helper(visited, map, i))
                return false;
        }
        return true;
    }
    
    private boolean helper(int[] visited, Map <Integer, List<Integer>> map, int i) {
        visited[i] = 1;
        //no prerequisit
        if (!map.containsKey(i)) {
            visited[i] = 2;
            return true;
        }
        for (int pre : map.get(i)) {
            if (visited[pre] == 2)
                break;
            if (visited[pre] == 1 || !helper(visited, map, pre))
                return false;
        }
        visited[i] = 2;
        return true;
    } 


The second problem, on the other hand, requires topological sort. Common approach to it is to first find all vertices with indegree 0. Then for each vertex with indegree 0, remove all its neighbor nodes. Iteratively perform this process until all nodes are found.

 public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Set<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new HashSet<>());
        }
        for (int i = 0; i < prerequisites.length; i++) {
            adjList.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        int[] indegrees = new int[numCourses];
        for (Set<Integer> pre : adjList) {
            for (int i : pre)
                indegrees[i]++;
        }
        Queue<Integer> first = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegrees[i] == 0)
                first.add(i);
        }
        int[] rst = new int[numCourses];
        int count = 0;
        while (!first.isEmpty()) {
            int curr = first.poll();
            for (int i : adjList.get(curr)) {
                indegrees[i]--;
                if (indegrees[i] == 0)
                    first.add(i);
            }
            rst[count++] = curr;
        }
        return count == numCourses ? rst : new int[]{};
    }


I was considering using DFS for the problem. However, traditional DFS for topological sort requires DAG, which cannot be guaranteed by this problem.

1 comment:

  1. The development of artificial intelligence (AI) has propelled more programming architects, information scientists, and different experts to investigate the plausibility of a vocation in machine learning. Notwithstanding, a few newcomers will in general spotlight a lot on hypothesis and insufficient on commonsense application. IEEE final year projects on machine learning In case you will succeed, you have to begin building machine learning projects in the near future.

    Projects assist you with improving your applied ML skills rapidly while allowing you to investigate an intriguing point. Furthermore, you can include projects into your portfolio, making it simpler to get a vocation, discover cool profession openings, and Final Year Project Centers in Chennai even arrange a more significant compensation.


    Data analytics is the study of dissecting crude data so as to make decisions about that data. Data analytics advances and procedures are generally utilized in business ventures to empower associations to settle on progressively Python Training in Chennai educated business choices. In the present worldwide commercial center, it isn't sufficient to assemble data and do the math; you should realize how to apply that data to genuine situations such that will affect conduct. In the program you will initially gain proficiency with the specialized skills, including R and Python dialects most usually utilized in data analytics programming and usage; Python Training in Chennai at that point center around the commonsense application, in view of genuine business issues in a scope of industry segments, for example, wellbeing, promoting and account.

    ReplyDelete