I will post announcements here from time to time.
(November 21, 2008) You can find the notes for today's make-up lecture HERE. The steaming video will be available shortly.
(November 6, 2008) Quiz 13 needs to be rescheduled to conform with University policy. I would like to have it at the regular time on Tuesday 11/15 (one week earlier).
(October 1, 2008) Tomorrow's Quiz 6 will be to solve a recurrence (not with the substitution method). Assignment 5 is now online, below.
(September 11, 2008) Homework Assignment 3 is now posted. See below.
(September 2, 2008) I am switching my Thursday office hours to Wednesday (same time). See my office hours, above.
(September 2, 2008) Homework Assignment 2 is now posted. This Thursday's quiz will be derived from Assignment 1 subject matter, as with the previous quiz.
(August 22, 2008) Homework Assignment 1 is now posted (see the Homework Assignments section, below). The quiz on Thursday, August 28 will resemble one of the questions on this homework. We will cover sums intensively on Tuesday, August 26.
(August 21, 2008) Here are the multiplication programs
mul1 and mul2 that I used in class.
They differ only in the multiplication routine. You may need to edit
the first line of each according to where perl is installed on your
system (usually /usr/bin/perl or /usr/local/bin/perl on Unix-like
systems). I don't know how to run perl scripts on MS Windows, so it's
not worth asking me. Also make sure that the files are executable.
Usage (in the directory where the programs reside):
./mul1 12 13
or
./mul2 1232139812739 232304052343145569758444401
etc. Here are the two test files I used: num1 and
num2. I edited num2 so it's now slightly different from
num1, which hasn't changed. Usage:
./mul[12] `cat num1` `cat num2`
This inserts the contents of the two files into the command line as
arguments.
There is a CSE department email list for CSCE 750. The list contains the departmental account addresses of all students registered for the course at the start of the semester. You are responsible for making sure your name on this list if you have any doubt. If you want your mail sent to another address, you may set this up either by editing the .forward file in your home directory, or by or by going to https://www.cse.sc.edu and clicking on Using Email/Forward your Email. You can put in this mail list any address you choose that gets mail to you.
Any mass mailing to the entire class will be done through the mail alias csce750 mentioned above. If I need to initiate an email to you individually, I will do so using the CSE departmental account that all students get as part of being registered in this class. You are responsible for reading email sent to this account or else setting up the dot-forward file to send it on to an account that you do read regularly.
Below are roughly the sections of the CLRS book that I will cover. I may de-emphasize some topics and add others, but this is basically the list.
| Topic | Text Reference |
| Summations | CLRS Appendix A |
| Intro to Algorithms | CLRS Ch 1 (brief) |
| Getting Started | Ch 2 (brief) |
| Order of Growth/Asymptotics | Ch 3 |
| Recurrences | Ch 4 |
| Numeric and Arithmetic Algorithms (supplemental) | |
| Heapsort | Ch 6 |
| Quicksort | Ch 7 |
| Lower Bounds for Sorting | Ch 8 (Section 1 only) |
| Order Statistics | Ch 9 |
| Counting and Probability | Appendix C |
| Elementary Data Structures | Ch 10 (brief) |
| Hash Tables | Ch 11 (Sections 1 and 2 only) |
| Binary Search Trees | Ch 12 (brief) |
| Red-Black Trees | Ch 13 |
| Augmenting Data Structures | Ch 14 (brief) |
| Dynamic Programming | Ch 15 |
| Greedy Algorithms | Ch 16 |
| Amortized Analysis | Ch 17 |
| Binomial Heaps | Ch 19 |
| Disjoint Sets | Ch 21 (Section 3 only) |
| Intro to NP-Completeness | Ch 34 Sections 1 and 2 |
| Elementary Graph Algorithms | Ch 22 |
| Minimum Spanning Trees | Ch 23 |
| Theory of NP-Completeness | Ch 34 Section 3 |
| Dijkstra's Algorithm | Ch 24 Section 3 |
| Floyd-Warshall Algorithm | Ch 25 Section 2 |
| Proving Problems NP-Complete | Ch 34 Sections 4 and 5 |
There will be weekly quizzes -- 13 in all during the semester. These will be taken during the first 10 minutes of class are are closed book, closed notes. The quizzes are weighted equally and your lowest quiz score will be dropped, effectively making 12 quizzes, each worth 5% of your grade (60% total). Each quiz will be a single problem similar to one of the homework problems given below. The general topic of the quiz will be either announced in class or by a mass emailing to the class.
Here is the schedule of quizzes. Note that some are on Tuesday and some are on Thursday.
| Quiz 1 | Thu 8/28 |
| Quiz 2 | Thu 9/4 |
| Quiz 3 | Thu 9/11 |
| Quiz 4 | Thu 9/18 |
| Quiz 5 | Thu 9/25 |
| Quiz 6 | Thu 10/2 |
| Quiz 7 | Tue 10/14 |
| Quiz 8 | Tue 10/21 |
| Quiz 9 | Tue 10/28 |
| Quiz 10 | Thu 11/6 |
| Quiz 11 | Thu 11/13 |
| Quiz 12 | Thu 11/20 |
| Quiz 13 | Tue 12/2 (tentatively rescheduled for 11/25) |
There will be a final exam on Thursday, December 11 from 2 to 5 pm. It is open book, open notes. The final counts for the other 40% of your grade. The final exam will be cumulative, but will emphasize topics that were not covered in the quizzes. The
APOGEE students must make arrangements to have the exams proctored during the times given above.
Each exam question will be loosely derived from the topics covered by homework exercises. So if you can do the homework exercises well, this should correlate with doing well on the exams.
Homeworks are to be completed, but you do not need to submit them unless you want feedback on one or more specific questions. They are for your own benefit to study for the exams. HOMEWORKS DO NOT COUNT TOWARD YOUR GRADE.
I will reschedule a student's taking the final exam only in the case of a significant medical emergency, with prior warning if possible. Nonmedical emergencies (car won't start, etc.) and planned events (sports meets, weddings, travel reservations, etc.) are not sufficient reason to reschedule an exam. Please consider this before committing to taking the course.
Fall 2008 Assignment 1:
Page 1062, Exercises A.1-1, A.1-3, A.1-4, A.1-6, A.1-7
Page 1067, Exercises A.2-1, A.2-2, A.2-3, A.2-4, A.2-5
Page 1069, Problem A-1(a,b,c)
Page 13, Exercise 1.2-3
Show by splitting the sum that the sum from n = 2 to ∞ of 1/(n lg n) diverges.
Fall 2008 Assignment 2:
Page 39, Problem 2-4(a,b,c,d)
Page 50, Exercises 3.1-1, 3.1-2, 3.1-3, 3.1-4
Page 57, Exercises 3.2-1, 3.2-3, 3.2-4, 3.2-6
Page 57ff, Problems 3.1(a,b,c), 3.2(a-f), 3.3(a,b)
Page 59, Problems 3.4(a,b,d,g)
Fall 2008 Assignment 3:
Page 67, Exercises 4.1-1, 4.1-2, 4.1-3, 4.1-4, 4.1-5, 4.1-6 (all substitution method)
Page 72, Exercise 4.2-1, 4.2-3, 4.2-5
Page 75, Exercises 4.3-1(a,b,c), 4.3-2, 4.3-3, 4.3-4
Page 85ff, Problems 4-1(a,c,f,g), 4-2, 4-4(a,c,e,g,j)
Fall 2008 Assignment 4:
Page 129ff, Exercises 6.1-1, 6.1-2, 6.1-3, 6.1-5, 6.1-6, 6.1-7
Page 132, Exercises 6.2-1, 6.2-2, 6.2-3, 6.2-5, 6.2-6
Page 135, Exercises 6.3-1, 6.3-2, 6.3-3
Optional (because it is a bit tricky): Page 136ff, Exercise 6.4-4
Page 140ff, Exercises 6.5-1, 6.5-2, 6.5-6, 6.5-8
Page 143, Problem 6-3(a,c,d,f)
Fall 2008 Assignment 5:
Page 1098ff, Exercises C.1-1, C.1-2, C.1-3, C.1-4, C. 1-7, C.1-8
Page 1105ff, Exercises C.2-2, C.2-3, C.2-4, C.2-5, C.2-9
Page 1111, Exercises C.3-1, C.3-2, C.3-3
Page 1116, Exercises C.4-2
Page 1125, Problem C-1(a,c)
Page 98, Exercises 5.2-3, 5.2-4, 5.2-5
Fall 2008 Assignment 6:
Page 168ff, Exercises 8.1-1, 8.1-3
Page 192ff, Exercises 9.3-3, 9.3-4, 9.3-5, 9.3-7
Page 194ff, Problems 9-1(a,b,c), 9-2(a,b,c,d,e)
Fall 2008 Assignment 7:
Page 277, Exercise 13.1-1, 13.1-2, 13.1-4, 13.1-5, 13.1-7
Page 279, Exercise 13.2-3, 13.2-4
Page 287, Exercise 13.3-2, 13.3-3, 13.3-5
Page 294, Problem 13-1(a,b,c,e) (for (a), don't worry about deletion)
Page 296, Problem 13-4(a,b,c,d) (Hint for part (b): this is similar to
the analysis of randomized Quicksort.)
Show the result of entering the following (key,priority) pairs in order into a
treap: (5,0.3), (9,0.7), (7,0.5), (2,0,1), (8,0.4), (4,0.2).
Fall 2008 Assignment 8:
Page 338, Exercise 15.2-1, 15.2-3, 15.2-4
Page 349, Exercise 15.3-1, 15.3-3
Page 356, Exercises 15.4-1, 15.4-2, 15.4-4, 15.4-5
Page 364ff, Problem 15-1, 15-4 (optional)
Fall 2008 Assignment 9:
Page 384, Exercise 16.2-5, 16.2-7
Page 392, Exercises 16.3-2, 16.3-3, 16.3-4, 16.3-5, 16.3-7
Page 416, Exercises 17.3-1, 17.3-2, 17.3-3, 17.3-4, 17.3-5, 17.3-6, 17.3-7
Page 425, Exercise 17.4-3
Page 426, Problem 17-1(a,b,c), 17-2(a,b,c)
Give the result of adding the keys 10,...,1 in that order into an
initially empty splay tree.
Fall 2008 Assignment 10:
Page 530, Exercises 22.1-1, 22.1-3
Page 538ff, Exercises 22.2-1, 22.2-3, 22.2-5, 22.2-6 (this is just a
test for graph bipartiteness)
Page 566, Exercises 23.1-1, 23.1-3, 23.1-5, 23.1-7
Run Kruskal's algorithm to find a MST for the graph in Figure 23.1 (page
562). Just give the order that edges are added to the tree.
Run Prim's algorithm to find a MST for the same graph, starting at
vertex d. Just give the order in which edges are added to the tree.
Fall 2007 Assignment 9:
Read the rest of Chapter 34, skipping the section about Circuit
satisfiability (on pages 987-994) and the proof of Theorem 34.9 (on
pages 997-998). We'll use Theorem 34.9, without proof, as a starting
point for understanding NP-complete problems.
Page 600, Exercises 24.3-1, 24.3-2, 24.3-4
Page 634ff, Exercise 25.2-1, 25.2-4
Page 982ff, Exercise 34.2-1, 34.2-3, 34.2-7, 34.2-11 (optional)
Page 1017ff, Exercises 34.5-1, 34.5-4 (hint: dynamic programming),
34.5-5, 34.5-8 (optional)
Page 1018ff, Problems 34-1(a,b,c), 34-2(a,b,c,d)
A sample first-offense admission can be found at admission.
This page was last modified Friday November 21, 2008 at 14:1:45 EST. It was compiled from the source index.ptex using the utility p2h.