CSC517-D: Algorithms
Prof. B. Rosenberg
Fall Semester, 2006-7 (071)
MWF 11:15-12:05
Memorial Building, Room 116
The Class Syllabus
Exams:
Class Text:
Announcements:
- There is a course blog which might be interesting.
- See last year's homepage for
more information.
- The grader is Valerie Leichtman
Workbook:
- Introduction
- Machine models, solvability, correctness, efficiency.
- Sorting a hand of cards, sorting a deck of cards..
- Tools of the Trade
- Sorting and Selection
- Randomized Algorithms and Probabilistic Analysis
- Hashing
- Resolution by chaining
- Hash functions
- Open addressing
- Universal and Perfect hashing
- Deletion in Hash tables
- Binary Search Trees
- Dynamic Programming
- Greedy Algorithms
- Activity Selection
- Greedy versus Dynamic Programing.
- Huffman codes
- Fast Fourier Transform
Exercises:
-
Problem 1-1. Exercises 2.1-1, 2.1-2, 2.1-3.
Due: Friday, Sept. 1
- Exercises 2.3-1, 2.3-2, 2.3-3 and 2.3-5; and Problem 2-2.
Due: Friday Sept. 15 (See
blog about ex. prob. numbering).
- Problems 3-1 through 3-3 (pages 57 and 58).
Due: Friday Sept. 22
- Exercises 6.2-1, 6.3-1, 6.4-1, 6.4-2, 6-4.3 and 6-4.4.
Due: Friday Sept. 29
New due date: Monday 2 Oct
- Exercises 7.1-1, 7.1-2, 7.1-3, 8.2-1, 8.2-2, 8.2-3, 8.3-1, 8.3-2, 8.4-1.
Due: Friday 6 Oct
- Read section 5.1 and 5.2; Do exercises 5.2-1, 5.2-2, 5.2-3, 5.2-4.
Due: Friday 13 Oct
- Do exerciese C.2-1, C.2-2, C.2-3, C.3-1, C.3-2, C.3-3.
Due: Friday 20 Oct
New due date: Monday 23 Oct.
- Do exercieses 11.2-1, 11.2-2, 11.2-3, 11.3-1 and 11.3-2.
Due: Friday 27 Oct
- Do exercises 12.1-1, 12.1-2, 12.1-3, 12.2-1, 12.2-2, 12.2-3.
Due: Friday 3 Nov
- Do exercise 12.3-1, 12.3-2, 12.3-3, 13.1-5, 13.1-6, 13.2-1,
13.2-2, 13.2-3, 13.2-4.
Due: Friday 17 Nov
- Do problems 15-2, 15-6, and 16-1.
Due: Monday 27 Nov
- Do exercises 16.3-1, 16.3-2 and 16.3-5.
Due: Friday 1 December
Practicum assignments:
- This is only for a person enrolled in the 400-numbered
practicum (only one person).
Investigate whether the formulas for hashing times of
successful and unsuccessful search are correct in practice.