Algorithm Analysis and Design
Syllabus
Lectures
Lecture # 1: The Stable Marriage Problem
Lecture # 3. Graphs (Read Chapter 3)
Lecture # 4 Greedy Algorithms (Read Chapter 4 of text)
The Floyd-Warshall All Pairs Shortest Path Algorithm
Lecture # 5. Divide and Conquer (Read Chapter 5 of text)
Lecture # 6. Sorting and Algorithm Design
Sorting Algorithms (powerpoint demonstrations)
Lecture # 7 Dynamic Programming -- The Exact-fit Knapsack
Lecture # 8 Longest Common Subsequence
Optimal Alignment of Two Strings
Lecture # 9 NP-Complete (Read Chapter 8)
Homework Assignments
Homework assignment # 1 -- text pages 22- 27 # 1, 2, 4, 6 due 9/7
Homework Assignment # 2 -- Big O Notation (due Sept. 14)
Homework assignment # 3 – text pages 67 – 70 # 4, 5, 6, 7, 8 due 9/21
Homework Assignment # 4 -- text pages 107 -- 112 # 2, 3, 5, 6, 7,
10, 11 due 9/28
Homework Assignment # 5 -- text pages 188 - 192 # 1, 2, 3, 4, 7,
8, 9 due October 5
Homework # 6 -- More Greedy Algorithms
Homework # 7 – Homework on Sorting Algorithms
(Due Oct. 22 -- to be handed in)
Direct Link to Sorting Lab applet
Homework Assignment # 8 -- Recurrence Relations (due Oct. 29)
Homework Assignment # 9 -- Dynamic Programming
(Due Nov. 9 -- programming probs to be submitted)
Homework Assignment # 10 -- text pages 316 - 334 # 5, 6,
19, 28 (due Nov. 16)
Software (for assignment # 6)
Group Assignment
Group Assignments updated on November 7. There are now only 3 teams.
Announcements
Take home exam Questions. You will prepare these questions
individually and expect to find 4 or 5 of them on the exam
Monday. The exam will
be closed book/closed notes, and about
80%
of the exam will consist of questions from this take home
portion. The rest of
the exam will be short answer/multiple choice
questions that test your broad understanding of the material
we covered, particularly the material on tractability and
NP-Complete problems.
Second Exam on Thursday, November 19 will cover material from
chapters 5 & 6 of the text.
First Exam on Monday, October 12 will cover the first 4 chapters of the text
(big-Oh Notation, Stable Matching, Graphs, Greedy Algorithms)
Material for Group Projects
Presentation on Bayseian Networks
Branch and Bound programs
code for Backtrack approach to the 0-1 Knapsack problem
code for branch and bound algorithm for the 0-1 Knapsack
code for backtracking algorithm for the N-Queens problem
code for the backtracking approach to the Hamiltonian Cycle
code for a branch and bound algorithm for finding a TSP cycle
code for Longest Common Subsequence Table Cell code