Design and Analysis of Algorithms

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

**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

hw2

hw3

hw4

hw5

hw6

hw7

hw8

hw9

Project (20% of homework): In this project you will implement a Fibonacci heap. The details are given below:

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

Last updated 09/10/12