In this course we will go through different paradigms for algorithm
as divide-and-conquer, prune-and-search, dynamic progamming, greedy strategy,
randomization, linear programming and different analysis techniques with different
data structures. We will apply these design and analysis techniques to develop
efficient graph and geometric algorithms.
Introduction to Algorithms (2nd edition) by T. H. Cormen, C. E. Leiserson,
R. Rivest, and C. Stein.
MIT press, McGraw-Hill book company.
pdf files for the slides
(Based on some old notes of Edelsbrunner and mine)
Matrix chain multiplications and Polygon triangulations
Longest common sequence (LCS)
Graphs (Representation and DFS)
Minimum spanning tree
All pairs shortest path
Linear programming framework
Convex Hull and Triangulation
Some geometric primitives
DL 480 11:10-12:30 TuTh
Office Hours : TuTh 12:30-1:00, 2:00-2:30 F or by appointment
CSE 6331 lab requirements
Lab due: November 6, 11:59pm.
For this lab, your task is to implement the Fibonacci heap data structure. To test your data structure, you need to create an executable that will read a text file containing a sequence of commands and update your data structure appropriately.
You will have to submit BOTH your executable and the source code. If you are submitting a Linux executable, make sure that it runs on the department server firstname.lastname@example.org.
If you are submitting a Windows executable, make sure that it runs on the department Windows machines. You are welcome to use any language of your choice.
The grader will run your executable on several test cases and then will look through your code.
In the test input files, every command will be specified in a separate line.
The following commands should be supported:
m - prints the minimum key in the heap
i <key> - inserts a new node with the key <key> into the heap
d - deletes the node with the minimum key from the heap
c <key> <new_key> - for the node with the key <key>, changes the key to <new_key>
x <key> - erases the node with the key <key>
You can assume that all <key> and <new_key> values in the input file will be unique.
If any command refers to a non-existing element, your program should print 'error'.
The sample input file will look like follows:
c 2 1
The program should print
Each of 5 commands is worth 2 points, so maximum grade for this lab is 10 points.
The points will be deducted for test case failures (if your code fails, you will
be given the test case) and implementation mistakes (make sure you are implementing
the Fibonacci heap as described in lecture notes and in the textbook).
Homework 30%, Midterm 30% and Final 40%
No late assignment will be accepted
Grader: Oleksiy Busaryev, email : email@example.com, Office: DL474,
Office hours : Tuesday, Friday 2:00--3:00 pm