|
|
CSCI 303, Fall 2009
|
What's new?
11/11/09 : Quiz 2 will be on Monday, November 23
Problems will come directly
from homeworks 5 and 6. You will not need a bluebook or a calculator.
11/11/09 : Homework 6 and solutions have been posted.
10/20/09 : The Midterm will be on Wednesday, October 28
You will not need a bluebook or a calculator.
There will be a review session on Friday, October 23 from 2-3:30 in GFS 118 (Please note the room change).
Dustin's office hours have been moved from Tuesday, October 27 to Wednesday, October 28 12-2pm in SAL 229.
10/20/09 : Homework 5 and solutions have been posted.
10/12/09: Homework 4 and solutions have been posted.
9/30/09: Homework 3 and solutions have been posted.
9/16/09 : Quiz 1 will be on Wednesday, September 23
Problems will come directly
from homeworks 1 and 2. You will not need a bluebook or a calculator.
9/14/09 : Homework 2 and solutions have been posted.
8/31/09: Homework 1 and solutions have been posted.
Course Info:
|
|
Professor Leonard M. Adleman |
|
Dustin Reishus Email: reishus[at]usc[dot]edu |
|
|
Textbook |
Introduction
to Algorithms (second Edition) |
|
Lectures |
|
|
Grades |
The final grade will be primarily based on class participation (10%), quizzes (20%), a midterm exam(30%), and a final exam (40%). Exams questions may come from topics covered in class lectures (except when the professor explicitly indicates otherwise) and from sections in the textbook indicated in the course outline. The grading policy is subject to change at any time for any reason. |
|
Exams |
The midterm and final will be closed book. Precision will matter; sloppy answers, even if correct, will receive fewer points than clean crisp ones. Bring a blue-book and be prepared to stay in your seat during the entire exam |
|
Homework |
There will be no graded homework. |
|
Integrity |
Plagiarism and other anti-intellectual behavior will be dealt with severely. This includes the possibility of failing the course or being expelled from the University. |
Course Outline
(Tentative)
Homework solutions will be posted throughout
the semester.
EASY PROBLEMS:
Introduction to analysis of algorithms:
Insertion sort, merge sort, asymptotic
notation
Reading: Chapter 1, Chapter 2.
(Chapter 3 contains "basic math" and should be read as needed during
the semester)
Recurrences, the master theorem, divide and
conquer: binary search, Strassen's algorithm
Reading: Chapter 4 (excluding Section 4.4), Section 28.2
Median and order statistics
Lower bounds on sorting
Data Structures, heaps, priority queues
Reading: Chapter 6
HARD PROBLEMS:
NP-Completeness:
P, NP, NP-completeness, reductions.
NP-completeness of 3-SAT, Subset Sum, Clique,
Vertex-Cover, Hamiltonian Path, Traveling Salesman.
Reading: Section 34.5
Cryptography:
RSA public key cryptography, Introduction to
number theory, Number theoretic algorithms, Primality (Miller-Rabin)
Undecidability:
Programs and the functions they compute.
Undecidability of the Halting problem. Reductions. Chaitin-Kolmogorov
Randomness
Optional
Topics (as time permits):
DNA computing
Quantum computing