CMSC351: Introduction to Algorithms (Spring 2012)

Course Information

Course Calendar

DateTitleRecommended Reading
1/26Introduction[1] Chap 1 & 2, [2] Chap 1
1/31Induction[1] Chap 2
2/2Analysis of algorithms and the O notation[1] Chap 3, [2] Chap 2
2/7Induction and algorithms[1] Chap 2 & 5
2/9Induction and algorithms, cont'd[1] Chap 5
2/14Recurrence relations[1] Sec 3.5
2/16Akra-Bazzi (Master) Theorem[1] Sec 3.5.2
2/21Introduction to Data Structures: Array, Linked List[1] Sec 4.2, [2] Sec 2.5
2/23Binary 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/19Single-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 and Projects

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.

AssignmentDate postedDue date
Homework 1Feb 2ndFeb 9thSolutions and ideas
Homework 2Feb 21stFeb 28thSolutions and ideas
Homework 3Mar 8thMar 15thSolutions and ideas
Homework 4Mar 29thApr 9thSolutions and ideas
Homework 5Apr 24thMay 9thSolutions 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:

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

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

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

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

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

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

Office Hours

Agenda

The official agenda detailing class policies and other details can be found here