Instructor:

Héctor Corrada Bravo

Center for Bioinformatics and Computational Biology

Department of Computer Science

Office: 3114F Biomolecular Sciences Building

Phone Number: 301-405-2481TAs:

Konstantinos Zampogiannis

Ioana Bercea

Scott ZimmermannLecture Meeting times

Tuesday and Thursday, 9:30am-10:45am

Room CSI 1115

Date | Title | Recommended Reading |
---|---|---|

1/26 | Introduction | [1] Chap 1 & 2, [2] Chap 1 |

1/31 | Induction | [1] Chap 2 |

2/2 | Analysis of algorithms and the O notation | [1] Chap 3, [2] Chap 2 |

2/7 | Induction and algorithms | [1] Chap 2 & 5 |

2/9 | Induction and algorithms, cont'd | [1] Chap 5 |

2/14 | Recurrence relations | [1] Sec 3.5 |

2/16 | Akra-Bazzi (Master) Theorem | [1] Sec 3.5.2 |

2/21 | Introduction to Data Structures: Array, Linked List | [1] Sec 4.2, [2] Sec 2.5 |

2/23 | Binary Search and Applications | [1] Sec 6.2 |

2/28 | Sorting: Insertion Sort, Selection Sorts, Merge Sort | [1] Sec 6.4 |

3/1 | Midterm 1 | |

3/6 | Sorting: Bucket Sort and Radix Sort | [1] Sec 6.4 |

3/8 | Quicksort | [1] Sec 6.4.4 |

3/13 | Hashing | [1] Sec 4.4 |

3/15 | Introduction to Graph Theory | [1] Sec 7.1, [2] Sec 3.1 and 3.2 |

3/20 | No class: Spring Break | |

3/22 | No class: Spring Break | |

3/27 | Trees and Binary Search Trees | [1] Sec 4.3 and 6.2 |

3/29 | Heap and Heapsort | [1] Sec 4.3.2 and 6.4.5 |

4/3 | Greedy Algorithms | [1] Sec 5.10, [2] Chap 4 |

4/5 | Dynamic Programming | [1] Sec 5.10, [2] Chap 6 |

4/10 | Midterm 2 | |

4/12 | DFS, BFS | [1] Sec 7.3.1 and 7.3.2, [2] Sec 3.3 and 3.4 |

4/17 | DAGS and Topological Sorting | [1] Sec 7.4, [2] Sec 3.3 and 3.4 |

4/19 | Single-Source Shortest Path | [1] Sec 7.5, [2] Sec 4.4 |

4/24 | All-pair Shortest Path | [1] Sec 7.7, [2] Sec 6.8 |

4/26 | Min. Spanning Tree and the concept of NP | [1] Sec 7.6, [2] 4.5 [1] Chap 11, [2] Sec 8.1 |

5/1 | Reduction and NP Completeness | [1] Chap 11, [2] Chap 8 |

5/3 | NP Completeness, cont'd | [1], Chap 11, [2] Chap 8 |

5/8 | Parallel Algorithms | [1] Chap 12 |

5/10 | Parallel Algorithms and Map-Reduce | |

5/15 | Final Exam CSI 1115 4:00pm-6:00pm |

Notes are from MohammadTaghi Hajiaghayi

[1] Manber, U. Introduction to Algorithms-A Creative Approach

[2] Kleinberg, J and Tardos, E. Algorithm Design

Homeworks are due AT THE START OF CLASS on the day indicated, and LATE OR MAKEUP HOMEWORKS WILL NOT BE ACCEPTED!!! Graded homeworks will be available for pickup at TA office hours. Any question regarding assignments should be sent to hcorrada@umiacs.umd.edu and CC'D to Konstantinos at kzampog@gmail.com with the subject line "cmsc351 assignment" (all lowercase) and then the question num- ber.

Assignment | Date posted | Due date | |
---|---|---|---|

Homework 1 | Feb 2nd | Feb 9th | Solutions and ideas |

Homework 2 | Feb 21st | Feb 28th | Solutions and ideas |

Homework 3 | Mar 8th | Mar 15th | Solutions and ideas |

Homework 4 | Mar 29th | Apr 9th | Solutions and ideas |

Homework 5 | Apr 24th | May 9th | Solutions and ideas |

Programming Projects

The first two problems satisfy the 3% requirements, the next two more problems are 3% bonus. We will grade the programming assignments on May 1st (you will have an option of one re-try May 10th that we grade again).

Project 1 |

Project 2 |

Project 3 |

Project 4 |

Submission instructions:

Use the CS submit server (`http://submit.cs.umd.edu`

). Meanwhile you may like to start implementing your solutions. Just keep in mind that:

You may only use c/c++ or Java.

Your program should not use more than 128MB of memory.

For each test case, your program may only run for few seconds: c/c++ users 4 secs, java users 7 secs. So you need to design efficient algorithms.

Your program should use standard input/output. So for example c/c++ users should use scanf/printf/cin/cout and Java users should use system.in/system.out. For more information you may like to read this:

`http://en.wikipedia.org/wiki/Standard_streams`

.All 4 problems are due May 10, 23:59. However, you are encouraged to submit your solutions before May 1st. On May 5, we will announce the grades of all submissions received before May 1st. Therefore you may have a chance to correct your codes and resubmit until the final due date May 10.

You may only use the basic libraries for reading and storing data. You may not use any of the sorted containers, linked lists, or algorithms in the standard libraries, instead, you should implement them yourselves. For example:

You can use arrays, ArrayList, vectors, and any kind of function related to input/output; however, You may "not" use linkedlist, qlist, sets, maps, Hashmaps, or sorting algorithms in the libraries.

Instructor Office Hours: Thursday 1:00pm-2:00pm BSB 3114F and by appointment

TA Office Hourse:

Konstantinos: Tue 12:00-1:30PM at A.V. Williams Bldg., Room 1112

Ioana: Office Hours: Wed 12:30PM-2:00PM at A.V. Williams Bldg., Room 1112

Anu Bandi (Sec. 02): Mon 4:00PM-5:30PM at A.V. Williams Bldg., Room 1112

Scott Zimmerman: Tue 2:00PM-3:00PM at A.V. Williams Bldg., Room 1112