Course Description

 In this course we will go through different paradigms for algorithm design such
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.

Book

 Introduction to Algorithms (2nd edition) by T. H. Cormen, C. E. Leiserson, R. Rivest, and C. Stein.
MIT press, McGraw-Hill book company.

Class Schedule

pdf files for the slides
(Based on some old notes of Edelsbrunner and mine)

Heapsort
Quicksort
Selection
BinarySearch
Red-Black Tree
DynamicProgramming
    Matrix chain multiplications and Polygon triangulations
    Longest common sequence (LCS)
Greedy Algorithm
Amortized Analysis
Fibonacci Heap1
Fibonacci Heap2
Union-Find
Graphs (Representation and DFS)
BFS
Topological Sort
Minimum spanning tree
Shortest path
All pairs shortest path
Network flow
Linear programming framework
Simplex algorithm
Duality
Planar Graphs
Convex Hull and Triangulation
Some geometric primitives
Segment intersection
NP-completeness

Meeting

DL 480 11:10-12:30 TuTh
Office: DL483
Phone:292-3563
Office Hours :  TuTh 12:30-1:00, 2:00-2:30 F or by appointment
 

 Homeworks

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 stdlinux@cse.ohio-state.edu.
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:

i 3
i 2
i 1
m
d
m
c 2 1
m
x 1
m
d
m

The program should print

1
2
1
3
error

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).

Grading

 Homework 30%,  Midterm 30% and Final 40%

 No late assignment will be accepted

Grader: Oleksiy Busaryev,  email : busaryev@gmail.com, Office: DL474, phone: 614-292-8578
Office hours : Tuesday, Friday 2:00--3:00 pm