11:45-12:40, M, W, F.
Melville Library, E4330
2424 CS Building; 632-8460
e-mail: keriko (at) cs.sunysb.edu
(Please put "CSE373" on the subject line.)
office hours: 3:30-5:00 Mon; 2:00-3:30 Wed
Yifan Peng
e-mail: yipeng (at) cs.sunysb.edu
office hour: 1-2pm, Thur., Rm 2110 CS building
Zhongyuan Xu
e-mail: zhoxu (at) cs.sunysb.edu
office hour: 4-5pm, Wed., Rm 2110 CS building
1. Algorithms and analysis (Chapter 2; 3 lectures)
2. Growth of functions (chapter 3, appendix A; 2 lectures)
3. Recurrence Relations (Chapters 4; 3 lectures )
4. Sorting (Chapters 6, 7, 8; 2 lectires)
5. Medians and order statistics (chapter 9; 2 lectures )
6. Binary search trees (Capter 12; 1 lecture )
7. Dynamic programming (Chapter 15; 5 lectures)
8. Greedy algorithms (Chapter 16; 2 lectures )
9. Graphs and graph algorithms (Chapters 22; 3 lectures)
10. Minimum spanning trees and shortest paths (Chapters 23, 24, 25; 6 lectures)
11. NP-Completeness (chapter 34; 4 lectures)
12. Approximation algorithms (chapter 35; 3 lectures)
2. Because one of the main goals of this course is to teach professionalism, any academic dishonesty will be viewed as the evidence that this goal has not been achieved and will be grounds for receiving a grade of F. (See CEAS Procedures and Guidelines Governing Academic Dishonesty, 1/81)
9/19: We will have test 1 on Friday, Sep. 25. It will be a 50-minute, open book test. It covers Chapters 2, 3 and 4.
9/19: Homework 1 is due on Monday, Sep. 21. Since the class size is large, we will not be able to finish grading before Friday's test. So, if you wish to study it to prepare for the test, please keep a copy for yourself. I will post my solutions on Tuesday, and we will review it on Wed's class.
10/23: We will have test 2 on Monday, Oct. 26.
It will be a 50-minute, open-book test.
It covers chapters 6, 7, 9, 12 and 15.
Some test questions are about specific details of
algorithms in Chapter 15. So, please make sure that
you bring the textbook to class on Monday.
11/2: Test 2 statistics:
Average: 29/50
Distribution: 40 to 50 => 10 people,
30 to 39=> 18 people, 20 to 29=>21 people, 10 to 19 => 10 people.
Homework 2 average: 83/120.
11/13: I am sick, and today's (Nov. 13) class is cancelled.
11/16: We will have test 3 on Friday, Nov. 20. The test covers Chapters 16, 22, 23. Again, it will be a 50-min, open-book test, and we will have a review session on Wed., Nov. 18.
You are encouraged, but not required, to form two-person homework teams to solve the homework questions together. Each team has at most two people, and both members are resposible for the submitted solutions and need to be able to orally present the solutions when asked. Each member of the team will receive the same grade points for that homework set. Please mark in your homework sheets clearly the names and ID's of both members of the team.
Homeworks are due in the class on the due date. Late homeworks are accepted only for exceptional cases, and no late homeworks will be accepted after they are reviewed in class.
A makeup test may be given for the midterm or final test for students who have legitmate reasons (severe illness or family emergency) to miss the test. Please show me the evidence, and let me know in advance if possible.
Discussion of homeworks are encouraged. However, no copying of solutions are allowed. Severe penalty will be imposed to both parties of the cheating case, including, at least, receiving zero point for the homework.
2-2, b, c (Just state the loop invariants, do not need to prove them)
3-3, part a (List all functions in the order of growth rate)
3-3 (extra): prove your result between lg(n!) and (lg n)!.
3-4, d, e (prove the correctness or present a counterexample)
(When you apply the Master theorem, make sure that you verify
all the required conditions.)
4-1, b, f
4-2 (You may assume that array A is actually a two-dimensional array
with A[i,j] denoting the jth bit of A[i].
You can present your algorithm in high-level pseudocodes. Please also
include a brief explanation why the total time of your algorithm is O(n).)
4-4, e
6.4-1 (First, show step-by-step, like in Figure 6.3, how BUILD-MAX-HEAP works on array A. Next, show
12.2-4
12.3-5
15.2-1 (Show the tables of m and s, as in
Figure 15.3.
15.4-4
15.5-2
15-2
16.1-3
16.2-5
16.3-2
16-1 (parts a, b, c)
22.1-5
22.2-6 [Hint: You may use, without proofs,
the results of Problem 22-1, part a (page 558).]
22.3-2; repeat the problem using the REVERSED alphabetical
order (in both lines 5-7, and in the adjacency list).
(For each DFS, re-draw the DFS tree, and show non-tree edges
by dash lines, and mark them as forward, backward, or cross edges,
as in Figure 22.4(p).)
22.3-7 (also explain why it is a counterexample).
22.4-1
22.5-2
22.5-7 [Hint: What does the component graph GSCC
look like if G is semiconnected?]
23-4 (For each of the three algorithms, determine whether it
is correct. If incorrect, show a counterexample.
If correct, you do not need to give a formal proof, just
give a brief explanation. Also, you do not need to describe
the implementations.)