|
|
CSCI 303 , Fall 2006
|
What's new:
Final Exam grades have been posted on http://totale.usc.edu.
Course Info:
|
|
Professor Leonard M. Adleman |
|
Yuriy Brun |
|
|
Textbook |
Introduction
to Algorithms (second Edition) |
|
Lectures |
14:00-15:20 MW in SLH100 |
|
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. |
September 11, 2006 – Lecture 6
September 13, 2006 – Lecture 7
September 18, 2006 – Lecture 8
September 20, 2006 – Lecture 9
September 25, 2006 – Lecture 10
September 27, 2006 – Lecture 11
November 13, 2006 – Lecture 23
November 15, 2006 – Lecture 24
November 20, 2006 – Lecture 25
November 22, 2006 – Lecture 26
November 27, 2006 – Lecture 27
November 29, 2006 – Lecture 28
Click here to for notes from Fall 2005
Course Outline (Tentative)
EASY PROBLEMS:
Introduction to analysis of algorithms:
Insertion sort, merge sort, asymptotic
notation
(Chapter 3 contains "basic math" and should be read as needed during
the semester)
Homework 1: 2.1-1, 2.2-1, 2.2-2, 2.3-1, 2.3-3, 1.2-2, 1.2-3, 1-1, 3.1-2, 3.1-4,
3-3
solutions
Recurrences, the master theorem, divide and
conquer: binary search, Strassen's algorithm
Reading: Chapter 4 (excluding Section 4.4), Section 28.2
Homework 2: 4.3-2, 4-1, 4-4, 4-6, 28.2-4
solutions
Median and order statistics
Homework 3: 9-1, 9.2-4, 9.3-1, 9-3.5, 9.3-8
solutions
Lower bounds on sorting
Homework 4: 8.1-1, 8.1-4
solutions
Data Structures, heaps, priority queues
Reading: Chapter 6
Homework 5 : 6.1-1, 6.1-6, 6.2-1, 6.2-6, 6.3-1, 6.4-4, 6.5-7
solutions
HARD PROBLEMS:
NP-Completeness:
P, NP, NP-completeness, reductions.
Reading: Sections 34.1, 34.2, 34.3 and 34.4 as needed
Homework 6: 34.1-3, 34.1-5, 34.2-3, 34.3-2, 34.3-3,
34.4-6, 34.4-7
solutions
NP-completeness of 3-SAT, Subset Sum,
Clique, Vertex-Cover, Hamiltonian Path, Traveling Salesman.
Homework 7: 34.5-5
solutions
Cryptography:
RSA public key cryptography, Introduction to
number theory, Number theoretic algorithms, Primality (Miller-Rabin)
Homework 8: 31.1-1, 31.1-7, 31.2-2, 31.6-1, 31.7-1
solutions
Undecidability:
Programs and the functions they compute.
Undecidability of the Halting problem. Reductions. Chaitin-Kolmogorov
Randomness
Optional
Homework 9 | solutions
Topics (as time permits):
DNA computing
Quantum computing