New platform

This year we have been using piazza.com to host resources and announcements about the course.

If you haven’t registered yet, please follow this link. (and add a comment to this post)

The statement for the first assignment has been published here.

 

ADC Exams, September 2018

The ADC exams are scheduled on the 6th and 7th September, at 2pm, in room PR001.

Room PR001 is in Precis building (the new building of the A&C Faculty), ground floor.

ADC Exam, 5th Feb 2018, starts at 2PM

The ADC exam will start at 2PM, and not at 1PM as scheduled on the FILS website.
The duration of the exam in 90 minutes.

I appreciate if you can disseminate this information to your colleagues which are not reading the ADC blog regularly.

Exam resources

Update: Solution to the last exercise we discussed: https://goo.gl/j4Darh

================================================================

Update: We’ll discuss possible exams subjects this Saturday, 02.02.2018, in the 10:30 – 12:30 interval. We’ll meet in JA001, as usual.

Exam samples from previous years:

Exam_v1

Exam_v2

Exam_v3

Every course is available here.

A link to several examples (+solutions) of recurrences solved using the Master Theorem.

A quiz from MIT on the subject of asymptotic complexities.

If you have any questions, please don’t hesitate to post a comment.

We would appreciate if you can take a minute to leave some feedback.

Assignment 3 2017-2018

Update: Added some additional small tests to debug your solution on small graphs.

Update: The deadline has been extended with 2 days.

=====================================

The third assignment has been published here.

You can test your solutions on vmchecker.

Sample tests

If you choose to implement in Java, the archive must contain:

• Radiation.java
• Readme

Important! The java files must not have any package declaration in it. If it has, then remove it before uploading the archive. Otherwise, only if you want to use a different structure, you will need to provide a Makefile.

If you implement in C/C++, you need to provide a Makefile with at least these 2 rules:

• build     – a rule to build the binary file
• run-p1  – a rule that runs the binary for the problem

Makefile examples:

• Makefile for C++
• Makefile for Java

Remember to describe in the Readme file the algorithm used in your solution, and its complexity.

Coding style suggestions.

The deadline for the assignment is 21.01.2018 23:59. (soft deadline)

Any questions can be addressed as comments on this post.

Shortest Path Algorithms – Quick Review

Shortest path algorithms have many applications in real life problems, such as:

• Finding the fastest route between two locations (Google Maps, GPS, etc.)
• In networking, finding a path between two nodes with the maximum possible bandwidth (represented by the minimum-weight edge along the path)
• Finding an optimal sequence of choices for reaching a certain goal state.
• Seam Carving 
• VLSI design, etc.

Definitions

Let G = (V, E) represent a graph.

Let w : E -> W be a function that associates to each edge a cost (weight). If an edge does not exist between two nodes we assume a cost of +infinite.

Let numNodes represent the number of vertices in the graph.

Let numEdges represent the number of edges in the graph.

Let minDist[u] refer to an algorithm’s estimation of the minimum distance from the source to node u.

Let parent[u] refer to the second-to-last element on the minimum cost path from the source to node v.

The general problem asks us to find a path between two given nodes such that total sum of the weights is minimum.

Relaxing an edge

Relaxation of an edge (u, v) refers to improving the current estimation of the minimum cost for a path from the source node to node v by using the respective edge.

void relaxEdge (Vertex u, Vertex v)
{
    if (minDist[v] > minDist[u] + w(u, v)) {
        minDist[v] = minDist[u] + w(u, v);
        parent[v] = u;
    }
}

Single source shortest path problem

Given one source node, find the shortest path to all the other nodes in the graph. Ideally, we want to analyze each node/edge only once.

Scenarios:   

• The graph is undirected and acyclic (a tree)
  In this situation there is only one path from one node to another so we can find the answer with a depth first search.
  Time complexity: Θ (numNodes + numEdges)                                                                              

• The graph is a directed and acyclic (a DAG)
  For solving the problem we can explore each node in sorted topological order and apply the relaxEdge procedure for each corresponding edge. This approach requires only two traversals of the graph.
  Time complexity: Θ  (numNodes + numEdges)                                                                            
