CSC 413/513: Introduction to Algorithms

Fall-2014

Syllabus : Posted on August-20-2014.

Last day to drop and receive 100% financial credit: Aug-27-2014
Last day to drop and (possibly) get a W grade: Oct-31-2014

Dr. Koh will instruct this class on and from Sep-25. Assignment 3 is still due on that day.

Test Schedule

Midterm on:
TBD

Syllabus: TBD.

Final on:
TBD

Syllabus: TBD


Assignments

For all assignments show your work, don't just write the answers.

Assignment 9

Due on TBD
1. Problems 22.4-1 (10 pts), 23.1-1 (5 pts), 23.2-8 (5 pts), 24.1-1 (5+5 pts).

Assignment 8

Due on TBD
1. Problem 16.1-2 (10 pts).
2. Problem 16.1-3 (16.1-4 in 2nd ed). Give 3 clear examples (3X5 pts).
3. Problem 22.3-5 (22.3-4 in 2nd ed) (3X5 pts).
4. Solve the 0-1 knapsack problem from assignment 7, as a fractional knapsack problem (5 pts).
5. (Graduate students only; extra credits for undergrads) Problem 22.2-7 (22.2-6 in 2nd ed) (10 pts).

Assignment 7

Due on TBD
1. Problem 15.2-1 (10 pts).
2. Find the LCS of "spanking" and "amputation" (10 pts).
3. Solve the 0-1 knapsack problem: w={2,5,3,8,6,10}, v={6,2,5,4,7,1}, W=16. (10 pts)
4.(Graduate students only; extra credits for undergrad students) Problem 15.4-5 (5 pts).

Assignment 6

Due on TBD. Problems 12.1-1 (2X5 pts), 12.2-1 (5 pts), 12.2-4 (5 pts), 12.3-4 (5 pts), 13.1-2 (5 pts), 13.3-2 (10 pts).

Assignment 5

Due on TBD. Problems 11.1-2 (3pts), 11.2-2 (5 pts), 11.2-5 (5 pts; apply the pigeon-hole principle), 11.3-4 (5 pts). Problem 11.3-3 for graduate students only (10 pts; extra credits for undergrads).

Assignment 4

Due on TBD. Problems 7.1-1 (10 pts), 7.2-2 (3 pts), 8.2-1 (10 pts), 8.3-1 (5 pts), 8.3-2 (3+4 pts), 8.4-1 (5 pts). Problem 8.1-3 (4X3 pts) for graduate students only (extra credits for undergrads).

Project

Due on TBD. Submit a one-page printed or handwritten report only. No emails.

Assignment 3

Due on Sep-25-2014. Problems 6.1-4 (4 pts), 6.1-6 (4 pts), 6.2-1 (6 pts), 6.3-2 (4 pts). Problem 6.3-3 (6 pts) for graduate students only (extra credits for undergrads). The complete problem statements can be found here (thanks to Jundi Wang).

Assignment 2
Solution

Due on Sep-16-2014. Note: "(repeated) substitution" refers to the iteration method shown in class.

Assignment 1
Solution

Due on Sep-04-2014.

Class Slides

File 1

Introduction, review of mathematical induction, asymptotic notation

File 2

Insertion sort, asymptotic analysis

File 3

Merge sort, recurrence relations, solution by substitution and iteration

File 4

Recurrences and master theorem, Heapsort.

File 5

Quicksort.

File 6

Lower bound of sorting, linear time sorting: counting sort, radix sort and bucket sort.

File 7

Hash tables.

File 8

Binary Search Trees.

File 9

Red Black Trees.

File 10

Insertion in Red Black Trees.

File 11

Dynamic Programming: LCS, matrix-chain multiplication.

File 12

Dynamic Programming: 0-1 Knapsack.

File 13

Greedy Algorithms: Activity Selection, fractional knapsack.

File 14

Graph basics with breadth first seach.

File 15

Graph algorithms: Depth first search.

File 16

Graph algorithms: Topological sort, minimum spanning tree and Prim's algorithm.

File 17

Graph algorithms: Single source shortest path, Bellman-Ford and Dijkstra's algorithms. Also contains Kruskal's algorithm for minimum spanning trees.

File 18

NP-Completeness.

File 19

NP-Completeness and reductions.