Home   Video/Audio Library     Course Archive   Papers Archive   Beyond the Box   CV   Service My Keeper Shelf Cultural References in Class

COSC 511 Design and Analysis of Algorithms FALL 2014

Restored 9/24/2014

Office Hours: 511E Pray-Harrold

Required Texts:

1. Lecture notes, Recordings

Date Lecture notes Video/Audio Reading
12/9 Simulated annealing
12/4 Monte Carlo method:
11/13 Beginning Network Flow See youtube examples Kleinberg & Tardos 7.1 and 7.2
10/30 Continuing dynamic programming: sequence alignment sequence alignment: 'name' and 'mean', 'miss' and 'misses' K & T Chapter 6 Dynamic programming -- the applications discussed in class
10/28 Continuing dynamic programming: subset sums, travelling salesman problem subset sums
10/26 Intro to dynamic programming: fibonacci numbers, weighted interval scheduling dynamic programming examples
weighted interval scheduling
10/16 Karatsuba (Recursive Integer Multiply) Algorithm pseudo-code and comment In class assignment
10/14 Read over Recursive (integer) multiply K & T section 5.5
We will come back to FFT (section 5.6) if we have time
--it is another divide and conquer algorithm
10/9 k-fold clustering, minimum spanning tree (K & T, chapter 4) Read over Divide and Conquer in K & T
10/2 Videos on various graph algorithms ( See here )
9/25 Topological sort, EPI #5.7, 5.8 solutions K&T chapter 4 Greedy algorithms (4.1, 4.2, 4.3, 4.4)
Do EPI problems 6.1, 6.8
9/23 Review of binary tree traversals, expression tree, graph traversals (BFS, DFS)
Notes		 K & T 3.4-3.6
Work through EPI5.7, 5.8, be prepared to discuss
9/18 Graph traversals
Notes		 K & T 3.1-3.3
9/11 Review of asymptotic behaviors for running time (K & T 2.1 - 2.4)
9/9 Gale Shipley algorithm KS chapter 1   KT chapter 2 -- review the Exercises 1-8
Do EPI 5.1 -- be prepared to discuss it in class
9/4 Review Big Oh, stack, queue, search tree, heap, hash table
Can a string be permuted into a palindrome? O(n) vs O(n! n). -- EPI #13.2 or EPI p. 28		 K&T 1.1, 1.2; K&T 2.1
EPI chpt 4


2. Assignments (Homework) s
Date Assigned Date Due Assignment
10/30 11/4 Dynamic Programming (subset sums, TSP)       Solution
10/16 10/16 In class assignment
10/9 -- 10/16 10/16 10/21 MST and shortest path
9/18 ? 9/30 n2 timing
9/23 9/23 In class work
9/11 ? 9/23 K & T Exercises (chpt 2) 2.1, 2.2, 2.3, 2.4
9/9 9/16 Exercise Gale Shipley algorithm see HW0909.txt , Solutions
9/4 9/11 Observe K&T Table 2.1.
Collect time measurements for n=100, 103, 104, 105 for O(n), O(n2), O(n3) programs.
You may need to choose different values for n in order to get observable growth curves.
Demonstrate (by graphing) that the measurements grow as expected for a particular program.
Any language is acceptable.
You must give hard copy of code, including how you obtain the execution times. The graphs must be hard copy.


3. Projects 4. Quizzes and Tests 5. General 6. Resources


Last changed: