CSCI 385 Spring 2006
Advanced Data Structures and Algorithms
Archived Class
Charles Cusack
Computer Science
Hope College
Main
Schedule
Grading
Gradebook
Homework
Worksheets

Policies
College
    Policies
Advice

Notes
Programs
Tutorials

CSCI 125
CSCI 255
MATH 131 (01 and 02)
Others

Admin
previous     next     today     future     all    

Schedule for weeks 1 through 17

Wk Day Date TopicResourcesEvents

1TueJan 10Introduction to the Course

ThuJan 12Algorithms and Problem SolvingIDAA 1.1-1.3

FriJan 13
  • Arrays
  • Stacks
  • Queues
  • Linked Lists
  • IDAA 1.4
  • Data Structures Notes
  • Data Structures Examples
  • HW 1 due

    2TueJan 17Graphs
  • Graphs and Trees Notes

  • ThuJan 19
  • Graphs
  • Trees
  • Graphs and Trees Notes
  • HW 2 due

    FriJan 20Trees
  • Graphs and Trees Notes
  • Project 1 Due

    3TueJan 24
  • Analysis of Algorithms
  • Complexity Classes
  • Complexity of Algorithms
  • IDAA 2.1-2.3
  • Algorithm Analysis Notes
  • Asymptotic Notation Notes

  • ThuJan 26
  • Analysis of Algorithms
  • Complexity Classes
  • Complexity of Algorithms
  • Asymptotic Notation Examples
  • HW 3 due

    FriJan 27Algorithm AnalysisWorksheet 1

    4TueJan 31
  • Analysis of Recursive Algorithms
  • Recurrence Relations
  • IDAA 2.4-2.5
  • IDAA Appendix B
  • Algorithms and Recurrences Examples
  • Recurrence Relations Notes
  • HW 4 due

    ThuFeb 02Solving Recurrence Relations
  • IDAA Appendix B
  • Solving Recurrence Relations Examples
  • Worksheet 1.5 (Not graded)

    FriFeb 03Brute Force:
  • Sorting (Selection and Bubble)
  • Searching (Sequential)
  • IDAA 3.1-3.2
  • Project 2 Due

  • 5TueFeb 07Brute Force:
  • Convex Hull, Closest Pair
  • Exhaustive Search
  • IDAA 3.3-3.4HW 5 due

    ThuFeb 09
  • Recurrences and Analysis
  • Brute Force
  • Quiz 1

    FriFeb 10Brute Force Algorithms
  • HW 6 due
  • Worksheet 2

  • 6TueFeb 14Winter BreakNo Class

    ThuFeb 16Divide-and-Conquer:
  • Sorting (Quick and Merge)
  • Searching (Binary)
  • Binary Tree Traversal
  • IDAA 4.1-4.4
  • Mergesort Notes
  • Quicksort Notes
  • HW 7 due

    FriFeb 17Divide and ConquerWorksheet 3

    7TueFeb 21Divide-and-Conquer: Strassen's algorithm and Closest Pair IDAA 4.5-4.6HW 8 due

    ThuFeb 23Decrease-and-Conquer:
  • Sorting (Insertion)
  • Searching (BFS)
  • Searching (DFS)
  • Sorting (Topological)
  • IDAA 5.1-5.3
  • BFS and DFS Notes

  • FriFeb 24Decrease-and-Conquer:
  • Constant Factor
  • Variable Size
  • IDAA 5.5-5.6HW 9 due

    8TueFeb 28Decrease-and-ConquerQuiz 2

    ThuMar 02Decrease and Conquer
  • Worksheet 4
  • Project 3 Due

  • FriMar 03EverythingReview for Midterm

    9TueMar 07Everything (IDAA 1-5)Midterm Exam

    ThuMar 09Transform-and-Conquer:
  • Sorting (pre sorting)
  • Searching (Trees)
  • Heaps and Heapsort
  • IDAA 6.1
  • IDAA 6.3-6.4
  • Heapsort Notes
  • Search Tree Applet
  • Heapsort Applet

  • FriMar 10Transform-and-Conquer:
  • Horner's Rule
  • Binary Exponentiation
  • IDAA 6.5

    10TueMar 14Transform-and-Conquer: Reductions IDAA 6.6HW 10 due

    ThuMar 16Transform and Conquer
  • Quiz 3
  • Project 4 Due

  • FriMar 17Spring BreakNo Class

    Spring Break Week

    11TueMar 28Space-Time Tradeoffs:
  • Counting Sort
  • Radix Sort
  • IDAA 7.1
  • Radix Sort Notes

  • ThuMar 30Space and Time Tradeoffs:
  • Hashing
  • B-Trees
  • IDAA 7.3-7.4
  • Hashing Notes
  • HW 11 due

    FriMar 31Space and Time TradeoffsWorksheet 5

    12TueApr 04Dynamic Programming:
  • Matrix Chain Multiplication
  • Knapsack Problem
  • Dynamic Programming Notes
  • IDAA 8.4

  • ThuApr 06Dynamic Programming:
  • Warshall's Algorithm
  • Floyd's Algorithm
  • IDAA 8.2
  • Warshall's Algorithm Notes
  • Floyd's Algorithm Animation

  • FriApr 07Dynamic Programming:
    Worksheet 6

    13TueApr 11Greedy Technique:
  • Fractional Knapsack
  • Huffman Encoding
  • IDAA 9.4
  • Greedy Algorithms Notes

  • ThuApr 13Greedy Technique:
  • Prim's Algorithm:
  • Kruskal's Algorithm
  • IDAA 9.1-9.2
  • Minimum Spanning Trees Notes
  • Spanning Tree Animations
  • Project 5 Due

    FriApr 14Good FridayNo Class

    14TueApr 18Greedy TechniqueWorksheet 7

    ThuApr 20P and NP
  • IDAA 10.3
  • P, NP, NP-Complete Notes
  • Quiz 4

    FriApr 21NP-Complete
  • IDAA 10.3
  • P, NP, NP-Complete Notes

  • 15TueApr 25P, NP, NPCWorksheet 8

    ThuApr 27Review for finalProject 6 Due

    FriApr 28Review for final

    16MonMay 01Final Exam 10:30amFinal Exam