CSC517: Data Structures and Algorithm Analysis - Spring 2005
Professor Christian A. Duncan
csc517@mail.cs.miami.edu

Resources

• Course Text Book: Algorithm Design by Goodrich and Tamassia
  (includes errata and more material)
• Black Board Site: use for discussion board and possibly other features.
  Try this direct link to the course: May not work unless you are already logged in.

Course Information

Course Notes (most likely very few will be provided, unfortunately)

• Course Syllabus (Lecture 1)
  (Tu, January 18)
  
• Lectures 1-2
  (Tu, January 18)
  (Th, January 20)
  Chapter One (Algorithm Analysis)
• Lecture 3
  (Tu, January 25)
  Chapter One (Algorithm Analysis)
• Lectures 4-5
  (Th, January 27)
  (Tu, February 1)
  Chapter Two (Basic Structures: Stacks, Queues, Trees)
• Lectures 6-7
  (Th, February 3)
  (Tu, February 8)
  Chapter Two (Heaps and Hash tables)
• Lecture 8
  (Th, February 10) Chapter Two (Hash tables) and
  Chapter Three (Binary Search Trees)
• Lectures 9-10
  (Tu, February 15)
  (Th, February 17)
  Chapter Three (AVL, Red-Black, and Splay Trees)
  No notes: Handed out PowerPoint slides
• Lecture 11
  (Tu, February 22)
  Chapter Three (Splay Trees, continued)
• Lecture 12
  (Th, February 24)
  Chapter Four (Sorting and Selection)
• Homework Review
  (Tu, March 1)
  (Guest lecture by TA: Wei)
• Lecture 13
  (Th, March 3)
  Chapter Four (Continuation of Sorting and Selection)
• Midterm Review
  (Tu, March 8)
  Review of Chapters 1-4
• Midterm
  (Th, March 10)
  Chapters 1-4 (except Section 4.2)
• Spring Break!!!
  (Tu, March 15)
  (Th, March 17)
• Lecture 14
  (Tu, March 22)
  Review of Midterm Solutions
  Chapter Four (Selection and Sets)
• Lecture 15
  (Th, March 24)
  Chapter Four (Sets)
• Lecture 16
  (Tu, March 29)
  Chapter Four (Sets)
  Chapter Five (Greedy - Knapsack Problem)
