A1-Beveled.gif

CSCI 303 , Fall 2007
Analysis of Algorithms

=================================================

What's new?

10/16/2007- Midterm on Wednesday 10/24/2007

10/22/2007 – Two sessions on Tuesday at VHE 217: one at 12:50-1:50 and other at 4:00-5:00.

11/07/2007 – Quiz grades have been uploaded on blackboard.

11/09/2007 – Midterm 1 grades have been uploaded on blackboard. (Minimum is 25, and maximum is 108 and the average is around 81 out of 110)

11/092007 – Quiz 2 will be on Wednesday 11/28/2007. It will cover homeworks 6, 7, and 8.

12/10/2007 – Quiz 2 grades have been posted on blackboard. Average is 4.5, minimum is 1 and maximum 10 out of 10.

12/10/2007 – Final is on Friday 14th (December) between 2-4pm.

11/20/2007 – Final grades have been uploaded on blackboard. (Minimum is 30, and maximum is 111 and the average is around 78.5 out of 120)

 

 =================================================

 Course Info:

 


Instructor

Professor Leonard M. Adleman
Office hours: by appointment 
Email : adleman[at]usc.edu

TA

Derya Ozkan 
Office hours: Monday between 10:50-11:50 and Thursday between 12:50-13:50. Office: PHE 216
Email: derya[at]usc.edu

Textbook

Introduction to Algorithms (second Edition)
Thomas H Cormen, Charles E. Leiserson, Ronald L. Rivest and Cliff Stein published by MIT Press and McGraw-Hill.

Lectures

14:00-15:20 MW in SSL 150 

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. 

 

=================================================


 
Class Notes

Spring 2007

 

 

=================================================

Course Outline (Tentative)

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)
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

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

Median and order statistics
Reading : Chapter 9.

Homework 3: 9-1, 9.2-4, 9.3-1, 9-3.5, 9.3-8

Lower bounds on sorting
Reading: Section 8.1

Homework 4: 8.1-1, 8.1-4

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

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

NP-completeness of 3-SAT, Subset Sum, Clique, Vertex-Cover, Hamiltonian Path, Traveling Salesman.
Reading: Section 34.5
Homework 7: 34.5-5


Cryptography:

RSA public key cryptography, Introduction to number theory, Number theoretic algorithms, Primality (Miller-Rabin)
Reading: Sections 31.1, 31.2, 31.6, 31.7, 31.8
Homework 8: 31.1-1, 31.1-7, 31.2-2, 31.6-1, 31.7-1


 Undecidability:

Programs and the functions they compute. Undecidability of the Halting problem. Reductions. Chaitin-Kolmogorov Randomness
Optional Reading : Godel, Escher Bach by Douglas Hofstadter
Homework 9

Topics (as time permits):

DNA computing
Quantum computing

 =================================================

To give some idea of how Professor Adleman grades, here are the results from some recent CS303 classes.

Fall 2006:
37 students
7 (19%) got A+ / A / A-
16 (43%) got B+ / B / B-
12 (32%) got C+ / C / C-
2 (5%) got D+ / D / D-

Fall 2001:
89 students
17 (19%) got A+ / A / A-
33 (37%) got B+ / B / B-
35 (39%) got C+ / C / C-
3 (3%) got D+ / D / D-
1 (1%) got F+ / F / F-

Fall 2000:
75 students
14 (19%) got A+ / A / A-
22 (29%) got B+ / B / B-
27 (36%) got C+ / C / C-
8 (11%) got D+ / D / D-
4 (5%) got F+ / F / F-

The University of Southern California does not screen or control the content on this website and thus does not guarantee the accuracy, integrity, or quality of such content. All content on this website is provided by and is the sole responsibility of the person from which such content originated, and such content does not necessarily reflect the opinions of the University administration or the Board of Trustees