|
|
CSCI 303 , Fall 2007
|
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:
|
|
Professor Leonard M. Adleman |
|
Derya Ozkan |
|
|
Textbook |
Introduction
to Algorithms (second Edition) |
|
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. |
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
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
Homework 3: 9-1, 9.2-4, 9.3-1, 9-3.5, 9.3-8
Lower bounds on sorting
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.
Homework 7: 34.5-5
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
Undecidability:
Programs and the functions they compute.
Undecidability of the Halting problem. Reductions. Chaitin-Kolmogorov
Randomness
Optional
Homework 9
Topics (as time permits):
DNA computing
Quantum computing