Assignment 1
Topic: No fibbing...Fibonacci Heaps
Due on:
30 September (Thursday), 2021
Maximum Marks: 10
This is an assignment motivated by a hard-core Electrical
Engineering application, efficient routing in communication networks.
Do you remember the statement discussed in class, that when Fredman
and Tarjan invented Fibonacci heaps, they showed the best
application for their new data structure, in reducing the time
complexity for the best-known routing mechanism for communication
networks, Dijkstra's algorithm? With binary heaps, the routing
problem took time O((n + m) log n) for a graph with n vertices
and m edges. With the new data structure, they showed that this
could be made much more efficient, to O(n log n + m), the fastest
known single source shortest paths routing for communication
networks (albeit using amortised analysis).
This assignment asks you to implement Fibonacci Heaps using a
linked representation. Read the theory and pseudo-code from the
[CLRS] textbook, and do not worry about amortised analysis, or
the possible time complexity issues.
Immplement at least the following operations:
make_heap, insert, find_min, delete_min, decrease_key
These correspond (roughly) to operations done in class with a
binary heap. Operations from this set are used in Dijkstra's
algorithm. Note: you do not have to implement Dijkstra's
algorithm using Fibonacci heaps. Just show examples of these
operations. You may like to start a Fibonacci heap from scratch,
or to explain a concept, read in a Fibonacci heap from a file on
the disk, and modify this Fibonacci heap.
Rules of the game
Programming is to be done in C/C++/Java. All assignments are to
be individual efforts in programming (no shared code, or
libraries or other code downloaded from the Internet): the entire
set of programs must be yours. We will use plagiarism detection
tools, and any violations will lead to your score being the magic
number said to have been discovered by the ancient Indians, and a
possible further disciplinary action based on the severity of the
offence. Assignment submission: on the day of the demo, please
submit your programs to the TAs immediately after the demo. You
will submit all your program files (and nothing else: no object
code, executables and the works) in ONE FLAT directory, with no
sub-directories. You should be able to use your program(s) to
display the result of all examples in the relevant chapter of the
[CLRS] textbook.
Demo Schedule:
Venue: Online
Demos:
Sumeet Agarwal,
Sumantra Dutta Roy,
Department of Electrical Engineering, IIT Delhi, Hauz Khas,
New Delhi - 110 016, INDIA.
sumeet@ee.iitd.ac.in,
sumantra@ee.iitd.ac.in