• A graph where each edge has an equal weight.
  For this scenario, the best approach is to apply the Breadth First Search algorithm. The order in which nodes are explored is given by the minimum number of edges from the source, which coincides with the shortest path.
  Time complexity: Θ  (numNodes + numEdges)                                                                                 
  • A graph with edges that have only positive weights.                                                                                                                
    When we extracted a node from the front of the queue during BFS, we had the guarantee that it was the closest unexplored node from the source, in terms of number of edges. If we change the problem so that edges have different but positive weights we need to replace the queue with another data structure that supports efficient interrogation for the closest node. This type of data structure is called a priority queue. We would also like to be able adjust the estimated value for a node efficiently, for when we relax an edge.
    The following algorithm is known as Dijkstra’s algorithm.

    
    // setup an initial distance estimation
    void initDistance(Graph, Vertex s)
    {
         for each Vertex v in Graph {
             minDist[v] = infinite;
             visited[v] = false;
         }
         // set minDist for source to 0
         minDist[s] = 0;
    }
    
    void Dijkstra(Graph, Vertex source)
    {
        initDistance(Graph, source);
        PriorityQueue PQ;
        PQ.add(source);
    
        while (!PQ.empty()) {
           // u is the closest unexplored node to the source
           Vertex u = PQ.extractMin();
           mark u as explored
    
           for each Vertex v that is connected to Vertex u {
               if Vertex v is not explored {
                   relaxEdge(v, u)
                   updatePQ(v);
                   // update PQ with the new estimation
                   // of distance for v
               }
          }
        }
    }
    

    For Java and C there already exist implementations for a priority queue data structure: PriorityQueue and priority_queue. These implementations have logarithmic time complexity for element addition and extraction, but don’t allow you to update the priority of a random element.

    Note that, since the priority queue will contain node references, to use these existing data structures you need to implement a comparator first and supply it to the constructor.

    The default Priority Queue in Java works as a min-heap (returns the minimum element, as indicated by the comparator), while the C++ equivalent data structure priority_queue is a max-heap (default behaviour is to return the maximum element).

    class NodeComparator implements Comparator
    {
        @Override
        public int compare(Vertex u, Vertex v) {
            return minDist[u.index] < minDist[v.index] ? 1 : -1;
        }
    }
    

    Complexity of Dijkstra’s algorithm

    We explore each node exactly once and this translates to one call to PQ.extractMin() for each node. We also only check each edge once, but in the worst case scenario we have to update the priority queue structure with each check.

    Therefore, we can express the complexity as:

    Θ (numNodes * Extract-Min + numEdges * UpdatePQ)

    The exact complexity of Dikstra’s algorithm depends on how we implement the priority queue:

    As a simple array:

    • Extract-Min: Θ (numNodes)
    • UpdatePQ: Θ (1)

    Time complexity: Θ (numNodes^2 + numEdges), which is efficient for dense graphs.

     As a binary heap:

    • Extract-Min: Ο( log(numNodes) )
    • UpdatePQ: Ο( log(numNodes) )

    Time complexity: Θ (numEdges * log(numEdges)), which is efficient for sparse graphs.

    As a Fibonacci heap:

    • Extract-Min: Ο( log(numNodes) )
    • UpdatePQ: Ο(1)*

    Time complexity: Θ (numNodes * log(numNodes) + numEdges)

    Possible exam questions

    • What is the order of exploration of the nodes, using Dijkstra’s algorithm, given a graph and a source node?
    • Why doesn’t Dijkstra work if we have negative weight edges? Think of a simple example.

     

• A graph with edges that have both negative and positive weights 
  For this scenario we may apply the Bellman Ford algorithm, where we basically relax each edge for numNodes-1 iterations:

  void BellmanFord(Graph, source)
  {
      initDistance(Graph, source);
      for (i = 1; i <= numNodes - 1; i++) {
          for each edge(u, v) in Graph {
              relax(u, v);
          }
      }
  }
  

  Complexity for Bellman Ford: Θ (numNodes * numEdges).

  Possible exam question:

  If it is still possible to relax an edge after we run Bellman-Ford than there exists a negative cycle in the graph.Why? Hint: How many iterations does it take to obtain the shortest distance for any destination in the worst case scenario?