• Lecture 17
  (Th, March 31)
  Chapter Five (Greedy Algorithms, Master's Theorem)
• Lecture 18
  (Tu, April 5)
  Chapter Five (Master's Theorem, Dynamic Programming)
• Lecture 19
  (Th, April 7)
  Chapter Five (Dynamic Programming)
• Lecture 20
  (Tu, April 12)
  Chapter Six (Unweighted Graphs)
• Lecture 21
  (Th, April 14)
  Chapter Six (Unweighted Graphs, continued)

Homework (and Reading) Assignments

• Homework 1: Due Thursday, January 27
  R-1.6, R-1.9, R-1.14, C-1.10, C-1.14, C-1.17, C-1.25
  Reading:
  • Chapter 1 (except 1.6 - only for CSC401 students)
  • Chapter 2 (except 2.6 - only for CSC401 students)
• Homework 2: Due Thursday, February 10
  R-2.3, R-2.4, R-2.5, C-2.1, C-2.20, C-2.31 (Extra Credit: C-2.21)
  Reading: Chapter 3 (except 3.6 - only for CSC401 students)
• Homework 3: Due Thursday, February 17
  R-2.19, R-2.20, R-2.24, R-3.2, C-3.1, C-3.3
  Reading: Chapter 3 (except 3.6 - only for CSC401 students)
• Homework 4: Due Thursday, February 24
  R-3.3, R-3.5, R-3.11(b), R-3.14(ab), C-3.11, C-3.29 (Extra Credit: C-3.20)
  Note on R-3.11: To save your hand, you do not have to draw the tree T'' after every insertion. If your final solution is correct, that is perfect. But for partial credit, show the stage after any major changes have been added, or maybe about every third insertion. Many of these insertions simply require recoloring.
• Homework 5: Due Thursday, March 3
  Extended: Due Tuesday, March 8
  R-4.5, R-4.6, R-4.14, C-4.9, C-4.22
  Reading: Chapter 4 (except 4.8 - only for CSC401 students)
• Homework 6: Due Thursday, March 31
  R-4.7, C-4.7, C-4.14, C-4.24
  Reading: Chapter 4 and 5
• Homework 7: Due Thursday, April 7
  R-5.1, R-5.2, R-5.4, R-5.11, C-5.1, C-5.2 (Extra Credit: C-5.10)
  
• Homework 8: Due Thursday. April 14
  R-5.12, C-5.3, C-5.4, R-6.1, R-6.2, R-6.4
  Reading: Chapter 6
• Homework 9: Due Thursday, April 21
  R-6.6, R-6.9, R-6.10, C-6.9, C-6.18, C-6.19
  Reading: Chapter 7
• (Make-up) Homework 10: Due Thursday, April 28
  R-7.1, R-7.5, R-7.7, C-7.3, C-7.7
  (Also worth looking at: R-7.2, R-7.4, R-7.8, R-7.9, C-7.2, C-7.4, C-7.5, C-7.6, C-7.8)
  Note: This homework is a make-up assignment. It will replace your lowest previous homework score. Regardless of whether you do it or not, you should look at these problems to help you study for the final exam!

CSC401 Practicum Information

Homework (and Reading) Assignments for CSC401 Practicum

1. Program 1: Due Thursday, February 3 (midnight)
   Read 1.6 and 2.6
   Do P-1.3
   
2. Program 2: Due Thursday, February 17 (midnight)
   Read 2.6 and 3.6
   Do P-2.3 (or if you wish P-2.2)
   If you choose the animation one (P-2.2), either do the code in Java, make sure it works on the Linux system, or verify with the TA that your graphical approach works for him. For example, if you do the graphics using DirectX, make sure the TA has Windows available to test it.
3. Program 3: Due Thursday, March 3 (midnight)
   Extended: Due Tuesday, March 8 (midnight)
   Read 3.6 and 4.8
   Do P-3.1 but you must do a splay tree instead.
   The methods in the Dictionary ADT to implement are:
   • findElement(k)
   • insertItem(k,e)
   • removeElement(k)
   • closestKeyBefore(k)
   • closestElementBefore(k)
   • closestKeyAfter(k)
   • closestElementAfter(k)
   In addition, to help the TA in grading your program:
   • As always remember to submit a README file explaining how to compile, run ,and use your program.
   • Provide a method to print out the tree.
     This can be either graphically or via ASCII text, but it should display both the tree contents and color.
   • Provide a menu-based (again text is fine) system to allow the user (TA) to interactively invoke the various methods. This will be the actual program the TA invokes. E.g.

     % testDictionary
     Welcome to my Splay Tree testing program.
          
     Menu:
       0) print the current tree
       1) find an element
       2) insert an item
       3) remove an element
       ...
       9) quit
     Please select an option:
     ...
     	    

4. Program 4: Due Thursday, March 24 (midnight)
   Do P-4.2/4.3. Basically, test merge-sort, deterministic quick-sort, and randomized quick-sort.
   Be sure to submit the program(s), a README file, and the report and to make sure your report is written in either DOC, PDF, or PS formats.
5. Program 5: Due Thursday, April 14 (midnight)
   Do P-5.2. The problem is pretty self-explanatory. Email me if there are any questions about this one.
6. Program 6: Due Thursday, April 28 (midnight)
   Do P-7.1. We shall be covering the algorithm in class next week, but essentially you are implementing Kruskal's algorithm to compute the minimum spanning tree. The main special instructions are as follows:
   • Input: the input to the program is a graph stored as a file.
   • Format: The graph shall be stored in the following format:

     N M
     S1 E1 W1
     S2 E2 W2
     S3 E3 W3
     ...
     SM EM WM
     	    

     Here, N is the number of nodes in the graph.
     M is the number of edges.
     Si, Ei are the start and end nodes (just numbers) of edge i in the graph.
     Wi is the weight of edge i in the graph.
     The graph is undirected.
     The weights are integers.
     Nodes are indexed starting at 1.
     For example, here is a simple graph of 4 nodes and 5 edges.

     4 5
     1 2 5
     2 3 6
     1 3 1
     3 4 2
     1 4 4
     	    

     The output will be the minimum spanning tree of the graph in the same format as the input. Notice that the number of edges is N-1. For example, the output of the above graph would be:

     4 3
     1 3 1
     3 4 2
     1 2 5
     

     When submitting, also submit a few test graphs, as well as the standard README file.