91.503 - Algorithms - Spring 2008

91.503 - Algorithms - Spring 2008
Dr. Haim Levkowitz
Associate Professor of Computer Science
University of Massachusetts Lowell, Lowell, MA

Announcements

Welcome to Spring 2008 91.503 Algorithms announcements page. Visit this page regularly to find out about homework assignments, exams, and other topics of interest.

Monday, 19 May 2008:

To clarify: you are allowed to bring your previous two cheat-sheets, in addition to the one you are making for the final. (This does not change my opinion that by doing so, you are potentially putting yourself at a disadvantage. But that's up to you.)
Solutions to HW6 and HW7.

Here are you grade through the last homework assignment (HW7). Please do NOT pay attention to the totals; they have been computed without the final exam's grade, which is worth 40%, so they are obviously low. In addition, Exam 2 grades are not final, in that, I am still looking at some people's Question 2 grades.

91.503		relative	raw	hw1	hw2	hw3	hw4	hw5	hw6	hw7	exam1	exam2	final exam, raw
				1	1	1	1	1	1	1	1	1	1
Spring 2008	Grade estimate			0.028571	0.028571	0.02857143	0.02857143	0.02857143	0.02857143	0.02857143	0.2	0.2	0.4
			100	100	100	100	100	100	100	100	100	100	100
grade dist ID
037		70	38	100	126	69	130	124	107	56	54	43	0
082		91	50	100	77	102	110	66	123	83	83	76	0
094		89	48	100	106	83	70	118	132	86	72	76	0
100		77	42	100	55	65	110	137	142	45	53	71	0
109		100	55	100	134	110	170	96	121	96	89	85	0
117		74	40	100	74	96	160	108	97	78	69	40	0
120		88	48	100	110	101	120	115	108	56	80	63	0
146		70	38	100	29	20	30	49	0	18	87	55	0
150		31	17	100	84	0	0	0	0	0	0	0	0
155		94	51	100	96	106	100	85	99	95	80	81	0
181		99	54	100	94	83	130	116	151	79	83	91	0
197		76	42	100	70	83	100	34	79	94	71	57	0
210		81	44	100	91	97	100	60	79	0	78	53	0
215		94	51	100	90	100	120	77	142	78	80	85	0
218		89	48	100	151	120	150	158	179	43	72	70	0
234		100	55	100	175	113	200	121	151	88	89	84	0
240		78	42	100	99	95	100	63	87	76	71	53	0
246		88	48	100	86	68	90	77	129	96	72	81	0
248		84	46	100	123	85	120	94	94	86	64	70	0
291		93	51	100	93	80	100	87	96	91	80	83	0
353		54	29	100	94	108	110	57	0	0	53	0	0
355		93	51	100	111	89	110	131	111	75	78	77	0
361		92	50	100	143	91	100	86	103	91	66	89	0
362		79	43	100	99	80	50	101	117	98	53	72	0
387		68	37	100	62	40	110	86	135	42	38	72	0
411		77	42	100	91	87	50	74	78	63	76	56	0
461		75	41	100	81	0	120	115	160	60	78	47	0
491		92	50	100	89	95	100	96	94	100	79	76	0
538		91	50	100	131	75	170	113	0	79	86	68	0
max		100	55	100	175	120	200	158	179	100	89	0	100
min		31	17	100	29	0	30	34	78	18	0	0	100
average		82	45	100	99	84	112				68	0	100
median		88	48	100	94	88	110				74	0	100
stdev		15	8	0	30	27	37				22

Friday, 16 May 2008:
1. Announcing the Final Exam Question Raffle: some of you have expressed some discontent with the questions of previous exams. Here is your opportunity to influence that, and gain something while doing so. I am soliciting suggestions for questions for our coming Final Exam next week. Here are the terms:
  1. You may submit as many questions as you want;
  2. questions should cover topics that have been discussed in class and / or been assigned as reading or assignments;
  3. for each question you submit, you should also submit a complete solution;
  4. if I choose your question for the final, AND if your submitted solution is both complete and correct, AND if I am reasonably convinced that you did not copy it from anybody / anywhere, you will immediately get full points for that question (all you'll have to do is write in the exam "this is my question" or something like that);
  5. if I choose your question but you have provided no solution, a partial or a wrong one, or your solution was actually "borrowed" from someone / somewhere, you get no immediate points;
  6. all entries must be in by Sunday, 17 May 2008, 5:00 p.m.
2. Some of you presented a different (possibly valid) solution approach to Question 2 of the last exam. If you want me to reconsider your answer, please drop off your exam paper (or scan and attach to an e-mail). No promises, but there may be a few additional points for you.
Tuesday, 29 April 2008: HW7 now due Wednesday, 7 May 2008, 11:59 p.m.
Monday, 28 April 2008: OK, by special request, I will allow the cheat-sheet for Exam 2 to be double-sided. This doesn't mean you must use both sides. In particular, the more you try to pack in, the more you'll have to search through during the exam. That can be wasteful. And, with more space, you stand the risk of copying more material verbatim than digesting and summarizing; try to avoid that, because digesting and summarizing will be much more useful than all that text on the page.
Tuesday, 22 April 2008:
1. Solutions to HW5.
2. Homework assignment 7 -- NP-Completeness (Ch. 34): due Sunday, 4 May 2008, 11:59 p.m. (but I recommend you do as much as you can by our 2nd exam, Wed. 30 April).
Monday, 14 April 2008:
1. Homework assignment 6 -- All-Pairs Shortest Paths (Ch. 25), Flow Networks (Ch. 26): due Wednesday, 23 April 2008, 11:59 pm.
2. I will (probably) post another assignment, to be due on 30 April 2008, the day of Exam 2, mostly for the purpose of practice for it.
3. The Final Exam will be held on Wednesday, 21 April 2008, 6:00-9:00 pm, OS311 (our usual classroom).
Thursday, 3 April 2008:
1. We will hold Exam 2 on 30 April 2008 (not on the 9th as previously announced in the syllabus); see revised topics page.
2. Solutions to HW3 and HW4.
Wednesday, 12 March 2008:
1. Homework assignment 5 -- Graph Algorithms, Chs. 23, 24: due Wednesday, April 9, 2008, 11:59 pm.

Wednesday, 12 March 2008:

Solutions to HW2 and Exam 1.

Here are (slightly updated) grades so far (hw1-4 and exam1). Note that letter grade estimates are just that, estimates. As the number of assignments and exams grows, and with changing grades and their weights, your letter grade may change. I would pay more attention to your numerical grades at this time.

91.503		relative	raw	hw1	hw2	hw3	hw4	hw5	hw6	hw7	hw8	exam1	exam2	final exam, raw
				1	1	1	1	0	0	0	0	1	0	0
Spring 2008	Grade estimate			0.125	0.125	0.125	0.125	0.125	0.125	0.125	0.125	0.5	0.5	0.4
			100	100	100	100	100	100	100	100	100	100	100	100
grade dist ID
037	B	84	77	100	126	101	120	0	0	0	0	54	0	0
082	A	97	89	100	77	102	110	0	0	0	0	83	0	0
094	B+	88	80	100	106	83	70	0	0	0	0	72	0	0
100	C+	73	67	100	55	65	110	0	0	0	0	53	0	0
109	A	100	92	100	134	0	130	0	0	0	0	84	0	0
117	B+	88	81	100	74	96	160	0	0	0	0	69	0	0
120	A	98	90	100	110	110	170	0	0	0	0	80	0	0
146	C+	67	61	100	29	20	30	0	0	0	0	77	0	0
150		53	48	100	84	0	0	0	0	0	0	0	0	0
155	A	98	90	100	96	106	100	0	0	0	0	80	0	0
181	A	97	89	100	94	83	130	0	0	0	0	83	0	0
197	B	82	75	100	70	83	100	0	0	0	0	61	0	0
210	A-	93	85	100	91	97	100	0	0	0	0	73	0	0
215	A	97	89	100	90	0	120	0	0	0	0	80	0	0
218	A-	94	86	100	151	120	150	0	0	0	0	72	0	0
234	A	100	92	100	175	113	200	0	0	0	0	84	0	0
240	B+	90	82	100	99	95	100	0	0	0	0	66	0	0
246	B+	89	82	100	86	0	0	0	0	0	0	67	0	0
248	B+	88	80	100	123	85	120	0	0	0	0	64	0	0
291	A-	92	84	100	93	80	100	0	0	0	0	75	0	0
353	B	83	76	100	94	108	110	0	0	0	0	53	0	0
355	A-	90	82	100	111	89	80	0	0	0	0	73	0	0
361	B+	89	82	100	143	91	100	0	0	0	0	66	0	0
362	B-	74	67	100	99	80	50	0	0	0	0	53	0	0
387	C	62	57	100	62	40	110	0	0	0	0	38	0	0
411	B	84	77	100	91	87	50	0	0	0	0	71	0	0
461	B	81	74	100	81	0	120	0	0	0	0	78	0	0
491	A-	96	88	100	89	95	100	0	0	0	0	79	0	0
538	B+	87	80	100	131	75	170	0	0	0	0	66	0	0
max		100	92	100	175	120	200	0	0	0	0	84	79	100
min		53	48	100	29	0	30	0	0	0	0	0	79	100
average		87	79	100	99	84	111					65	79	100
median		89	82	100	94	89	110					71	79	100
stdev		12	11	0	30	28	38					21

Wednesday, 5 March 2008:
- Re: Homework assignment 4 : since my instructions could be interpreted ambiguously, I will accept your current submissions, attempting a total of 100 point for the entire assignment.

Thursday, 28 February 2008:

Please include your name in your homework assignment submission files -- it makes it easier for the TA to know who you are.
The Graduate file system was full last night; many of your submissions didn't go through. I have reopened submissions until tomorrow (Friday) at midnight.

Here are your grades for hw1 and hw2. You should have -- in your @student.uml.edu address -- a message with your grade dist ID.

91.503	hw1	hw2
Spring 2008	2.50%	2.50%
	100	100
grade dist ID	0	0
037	100	126
082	100	77
094	100	106
100	100	55
109	100	134
117	100	74
120	100	110
146	100	29
150	100	84
155	100	96
181	100	94
197	100	70
210	100	91
215	100	90
218	100	151
234	100	175
240	100	99
246	100	86
248	100	123
291	100	93
353	100	94
355	100	111
361	100	143
362	100	99
387	100	62
411	100	91
461	100	81
491	100	89
538	100	131
max	100.0	175.0
min	100.0	29.0
average	100.0	98.7
median	100.0	94.0
stdev	0.0	30.2

Please address all grading questions to the TA, Ms. Minseo Park (mpark@cs.uml.edu -- with a cc to me).

Wednesday, 27 February 2008:
1. Homework assignment 4 -- Amortized Analysis and a little of Graph Algorithms: due Wednesday, March 5, 2008, 11:59 pm.
2. Remember, next week (March 5) is our first exam. Bring with you one, single-sided, hand-written sheet of paper with whatever information you care to put in it. You will have to turn it in with your exam (I will return it to you).
Wednesday, 20 February 2008:
1. Homework assignment 3 -- Greedy Algorithms: due Wednesday, February 27, 2008, 11:59 pm.
Sunday, 10 February 2008:
1. Homework assignment 2 -- Dynamic programming: due Wednesday, February 20, 2008, 11:59 pm.

Wednesday, 6 February 2008:
1. Someone left a water bottle after class tonight; I have it.

Thursday, 24 January 2008:
1. announcements, announcements; and
2. more announcements ... coming up

Make sure to READ AND FOLLOW the Academic Honesty guidelines!

Important dates

See the Graduate Spring 2008 Academic Calendar and the Undergraduate Spring 2008 Academic Calendar.

Back to syllabus