Assignment 2 2017-2018

Update 18.12.2017:

You can now upload your solutions on vmchecker. There will be a bonus for the fastest solutions to the the first problem. 

Update 14.12.2017:

I’ve uploaded sample tests for the first and second problem.

========================================================

The second assignment has been published here.

It will be available on vmchecker very soon.

If you choose to implement in Java, the archive must contain:

• Plants.java
• Madripoor.java
• Readme

Important! The java files must not have any package declaration in it. If it has, then remove it before uploading the archive. Otherwise, only if you want to use a different structure, you will need to provide a Makefile.

If you implement in C/C++, you need to provide a Makefile with at least these 3 rules:

• build     – a rule to build the binary files
• run-p1  – a rule that runs the binary for the first problem
• run-p2  – a rule that runs the binary for the second problem

Makefile examples:

• Makefile for C++
• Makefile for Java

Remember to describe in the Readme file the algorithm used in your solution, and its complexity.

Coding style suggestions.

The deadline for the assignment is 08.01.2018 23:59. (HARD deadline, no later submissions accepted)

Any questions can be addressed as comments on this post.

Laboratory recovery – 08.12.2017

Hello everyone,

We are going to recuperate the laboratory that we missed on 1 December this Friday, 08.12.2017, in the 12:00-14:00 interval.
The topic of the laboratory will be graph algorithms [0]: we will discuss how to represent a graph in memory [1] and review some simple graph applications.

I strongly encourage you to come this Friday; The notions we are going to discuss will be necessary to solve the second assignment (which will be published shortly) and, in a more general way, you will hopefully find the opportunity to apply them in future projects/job interviews.

[0] https://adcfils.wordpress.com/2010/12/09/course-7/
[1] https://adcfils.wordpress.com/2015/01/05/graph-representation-quick-tutorial/

Assignment 1 2017-2018

Last Update 01.12.2017:

Readme file should be a plain text file (so that it can be easily read on any operating system/environment).

In Java, if you use Scanner [0], you need to specify the correct charset for the second problem (“UTF-8” [1]):

new Scanner(new File(fileName), "UTF-8");

However, I suggest you use BufferReader instead. [2] (an explanation [3])

[0] https://docs.oracle.com/javase/9/docs/api/java/util/Scanner.html
[1] https://en.wikipedia.org/wiki/UTF-8
[2] https://docs.oracle.com/javase/9/docs/api/java/io/BufferedReader.html
[3] http://www.geeksforgeeks.org/difference-between-scanner-and-bufferreader-class-in-java/

========================================================================

 

The first assignment has been published here.

You are now able to upload the archive with your solution, for automatic judging on vmchecker. You can log in on it using your moodle accounts.

If you choose to implement in Java, the archive must contain:

• Tunnel.java
• FileDiff.java
• Readme

Important! The java files must not have any package declaration in it. If it has, then remove it before uploading the archive. Otherwise, only if you want to use a different structure, you will need to provide a Makefile.

If you implement in C/C++, you need to provide a Makefile with at least these 3 rules:

• build     – a rule to build the binary files
• run-p1  – a rule that runs the binary for the first problem
• run-p2  – a rule that runs the binary for the second problem

Makefile examples:

• Makefile for C++
• Makefile for Java

Sample tests for the two problems: sample_tests (these are some of the tests actually used for evaluating your solution)

Remember to describe in the Readme file the algorithm used in your solution, and its complexity.

Coding style suggestions.

The deadline for the assignment is 04.12.2017 23:59.

Any questions can be addressed as comments on this post.

 

A set of small sample tests for the FileDiff problem, that are easier to debug but require that you implement the minimum lexicographically condition correctly:  File Diff extra sample tests

Lecture & lab from 29 Sep 2017 postponed

As I am attending a conference until the end of the week, the ADC lecture and lab scheduled this Friday (29 Sep 2017) are postponed.