(November 20, 2011) Here are all of this semester's quizzes. Solutions were covered in class.
(November 18, 2011) Here is ASSIGNMENT 13, which mostly deals with NP-completeness and reductions. It also has questions about Dijkstra's algorithm. There will likely be two questions on the final exam adapted from this assignment (one for each topic). For the former topic (NP-completeness), emphasis is on reductions (questions from Section 34.5 as well as the questions not in the text).
(November 10, 2011) Here is ASSIGNMENT 12. The thirteenth quiz will adapt a question from this assignment.
(November 6, 2011) Here is ASSIGNMENT 11. The twelfth quiz will adapt a question from this assignment.
(October 27, 2011) Here is ASSIGNMENT 10. The eleventh quiz will adapt a question from this assignment.
(October 19, 2011) Here is ASSIGNMENT 9. The tenth quiz will adapt a question from this assignment.
(October 13, 2011) Here is ASSIGNMENT 8. The ninth quiz will adapt a question from this assignment. The quiz will not be on material from Sections 15.3 or 15.4.
(October 6, 2011) Here is ASSIGNMENT 7. The eighth quiz will adapt a question from this assignment. The quiz will not be about treaps.
(September 29, 2011) Here is a PROOF that E(n) = O(n lg n), were E(n) is the expected running time of randomized Quicksort on n items.
(September 27, 2011) Here is ASSIGNMENT 6. The seventh quiz will adapt a question from this assignment.
(September 22, 2011) Here is ASSIGNMENT 5. The sixth quiz will adapt a question from Sections 6.1 or 6.5 of this assignment. All questions are fair game for the final exam.
(September 15, 2011) Here is ASSIGNMENT 4. The fifth quiz will adapt a question from the Appendix C portion of this assignment.
(September 13, 2011) Here is the schedule of quizzes for the rest of the semester. Quizzes will be given in class at the beginning of class. The last quiz is the Thursday before Thanksgiving vacation.
| Quiz 3 | Tue 9/13 |
| Quiz 4 | Thu 9/15 |
| Quiz 5 | Tue 9/20 |
| Quiz 6 | Tue 9/27 |
| Quiz 7 | Tue 10/4 |
| Quiz 8 | Tue 10/11 |
| Quiz 9 | Tue 10/18 |
| Quiz 10 | Thu 10/27 |
| Quiz 11 | Thu 11/3 |
| Quiz 12 | Thu 11/10 |
| Quiz 13 | Thu 11/17 |
(September 9, 2011) Here is ASSIGNMENT 3. The third quiz (on Tuesday, 9/13 at the start of class) will adapt a question from the Section 4.2 or 4.3 portion of this assignment.
(September 2, 2011) Here is ASSIGNMENT 2. The second quiz (on Thursday, 9/8 at the start of class) will adapt a question from this assignment.
(September 2, 2011) 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.
(August 30, 2011) The first quiz question will not be derived from questions A.1-6.
(August 19, 2011) I fixed a mistake below about when APOGEE students will be mailed the quizzes on quiz days. It now correctly reads 12:30pm instead of 9:30pm.
(August 19, 2011) Here is ASSIGNMENT 1. The first quiz (on Thursday, 9/1 at the start of class) will adapt a question from this assignment.
(August 19, 2011) Yesterday (8/18), I sent a test email message to the official class list. If you did not get this email you should check that you are properly registered for the class and that your email is forwarded correctly (see Email, below).
(August 9, 2011) There will be NO CLASS on 8/23 or 8/25. I am away at a conference that whole week. We will decide on two make-up sessions, most likely on Fridays (they will be recorded, so attending them is not absolutely necessary). Regular class will resume on 8/30.
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 that your name is on this list. 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 or Fibonacci Heaps | Ch 19 or 20 |
| 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 homework assignments, but they are not for credit. Rather they serve as sample questions for the associated quizzes (see below).
There will be weekly quizzes -- 13 in all during the semester. These will be taken during the first 10-15 minutes of class and 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 assigned the previous week. The general topic of the quiz may be either announced in class or by a mass emailing to the class. The first quiz is on Thursday, September 1, 2011.
APOGEE Students: If you are taking the course remotely, you will be emailed the quiz as a PDF attachment at the time of the quiz (12:30pm), and you will have 20 minutes to email me your answer. Your answer format is flexible; scanned handwritten paper is acceptable, but if you want to put your answer in an email message body, please read THIS first.
There will be a final exam on Friday, December 9, 2011 from 2 to 5 pm. It is open book, open notes, but no electronic devices except for legitimate use by students with documented special needs. 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.
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.
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.
A sample first-offense admission can be found at admission.
This page was last modified Sunday November 20, 2011 at 13:29:42 EST. It was compiled from the source index.ptex using the utility p2h.