lu.se

Datavetenskap

Lunds Tekniska Högskola

Denna sida på svenska This page in English

EDAF05 Algorithms, data structures, and complexity

EDAF05

News

  • The exam from May 29, 2018 and solutions.
  • Congratulations to Ludvig Pärsson and Sepehr Noorzadeh who are the outstanding winners of the competiion!!!
  • Other very very good accomplishments have been achieved by Jos Rosenqvist and Martin Karlsson who were second, and the two groups Simon Andersson and Sara Nilsson, and Jakob Navrozidis and Sara Jendeberg. Very well done!!!
  • The final standing is here.
  • Deadline for the competition for RAILROAD is Monday, May 28, at 12.00. Both Minsk.in and huge.in are used as inputs.
  • The current standings for the competition has been updated and is here. Four groups remain on the list, all of which show really very good competence!
  • Here are huge input and correct output for RAILROAD.
  • About electronic devices on the exam: you can bring a pocket calculator such as an HP 50g but not any device with which you can connect to the Internet. I doubt you will have any use of an advanced calculator but if that is a trusty companion, feel free to bring it.
  • I have reset the highscore list for GORILLA and uploaded the huge input file to Forsete. The deadline for the competition is May 19 at 17.00 (this huge file is larger than the previously uploaded so please download again using the link below).
  • Here are huge input and correct output for GORILLA. I will upload them to Forsete after the lab's normal deadline and use a competition deadline 48 hours later (i.e. May 19 at 17.00).
  • The next lecture is a guest lecture by Andreas Björklund on Monday May 21st at 10.15 - 11.00 on graph coloring. 
  • I have uploaded input and correct files for RAILROAD, lab 6. Submitted files to Forsete should print the value of the maximum flow but not the edges in a minimum cut, but you should be able to print a minimum cut on the lab.
  • The file BLOSUM62.txt from Thore's labs is present in the directory where your program is tested i.e. you can open it and read it. If you wish, you can instead hard code the matrix directly in the program. 
  • I have uploaded input and correct files for GORILLA, lab 5. Submitted files to Forsete should not print an alignment but only the value, but on the lab you should also print the alignment strings for each pair.
  • I will upload a huge input file for GORILLA at a later time. If you get a mail from Forsete saying you have passed this lab, that is sufficient. I will delay uploading the huge file for RAILWAY as well, in order for you to be encouraged to finish the labs early and have no late labs since there will be no "uppsamlingslabb".
  • One of the input files to CLOSESTPAIR is available here.
  • The CLOSESTPAIR huge input file has been reduced from 5,000,000 to 2,000,000 points and is here with correct output here.
  • The Forsete software has now moved to a different computer: forsete.cs.lth.se. It has 32 GB RAM, and an Intel i7-3820 with 3.6 GHz, which can run 8 threads concurrently. You still should send your assignments to edaf05@forsete.net and the only differences you should note is that the highscore lists of the first three labs will not be updated, that this computer is somewhat faster than the previous, and that the highscore lists for the last three labs will be updated directly since they now are located on the same computer. The website is a good illustration of how the web looked around 1991 ;-)
  • OpenMP can now be used with C/C++ (OpenMP is a semi-automatic parallelization method in which the programmer guarantees the safety of running loop iterations in parallel and the compiler takes care of the details).
  • Some time after 15 on Friday Forsete is intended to run on a new machine, forsete.cs.lth.se, and then hopefully the problems with outdated highscore lists will be solved as well.
  • It is now possible to select which C++ compiler to use: file name extension "cc" gives clang++ and "cpp" gives g++. They are better at different things so try both!
  • The correct result for the SPANNING data/tinyEWG-alpha file is 181.
  • If after all labs there are two groups with the smallest point, the one with the smallest point on lab 6 is the total winner.
  • The current standings on the course competition is here. I think we have all learned a lot from this week: for instance that Java programs can be really fast. There are now maybe seven groups which have a reasonable chance of winning, one of which is our guests from California/North Carolina. It will be interesting to see the results of next week! 
  • Anonymous list of all submissions for WORDLADDERS before the deadline is here.
  • SPANNING huge files: input, correct.
  • WORDLADDERS huge files: wordlist, pairs, correct.
  • Change for WORDLADDERS: you are allowed to create the graph in quadratic time. The wordlist now is the 5757-file and the number of wordpairs has been increased to 20,000. A normal program now should take around 10 s to complete.
  • No lecture on april 17. I will use May 15 instead (also 8-10) and the purpose is to not be too far ahead with lectures as compared to the labs.
  • You are NOT allowed to build the word-graph in Lab 2 in quadratic time (which would take too much time).
  • The fourth assignment, CLOSESTPAIR, is now on Forsete. Your program should read input from a file given as program parameter. A huge input file is here and the correct output is here. A relative difference in output of 1e-6 is tolerated. We use ndiff for comparing the numerical values (unpack in terminal with tar xvf ndiff-2.0.tar.bz2, cd to the new directory, type ./configure and then make).
  • The huge input files to WORDLADDERS are here: wordlist (which is the same as in Thore's data), wordpairs, and correct. You have 120 s to passed them but if it turns out to be problematic if you use Python 3 or e.g. Haskell, I will either increase the timelimit or reduce the wordpairs file. So far a Java solution needed about 70 s.
  • The third assignment, SPANNING, has been uploaded to Forsete and the current list is here.
  • Forsete now also supports Haskell, Rust, Fortran 77, and Fortran 95. File name extensions hs, rs, f77 and f95.
  • The second assignment, WORDLADDERS, has been uploaded to Forsete and the current list is here.
  • Forsete now can handle Scala code again. Please resubmit if it did not work before.
  • Current standings on the course competition is here.
  • Anonymous list of all submissions before the deadline for STABLEMARRIAGE is here.
  • Timing for the competition is done as follows. First your program is compiled. Then timing starts. Your program is given each input file as System.in and the output from System.out is saved in a file. When all input files have been used, the timing is stopped. After that the correctness of the output is checked.
  • There is now a high score list for STABLEMARRIAGE here. There is a maximum execution time of 60 s. One input set with parameters WORST and N=3000 is included. The execution time is the sum of running all tests but not checking them. HAVE FUN! Here are huge.in and huge.correct.
  • The slides from extra lecture on the Unix terminal is here.

Textbook:

There are two alternative textbooks:

  • Kleinberg/Tardos: Algorithm Design 1st (from 2005/2006) or 2nd edition (I am not sure when 2nd edition will be available). Here is a link to adlibris. 1st edition is 823 pages of which about 530 are for this course and the rest for EDAN55 which no longer is offered. ISBN10: 0321372913, ISBN13: 9780321372918 (paperback) and ISBN10: 0321295358, ISBN13: 9780321295354 (hard copy)
  • Skeppstedt: Algorithms: a concise introduction. This book was written for this course. It is 148 pages. It is only available from Amazon and the book's site is here (the link to amazon is to the German site which offers free shipping to Sweden when amount exceeds what seems to be two copies or more).

For the exam you are allowed to bring books but no electronic devices.

Personal

Course lecturer:

Jonas Skeppstedt

Assistants 2018:

Alexander Hansson

Måns Magnusson

Alfred Åkesson

Lars Åström

Kursombud 2018:

D: 

F:

Pi: 

Kursfakta

Omfattning: 5 hp

Kursperiod: VT 2018

Obligatorisk för: D2

Valfri för: E3, F3

Course responsible: 
Jonas Skeppstedt



e-post: jonas.skeppstedt@cs.lth.se  but please don’t send me email. Talk to me instead at my office hours 12.30 - 13.00 every weekday in LP1 and LP4. My office is in E-building, room E:2190.

Schema  via TimeEdit

Formell kursbeskrivning KA: Klicka här!