CSC517-F: Algorithms
Prof. B. Rosenberg
Fall Semester, 2005-6 (061)
MWF 1:25-2:15 PM
Memorial Building, Room 205
The Class Syllabus
Exams:
- Midterm: Wed Oct. 19.
Example midterm
Histogram
- Final: Monday Dec 12, in class.
All material from midterm until the class of Friday, Dec. 9.
- Hashing
- Binary Search Trees
- Dynamic Programming and Greedy Algorithms
- Graph Algorithms
- Mininum Spanning Trees
- Shortest Paths
Class Text:
Announcements:
Workbook:
- Introduction
- Mathematical Preliminaries
- Sorting and Selection
- Hashing
- Resolution by chaining
- Hash functions
- Open addressing
- Universal and Perfect hashing
- Deletion in Hash tables
- Binary Search Trees
- Algorithm techniques and paradigms
- Dynamic Programming
- Greedy Algorithms
- Activity Selection
- Greedy versus Dynamic Programing.
- Huffman codes
- Amortized Analysis (optional material)
- aggreate, accounting and potential methods
- Dynamic tables
- Linear Programming (special topic)
- Graph Algorithms
- Breadth-first search
- Depth-first search
- Topological Sort
- Strongly Connected Components
- Union-Find and Kruskal MST
- Prim MST.
- Bellman-Ford single-source Shortest Paths
- Dijkstra's algorithm;
Exercises:
- Exercises 2.1-1 through 2.1-4;
Exercises 2.2-1 through 2.2-4.
Due: Wed 7 Sept
- Exercises 2.3-1 through 2.3-5 and Problem 2-2 (page 38).
Due: Friday Sept 16.
- Problems 3-1 through 3-4. Problems 4-1 through 4-4.
Due: Friday Sept 23.
- Exercisess 6.1-1 through 6.1-5; 6.2-1 through 6.2-4; 6.4-1
through 6.4-4.
Due: Friday Sept 30.
- Exercises 7.1-1, -2 and -3; 7.2-1, -2, and -3; 7.3-1 and -2.
Due: Monday Oct 10.
- Problems 6-2 (page 143); 7-1 and 7-2 (pages 159, 161); 8-2 and 8-4
(pages 178-179).
Due: Monday Oct 17.
-
Exercises 11.2-1, 11.2-2, 11.2-3; 11.3-1, 11.3-2, 11.3-3, 11.3-4;
11.4-1, 11.4-2.
Due: Friday Oct 28.
-
Exercises 12.1-1 through -5; 12.2-1 though -3; 12.3-1 through -5.
Due: Wed Nov 9.
-
Exercises 13.2-1 through -4; 13.3-1 through -3; and 13.4-1 through
-3.
Due: Fri Nov 18.
-
Exercises 15.1-1 through -3; 15.2-1 through -3; and 15.5-1 through -3.
Due: Wed Nov 30
Happy Thanksgiving
-
Exercises 16.1-2, 16.1-3; 16.3-1, 16.3-2; and problem 16-1 (page 402).
Practicum assignments:
- Using C on Unix of Windows, write Insertion Sort and Merge Sort.
Test them on data sets of increasing size and plot the run time, verifying
that Insertion Sort is quadratic and Merge Sort is n log n. Give the
cross over point, if any, when Merge Sort is faster than Insertion Sort
in actual run time.
Due: Monday Oct 3.
- Use the qsort libc function to sort a large data set of words.
You will have to master function pointers.
Compare speed to your implementations of Insertion and Merge Sort.
How does qsort avoid bad run times?
Due: Monday Nov 11.
- Implement a Skip List. Operations should be find, insert, and delete.
Due: Monday Dec 5.