CSE 208 : Algorithm Sessional

This is the course homepage for CSE 208. In this webpage assignments, notifications and marks will be uploaded from time to time.

October 2009

Course Teachers:

Your marks are here

Quiz marks are here

Week Topic Assignment
1, 2Introduction to Algorithms.
Order and Complexity.
Graph input, Graph searching using BFS, DFS
3, 4 Binary Search
Tutorial on Binary Search
5-8 Single Source Shortest Path,
Minimum Cost Spanning Tree
Offline : A1, A2, B1, B2: Implement Kruskal's algorithm, Prim's algorithm, Dijkstra's Algorithm in 3 separate files.

Input format for all three:
First line contains two integers n and m. n denotes number of vertices and m denotes number of edges. Next m lines each contain three integers u,v,w where u,v denote there is an edge from vertex u to vertex v in the graph and w denotes the weight of that edge. 1<=u,v<=1000.


Ouput :
[Prim] [Kruskal] Print the cost of the minimum cost spanning tree and also print the edges present in that tree.
[Dijkstra] Print the cost of the shortest path from node 1 to every other node. Also print the shortest paths.

A1 and B1 will submit all these on 7th week.
A2 and B2 will have a lecture on Kruskal, Prim, Dijkstra on 6th week and they will have to submit this assignment on 8th week.

There will be an online test also on these topics. You should keep the offline codes during the online test. They will come handy at that time.

Bonus Assignment :

  1. Solve the Multi Peg Tower of Hanoi Problem using the algorithm given in Kaykobad et. al. Given the number of pegs and number of disks your program should be able to tell the presumed optimal number of moves needed.
  2. Simulation of Multi Peg Tower of Hanoi (The program should graphically depict the algorithm running). You are free to use C++ or Java or C# for this assignment. For graphics in C++, you can use igraphics or openGL. For Java you can use java default drawing functions.

    Examples :

    MPTOH Java Simulation: This simulation solves the multipeg tower of hanoi problem and simulates using java graphics. The animation is clean and fast. You can use it for your own educational purposes also. You will need to have Java installed in your computer to run it.

    MPTOH CPP Simulation: This simulation solves the MPTOH problem and simulates graphically using C++.

  3. A Careful Approach Requirment for this bonus is getting ACCEPTED from live archive. You will need an live archive id to submit the problem, which you can obtain freely by registering in that site.

Caution : Runtime Errors
A lot of you get RTE (Runtime Error) with our judge data. The reason is, you have missed some bounds checking or made some trivial mistakes in the code. When you get reply "Contact staff" or "Runtime error", most of cases the meaning is a crash during execution.

In a contest/ judge systems main runtime error scenarios are :

SIGFPE :
The SIGFPE reports a fatal arithmetic error. Although the name is derived from "floating-point exception", this signal actually covers all arithmetic errors, including division by zero and overflow. If a program stores integer data in a location which is then used in a floating-point operation, this often causes an "invalid operation" exception, because the processor cannot recognize the data as a floating-point number.
SIGSESV :
This is generated when a program tries to read or write outside the memory that is allocated for it. The name is an abbreviation for "segmentation violation". The most common way of getting a SIGSEGV condition is by dereferencing a null or uninitialized pointer. A null pointer refers to the address 0. Another common way of getting into a SIGSEGV situation is when you use a pointer to step through an array, but fail to check for the end of the array.
SIGILL :
The name of this signal is derived from "illegal instruction"; it means your program is trying to execute garbage or a privileged instruction. Since the C compiler generates only valid instructions, SIGILL typically indicates that the executable file is corrupted, or that you are trying to execute data. Some common ways of getting into the latter situation are by passing an invalid object where a pointer to a function was expected, or by writing past the end of an automatic array (or similar problems with pointers to automatic variables) and corrupting other data on the stack such as the return address of a stack frame.
9-12 Dynamic Programming

Extra Lecture

A1, B1 : Joint lecture 7th week
A2, B2 : Joint lecture 8th week

9th Week, Sunday 03 January, 2010

Venue :
1st Floor, New Academic Building,
West Palashi

Time :
A1, A2 : 9:00 AM
B1, B2 : 10:00 AM



13

CSE 208 Quiz

  • 13th Week Wednesday
  • 03 February
  • 03:00 - 04:00 PM
  • New Academic Building
  • 1st Floor

Course webpage maintained by Md. Tanvir Al Amin
Department of Computer Science and Engineering, EME building, Palashi, Dhaka, Bangladesh. The Department is part of the Faculty of Electrical and Electronic Engineering at the Bangladesh University of Engineering & Technology. No part or content of this website may be copied or reproduced without permission of the department authority.